exec-ddl

CREATE TABLE xysd (x INT PRIMARY KEY, y INT, s STRING, d DECIMAL NOT NULL, UNIQUE (s DESC, d))

----

exec-ddl

CREATE TABLE uv (u INT, v INT NOT NULL)

----

exec-ddl

CREATE TABLE mn (m INT PRIMARY KEY, n INT, UNIQUE (n))

----

exec-ddl

CREATE TABLE fk (

k INT PRIMARY KEY,

v INT,

r1 INT NOT NULL REFERENCES xysd(x),

r2 INT REFERENCES xysd(x)

)

----

exec-ddl

CREATE TABLE abc (a INT, b INT, c INT, PRIMARY KEY (a, b, c))

----

exec-ddl

CREATE TABLE xyz (x INT, y INT, z INT, PRIMARY KEY (x, y))

----

exec-ddl

CREATE TABLE ref (

r1 INT NOT NULL,

r2 INT,

r3 INT NOT NULL,

FOREIGN KEY (r1, r2, r3) REFERENCES abc(a, b, c)

)

----

# Inner-join.

build

SELECT *, rowid FROM xysd INNER JOIN uv ON x=u

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int!null) v:8(int!null) rowid:9(int!null)

├── key: (9)

├── fd: (1)-->(2-4), (3,4)~~>(1,2,7), (9)-->(1-4,7,8), (1)==(7), (7)==(1)

├── prune: (1-4,7-9)

├── interesting orderings: (+(1|7)) (-3,+4,+(1|7)) (+9)

└── inner-join (hash)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid) u:7(int!null) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)

├── key: (9)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (9)-->(7,8,10,11), (1)==(7), (7)==(1)

├── prune: (2-6,8-11)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ ├── interesting orderings: (+9)

│ └── unfiltered-cols: (7-11)

└── filters

└── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

├── variable: x:1 [type=int]

└── variable: u:7 [type=int]

# Inner-join-apply.

opt

SELECT (SELECT (VALUES (x), (y))) FROM xysd

----

project

├── columns: column1:9(int)

├── prune: (9)

├── ensure-distinct-on

│ ├── columns: x:1(int!null) column1:7(int)

│ ├── grouping columns: x:1(int!null)

│ ├── error: "more than one row returned by a subquery used as an expression"

│ ├── key: (1)

│ ├── fd: (1)-->(7)

│ ├── prune: (7)

│ ├── inner-join-apply

│ │ ├── columns: x:1(int!null) y:2(int) column1:7(int)

│ │ ├── fd: (1)-->(2)

│ │ ├── prune: (7)

│ │ ├── interesting orderings: (+1)

│ │ ├── scan xysd

│ │ │ ├── columns: x:1(int!null) y:2(int)

│ │ │ ├── key: (1)

│ │ │ ├── fd: (1)-->(2)

│ │ │ ├── prune: (1,2)

│ │ │ └── interesting orderings: (+1)

│ │ ├── values

│ │ │ ├── columns: column1:7(int)

│ │ │ ├── outer: (1,2)

│ │ │ ├── cardinality: [2 - 2]

│ │ │ ├── prune: (7)

│ │ │ ├── tuple [type=tuple{int}]

│ │ │ │ └── variable: x:1 [type=int]

│ │ │ └── tuple [type=tuple{int}]

│ │ │ └── variable: y:2 [type=int]

│ │ └── filters (true)

│ └── aggregations

│ └── const-agg [as=column1:7, type=int, outer=(7)]

│ └── variable: column1:7 [type=int]

└── projections

└── variable: column1:7 [as=column1:9, type=int, outer=(7)]

# Inner-join-apply nested in inner-join-apply with outer column references to

# each parent.

opt disable=TryDecorrelateMax1Row

SELECT * FROM xysd WHERE (SELECT v FROM uv WHERE (SELECT n FROM mn WHERE n=v)=x)=x

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (1-4)

├── interesting orderings: (+1) (-3,+4,+1)

