Binary operators

A binary operator has two relational children. The following operators are binary operators:

• Apply join
  • Cross apply
  • Outer apply
  • Semi apply
  • Anti-Semi apply
• Hash join
• Merge join
• Recursive union

Database schema

The queries and execution plans on this page are based on the following database schema:

CREATE TABLE Singers (
  SingerId   INT64 NOT NULL,
  FirstName  STRING(1024),
  LastName   STRING(1024),
  SingerInfo BYTES(MAX),
  BirthDate  DATE
) PRIMARY KEY(SingerId);

CREATE INDEX SingersByFirstLastName ON Singers(FirstName, LastName);

CREATE TABLE Albums (
  SingerId        INT64 NOT NULL,
  AlbumId         INT64 NOT NULL,
  AlbumTitle      STRING(MAX),
  MarketingBudget INT64
) PRIMARY KEY(SingerId, AlbumId),
  INTERLEAVE IN PARENT Singers ON DELETE CASCADE;

CREATE INDEX AlbumsByAlbumTitle ON Albums(AlbumTitle);

CREATE INDEX AlbumsByAlbumTitle2 ON Albums(AlbumTitle) STORING (MarketingBudget);

CREATE TABLE Songs (
  SingerId  INT64 NOT NULL,
  AlbumId   INT64 NOT NULL,
  TrackId   INT64 NOT NULL,
  SongName  STRING(MAX),
  Duration  INT64,
  SongGenre STRING(25)
) PRIMARY KEY(SingerId, AlbumId, TrackId),
  INTERLEAVE IN PARENT Albums ON DELETE CASCADE;

CREATE INDEX SongsBySingerAlbumSongNameDesc ON Songs(SingerId, AlbumId, SongName DESC), INTERLEAVE IN Albums;

CREATE INDEX SongsBySongName ON Songs(SongName);

CREATE TABLE Concerts (
  VenueId      INT64 NOT NULL,
  SingerId     INT64 NOT NULL,
  ConcertDate  DATE NOT NULL,
  BeginTime    TIMESTAMP,
  EndTime      TIMESTAMP,
  TicketPrices ARRAY<INT64>
) PRIMARY KEY(VenueId, SingerId, ConcertDate);

You can use the following Data Manipulation Language (DML) statements to add data to these tables:

INSERT INTO Singers (SingerId, FirstName, LastName, BirthDate)
VALUES (1, "Marc", "Richards", "1970-09-03"),
       (2, "Catalina", "Smith", "1990-08-17"),
       (3, "Alice", "Trentor", "1991-10-02"),
       (4, "Lea", "Martin", "1991-11-09"),
       (5, "David", "Lomond", "1977-01-29");

INSERT INTO Albums (SingerId, AlbumId, AlbumTitle)
VALUES (1, 1, "Total Junk"),
       (1, 2, "Go, Go, Go"),
       (2, 1, "Green"),
       (2, 2, "Forever Hold Your Peace"),
       (2, 3, "Terrified"),
       (3, 1, "Nothing To Do With Me"),
       (4, 1, "Play");

INSERT INTO Songs (SingerId, AlbumId, TrackId, SongName, Duration, SongGenre)
VALUES (2, 1, 1, "Let's Get Back Together", 182, "COUNTRY"),
       (2, 1, 2, "Starting Again", 156, "ROCK"),
       (2, 1, 3, "I Knew You Were Magic", 294, "BLUES"),
       (2, 1, 4, "42", 185, "CLASSICAL"),
       (2, 1, 5, "Blue", 238, "BLUES"),
       (2, 1, 6, "Nothing Is The Same", 303, "BLUES"),
       (2, 1, 7, "The Second Time", 255, "ROCK"),
       (2, 3, 1, "Fight Story", 194, "ROCK"),
       (3, 1, 1, "Not About The Guitar", 278, "BLUES");

Apply join

An apply join is the primary join operator used by Spanner. Apply join operators execute row-oriented processing, unlike operators that execute set-based processing such as hash join. The apply operator has two inputs, input (left child) and map (right child). The apply operator applies each row on the input side to the map side using an apply method: cross, outer, semi, or anti-semi. Additionally, a variant of an apply join also appears on the map side of a Distributed apply.

The Apply join operator is most efficient when:

• The cardinality of the input is low.
• The join key is a prefix of the map-side primary key.
• The query joins two interleaved tables.

Properties and execution statistics

A property of an operator describes a trait that is used when the operator is executed. An execution statistic is a value collected during query execution to help you assess performance of the operator.

Cross apply

A Cross apply performs an inner join where only matching rows are returned.

The following query demonstrates this operator:

The query requests the first name of each singer, along with the name of only one of the singer's songs.

 SELECT si.firstname,
       (SELECT so.songname
        FROM   songs AS so
        WHERE  so.singerid = si.singerid
        LIMIT  1)
FROM   singers AS si;

/*-----------+--------------------------+
 | FirstName | Unspecified              |
 +-----------+--------------------------+
 | Alice     | Not About The Guitar     |
 | Catalina  | Let's Get Back Together  |
 | David     | NULL                     |
 | Lea       | NULL                     |
 | Marc      | NULL                     |
 +-----------+--------------------------*/

The query populates the first column from the Singers table, and the second column from the Songs table. In cases where a SingerId existed in the Singers table but there was no matching SingerId in the Songs table, the second column contains NULL.

The execution plan begins as follows:

The top-level node is a distributed union operator. The distributed union operator distributes sub plans to remote servers. The subplan contains a serialize result operator that computes the singer's first name and the name of one of the singer's songs and serializes each row of the output.

The serialize result operator receives its input from a cross apply operator. The input side for the cross apply operator is a table scan on the Singers table.

The execution plan continues as follows:

The map side for the cross apply operation contains the following (from top to bottom):

• An aggregate operator that returns Songs.SongName.
• A limit operator that limits the number of songs returned to one per singer.
• An index scan on the SongsBySingerAlbumSongNameDesc index.

The cross apply operator maps each row from the input side to a row in the map side that has the same SingerId. The cross apply operator output is the FirstName value from the input row, and the SongName value from the map row. (The SongName value is NULL if there is no map row that matches on SingerId.) The distributed union operator at the top of the execution plan then combines all of the output rows from the remote servers and returns them as the query results.

Outer apply

An outer apply provides left outer join semantics. It ensures that each execution on the map side returns at least one row by adding NULL-padding if needed.

Semi apply

The semi apply operator returns input columns only when a match occurs on the map side.

The following query uses a semi join to find which singers do have an Album:

SELECT
  FirstName,
  LastName
FROM
  Singers
WHERE
  SingerId IN (
  SELECT
    SingerId
  FROM
    Albums);

/*-----------+----------+
 | FirstName | LastName |
 +-----------+----------+
 | Marc      | Richards |
 | Catalina  | Smith    |
 | Alice     | Trentor  |
 | Lea       | Martin   |
 +-----------+----------*/

The plan segment appears as follows:

Anti-semi apply

An Anti-semi apply operator is similar to a semi apply operator, except that it returns the input table columns only when a match doesn't occur on the map side.

The following query uses an anti-semi join to find which singers don't have an Album:

SELECT
  FirstName,
  LastName
FROM
  Singers
WHERE
  SingerId NOT IN (
  SELECT
    SingerId
  FROM
    Albums);

/*-----------+----------+
 | FirstName | LastName |
 +-----------+----------+
 | David     | Lomond   |
 +-----------+----------*/

The plan segment appears as follows:

Hash join

A hash join operator is a hash-based implementation of SQL joins. Hash joins execute set-based processing. The hash join operator reads rows from input marked as build (left child) and inserts them into a hash table based on a join condition. The hash join operator then reads rows from input marked as probe (right child). For each row it reads from the probe input, the hash join operator looks for matching rows in the hash table. The hash join operator returns the matching rows as its result.

Hash join has the following advantages:

• It doesn't require the inputs to be sorted
• It computes a bloom filter when building the hash table. The operator uses the filter to exclude rows from the probe side that have no matches. Note that this is a residual filter, not a seek filter.

The following query demonstrates this operator:

SELECT a.albumtitle,
       s.songname
FROM   albums AS a join@{join_method=hash_join} songs AS s
ON a.singerid = s.singerid
AND    a.albumid = s.albumid;