└── inner-join-apply

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:8(int!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(8), (8)==(1)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── key: (1)

│ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ ├── prune: (1-4)

│ └── interesting orderings: (+1) (-3,+4,+1)

├── max1-row

│ ├── columns: v:8(int!null)

│ ├── error: "more than one row returned by a subquery used as an expression"

│ ├── outer: (1)

│ ├── cardinality: [0 - 1]

│ ├── key: ()

│ ├── fd: ()-->(8)

│ └── project

│ ├── columns: v:8(int!null)

│ ├── outer: (1)

│ ├── fd: ()-->(8)

│ ├── prune: (8)

│ └── inner-join (hash)

│ ├── columns: v:8(int!null) n:13(int!null)

│ ├── outer: (1)

│ ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)

│ ├── fd: ()-->(8,13), (8)==(13), (13)==(8)

│ ├── interesting orderings: (+13)

│ ├── scan uv

│ │ ├── columns: v:8(int!null)

│ │ ├── prune: (8)

│ │ └── unfiltered-cols: (7-11)

│ ├── scan mn

│ │ ├── columns: n:13(int)

│ │ ├── lax-key: (13)

│ │ ├── prune: (13)

│ │ ├── interesting orderings: (+13)

│ │ └── unfiltered-cols: (12-15)

│ └── filters

│ ├── eq [type=bool, outer=(8,13), constraints=(/8: (/NULL - ]; /13: (/NULL - ]), fd=(8)==(13), (13)==(8)]

│ │ ├── variable: n:13 [type=int]

│ │ └── variable: v:8 [type=int]

│ └── eq [type=bool, outer=(1,13), constraints=(/1: (/NULL - ]; /13: (/NULL - ]), fd=(1)==(13), (13)==(1)]

│ ├── variable: x:1 [type=int]

│ └── variable: n:13 [type=int]

└── filters

└── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

├── variable: x:1 [type=int]

└── variable: v:8 [type=int]

# Inner-join nested in inner-join-apply with outer column reference to top-level

# inner-join-apply.

opt

SELECT * FROM xysd WHERE (SELECT v FROM uv WHERE (SELECT m FROM mn WHERE m=y)=x)=x

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (1-4)

└── select

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:8(int!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(8), (8)==(1)

├── prune: (2-4)

├── ensure-distinct-on

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:8(int)

│ ├── grouping columns: x:1(int!null)

│ ├── error: "more than one row returned by a subquery used as an expression"

│ ├── key: (1)

│ ├── fd: (1)-->(2-4,8), (3,4)~~>(1,2)

│ ├── prune: (2-4,8)

│ ├── right-join (hash)

│ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:8(int) m:12(int)

│ │ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ │ ├── prune: (3,4,8)

│ │ ├── reject-nulls: (8,12)

│ │ ├── interesting orderings: (+1) (-3,+4,+1) (+12)

│ │ ├── inner-join (cross)

│ │ │ ├── columns: v:8(int!null) m:12(int!null)

│ │ │ ├── prune: (8,12)

│ │ │ ├── interesting orderings: (+12)

│ │ │ ├── scan uv

│ │ │ │ ├── columns: v:8(int!null)

│ │ │ │ ├── prune: (8)

│ │ │ │ └── unfiltered-cols: (7-11)

│ │ │ ├── scan mn

│ │ │ │ ├── columns: m:12(int!null)

│ │ │ │ ├── key: (12)

│ │ │ │ ├── prune: (12)

│ │ │ │ ├── interesting orderings: (+12)

│ │ │ │ └── unfiltered-cols: (12-15)

│ │ │ └── filters (true)

│ │ ├── scan xysd

│ │ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ │ │ ├── key: (1)

│ │ │ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ │ │ ├── prune: (1-4)

│ │ │ ├── interesting orderings: (+1) (-3,+4,+1)

│ │ │ └── unfiltered-cols: (1-6)

│ │ └── filters

│ │ ├── eq [type=bool, outer=(1,2), constraints=(/1: (/NULL - ]; /2: (/NULL - ]), fd=(1)==(2), (2)==(1)]

│ │ │ ├── variable: x:1 [type=int]

│ │ │ └── variable: y:2 [type=int]

│ │ └── eq [type=bool, outer=(1,12), constraints=(/1: (/NULL - ]; /12: (/NULL - ]), fd=(1)==(12), (12)==(1)]

│ │ ├── variable: x:1 [type=int]

│ │ └── variable: m:12 [type=int]

│ └── aggregations

│ ├── const-agg [as=y:2, type=int, outer=(2)]

│ │ └── variable: y:2 [type=int]

│ ├── const-agg [as=s:3, type=string, outer=(3)]

│ │ └── variable: s:3 [type=string]

│ ├── const-agg [as=d:4, type=decimal, outer=(4)]

│ │ └── variable: d:4 [type=decimal]

│ └── const-agg [as=v:8, type=int, outer=(8)]

│ └── variable: v:8 [type=int]

└── filters

└── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

├── variable: x:1 [type=int]

└── variable: v:8 [type=int]

# Left-join.

build

SELECT *, rowid FROM xysd LEFT JOIN uv ON x=u

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int) rowid:9(int)