/*-----------------------+--------------------------+
 | AlbumTitle            | SongName                 |
 +-----------------------+--------------------------+
 | Nothing To Do With Me | Not About The Guitar     |
 | Green                 | The Second Time          |
 | Green                 | Starting Again           |
 | Green                 | Nothing Is The Same      |
 | Green                 | Let's Get Back Together  |
 | Green                 | I Knew You Were Magic    |
 | Green                 | Blue                     |
 | Green                 | 42                       |
 | Terrified             | Fight Story              |
 +-----------------------+--------------------------*/

The execution plan segment appears as follows:

In the execution plan, build is a distributed union that distributes scans on the table Albums. Probe is a distributed union operator that distributes scans on the index SongsBySingerAlbumSongNameDesc. The hash join operator reads all rows from the build side. Each build row is placed in a hash table based on the columns in the condition a.SingerId = s.SingerId AND a.AlbumId = s.AlbumId. Next, the hash join operator reads all rows from the probe side. For each probe row, the hash join operator looks for matches in the hash table. The resulting matches are returned by the hash join operator.

Resulting matches in the hash table might also be filtered by a residual condition before they're returned. (An example of where residual conditions appear is in non-equality joins). Hash join execution plans can be complex due to memory management and join variants. The main hash join algorithm is adapted to handle inner, semi, anti, and outer join variants.

Properties and execution statistics

A property of an operator describes a trait that is used when the operator is executed. An execution statistic is a value collected during query execution to help you assess performance of the operator.

Merge join

A merge join operator is a merge-based implementation of SQL join. Both sides of the join produce rows ordered by the columns used in the join condition. The merge join consumes both input streams concurrently and outputs rows when the join condition is satisfied. If inputs are not sorted, the optimizer adds explicit Sort operators to the plan.

Merge join has the following advantages:

• If the data is already sorted, it doesn't need any memory.
• Even if the data is not sorted, for a distributed join, it can perform the sort on each individual split, rather than creating a large hash table on the root.

Merge join isn't selected automatically by the optimizer. To use this operator, set the join method to MERGE_JOIN on the query hint, as shown in the following example:

SELECT a.albumtitle,
       s.songname
FROM   albums AS a join@{join_method=merge_join} songs AS s
ON     a.singerid = s.singerid
AND    a.albumid = s.albumid;

/*-----------------------+--------------------------+
 | AlbumTitle            | SongName                 |
 +-----------------------+--------------------------+
 | Green                 | The Second Time          |
 | Green                 | Starting Again           |
 | Green                 | Nothing Is The Same      |
 | Green                 | Let's Get Back Together  |
 | Green                 | I Knew You Were Magic    |
 | Green                 | Blue                     |
 | Green                 | 42                       |
 | Terrified             | Fight Story              |
 | Nothing To Do With Me | Not About The Guitar     |
 +-----------------------+--------------------------*/

The execution plan appears as follows:

In this execution plan, the merge join is distributed so that the join executes where the data resides. This also lets the merge join in this example operate without additional sort operators, because both table scans are already sorted by SingerId, AlbumId, which is the join condition. In this plan, the left scan of the Albums table advances whenever its SingerId, AlbumId is less than the right scan's SingerId_1, AlbumId_1 values. Similarly, the right scan advances whenever its values are less than the left scan's values. This merge advance continues searching for equivalences to return matching rows.

Consider another merge join example using the following query:

SELECT a.albumtitle,
       s.songname
FROM   albums AS a join@{join_method=merge_join} songs AS s
ON a.albumid = s.albumid;