├── key: (1,9)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (9)-->(7,8)

├── prune: (1-4,7-9)

├── reject-nulls: (7-9)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

└── left-join (hash)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid) u:7(int) v:8(int) rowid:9(int) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)

├── key: (1,9)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (9)-->(7,8,10,11)

├── prune: (2-6,8-11)

├── reject-nulls: (7-11)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ ├── interesting orderings: (+9)

│ └── unfiltered-cols: (7-11)

└── filters

└── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

├── variable: x:1 [type=int]

└── variable: u:7 [type=int]

# Left-join with single row left input: column u should be constant.

build

SELECT * FROM (SELECT * FROM xysd WHERE x=123) AS xysd1 LEFT JOIN uv ON y=u

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int)

├── fd: ()-->(1-4,7)

├── prune: (1-4,7,8)

├── reject-nulls: (7,8)

└── left-join (hash)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int) rowid:9(int) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)

├── key: (9)

├── fd: ()-->(1-4,7), (9)-->(8,10,11)

├── prune: (1,3,4,8-11)

├── reject-nulls: (7-11)

├── interesting orderings: (+9)

├── project

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── cardinality: [0 - 1]

│ ├── key: ()

│ ├── fd: ()-->(1-4)

│ ├── prune: (1-4)

│ └── select

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── cardinality: [0 - 1]

│ ├── key: ()

│ ├── fd: ()-->(1-6)

│ ├── prune: (2-6)

│ ├── scan xysd

│ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ │ ├── key: (1)

│ │ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ │ ├── prune: (1-6)

│ │ └── interesting orderings: (+1) (-3,+4,+1)

│ └── filters

│ └── eq [type=bool, outer=(1), constraints=(/1: [/123 - /123]; tight), fd=()-->(1)]

│ ├── variable: x:1 [type=int]

│ └── const: 123 [type=int]

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ ├── interesting orderings: (+9)

│ └── unfiltered-cols: (7-11)

└── filters

└── eq [type=bool, outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

├── variable: y:2 [type=int]

└── variable: u:7 [type=int]

# Left-join with single row left input: columns u and v should be constant.

# Note: we need norm here so that the AND gets normalized to multiple filter items.

norm

SELECT * FROM (SELECT * FROM xysd WHERE x=123) AS xysd1 LEFT JOIN uv ON y=u AND v=x+y

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int)

├── immutable

├── fd: ()-->(1-4,7,8)

├── prune: (1-4,7,8)

├── reject-nulls: (7,8)

└── left-join (hash)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int) column12:12(int)

├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)

├── immutable

├── fd: ()-->(1-4,7,8,12)

├── prune: (1,3,4)

├── reject-nulls: (7,8)

├── project

│ ├── columns: column12:12(int) x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── cardinality: [0 - 1]

│ ├── immutable

│ ├── key: ()

│ ├── fd: ()-->(1-4,12)

│ ├── prune: (1-4,12)

│ ├── select

│ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ │ ├── cardinality: [0 - 1]

│ │ ├── key: ()

│ │ ├── fd: ()-->(1-4)

│ │ ├── prune: (2-4)

│ │ ├── scan xysd

│ │ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ │ │ ├── key: (1)

│ │ │ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ │ │ ├── prune: (1-4)

│ │ │ └── interesting orderings: (+1) (-3,+4,+1)

│ │ └── filters

│ │ └── eq [type=bool, outer=(1), constraints=(/1: [/123 - /123]; tight), fd=()-->(1)]

│ │ ├── variable: x:1 [type=int]

│ │ └── const: 123 [type=int]

│ └── projections

│ └── plus [as=column12:12, type=int, outer=(1,2), immutable]

│ ├── variable: x:1 [type=int]

│ └── variable: y:2 [type=int]

├── scan uv

│ ├── columns: u:7(int) v:8(int!null)

│ ├── prune: (7,8)

│ └── unfiltered-cols: (7-11)

└── filters

├── eq [type=bool, outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

│ ├── variable: y:2 [type=int]

│ └── variable: u:7 [type=int]

└── eq [type=bool, outer=(8,12), constraints=(/8: (/NULL - ]; /12: (/NULL - ]), fd=(8)==(12), (12)==(8)]

├── variable: column12:12 [type=int]

└── variable: v:8 [type=int]

# Left-join-apply.

opt

SELECT * FROM xysd WHERE (SELECT u FROM uv WHERE u=x) IS NULL

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (1-4)

└── select

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int)

├── key: (1)

├── fd: ()-->(7), (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── ensure-distinct-on

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int)

│ ├── grouping columns: x:1(int!null)

│ ├── error: "more than one row returned by a subquery used as an expression"

│ ├── key: (1)

│ ├── fd: (1)-->(2-4,7), (3,4)~~>(1,2)

│ ├── prune: (2-4,7)

│ ├── left-join (hash)

│ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int)

│ │ ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)

│ │ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ │ ├── prune: (2-4)

│ │ ├── reject-nulls: (7)

│ │ ├── interesting orderings: (+1) (-3,+4,+1)

│ │ ├── scan xysd

│ │ │ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ │ │ ├── key: (1)

│ │ │ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ │ │ ├── prune: (1-4)

│ │ │ ├── interesting orderings: (+1) (-3,+4,+1)

│ │ │ └── unfiltered-cols: (1-6)

│ │ ├── scan uv

│ │ │ ├── columns: u:7(int)

│ │ │ ├── prune: (7)

│ │ │ └── unfiltered-cols: (7-11)

│ │ └── filters

│ │ └── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

│ │ ├── variable: u:7 [type=int]

│ │ └── variable: x:1 [type=int]

│ └── aggregations

│ ├── const-agg [as=y:2, type=int, outer=(2)]

│ │ └── variable: y:2 [type=int]

│ ├── const-agg [as=s:3, type=string, outer=(3)]

│ │ └── variable: s:3 [type=string]

│ ├── const-agg [as=d:4, type=decimal, outer=(4)]

│ │ └── variable: d:4 [type=decimal]

│ └── const-agg [as=u:7, type=int, outer=(7)]

│ └── variable: u:7 [type=int]

└── filters

└── is [type=bool, outer=(7), constraints=(/7: [/NULL - /NULL]; tight), fd=()-->(7)]

├── variable: u:7 [type=int]

└── null [type=unknown]

# Right-join.

build

SELECT *, rowid FROM xysd RIGHT JOIN uv ON x=u

----

project

├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:7(int) v:8(int!null) rowid:9(int!null)

├── key: (9)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (9)-->(1-4,7,8)

├── prune: (1-4,7-9)

├── reject-nulls: (1-4)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

└── right-join (hash)

├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid) u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── key: (9)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (9)-->(1-8,10,11)

├── prune: (2-6,8-11)

├── reject-nulls: (1-6)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ └── interesting orderings: (+1) (-3,+4,+1)

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ └── interesting orderings: (+9)

└── filters

└── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

├── variable: x:1 [type=int]

└── variable: u:7 [type=int]

# Full-join.

build

SELECT *, rowid FROM xysd FULL JOIN uv ON x=u

----

project

├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:7(int) v:8(int) rowid:9(int)

├── key: (1,9)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (9)-->(7,8)