/*-----------------------+--------------------------+
 | AlbumTitle            | SongName                 |
 +-----------------------+--------------------------+
 | Total Junk            | The Second Time          |
 | Total Junk            | Starting Again           |
 | Total Junk            | Nothing Is The Same      |
 | Total Junk            | Let's Get Back Together  |
 | Total Junk            | I Knew You Were Magic    |
 | Total Junk            | Blue                     |
 | Total Junk            | 42                       |
 | Total Junk            | Not About The Guitar     |
 | Green                 | The Second Time          |
 | Green                 | Starting Again           |
 | Green                 | Nothing Is The Same      |
 | Green                 | Let's Get Back Together  |
 | Green                 | I Knew You Were Magic    |
 | Green                 | Blue                     |
 | Green                 | 42                       |
 | Green                 | Not About The Guitar     |
 | Nothing To Do With Me | The Second Time          |
 | Nothing To Do With Me | Starting Again           |
 | Nothing To Do With Me | Nothing Is The Same      |
 | Nothing To Do With Me | Let's Get Back Together  |
 | Nothing To Do With Me | I Knew You Were Magic    |
 | Nothing To Do With Me | Blue                     |
 | Nothing To Do With Me | 42                       |
 | Nothing To Do With Me | Not About The Guitar     |
 | Play                  | The Second Time          |
 | Play                  | Starting Again           |
 | Play                  | Nothing Is The Same      |
 | Play                  | Let's Get Back Together  |
 | Play                  | I Knew You Were Magic    |
 | Play                  | Blue                     |
 | Play                  | 42                       |
 | Play                  | Not About The Guitar     |
 | Terrified             | Fight Story              |
 +-----------------------+--------------------------*/

The execution plan appears as follows:

In the preceding execution plan, the query optimizer introduced additional sort operators to execute the merge join. The JOIN condition in this example query is only on AlbumId, which isn't how the data is stored, so a sort must be added. The query engine supports a Distributed Merge algorithm, which lets the sort occur locally instead of globally, distributing and parallelizing the CPU cost.

The resulting matches might also be filtered by a residual condition. For example, residual conditions appear in non-equality joins. Merge join execution plans can be complex due to additional sort requirements. The main merge join algorithm handles inner, semi, anti, and outer join variants.

Properties and execution statistics

A property of an operator describes a trait that is used when the operator is executed. An execution statistic is a value collected during query execution to help you assess performance of the operator.

Recursive union

A recursive union operator performs a union of two inputs, one that represents a base case, and the other that represents a recursive case. It's used in graph queries with quantified path traversals. The base input is processed first and exactly once. The recursive input is processed until the recursion terminates. The recursion terminates when the upper bound, if specified, is reached, or when the recursion doesn't produce any new results. In the following example, the Collaborations table is added to the schema, and a property graph called MusicGraph is created.

CREATE TABLE Collaborations (
    SingerId INT64 NOT NULL,
    FeaturingSingerId INT64 NOT NULL,
    AlbumTitle STRING(MAX) NOT NULL,
) PRIMARY KEY(SingerId, FeaturingSingerId, AlbumTitle);

CREATE OR REPLACE PROPERTY GRAPH MusicGraph
    NODE TABLES(
        Singers
            KEY(SingerId)
            LABEL Singers PROPERTIES(
                BirthDate,
                FirstName,
                LastName,
                SingerId,
                SingerInfo)
            )
EDGE TABLES(
    Collaborations AS CollabWith
        KEY(SingerId, FeaturingSingerId, AlbumTitle)
        SOURCE KEY(SingerId) REFERENCES Singers(SingerId)
        DESTINATION KEY(FeaturingSingerId) REFERENCES Singers(SingerId)
        LABEL CollabWith PROPERTIES(
          AlbumTitle,
          FeaturingSingerId,
          SingerId),
);

The following graph query finds singers who have collaborated with a given singer or collaborated with those collaborators.

GRAPH MusicGraph
MATCH (singer:Singers {singerId:42})-[c:CollabWith]->{1,2}(featured:Singers)
RETURN singer.SingerId AS singer, featured.SingerId AS featured

The recursive union operator filters the Singers table to find the singer with the given SingerId. This is the base input to the recursive union. The recursive input to the recursive union comprises a distributed cross apply or other join operator for other queries that repeatedly joins the Collaborations table with the results of the previous iteration of the join. The rows from the base input form the zeroth iteration. At each iteration, the output of the iteration is stored by the recursive spool scan. Rows from the recursive spool scan are joined with the Collaborations table on spoolscan.featuredSingerId = Collaborations.SingerId. Recursion terminates when two iterations are complete, since that's the specified upper bound in the query.

Properties and execution statistics

A property of an operator describes a trait that is used when the operator is executed. An execution statistic is a value collected during query execution to help you assess performance of the operator.