├── prune: (1-4,7-9)

├── reject-nulls: (1-4,7-9)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

└── full-join (hash)

├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid) u:7(int) v:8(int) rowid:9(int) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── multiplicity: left-rows(one-or-more), right-rows(exactly-one)

├── key: (1,9)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (9)-->(7,8,10,11)

├── prune: (2-6,8-11)

├── reject-nulls: (1-11)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ ├── interesting orderings: (+9)

│ └── unfiltered-cols: (7-11)

└── filters

└── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

├── variable: x:1 [type=int]

└── variable: u:7 [type=int]

# Semi-join.

opt

SELECT * FROM xysd WHERE EXISTS(SELECT * FROM uv WHERE x=u)

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

└── inner-join (lookup xysd)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int!null)

├── key columns: [7] = [1]

├── lookup columns are key

├── key: (7)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(7), (7)==(1)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── distinct-on

│ ├── columns: u:7(int)

│ ├── grouping columns: u:7(int)

│ ├── key: (7)

│ └── scan uv

│ ├── columns: u:7(int)

│ ├── prune: (7)

│ └── unfiltered-cols: (7-11)

└── filters (true)

# Semi-join with empty right input. The cardinality should be zero.

expr

(SemiJoin

(Values

[

(Tuple [ (Const 1 "int") (Const 10 "int") ] "tuple{int}" )

(Tuple [ (Const 2 "int") (Const 20 "int") ] "tuple{int}" )

(Tuple [ (Const 3 "int") (Const 30 "int") ] "tuple{int}" )

]

[ (Cols [ (NewColumn "x" "int") (NewColumn "y" "int") ]) ]

)

(Select (Scan [ (Table "uv") (Cols "u,v") ]) [ (False) ])

[ (Eq (Var "x") (Var "u")) ]

[]

)

----

semi-join (hash)

├── columns: x:1(int!null) y:2(int!null)

├── cardinality: [0 - 0]

├── prune: (2)

├── values

│ ├── columns: x:1(int!null) y:2(int!null)

│ ├── cardinality: [3 - 3]

│ ├── prune: (1,2)

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 1 [type=int]

│ │ └── const: 10 [type=int]

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 2 [type=int]

│ │ └── const: 20 [type=int]

│ └── tuple [type=tuple{int}]

│ ├── const: 3 [type=int]

│ └── const: 30 [type=int]

├── select

│ ├── columns: u:3(int) v:4(int!null)

│ ├── cardinality: [0 - 0]

│ ├── prune: (3,4)

│ ├── scan uv

│ │ ├── columns: u:3(int) v:4(int!null)

│ │ └── prune: (3,4)

│ └── filters

│ └── false [type=bool, constraints=(contradiction; tight)]

└── filters

└── eq [type=bool, outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]

├── variable: x:1 [type=int]

└── variable: u:3 [type=int]

# Semi-join with False filters. The cardinality should be zero.

expr

(SemiJoin

(Values

[

(Tuple [ (Const 1 "int") (Const 10 "int") ] "tuple{int}" )

(Tuple [ (Const 2 "int") (Const 20 "int") ] "tuple{int}" )

(Tuple [ (Const 3 "int") (Const 30 "int") ] "tuple{int}" )

]

[ (Cols [ (NewColumn "x" "int") (NewColumn "y" "int") ]) ]

)

(Scan [ (Table "uv") (Cols "u,v") ])

[ (False) ]

[]

)

----

semi-join (cross)

├── columns: x:1(int!null) y:2(int!null)

├── cardinality: [0 - 0]

├── prune: (1,2)

├── values

│ ├── columns: x:1(int!null) y:2(int!null)

│ ├── cardinality: [3 - 3]

│ ├── prune: (1,2)

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 1 [type=int]

│ │ └── const: 10 [type=int]

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 2 [type=int]

│ │ └── const: 20 [type=int]

│ └── tuple [type=tuple{int}]

│ ├── const: 3 [type=int]

│ └── const: 30 [type=int]

├── scan uv

│ ├── columns: u:3(int) v:4(int!null)

│ ├── prune: (3,4)

│ └── unfiltered-cols: (3-7)

└── filters

└── false [type=bool, constraints=(contradiction; tight)]

# Semi-join-apply.

opt

SELECT * FROM xysd WHERE EXISTS(SELECT * FROM uv WHERE v=x OFFSET 1)

----

semi-join-apply

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── key: (1)

│ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ ├── prune: (1-4)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── offset

│ ├── columns: v:8(int!null)

│ ├── outer: (1)

│ ├── fd: ()-->(8)

│ ├── select

│ │ ├── columns: v:8(int!null)

│ │ ├── outer: (1)

│ │ ├── fd: ()-->(8)

│ │ ├── scan uv

│ │ │ ├── columns: v:8(int!null)

│ │ │ └── prune: (8)

│ │ └── filters

│ │ └── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

│ │ ├── variable: v:8 [type=int]

│ │ └── variable: x:1 [type=int]

│ └── const: 1 [type=int]

└── filters (true)

# Semi-join nested in semi-join with outer column reference to top-level join.

opt

SELECT * FROM xysd WHERE EXISTS(SELECT * FROM uv WHERE EXISTS(SELECT * FROM mn WHERE x=m AND x=v))

----

semi-join-apply

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── key: (1)

│ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ ├── prune: (1-4)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── semi-join (cross)

│ ├── columns: v:8(int!null)

│ ├── outer: (1)

│ ├── fd: ()-->(8)

│ ├── scan uv

│ │ ├── columns: v:8(int!null)

│ │ ├── prune: (8)

│ │ └── unfiltered-cols: (7-11)

│ ├── scan mn

│ │ ├── columns: m:12(int!null)

│ │ ├── key: (12)

│ │ ├── prune: (12)

│ │ ├── interesting orderings: (+12)

│ │ └── unfiltered-cols: (12-15)

│ └── filters

│ ├── eq [type=bool, outer=(1,12), constraints=(/1: (/NULL - ]; /12: (/NULL - ]), fd=(1)==(12), (12)==(1)]

│ │ ├── variable: x:1 [type=int]

│ │ └── variable: m:12 [type=int]

│ └── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

│ ├── variable: x:1 [type=int]

│ └── variable: v:8 [type=int]

└── filters (true)

# Anti-join.

opt

SELECT * FROM xysd WHERE NOT EXISTS(SELECT * FROM uv WHERE x=u)

----

anti-join (hash)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── key: (1)

│ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ ├── prune: (1-4)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan uv

│ ├── columns: u:7(int)

│ ├── prune: (7)

│ └── unfiltered-cols: (7-11)

└── filters

└── eq [type=bool, outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ]), fd=(1)==(7), (7)==(1)]

├── variable: x:1 [type=int]

└── variable: u:7 [type=int]

# Anti-join with empty right input. The cardinality of the left input should be

# passed through.

expr

(AntiJoin

(Values

[

(Tuple [ (Const 1 "int") (Const 10 "int") ] "tuple{int}" )

(Tuple [ (Const 2 "int") (Const 20 "int") ] "tuple{int}" )

(Tuple [ (Const 3 "int") (Const 30 "int") ] "tuple{int}" )

]

[ (Cols [ (NewColumn "x" "int") (NewColumn "y" "int") ]) ]

)

(Select (Scan [ (Table "uv") (Cols "u,v") ]) [ (False) ])

[ (Eq (Var "x") (Var "u")) ]

[]

)

----

anti-join (hash)

├── columns: x:1(int!null) y:2(int!null)

├── cardinality: [3 - 3]

├── prune: (2)

├── values

│ ├── columns: x:1(int!null) y:2(int!null)

│ ├── cardinality: [3 - 3]

│ ├── prune: (1,2)

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 1 [type=int]

│ │ └── const: 10 [type=int]

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 2 [type=int]

│ │ └── const: 20 [type=int]

│ └── tuple [type=tuple{int}]

│ ├── const: 3 [type=int]

│ └── const: 30 [type=int]

├── select

│ ├── columns: u:3(int) v:4(int!null)

│ ├── cardinality: [0 - 0]

│ ├── prune: (3,4)

│ ├── scan uv

│ │ ├── columns: u:3(int) v:4(int!null)

│ │ └── prune: (3,4)

│ └── filters

│ └── false [type=bool, constraints=(contradiction; tight)]

└── filters

└── eq [type=bool, outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]

├── variable: x:1 [type=int]

└── variable: u:3 [type=int]

# Anti-join with False filters. The cardinality of the left input should be

# passed through.

expr

(AntiJoin

(Values

[

(Tuple [ (Const 1 "int") (Const 10 "int") ] "tuple{int}" )

(Tuple [ (Const 2 "int") (Const 20 "int") ] "tuple{int}" )

(Tuple [ (Const 3 "int") (Const 30 "int") ] "tuple{int}" )

]

[ (Cols [ (NewColumn "x" "int") (NewColumn "y" "int") ]) ]

)

(Scan [ (Table "uv") (Cols "u,v") ])

[ (False) ]

[]

)

----

anti-join (cross)

├── columns: x:1(int!null) y:2(int!null)

├── cardinality: [3 - 3]

├── prune: (1,2)

├── values

│ ├── columns: x:1(int!null) y:2(int!null)

│ ├── cardinality: [3 - 3]

│ ├── prune: (1,2)

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 1 [type=int]

│ │ └── const: 10 [type=int]

│ ├── tuple [type=tuple{int}]

│ │ ├── const: 2 [type=int]

│ │ └── const: 20 [type=int]

│ └── tuple [type=tuple{int}]

│ ├── const: 3 [type=int]

│ └── const: 30 [type=int]

├── scan uv

│ ├── columns: u:3(int) v:4(int!null)

│ ├── prune: (3,4)

│ └── unfiltered-cols: (3-7)

└── filters

└── false [type=bool, constraints=(contradiction; tight)]

# Anti-join-apply.

opt

SELECT * FROM xysd WHERE NOT EXISTS(SELECT * FROM uv WHERE v=x OFFSET 1)

----

anti-join-apply

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (2-4)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

│ ├── key: (1)

│ ├── fd: (1)-->(2-4), (3,4)~~>(1,2)

│ ├── prune: (1-4)

│ └── interesting orderings: (+1) (-3,+4,+1)

├── offset

│ ├── columns: v:8(int!null)

│ ├── outer: (1)

│ ├── fd: ()-->(8)

│ ├── select

│ │ ├── columns: v:8(int!null)

│ │ ├── outer: (1)

│ │ ├── fd: ()-->(8)

│ │ ├── scan uv

│ │ │ ├── columns: v:8(int!null)

│ │ │ └── prune: (8)

│ │ └── filters

│ │ └── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

│ │ ├── variable: v:8 [type=int]

│ │ └── variable: x:1 [type=int]

│ └── const: 1 [type=int]

└── filters (true)

# Cross-join.

build

SELECT * FROM xysd, uv

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:7(int) v:8(int!null)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (1-4,7,8)

├── interesting orderings: (+1) (-3,+4,+1)

└── inner-join (cross)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid) u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

├── key: (1,9)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (9)-->(7,8,10,11)

├── prune: (1-11)

├── interesting orderings: (+1) (-3,+4,+1) (+9)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) xysd.crdb_internal_mvcc_timestamp:5(decimal) xysd.tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan uv

│ ├── columns: u:7(int) v:8(int!null) rowid:9(int!null) uv.crdb_internal_mvcc_timestamp:10(decimal) uv.tableoid:11(oid)

│ ├── key: (9)

│ ├── fd: (9)-->(7,8,10,11)

│ ├── prune: (7-11)

│ ├── interesting orderings: (+9)

│ └── unfiltered-cols: (7-11)

└── filters (true)

# Self-join.

build

SELECT * FROM xysd, xysd AS xysd

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) x:7(int!null) y:8(int) s:9(string) d:10(decimal!null)

├── key: (1,7)

├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(8-10), (9,10)~~>(7,8)

├── prune: (1-4,7-10)

├── interesting orderings: (+1) (-3,+4,+1) (+7) (-9,+10,+7)

└── inner-join (cross)

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) crdb_internal_mvcc_timestamp:5(decimal) tableoid:6(oid) x:7(int!null) y:8(int) s:9(string) d:10(decimal!null) crdb_internal_mvcc_timestamp:11(decimal) tableoid:12(oid)

├── key: (1,7)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6), (7)-->(8-12), (9,10)~~>(7,8,11,12)

├── prune: (1-12)

├── interesting orderings: (+1) (-3,+4,+1) (+7) (-9,+10,+7)

├── scan xysd

│ ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) crdb_internal_mvcc_timestamp:5(decimal) tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ ├── interesting orderings: (+1) (-3,+4,+1)

│ └── unfiltered-cols: (1-6)

├── scan xysd

│ ├── columns: x:7(int!null) y:8(int) s:9(string) d:10(decimal!null) crdb_internal_mvcc_timestamp:11(decimal) tableoid:12(oid)

│ ├── key: (7)

│ ├── fd: (7)-->(8-12), (9,10)~~>(7,8,11,12)

│ ├── prune: (7-12)

│ ├── interesting orderings: (+7) (-9,+10,+7)

│ └── unfiltered-cols: (7-12)

└── filters (true)

# Propagate outer columns.

build

SELECT * FROM xysd WHERE EXISTS(SELECT * FROM (SELECT x) INNER JOIN (SELECT y) ON x::string = s)

----

project

├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null)

├── immutable

├── key: (1)

├── fd: (1)-->(2-4), (3,4)~~>(1,2)

├── prune: (1-4)

├── interesting orderings: (+1) (-3,+4,+1)

└── select

├── columns: xysd.x:1(int!null) xysd.y:2(int) s:3(string) d:4(decimal!null) crdb_internal_mvcc_timestamp:5(decimal) tableoid:6(oid)

├── immutable

├── key: (1)

├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

├── prune: (4-6)

├── interesting orderings: (+1) (-3,+4,+1)

├── scan xysd

│ ├── columns: xysd.x:1(int!null) xysd.y:2(int) s:3(string) d:4(decimal!null) crdb_internal_mvcc_timestamp:5(decimal) tableoid:6(oid)

│ ├── key: (1)

│ ├── fd: (1)-->(2-6), (3,4)~~>(1,2,5,6)

│ ├── prune: (1-6)

│ └── interesting orderings: (+1) (-3,+4,+1)

└── filters

└── exists [type=bool, outer=(1-3), immutable, correlated-subquery]

└── inner-join (cross)

├── columns: x:7(int) y:8(int)

├── outer: (1-3)

├── cardinality: [0 - 1]

├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-one)

├── immutable

├── key: ()

├── fd: ()-->(7,8)

├── prune: (8)

├── project

│ ├── columns: x:7(int)

│ ├── outer: (1)

│ ├── cardinality: [1 - 1]

│ ├── key: ()

│ ├── fd: ()-->(7)

│ ├── prune: (7)

│ ├── values

│ │ ├── cardinality: [1 - 1]

│ │ ├── key: ()

│ │ └── tuple [type=tuple]

│ └── projections

│ └── variable: xysd.x:1 [as=x:7, type=int, outer=(1)]

├── project

│ ├── columns: y:8(int)

│ ├── outer: (2)

│ ├── cardinality: [1 - 1]

│ ├── key: ()

│ ├── fd: ()-->(8)

│ ├── prune: (8)

│ ├── values

│ │ ├── cardinality: [1 - 1]

│ │ ├── key: ()

│ │ └── tuple [type=tuple]

│ └── projections

│ └── variable: xysd.y:2 [as=y:8, type=int, outer=(2)]

└── filters

└── eq [type=bool, outer=(3,7), immutable]

├── cast: STRING [type=string]

│ └── variable: x:7 [type=int]

└── variable: s:3 [type=string]

# Calculate semi-join cardinality when left side has non-zero cardinality.

opt

SELECT * FROM (SELECT count(*) cnt FROM xysd) WHERE EXISTS(SELECT * FROM uv WHERE cnt=1)

----

select

├── columns: cnt:7(int!null)