join

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 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
----
inner-join (hash)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int!null) v:6(int!null) rowid:7(int!null)
 ├── key: (7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6), (1)==(5), (5)==(1)
 ├── prune: (2-4,6,7)
 ├── interesting orderings: (+1) (-3,+4,+1) (+7)
 ├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)
 ├── 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)
 ├── scan uv
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+7)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: u:5 [type=int]

# Inner-join-apply.
opt
SELECT (SELECT (VALUES (x), (y))) FROM xysd
----
project
 ├── columns: column1:7(int)
 ├── prune: (7)
 ├── inner-join-apply
 │    ├── columns: x:1(int!null) y:2(int) column1:5(int) column1:6(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2,5,6)
 │    ├── prune: (6)
 │    ├── interesting orderings: (+1)
 │    ├── scan xysd
 │    │    ├── columns: x:1(int!null) y:2(int)
 │    │    ├── key: (1)
 │    │    ├── fd: (1)-->(2)
 │    │    ├── prune: (1,2)
 │    │    └── interesting orderings: (+1)
 │    ├── inner-join-apply
 │    │    ├── columns: column1:5(int) column1:6(int)
 │    │    ├── outer: (1,2)
 │    │    ├── cardinality: [1 - 1]
 │    │    ├── key: ()
 │    │    ├── fd: ()-->(5,6)
 │    │    ├── prune: (6)
 │    │    ├── max1-row
 │    │    │    ├── columns: column1:5(int)
 │    │    │    ├── error: "more than one row returned by a subquery used as an expression"
 │    │    │    ├── outer: (1,2)
 │    │    │    ├── cardinality: [1 - 1]
 │    │    │    ├── key: ()
 │    │    │    ├── fd: ()-->(5)
 │    │    │    └── values
 │    │    │         ├── columns: column1:5(int)
 │    │    │         ├── outer: (1,2)
 │    │    │         ├── cardinality: [2 - 2]
 │    │    │         ├── prune: (5)
 │    │    │         ├── tuple [type=tuple{int}]
 │    │    │         │    └── variable: x:1 [type=int]
 │    │    │         └── tuple [type=tuple{int}]
 │    │    │              └── variable: y:2 [type=int]
 │    │    ├── values
 │    │    │    ├── columns: column1:6(int)
 │    │    │    ├── outer: (5)
 │    │    │    ├── cardinality: [1 - 1]
 │    │    │    ├── key: ()
 │    │    │    ├── fd: ()-->(6)
 │    │    │    ├── prune: (6)
 │    │    │    └── tuple [type=tuple{int}]
 │    │    │         └── variable: column1:5 [type=int]
 │    │    └── filters (true)
 │    └── filters (true)
 └── projections
      └── variable: column1:6 [as=column1:7, type=int, outer=(6)]

# Inner-join-apply nested in inner-join-apply with outer column references to
# each parent.
opt
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)
 └── select
      ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:6(int!null)
      ├── key: (1)
      ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(6), (6)==(1)
      ├── prune: (2-4)
      ├── ensure-distinct-on
      │    ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:6(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,6), (3,4)~~>(1,2)
      │    ├── prune: (2-4,6)
      │    ├── left-join (hash)
      │    │    ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:6(int) n:9(int)
      │    │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (6)==(9), (9)==(6)
      │    │    ├── prune: (2-4)
      │    │    ├── reject-nulls: (6,9)
      │    │    ├── interesting orderings: (+1) (-3,+4,+1) (+9)
      │    │    ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)
      │    │    ├── 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)
      │    │    ├── inner-join (hash)
      │    │    │    ├── columns: v:6(int!null) n:9(int!null)
      │    │    │    ├── fd: (6)==(9), (9)==(6)
      │    │    │    ├── interesting orderings: (+9)
      │    │    │    ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
      │    │    │    ├── scan uv
      │    │    │    │    ├── columns: v:6(int!null)
      │    │    │    │    └── prune: (6)
      │    │    │    ├── scan mn
      │    │    │    │    ├── columns: n:9(int)
      │    │    │    │    ├── lax-key: (9)
      │    │    │    │    ├── prune: (9)
      │    │    │    │    └── interesting orderings: (+9)
      │    │    │    └── filters
      │    │    │         └── eq [type=bool, outer=(6,9), constraints=(/6: (/NULL - ]; /9: (/NULL - ]), fd=(6)==(9), (9)==(6)]
      │    │    │              ├── variable: n:9 [type=int]
      │    │    │              └── variable: v:6 [type=int]
      │    │    └── filters
      │    │         └── eq [type=bool, outer=(1,9), constraints=(/1: (/NULL - ]; /9: (/NULL - ]), fd=(1)==(9), (9)==(1)]
      │    │              ├── variable: x:1 [type=int]
      │    │              └── variable: n:9 [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:6, type=int, outer=(6)]
      │              └── variable: v:6 [type=int]
      └── filters
           └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
                ├── variable: x:1 [type=int]
                └── variable: v:6 [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:6(int!null)
      ├── key: (1)
      ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(6), (6)==(1)
      ├── prune: (2-4)
      ├── ensure-distinct-on
      │    ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:6(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,6), (3,4)~~>(1,2)
      │    ├── prune: (2-4,6)
      │    ├── right-join (hash)
      │    │    ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) v:6(int) m:8(int)
      │    │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
      │    │    ├── prune: (3,4,6)
      │    │    ├── reject-nulls: (6,8)
      │    │    ├── interesting orderings: (+1) (-3,+4,+1) (+8)
      │    │    ├── inner-join (cross)
      │    │    │    ├── columns: v:6(int!null) m:8(int!null)
      │    │    │    ├── prune: (6,8)
      │    │    │    ├── interesting orderings: (+8)
      │    │    │    ├── scan uv
      │    │    │    │    ├── columns: v:6(int!null)
      │    │    │    │    └── prune: (6)
      │    │    │    ├── scan mn
      │    │    │    │    ├── columns: m:8(int!null)
      │    │    │    │    ├── key: (8)
      │    │    │    │    ├── prune: (8)
      │    │    │    │    └── interesting orderings: (+8)
      │    │    │    └── 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)
      │    │    └── 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,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]
      │    │              ├── variable: x:1 [type=int]
      │    │              └── variable: m:8 [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:6, type=int, outer=(6)]
      │              └── variable: v:6 [type=int]
      └── filters
           └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
                ├── variable: x:1 [type=int]
                └── variable: v:6 [type=int]

# Left-join.
build
SELECT *, rowid FROM xysd LEFT JOIN uv ON x=u
----
left-join (hash)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) v:6(int) rowid:7(int)
 ├── key: (1,7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6)
 ├── prune: (2-4,6,7)
 ├── reject-nulls: (5-7)
 ├── interesting orderings: (+1) (-3,+4,+1) (+7)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)
 ├── 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)
 ├── scan uv
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+7)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: u:5 [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:5(int)
      ├── key: (1)
      ├── fd: ()-->(5), (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:5(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-5), (3,4)~~>(1,2)
      │    ├── prune: (2-5)
      │    ├── left-join (hash)
      │    │    ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int)
      │    │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
      │    │    ├── prune: (2-4)
      │    │    ├── reject-nulls: (5)
      │    │    ├── interesting orderings: (+1) (-3,+4,+1)
      │    │    ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)
      │    │    ├── 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)
      │    │    ├── scan uv
      │    │    │    ├── columns: u:5(int)
      │    │    │    └── prune: (5)
      │    │    └── filters
      │    │         └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      │    │              ├── variable: u:5 [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:5, type=int, outer=(5)]
      │              └── variable: u:5 [type=int]
      └── filters
           └── is [type=bool, outer=(5), constraints=(/5: [/NULL - /NULL]; tight), fd=()-->(5)]
                ├── variable: u:5 [type=int]
                └── null [type=unknown]

# Right-join.
build
SELECT *, rowid FROM xysd RIGHT JOIN uv ON x=u
----
right-join (hash)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:5(int) v:6(int!null) rowid:7(int!null)
 ├── key: (7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(1-6)
 ├── prune: (2-4,6,7)
 ├── reject-nulls: (1-4)
 ├── interesting orderings: (+1) (-3,+4,+1) (+7)
 ├── 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)
 ├── scan uv
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+7)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: u:5 [type=int]

# Full-join.
build
SELECT *, rowid FROM xysd FULL JOIN uv ON x=u
----
full-join (hash)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:5(int) v:6(int) rowid:7(int)
 ├── key: (1,7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6)
 ├── prune: (2-4,6,7)
 ├── reject-nulls: (1-7)
 ├── interesting orderings: (+1) (-3,+4,+1) (+7)
 ├── multiplicity: left-rows(one-or-more), right-rows(exactly-one)
 ├── 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)
 ├── scan uv
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+7)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: u:5 [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)
 └── inner-join (lookup xysd)
      ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int!null)
      ├── key columns: [5] = [1]
      ├── lookup columns are key
      ├── key: (5)
      ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(5), (5)==(1)
      ├── distinct-on
      │    ├── columns: u:5(int)
      │    ├── grouping columns: u:5(int)
      │    ├── key: (5)
      │    └── scan uv
      │         ├── columns: u:5(int)
      │         └── prune: (5)
      └── filters (true)

# 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)
 ├── offset
 │    ├── columns: v:6(int!null)
 │    ├── outer: (1)
 │    ├── fd: ()-->(6)
 │    ├── select
 │    │    ├── columns: v:6(int!null)
 │    │    ├── outer: (1)
 │    │    ├── fd: ()-->(6)
 │    │    ├── scan uv
 │    │    │    ├── columns: v:6(int!null)
 │    │    │    └── prune: (6)
 │    │    └── filters
 │    │         └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
 │    │              ├── variable: v:6 [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)
 ├── semi-join (cross)
 │    ├── columns: v:6(int!null)
 │    ├── outer: (1)
 │    ├── fd: ()-->(6)
 │    ├── scan uv
 │    │    ├── columns: v:6(int!null)
 │    │    └── prune: (6)
 │    ├── scan mn
 │    │    ├── columns: m:8(int!null)
 │    │    ├── key: (8)
 │    │    ├── prune: (8)
 │    │    └── interesting orderings: (+8)
 │    └── filters
 │         ├── eq [type=bool, outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]
 │         │    ├── variable: x:1 [type=int]
 │         │    └── variable: m:8 [type=int]
 │         └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
 │              ├── variable: x:1 [type=int]
 │              └── variable: v:6 [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)
 ├── scan uv
 │    ├── columns: u:5(int)
 │    └── prune: (5)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: u:5 [type=int]

# 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:6(int!null)
 │    ├── outer: (1)
 │    ├── fd: ()-->(6)
 │    ├── select
 │    │    ├── columns: v:6(int!null)
 │    │    ├── outer: (1)
 │    │    ├── fd: ()-->(6)
 │    │    ├── scan uv
 │    │    │    ├── columns: v:6(int!null)
 │    │    │    └── prune: (6)
 │    │    └── filters
 │    │         └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
 │    │              ├── variable: v:6 [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:5(int) v:6(int!null)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
 ├── prune: (1-6)
 ├── interesting orderings: (+1) (-3,+4,+1)
 └── inner-join (cross)
      ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) v:6(int!null) rowid:7(int!null)
      ├── key: (1,7)
      ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6)
      ├── prune: (1-7)
      ├── interesting orderings: (+1) (-3,+4,+1) (+7)
      ├── 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)
      ├── scan uv
      │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
      │    ├── key: (7)
      │    ├── fd: (7)-->(5,6)
      │    ├── prune: (5-7)
      │    └── interesting orderings: (+7)
      └── filters (true)

# Self-join.
build
SELECT * FROM xysd, xysd AS xysd
----
inner-join (cross)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)-->(6-8), (7,8)~~>(5,6)
 ├── prune: (1-8)
 ├── interesting orderings: (+1) (-3,+4,+1) (+5) (-7,+8,+5)
 ├── 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)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters (true)

# Propagate outer columns.
build
SELECT * FROM xysd WHERE EXISTS(SELECT * FROM (SELECT x) INNER JOIN (SELECT y) ON x::string = s)
----
select
 ├── 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: (4)
 ├── 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)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 └── filters
      └── exists [type=bool, outer=(1-3), correlated-subquery]
           └── inner-join (cross)
                ├── columns: x:5(int) y:6(int)
                ├── outer: (1-3)
                ├── cardinality: [0 - 1]
                ├── key: ()
                ├── fd: ()-->(5,6)
                ├── prune: (6)
                ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-one)
                ├── project
                │    ├── columns: x:5(int)
                │    ├── outer: (1)
                │    ├── cardinality: [1 - 1]
                │    ├── key: ()
                │    ├── fd: ()-->(5)
                │    ├── prune: (5)
                │    ├── values
                │    │    ├── cardinality: [1 - 1]
                │    │    ├── key: ()
                │    │    └── tuple [type=tuple]
                │    └── projections
                │         └── variable: xysd.x:1 [as=x:5, type=int, outer=(1)]
                ├── project
                │    ├── columns: y:6(int)
                │    ├── outer: (2)
                │    ├── cardinality: [1 - 1]
                │    ├── key: ()
                │    ├── fd: ()-->(6)
                │    ├── prune: (6)
                │    ├── values
                │    │    ├── cardinality: [1 - 1]
                │    │    ├── key: ()
                │    │    └── tuple [type=tuple]
                │    └── projections
                │         └── variable: xysd.y:2 [as=y:6, type=int, outer=(2)]
                └── filters
                     └── eq [type=bool, outer=(3,5)]
                          ├── cast: STRING [type=string]
                          │    └── variable: x:5 [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)
----
project
 ├── columns: cnt:5(int!null)
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(5)
 └── inner-join (cross)
      ├── columns: count_rows:5(int!null)
      ├── cardinality: [0 - 1]
      ├── key: ()
      ├── fd: ()-->(5)
      ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-one)
      ├── select
      │    ├── columns: count_rows:5(int!null)
      │    ├── cardinality: [0 - 1]
      │    ├── key: ()
      │    ├── fd: ()-->(5)
      │    ├── scalar-group-by
      │    │    ├── columns: count_rows:5(int!null)
      │    │    ├── cardinality: [1 - 1]
      │    │    ├── key: ()
      │    │    ├── fd: ()-->(5)
      │    │    ├── prune: (5)
      │    │    ├── scan xysd@secondary
      │    │    └── aggregations
      │    │         └── count-rows [as=count_rows:5, type=int]
      │    └── filters
      │         └── eq [type=bool, outer=(5), constraints=(/5: [/1 - /1]; tight), fd=()-->(5)]
      │              ├── variable: count_rows:5 [type=int]
      │              └── const: 1 [type=int]
      ├── scan uv
      │    ├── limit: 1
      │    └── key: ()
      └── filters (true)

# Calculate semi-join-apply cardinality.
expr
(SemiJoinApply
    (FakeRel
        [
            (OutputCols [ (NewColumn "a" "int") ])
            (Cardinality "0-10")
        ]
    )
    (FakeRel
        [
            (OutputCols [ (NewColumn "a" "int") ])
        ]
    )
    [ ]
    [ ]
)
----
semi-join-apply
 ├── columns: a:1(int)
 ├── cardinality: [0 - 10]
 ├── fake-rel
 │    ├── columns: a:1(int)
 │    └── cardinality: [0 - 10]
 ├── fake-rel
 │    ├── columns: a:2(int)
 │    └── cardinality: [0 - 0]
 └── filters (true)

# Calculate anti-join cardinality when left side has non-zero cardinality.
opt
SELECT * FROM (SELECT * FROM (VALUES (1), (2))) WHERE NOT EXISTS(SELECT * FROM uv WHERE u=column1)
----
anti-join (hash)
 ├── columns: column1:1(int!null)
 ├── cardinality: [0 - 2]
 ├── values
 │    ├── columns: column1:1(int!null)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (1)
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 1 [type=int]
 │    └── tuple [type=tuple{int}]
 │         └── const: 2 [type=int]
 ├── scan uv
 │    ├── columns: u:2(int)
 │    └── prune: (2)
 └── filters
      └── eq [type=bool, outer=(1,2), constraints=(/1: (/NULL - ]; /2: (/NULL - ]), fd=(1)==(2), (2)==(1)]
           ├── variable: u:2 [type=int]
           └── variable: column1:1 [type=int]

# Calculate anti-join-apply cardinality.
expr
(AntiJoinApply
    (FakeRel
        [
            (OutputCols [ (NewColumn "a" "int") ])
            (Cardinality "0-10")
        ]
    )
    (FakeRel
        [
            (OutputCols [ (NewColumn "a" "int") ])
        ]
    )
    [ ]
    [ ]
)
----
anti-join-apply
 ├── columns: a:1(int)
 ├── cardinality: [0 - 10]
 ├── fake-rel
 │    ├── columns: a:1(int)
 │    └── cardinality: [0 - 10]
 ├── fake-rel
 │    ├── columns: a:2(int)
 │    └── cardinality: [0 - 0]
 └── filters (true)

# Calculate inner-join cardinality.
build
SELECT * FROM (VALUES (1), (2)) INNER JOIN (SELECT * FROM uv LIMIT 2) ON True
----
inner-join (cross)
 ├── columns: column1:1(int!null) u:2(int) v:3(int!null)
 ├── cardinality: [0 - 4]
 ├── prune: (1-3)
 ├── values
 │    ├── columns: column1:1(int!null)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (1)
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 1 [type=int]
 │    └── tuple [type=tuple{int}]
 │         └── const: 2 [type=int]
 ├── limit
 │    ├── columns: u:2(int) v:3(int!null)
 │    ├── cardinality: [0 - 2]
 │    ├── prune: (2,3)
 │    ├── project
 │    │    ├── columns: u:2(int) v:3(int!null)
 │    │    ├── limit hint: 2.00
 │    │    ├── prune: (2,3)
 │    │    └── scan uv
 │    │         ├── columns: u:2(int) v:3(int!null) rowid:4(int!null)
 │    │         ├── key: (4)
 │    │         ├── fd: (4)-->(2,3)
 │    │         ├── limit hint: 2.00
 │    │         ├── prune: (2-4)
 │    │         └── interesting orderings: (+4)
 │    └── const: 2 [type=int]
 └── filters
      └── true [type=bool]

# Calculate left-join cardinality.
build
SELECT * FROM (VALUES (1), (2), (3)) LEFT JOIN (SELECT * FROM uv LIMIT 2) ON True
----
left-join (cross)
 ├── columns: column1:1(int!null) u:2(int) v:3(int)
 ├── cardinality: [3 - 6]
 ├── prune: (1-3)
 ├── reject-nulls: (2,3)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 ├── values
 │    ├── columns: column1:1(int!null)
 │    ├── cardinality: [3 - 3]
 │    ├── prune: (1)
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 1 [type=int]
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 2 [type=int]
 │    └── tuple [type=tuple{int}]
 │         └── const: 3 [type=int]
 ├── limit
 │    ├── columns: u:2(int) v:3(int!null)
 │    ├── cardinality: [0 - 2]
 │    ├── prune: (2,3)
 │    ├── project
 │    │    ├── columns: u:2(int) v:3(int!null)
 │    │    ├── limit hint: 2.00
 │    │    ├── prune: (2,3)
 │    │    └── scan uv
 │    │         ├── columns: u:2(int) v:3(int!null) rowid:4(int!null)
 │    │         ├── key: (4)
 │    │         ├── fd: (4)-->(2,3)
 │    │         ├── limit hint: 2.00
 │    │         ├── prune: (2-4)
 │    │         └── interesting orderings: (+4)
 │    └── const: 2 [type=int]
 └── filters
      └── true [type=bool]

# Calculate right-join cardinality.
build
SELECT * FROM (SELECT * FROM uv LIMIT 2) RIGHT JOIN (VALUES (1), (2), (3)) ON True
----
right-join (cross)
 ├── columns: u:1(int) v:2(int) column1:4(int!null)
 ├── cardinality: [3 - 6]
 ├── prune: (1,2,4)
 ├── reject-nulls: (1,2)
 ├── limit
 │    ├── columns: u:1(int) v:2(int!null)
 │    ├── cardinality: [0 - 2]
 │    ├── prune: (1,2)
 │    ├── project
 │    │    ├── columns: u:1(int) v:2(int!null)
 │    │    ├── limit hint: 2.00
 │    │    ├── prune: (1,2)
 │    │    └── scan uv
 │    │         ├── columns: u:1(int) v:2(int!null) rowid:3(int!null)
 │    │         ├── key: (3)
 │    │         ├── fd: (3)-->(1,2)
 │    │         ├── limit hint: 2.00
 │    │         ├── prune: (1-3)
 │    │         └── interesting orderings: (+3)
 │    └── const: 2 [type=int]
 ├── values
 │    ├── columns: column1:4(int!null)
 │    ├── cardinality: [3 - 3]
 │    ├── prune: (4)
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 1 [type=int]
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 2 [type=int]
 │    └── tuple [type=tuple{int}]
 │         └── const: 3 [type=int]
 └── filters
      └── true [type=bool]

# Calculate full-join cardinality.
build
SELECT * FROM (VALUES (NULL), (NULL)) a FULL JOIN (VALUES (NULL), (NULL)) b ON True
----
full-join (cross)
 ├── columns: column1:1(unknown) column1:2(unknown)
 ├── cardinality: [2 - 4]
 ├── prune: (1,2)
 ├── reject-nulls: (1,2)
 ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 ├── values
 │    ├── columns: column1:1(unknown)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (1)
 │    ├── tuple [type=tuple{unknown}]
 │    │    └── null [type=unknown]
 │    └── tuple [type=tuple{unknown}]
 │         └── null [type=unknown]
 ├── values
 │    ├── columns: column1:2(unknown)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (2)
 │    ├── tuple [type=tuple{unknown}]
 │    │    └── null [type=unknown]
 │    └── tuple [type=tuple{unknown}]
 │         └── null [type=unknown]
 └── filters
      └── true [type=bool]

# Calculate full-join cardinality when both sides have an empty key (#44029).
build
SELECT * FROM (VALUES (1, 2)) a(a1,a2) FULL JOIN (VALUES (3, 4)) b(b1,b2) ON a1=b1
----
full-join (hash)
 ├── columns: a1:1(int) a2:2(int) b1:3(int) b2:4(int)
 ├── cardinality: [1 - 2]
 ├── prune: (2,4)
 ├── reject-nulls: (1-4)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── values
 │    ├── columns: column1:1(int!null) column2:2(int!null)
 │    ├── cardinality: [1 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(1,2)
 │    ├── prune: (1,2)
 │    └── tuple [type=tuple{int, int}]
 │         ├── const: 1 [type=int]
 │         └── const: 2 [type=int]
 ├── values
 │    ├── columns: column1:3(int!null) column2:4(int!null)
 │    ├── cardinality: [1 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(3,4)
 │    ├── prune: (3,4)
 │    └── tuple [type=tuple{int, int}]
 │         ├── const: 3 [type=int]
 │         └── const: 4 [type=int]
 └── filters
      └── eq [type=bool, outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]
           ├── variable: column1:1 [type=int]
           └── variable: column1:3 [type=int]

# Calculate full-join cardinality with false filter.
build
SELECT * FROM (VALUES (NULL), (NULL)) a FULL JOIN (VALUES (NULL), (NULL)) b ON a.column1=b.column1
----
full-join (cross)
 ├── columns: column1:1(unknown) column1:2(unknown)
 ├── cardinality: [2 - 4]
 ├── prune: (1,2)
 ├── reject-nulls: (1,2)
 ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 ├── values
 │    ├── columns: column1:1(unknown)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (1)
 │    ├── tuple [type=tuple{unknown}]
 │    │    └── null [type=unknown]
 │    └── tuple [type=tuple{unknown}]
 │         └── null [type=unknown]
 ├── values
 │    ├── columns: column1:2(unknown)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (2)
 │    ├── tuple [type=tuple{unknown}]
 │    │    └── null [type=unknown]
 │    └── tuple [type=tuple{unknown}]
 │         └── null [type=unknown]
 └── filters
      └── cast: BOOL [type=bool]
           └── null [type=unknown]

# Calculate full-join cardinality of one input with unknown cardinality.
build
SELECT * FROM xysd FULL JOIN (SELECT * FROM (VALUES (1), (2))) ON True
----
full-join (cross)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) column1:5(int)
 ├── cardinality: [2 - ]
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
 ├── prune: (1-5)
 ├── reject-nulls: (1-5)
 ├── interesting orderings: (+1) (-3,+4,+1)
 ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 ├── 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)
 ├── values
 │    ├── columns: column1:5(int!null)
 │    ├── cardinality: [2 - 2]
 │    ├── prune: (5)
 │    ├── tuple [type=tuple{int}]
 │    │    └── const: 1 [type=int]
 │    └── tuple [type=tuple{int}]
 │         └── const: 2 [type=int]
 └── filters
      └── true [type=bool]

# Keys on both sides of full-join.
build
SELECT * FROM (SELECT * FROM xysd LIMIT 1) FULL JOIN (SELECT * FROM xysd LIMIT 1) ON True
----
full-join (cross)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) x:5(int) y:6(int) s:7(string) d:8(decimal)
 ├── cardinality: [0 - 2]
 ├── prune: (1-8)
 ├── reject-nulls: (1-8)
 ├── interesting orderings: (+1) (-3,+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── limit
 │    ├── 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)
 │    ├── 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)
 │    │    ├── limit hint: 1.00
 │    │    ├── prune: (1-4)
 │    │    └── interesting orderings: (+1) (-3,+4,+1)
 │    └── const: 1 [type=int]
 ├── limit
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── cardinality: [0 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(5-8)
 │    ├── prune: (5-8)
 │    ├── interesting orderings: (+5) (-7,+8,+5)
 │    ├── scan xysd
 │    │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    │    ├── key: (5)
 │    │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    │    ├── limit hint: 1.00
 │    │    ├── prune: (5-8)
 │    │    └── interesting orderings: (+5) (-7,+8,+5)
 │    └── const: 1 [type=int]
 └── filters
      └── true [type=bool]

# Nullable FD determinant on right side of left-join becomes lax.
build
SELECT * FROM xysd LEFT JOIN (SELECT u, sum(v) FROM uv GROUP BY u) ON u IS NOT NULL
----
left-join (cross)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) sum:8(decimal)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)~~>(8), (1,5)-->(8)
 ├── prune: (1-4,8)
 ├── reject-nulls: (5,8)
 ├── interesting orderings: (+1) (-3,+4,+1)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 ├── 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)
 ├── group-by
 │    ├── columns: u:5(int) sum:8(decimal!null)
 │    ├── grouping columns: u:5(int)
 │    ├── key: (5)
 │    ├── fd: (5)-->(8)
 │    ├── prune: (8)
 │    ├── project
 │    │    ├── columns: u:5(int) v:6(int!null)
 │    │    ├── prune: (5,6)
 │    │    └── scan uv
 │    │         ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    │         ├── key: (7)
 │    │         ├── fd: (7)-->(5,6)
 │    │         ├── prune: (5-7)
 │    │         └── interesting orderings: (+7)
 │    └── aggregations
 │         └── sum [as=sum:8, type=decimal, outer=(6)]
 │              └── variable: v:6 [type=int]
 └── filters
      └── is-not [type=bool, outer=(5), constraints=(/5: (/NULL - ]; tight)]
           ├── variable: u:5 [type=int]
           └── null [type=unknown]

# Not-null FD determinant on right side of left-join stays strict.
build
SELECT * FROM xysd LEFT JOIN (SELECT u, sum(v) FROM uv WHERE u IS NOT NULL GROUP BY u) ON True
----
left-join (cross)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) sum:8(decimal)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)-->(8)
 ├── prune: (1-4,8)
 ├── reject-nulls: (5,8)
 ├── interesting orderings: (+1) (-3,+4,+1)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 ├── 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)
 ├── group-by
 │    ├── columns: u:5(int!null) sum:8(decimal!null)
 │    ├── grouping columns: u:5(int!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(8)
 │    ├── prune: (8)
 │    ├── project
 │    │    ├── columns: u:5(int!null) v:6(int!null)
 │    │    ├── prune: (5,6)
 │    │    └── select
 │    │         ├── columns: u:5(int!null) v:6(int!null) rowid:7(int!null)
 │    │         ├── key: (7)
 │    │         ├── fd: (7)-->(5,6)
 │    │         ├── prune: (6,7)
 │    │         ├── interesting orderings: (+7)
 │    │         ├── scan uv
 │    │         │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    │         │    ├── key: (7)
 │    │         │    ├── fd: (7)-->(5,6)
 │    │         │    ├── prune: (5-7)
 │    │         │    └── interesting orderings: (+7)
 │    │         └── filters
 │    │              └── is-not [type=bool, outer=(5), constraints=(/5: (/NULL - ]; tight)]
 │    │                   ├── variable: u:5 [type=int]
 │    │                   └── null [type=unknown]
 │    └── aggregations
 │         └── sum [as=sum:8, type=decimal, outer=(6)]
 │              └── variable: v:6 [type=int]
 └── filters
      └── true [type=bool]

# Nullable FD determinant on left side of right-join becomes lax.
build
SELECT * FROM (SELECT u, sum(v) FROM uv GROUP BY u) RIGHT JOIN xysd ON u IS NOT NULL
----
right-join (cross)
 ├── columns: u:1(int) sum:4(decimal) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1,5)
 ├── fd: (5)-->(6-8), (7,8)~~>(5,6), (1)~~>(4), (1,5)-->(4)
 ├── prune: (4-8)
 ├── reject-nulls: (1,4)
 ├── interesting orderings: (+5) (-7,+8,+5)
 ├── group-by
 │    ├── columns: u:1(int) sum:4(decimal!null)
 │    ├── grouping columns: u:1(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(4)
 │    ├── prune: (4)
 │    ├── project
 │    │    ├── columns: u:1(int) v:2(int!null)
 │    │    ├── prune: (1,2)
 │    │    └── scan uv
 │    │         ├── columns: u:1(int) v:2(int!null) rowid:3(int!null)
 │    │         ├── key: (3)
 │    │         ├── fd: (3)-->(1,2)
 │    │         ├── prune: (1-3)
 │    │         └── interesting orderings: (+3)
 │    └── aggregations
 │         └── sum [as=sum:4, type=decimal, outer=(2)]
 │              └── variable: v:2 [type=int]
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── is-not [type=bool, outer=(1), constraints=(/1: (/NULL - ]; tight)]
           ├── variable: u:1 [type=int]
           └── null [type=unknown]

# Not-null FD determinant on left side of right-join stays strict.
build
SELECT * FROM (SELECT u, sum(v) FROM uv WHERE u IS NOT NULL GROUP BY u) RIGHT JOIN xysd ON True
----
right-join (cross)
 ├── columns: u:1(int) sum:4(decimal) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1,5)
 ├── fd: (1)-->(4), (5)-->(6-8), (7,8)~~>(5,6)
 ├── prune: (4-8)
 ├── reject-nulls: (1,4)
 ├── interesting orderings: (+5) (-7,+8,+5)
 ├── group-by
 │    ├── columns: u:1(int!null) sum:4(decimal!null)
 │    ├── grouping columns: u:1(int!null)
 │    ├── key: (1)
 │    ├── fd: (1)-->(4)
 │    ├── prune: (4)
 │    ├── project
 │    │    ├── columns: u:1(int!null) v:2(int!null)
 │    │    ├── prune: (1,2)
 │    │    └── select
 │    │         ├── columns: u:1(int!null) v:2(int!null) rowid:3(int!null)
 │    │         ├── key: (3)
 │    │         ├── fd: (3)-->(1,2)
 │    │         ├── prune: (2,3)
 │    │         ├── interesting orderings: (+3)
 │    │         ├── scan uv
 │    │         │    ├── columns: u:1(int) v:2(int!null) rowid:3(int!null)
 │    │         │    ├── key: (3)
 │    │         │    ├── fd: (3)-->(1,2)
 │    │         │    ├── prune: (1-3)
 │    │         │    └── interesting orderings: (+3)
 │    │         └── filters
 │    │              └── is-not [type=bool, outer=(1), constraints=(/1: (/NULL - ]; tight)]
 │    │                   ├── variable: u:1 [type=int]
 │    │                   └── null [type=unknown]
 │    └── aggregations
 │         └── sum [as=sum:4, type=decimal, outer=(2)]
 │              └── variable: v:2 [type=int]
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── true [type=bool]

# Nullable FD determinant on right side of full-join becomes lax.
build
SELECT * FROM xysd FULL JOIN (SELECT u, sum(v) FROM uv GROUP BY u) ON u IS NOT NULL
----
full-join (cross)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:5(int) sum:8(decimal)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)~~>(8), (1,5)-->(8)
 ├── prune: (1-4,8)
 ├── reject-nulls: (1-5,8)
 ├── interesting orderings: (+1) (-3,+4,+1)
 ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 ├── 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)
 ├── group-by
 │    ├── columns: u:5(int) sum:8(decimal!null)
 │    ├── grouping columns: u:5(int)
 │    ├── key: (5)
 │    ├── fd: (5)-->(8)
 │    ├── prune: (8)
 │    ├── project
 │    │    ├── columns: u:5(int) v:6(int!null)
 │    │    ├── prune: (5,6)
 │    │    └── scan uv
 │    │         ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    │         ├── key: (7)
 │    │         ├── fd: (7)-->(5,6)
 │    │         ├── prune: (5-7)
 │    │         └── interesting orderings: (+7)
 │    └── aggregations
 │         └── sum [as=sum:8, type=decimal, outer=(6)]
 │              └── variable: v:6 [type=int]
 └── filters
      └── is-not [type=bool, outer=(5), constraints=(/5: (/NULL - ]; tight)]
           ├── variable: u:5 [type=int]
           └── null [type=unknown]

# Nullable FD determinant on left side of full-join becomes lax.
build
SELECT * FROM (SELECT u, sum(v) FROM uv GROUP BY u) FULL JOIN xysd ON u IS NOT NULL
----
full-join (cross)
 ├── columns: u:1(int) sum:4(decimal) x:5(int) y:6(int) s:7(string) d:8(decimal)
 ├── key: (1,5)
 ├── fd: (5)-->(6-8), (7,8)~~>(5,6), (1)~~>(4), (1,5)-->(4)
 ├── prune: (4-8)
 ├── reject-nulls: (1,4-8)
 ├── interesting orderings: (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 ├── group-by
 │    ├── columns: u:1(int) sum:4(decimal!null)
 │    ├── grouping columns: u:1(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(4)
 │    ├── prune: (4)
 │    ├── project
 │    │    ├── columns: u:1(int) v:2(int!null)
 │    │    ├── prune: (1,2)
 │    │    └── scan uv
 │    │         ├── columns: u:1(int) v:2(int!null) rowid:3(int!null)
 │    │         ├── key: (3)
 │    │         ├── fd: (3)-->(1,2)
 │    │         ├── prune: (1-3)
 │    │         └── interesting orderings: (+3)
 │    └── aggregations
 │         └── sum [as=sum:4, type=decimal, outer=(2)]
 │              └── variable: v:2 [type=int]
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── is-not [type=bool, outer=(1), constraints=(/1: (/NULL - ]; tight)]
           ├── variable: u:1 [type=int]
           └── null [type=unknown]

# Merge join (inner).
expr
(MergeJoin
    (Scan [ (Table "xysd") (Cols "x,y,s,d") ])
    (Sort (Scan [ (Table "uv") (Cols "u,v,rowid") ]))
    [ ]
    [
        (JoinType "inner-join")
        (LeftEq "+x")
        (RightEq "+u")
        (LeftOrdering "+x")
        (RightOrdering "+u")
    ]
)
----
inner-join (merge)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int!null) v:6(int!null) rowid:7(int!null)
 ├── left ordering: +1
 ├── right ordering: +5
 ├── key: (7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6), (1)==(5), (5)==(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)
 │    ├── ordering: +1
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 ├── sort
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── ordering: +5
 │    └── scan uv
 │         ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │         ├── key: (7)
 │         └── fd: (7)-->(5,6)
 └── filters (true)

# Merge join (left).
expr
(MergeJoin
    (Scan [ (Table "xysd") (Cols "x,y,s,d") ])
    (Sort (Scan [ (Table "uv") (Cols "u,v,rowid") ]))
    [ ]
    [
        (JoinType "left-join")
        (LeftEq "+x")
        (RightEq "+u")
        (LeftOrdering "+x")
        (RightOrdering "+u")
    ]
)
----
left-join (merge)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) v:6(int) rowid:7(int)
 ├── left ordering: +1
 ├── right ordering: +5
 ├── key: (1,7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(5,6)
 ├── 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)
 │    ├── ordering: +1
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 ├── sort
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── ordering: +5
 │    └── scan uv
 │         ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │         ├── key: (7)
 │         └── fd: (7)-->(5,6)
 └── filters (true)

# Merge join (right) with remaining ON condition.
expr
(MergeJoin
    (Scan [ (Table "xysd") (Cols "x,y,s,d") ])
    (Sort (Scan [ (Table "uv") (Cols "u,v,rowid") ]))
    [ (Gt (Var "y") (Var "v")) ]
    [
        (JoinType "right-join")
        (LeftEq "+x")
        (RightEq "+u")
        (LeftOrdering "+x")
        (RightOrdering "+u")
    ]
)
----
right-join (merge)
 ├── columns: x:1(int) y:2(int) s:3(string) d:4(decimal) u:5(int) v:6(int!null) rowid:7(int!null)
 ├── left ordering: +1
 ├── right ordering: +5
 ├── key: (7)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (7)-->(1-6)
 ├── 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)
 │    ├── ordering: +1
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 ├── sort
 │    ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │    ├── key: (7)
 │    ├── fd: (7)-->(5,6)
 │    ├── ordering: +5
 │    └── scan uv
 │         ├── columns: u:5(int) v:6(int!null) rowid:7(int!null)
 │         ├── key: (7)
 │         └── fd: (7)-->(5,6)
 └── filters
      └── gt [type=bool, outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]
           ├── variable: y:2 [type=int]
           └── variable: v:6 [type=int]

# Regression test #36183.
opt
SELECT (SELECT m FROM
  (SELECT * FROM (SELECT * FROM [INSERT INTO uv VALUES (1, 2) RETURNING *] WHERE false) JOIN (SELECT * FROM uv WHERE false) ON true)
  JOIN (SELECT * FROM mn WHERE uv.u IN (SELECT n FROM mn)) ON true
) FROM uv
----
with &1
 ├── columns: m:19(int)
 ├── volatile, side-effects, mutations
 ├── fd: ()-->(19)
 ├── prune: (19)
 ├── project
 │    ├── columns: uv.u:4(int!null) uv.v:5(int!null)
 │    ├── cardinality: [1 - 1]
 │    ├── volatile, side-effects, mutations
 │    ├── key: ()
 │    ├── fd: ()-->(4,5)
 │    ├── prune: (4,5)
 │    └── insert uv
 │         ├── columns: uv.u:4(int!null) uv.v:5(int!null) rowid:6(int!null)
 │         ├── insert-mapping:
 │         │    ├── column1:7 => uv.u:4
 │         │    ├── column2:8 => uv.v:5
 │         │    └── column9:9 => rowid:6
 │         ├── cardinality: [1 - 1]
 │         ├── volatile, side-effects, mutations
 │         ├── key: ()
 │         ├── fd: ()-->(4-6)
 │         └── values
 │              ├── columns: column1:7(int!null) column2:8(int!null) column9:9(int)
 │              ├── cardinality: [1 - 1]
 │              ├── volatile, side-effects
 │              ├── key: ()
 │              ├── fd: ()-->(7-9)
 │              ├── prune: (7-9)
 │              └── tuple [type=tuple{int, int, int}]
 │                   ├── const: 1 [type=int]
 │                   ├── const: 2 [type=int]
 │                   └── function: unique_rowid [type=int]
 └── project
      ├── columns: m:19(int)
      ├── fd: ()-->(19)
      ├── prune: (19)
      ├── scan uv
      └── projections
           └── subquery [as=m:19, type=int, subquery]
                └── values
                     ├── columns: mn.m:15(int!null)
                     ├── cardinality: [0 - 0]
                     ├── key: ()
                     ├── fd: ()-->(15)
                     └── prune: (15)

# Regression test #40456.
opt
SELECT NULL
FROM uv
WHERE NOT EXISTS(SELECT uv.u);
----
values
 ├── columns: "?column?":5(unknown!null)
 ├── cardinality: [0 - 0]
 ├── key: ()
 ├── fd: ()-->(5)
 └── prune: (5)

# Regression test #43651: outer join with empty key.
opt
SELECT a FROM
    (VALUES (NULL)) AS t1(a)
  FULL JOIN
    (VALUES ('23:59:59.999999':::TIME)) AS t2(b)
  ON false
----
full-join (cross)
 ├── columns: a:1(unknown)
 ├── cardinality: [2 - 2]
 ├── prune: (1)
 ├── reject-nulls: (1)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── values
 │    ├── columns: column1:1(unknown)
 │    ├── cardinality: [1 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(1)
 │    ├── prune: (1)
 │    └── tuple [type=tuple{unknown}]
 │         └── null [type=unknown]
 ├── values
 │    ├── cardinality: [1 - 1]
 │    ├── key: ()
 │    └── tuple [type=tuple]
 └── filters
      └── false [type=bool]

exec-ddl
CREATE TABLE t1 (x INT, y INT)
----

exec-ddl
CREATE TABLE t2 (x INT, y INT)
----

# Outer join when both sides have a key. Because x can still have NULL values,
# we cannot say that the outer join has a strict key. For example, this is a
# possible valid result for this query:
#   t1.x | t1.y | t2.x | t2.y
#   -----+------+------+------
#      1 |    1 |    1 |    2
#   NULL |    1 | NULL | NULL
#   NULL | NULL | NULL |    2
# Here (t1.x, t2.x) is a lax key but not a strict key.
opt
SELECT * FROM
  (SELECT * FROM (SELECT DISTINCT ON (x) x, y FROM t1) WHERE y IS NOT NULL) AS t1
FULL JOIN
  (SELECT * FROM (SELECT DISTINCT ON (x) x, y FROM t2) WHERE y IS NOT NULL) AS t2
ON t1.x = t2.x
----
full-join (hash)
 ├── columns: x:1(int) y:2(int) x:4(int) y:5(int)
 ├── lax-key: (1,4)
 ├── fd: (1)~~>(2), (4)~~>(5), (1,4)~~>(2,5)
 ├── reject-nulls: (1,2,4,5)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── select
 │    ├── columns: t1.x:1(int) t1.y:2(int!null)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2)
 │    ├── distinct-on
 │    │    ├── columns: t1.x:1(int) t1.y:2(int)
 │    │    ├── grouping columns: t1.x:1(int)
 │    │    ├── key: (1)
 │    │    ├── fd: (1)-->(2)
 │    │    ├── prune: (2)
 │    │    ├── scan t1
 │    │    │    ├── columns: t1.x:1(int) t1.y:2(int)
 │    │    │    └── prune: (1,2)
 │    │    └── aggregations
 │    │         └── first-agg [as=t1.y:2, type=int, outer=(2)]
 │    │              └── variable: t1.y:2 [type=int]
 │    └── filters
 │         └── is-not [type=bool, outer=(2), constraints=(/2: (/NULL - ]; tight)]
 │              ├── variable: t1.y:2 [type=int]
 │              └── null [type=unknown]
 ├── select
 │    ├── columns: t2.x:4(int) t2.y:5(int!null)
 │    ├── key: (4)
 │    ├── fd: (4)-->(5)
 │    ├── distinct-on
 │    │    ├── columns: t2.x:4(int) t2.y:5(int)
 │    │    ├── grouping columns: t2.x:4(int)
 │    │    ├── key: (4)
 │    │    ├── fd: (4)-->(5)
 │    │    ├── prune: (5)
 │    │    ├── scan t2
 │    │    │    ├── columns: t2.x:4(int) t2.y:5(int)
 │    │    │    └── prune: (4,5)
 │    │    └── aggregations
 │    │         └── first-agg [as=t2.y:5, type=int, outer=(5)]
 │    │              └── variable: t2.y:5 [type=int]
 │    └── filters
 │         └── is-not [type=bool, outer=(5), constraints=(/5: (/NULL - ]; tight)]
 │              ├── variable: t2.y:5 [type=int]
 │              └── null [type=unknown]
 └── filters
      └── eq [type=bool, outer=(1,4), constraints=(/1: (/NULL - ]; /4: (/NULL - ]), fd=(1)==(4), (4)==(1)]
           ├── variable: t1.x:1 [type=int]
           └── variable: t2.x:4 [type=int]

# InnerJoin with an equality between one key column and one non-key column.
# Neither input is guaranteed a match for every row. Rows from uv will not be
# duplicated because the x column is unique. Rows from xysd may be duplicated
# because the v column is not unique.
norm
SELECT * FROM xysd INNER JOIN uv ON x=v
----
inner-join (hash)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) u:5(int) v:6(int!null)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (1)==(6), (6)==(1)
 ├── prune: (2-5)
 ├── interesting orderings: (+1) (-3,+4,+1)
 ├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)
 ├── 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)
 ├── scan uv
 │    ├── columns: u:5(int) v:6(int!null)
 │    └── prune: (5,6)
 └── filters
      └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
           ├── variable: x:1 [type=int]
           └── variable: v:6 [type=int]

# InnerJoin with a not-null foreign key equality. Since the foreign key is
# not-null, rows from the fk table are guaranteed a match. Since x is a key
# column, rows from the fk table will not be duplicated.
norm
SELECT * FROM fk INNER JOIN xysd ON x = r1
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (3)==(5), (5)==(3)
 ├── prune: (1,2,4,6-8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(exactly-one), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(3,5), constraints=(/3: (/NULL - ]; /5: (/NULL - ]), fd=(3)==(5), (5)==(3)]
           ├── variable: x:5 [type=int]
           └── variable: r1:3 [type=int]

# InnerJoin with a nullable foreign key equality condition.
norm
SELECT * FROM fk INNER JOIN xysd ON x = r2
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int!null) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (4)==(5), (5)==(4)
 ├── prune: (1-3,6-8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(4,5), constraints=(/4: (/NULL - ]; /5: (/NULL - ]), fd=(4)==(5), (5)==(4)]
           ├── variable: x:5 [type=int]
           └── variable: r2:4 [type=int]

# Cross join. Rows from fk are guaranteed matches because the not-null foreign
# key implies that xysd has at least one row whenever fk does.
norm
SELECT * FROM fk CROSS JOIN xysd
----
inner-join (cross)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6)
 ├── prune: (1-8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters (true)

# LeftJoin case with a not-null foreign key. Since fk rows are all guaranteed
# exactly one match, xysd will not be null-extended and the LeftJoin can
# therefore be simplified.
norm
SELECT * FROM fk LEFT JOIN xysd ON x = r1
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (1)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (3)==(5), (5)==(3)
 ├── prune: (1,2,4,6-8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(exactly-one), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(3,5), constraints=(/3: (/NULL - ]; /5: (/NULL - ]), fd=(3)==(5), (5)==(3)]
           ├── variable: x:5 [type=int]
           └── variable: r1:3 [type=int]


# LeftJoin case with a nullable foreign key. The LeftJoin cannot be simplified
# because a nullable foreign key is not guaranteed matches.
norm
SELECT * FROM fk LEFT JOIN xysd ON x = r2
----
left-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int) y:6(int) s:7(string) d:8(decimal)
 ├── key: (1)
 ├── fd: (1)-->(2-8), (5)-->(6-8), (7,8)~~>(5,6)
 ├── prune: (1-3,6-8)
 ├── reject-nulls: (5-8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(exactly-one), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(4,5), constraints=(/4: (/NULL - ]; /5: (/NULL - ]), fd=(4)==(5), (5)==(4)]
           ├── variable: x:5 [type=int]
           └── variable: r2:4 [type=int]

# FullJoin with equality between key columns. The FullJoin adds back any rows
# that are filtered out, and the equality between key columns ensures that no
# rows are duplicated. Note that both sides may be null-extended.
norm
SELECT * FROM mn FULL JOIN xysd ON m = x
----
full-join (hash)
 ├── columns: m:1(int) n:2(int) x:3(int) y:4(int) s:5(string) d:6(decimal)
 ├── key: (1,3)
 ├── fd: (1)-->(2), (2)~~>(1), (3)-->(4-6), (5,6)~~>(3,4)
 ├── prune: (2,4-6)
 ├── reject-nulls: (1-6)
 ├── interesting orderings: (+1) (+2,+1) (+3) (-5,+6,+3)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── scan mn
 │    ├── columns: m:1(int!null) n:2(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2), (2)~~>(1)
 │    ├── prune: (1,2)
 │    └── interesting orderings: (+1) (+2,+1)
 ├── scan xysd
 │    ├── columns: x:3(int!null) y:4(int) s:5(string) d:6(decimal!null)
 │    ├── key: (3)
 │    ├── fd: (3)-->(4-6), (5,6)~~>(3,4)
 │    ├── prune: (3-6)
 │    └── interesting orderings: (+3) (-5,+6,+3)
 └── filters
      └── eq [type=bool, outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]
           ├── variable: m:1 [type=int]
           └── variable: x:3 [type=int]

# Self-join case. Since the condition is equating a key column with itself,
# every row from both inputs is guaranteed to be included in the join output
# exactly once.
norm
SELECT * FROM xysd INNER JOIN xysd AS a ON xysd.x = a.x
----
inner-join (hash)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 ├── key: (5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)-->(6-8), (7,8)~~>(5,6), (1)==(5), (5)==(1)
 ├── prune: (2-4,6-8)
 ├── interesting orderings: (+1) (-3,+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 ├── scan xysd
 │    ├── columns: xysd.x:1(int!null) xysd.y:2(int) xysd.s:3(string) xysd.d:4(decimal!null)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 ├── scan a
 │    ├── columns: a.x:5(int!null) a.y:6(int) a.s:7(string) a.d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: xysd.x:1 [type=int]
           └── variable: a.x:5 [type=int]

# Case with a values cross join in the input of an InnerJoin.
norm
SELECT * FROM
fk INNER JOIN (SELECT * FROM xysd CROSS JOIN (VALUES (1), (2))) ON r1 = x
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null) column1:9(int!null)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (3)==(5), (5)==(3)
 ├── prune: (1,2,4,6-9)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── inner-join (cross)
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null) column1:9(int!null)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-9)
 │    ├── interesting orderings: (+5) (-7,+8,+5)
 │    ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 │    ├── scan xysd
 │    │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    │    ├── key: (5)
 │    │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    │    ├── prune: (5-8)
 │    │    └── interesting orderings: (+5) (-7,+8,+5)
 │    ├── values
 │    │    ├── columns: column1:9(int!null)
 │    │    ├── cardinality: [2 - 2]
 │    │    ├── prune: (9)
 │    │    ├── tuple [type=tuple{int}]
 │    │    │    └── const: 1 [type=int]
 │    │    └── tuple [type=tuple{int}]
 │    │         └── const: 2 [type=int]
 │    └── filters (true)
 └── filters
      └── eq [type=bool, outer=(3,5), constraints=(/3: (/NULL - ]; /5: (/NULL - ]), fd=(3)==(5), (5)==(3)]
           ├── variable: r1:3 [type=int]
           └── variable: x:5 [type=int]

# Case with a self-join in the input of an InnerJoin.
norm
SELECT * FROM fk
INNER JOIN (SELECT * FROM xysd INNER JOIN xysd AS a ON xysd.x = a.x) f(x) ON r1 = f.x
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int) s:7(string) d:8(decimal!null) x:9(int!null) y:10(int) s:11(string) d:12(decimal!null)
 ├── key: (1)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (9)-->(10-12), (11,12)~~>(9,10), (5)==(3,9), (9)==(3,5), (3)==(5,9)
 ├── prune: (1,2,4,6-8,10-12)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5) (+9) (-11,+12,+9)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── inner-join (hash)
 │    ├── columns: xysd.x:5(int!null) xysd.y:6(int) xysd.s:7(string) xysd.d:8(decimal!null) a.x:9(int!null) a.y:10(int) a.s:11(string) a.d:12(decimal!null)
 │    ├── key: (9)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6), (9)-->(10-12), (11,12)~~>(9,10), (5)==(9), (9)==(5)
 │    ├── prune: (6-8,10-12)
 │    ├── interesting orderings: (+5) (-7,+8,+5) (+9) (-11,+12,+9)
 │    ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
 │    ├── scan xysd
 │    │    ├── columns: xysd.x:5(int!null) xysd.y:6(int) xysd.s:7(string) xysd.d:8(decimal!null)
 │    │    ├── key: (5)
 │    │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    │    ├── prune: (5-8)
 │    │    └── interesting orderings: (+5) (-7,+8,+5)
 │    ├── scan a
 │    │    ├── columns: a.x:9(int!null) a.y:10(int) a.s:11(string) a.d:12(decimal!null)
 │    │    ├── key: (9)
 │    │    ├── fd: (9)-->(10-12), (11,12)~~>(9,10)
 │    │    ├── prune: (9-12)
 │    │    └── interesting orderings: (+9) (-11,+12,+9)
 │    └── filters
 │         └── eq [type=bool, outer=(5,9), constraints=(/5: (/NULL - ]; /9: (/NULL - ]), fd=(5)==(9), (9)==(5)]
 │              ├── variable: xysd.x:5 [type=int]
 │              └── variable: a.x:9 [type=int]
 └── filters
      └── eq [type=bool, outer=(3,5), constraints=(/3: (/NULL - ]; /5: (/NULL - ]), fd=(3)==(5), (5)==(3)]
           ├── variable: r1:3 [type=int]
           └── variable: xysd.x:5 [type=int]

# Case with an equality with a synthesized column.
norm
SELECT * FROM mn LEFT JOIN xysd ON y = (n * 2)
----
project
 ├── columns: m:1(int!null) n:2(int) x:3(int) y:4(int) s:5(string) d:6(decimal)
 ├── key: (1,3)
 ├── fd: (1)-->(2), (2)~~>(1), (3)-->(4-6), (5,6)~~>(3,4)
 ├── prune: (1-6)
 ├── reject-nulls: (3-6)
 ├── interesting orderings: (+1) (+2,+1) (+3) (-5,+6,+3)
 └── left-join (hash)
      ├── columns: m:1(int!null) n:2(int) x:3(int) y:4(int) s:5(string) d:6(decimal) column7:7(int)
      ├── key: (1,3)
      ├── fd: (1)-->(2), (2)~~>(1), (2)-->(7), (3)-->(4-6), (5,6)~~>(3,4)
      ├── prune: (1-3,5,6)
      ├── reject-nulls: (3-6)
      ├── interesting orderings: (+1) (+2,+1) (+3) (-5,+6,+3)
      ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
      ├── project
      │    ├── columns: column7:7(int) m:1(int!null) n:2(int)
      │    ├── key: (1)
      │    ├── fd: (1)-->(2), (2)~~>(1), (2)-->(7)
      │    ├── prune: (1,2,7)
      │    ├── interesting orderings: (+1) (+2,+1)
      │    ├── scan mn
      │    │    ├── columns: m:1(int!null) n:2(int)
      │    │    ├── key: (1)
      │    │    ├── fd: (1)-->(2), (2)~~>(1)
      │    │    ├── prune: (1,2)
      │    │    └── interesting orderings: (+1) (+2,+1)
      │    └── projections
      │         └── mult [as=column7:7, type=int, outer=(2)]
      │              ├── variable: n:2 [type=int]
      │              └── const: 2 [type=int]
      ├── scan xysd
      │    ├── columns: x:3(int!null) y:4(int) s:5(string) d:6(decimal!null)
      │    ├── key: (3)
      │    ├── fd: (3)-->(4-6), (5,6)~~>(3,4)
      │    ├── prune: (3-6)
      │    └── interesting orderings: (+3) (-5,+6,+3)
      └── filters
           └── eq [type=bool, outer=(4,7), constraints=(/4: (/NULL - ]; /7: (/NULL - ]), fd=(4)==(7), (7)==(4)]
                ├── variable: column7:7 [type=int]
                └── variable: y:4 [type=int]

# Case with columns that don't come from base tables.
norm
SELECT * FROM (SELECT * FROM uv UNION (SELECT * FROM uv)) f(v1, v2) INNER JOIN xysd ON v2 = x
----
inner-join (hash)
 ├── columns: v1:7(int) v2:8(int!null) x:9(int!null) y:10(int) s:11(string) d:12(decimal!null)
 ├── key: (7,9)
 ├── fd: (9)-->(10-12), (11,12)~~>(9,10), (8)==(9), (9)==(8)
 ├── prune: (10-12)
 ├── interesting orderings: (+9) (-11,+12,+9)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 ├── union
 │    ├── columns: u:7(int) v:8(int!null)
 │    ├── left columns: uv.u:1(int) uv.v:2(int)
 │    ├── right columns: uv.u:4(int) uv.v:5(int)
 │    ├── key: (7,8)
 │    ├── scan uv
 │    │    ├── columns: uv.u:1(int) uv.v:2(int!null)
 │    │    └── prune: (1,2)
 │    └── scan uv
 │         ├── columns: uv.u:4(int) uv.v:5(int!null)
 │         └── prune: (4,5)
 ├── scan xysd
 │    ├── columns: x:9(int!null) y:10(int) s:11(string) d:12(decimal!null)
 │    ├── key: (9)
 │    ├── fd: (9)-->(10-12), (11,12)~~>(9,10)
 │    ├── prune: (9-12)
 │    └── interesting orderings: (+9) (-11,+12,+9)
 └── filters
      └── eq [type=bool, outer=(8,9), constraints=(/8: (/NULL - ]; /9: (/NULL - ]), fd=(8)==(9), (9)==(8)]
           ├── variable: v:8 [type=int]
           └── variable: x:9 [type=int]

# Self-join case with different columns.
norm
SELECT * FROM xysd INNER JOIN xysd AS a ON xysd.x = a.y
----
inner-join (hash)
 ├── columns: x:1(int!null) y:2(int) s:3(string) d:4(decimal!null) x:5(int!null) y:6(int!null) s:7(string) d:8(decimal!null)
 ├── key: (5)
 ├── fd: (1)-->(2-4), (3,4)~~>(1,2), (5)-->(6-8), (7,8)~~>(5,6), (1)==(6), (6)==(1)
 ├── prune: (2-5,7,8)
 ├── interesting orderings: (+1) (-3,+4,+1) (+5) (-7,+8,+5)
 ├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)
 ├── scan xysd
 │    ├── columns: xysd.x:1(int!null) xysd.y:2(int) xysd.s:3(string) xysd.d:4(decimal!null)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3,4)~~>(1,2)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (-3,+4,+1)
 ├── scan a
 │    ├── columns: a.x:5(int!null) a.y:6(int) a.s:7(string) a.d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
           ├── variable: xysd.x:1 [type=int]
           └── variable: a.y:6 [type=int]

# Case with an equality between a not-null foreign key and an unreferenced
# column.
norm
SELECT * FROM fk INNER JOIN xysd ON r1 = y
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) x:5(int!null) y:6(int!null) s:7(string) d:8(decimal!null)
 ├── key: (1,5)
 ├── fd: (1)-->(2-4), (5)-->(6-8), (7,8)~~>(5,6), (3)==(6), (6)==(3)
 ├── prune: (1,2,4,5,7,8)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (-7,+8,+5)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan xysd
 │    ├── columns: x:5(int!null) y:6(int) s:7(string) d:8(decimal!null)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6-8), (7,8)~~>(5,6)
 │    ├── prune: (5-8)
 │    └── interesting orderings: (+5) (-7,+8,+5)
 └── filters
      └── eq [type=bool, outer=(3,6), constraints=(/3: (/NULL - ]; /6: (/NULL - ]), fd=(3)==(6), (6)==(3)]
           ├── variable: r1:3 [type=int]
           └── variable: y:6 [type=int]

# Case where left table has a foreign key that references a table that isn't
# from the right input.
norm
SELECT * FROM fk INNER JOIN mn ON k = m
----
inner-join (hash)
 ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int) m:5(int!null) n:6(int)
 ├── key: (5)
 ├── fd: (1)-->(2-4), (5)-->(6), (6)~~>(5), (1)==(5), (5)==(1)
 ├── prune: (2-4,6)
 ├── interesting orderings: (+1) (+3,+1) (+4,+1) (+5) (+6,+5)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-one)
 ├── scan fk
 │    ├── columns: k:1(int!null) v:2(int) r1:3(int!null) r2:4(int)
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4)
 │    ├── prune: (1-4)
 │    └── interesting orderings: (+1) (+3,+1) (+4,+1)
 ├── scan mn
 │    ├── columns: m:5(int!null) n:6(int)
 │    ├── key: (5)
 │    ├── fd: (5)-->(6), (6)~~>(5)
 │    ├── prune: (5,6)
 │    └── interesting orderings: (+5) (+6,+5)
 └── filters
      └── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
           ├── variable: k:1 [type=int]
           └── variable: m:5 [type=int]

# Case with a match-simple foreign key with one nullable column.
norm
SELECT *
FROM ref
INNER JOIN abc 
ON (r1, r2, r3) = (a, b, c)
----
inner-join (hash)
 ├── columns: r1:1(int!null) r2:2(int!null) r3:3(int!null) a:5(int!null) b:6(int!null) c:7(int!null)
 ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
 ├── interesting orderings: (+1,+2,+3) (+5,+6,+7)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 ├── scan ref
 │    ├── columns: r1:1(int!null) r2:2(int) r3:3(int!null)
 │    ├── prune: (1-3)
 │    └── interesting orderings: (+1,+2,+3)
 ├── scan abc
 │    ├── columns: a:5(int!null) b:6(int!null) c:7(int!null)
 │    ├── key: (5-7)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+5,+6,+7)
 └── filters
      ├── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      │    ├── variable: r1:1 [type=int]
      │    └── variable: a:5 [type=int]
      ├── eq [type=bool, outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]
      │    ├── variable: r2:2 [type=int]
      │    └── variable: b:6 [type=int]
      └── eq [type=bool, outer=(3,7), constraints=(/3: (/NULL - ]; /7: (/NULL - ]), fd=(3)==(7), (7)==(3)]
           ├── variable: r3:3 [type=int]
           └── variable: c:7 [type=int]

# Case with a not-null multi-column foreign key.
norm
SELECT *
FROM (SELECT r1, r2, r3 FROM ref WHERE r2 IS NOT NULL)
INNER JOIN abc
ON (r1, r2, r3) = (a, b, c)
----
inner-join (hash)
 ├── columns: r1:1(int!null) r2:2(int!null) r3:3(int!null) a:5(int!null) b:6(int!null) c:7(int!null)
 ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
 ├── interesting orderings: (+1,+2,+3) (+5,+6,+7)
 ├── multiplicity: left-rows(exactly-one), right-rows(zero-or-more)
 ├── select
 │    ├── columns: r1:1(int!null) r2:2(int!null) r3:3(int!null)
 │    ├── prune: (1,3)
 │    ├── interesting orderings: (+1,+2,+3)
 │    ├── scan ref
 │    │    ├── columns: r1:1(int!null) r2:2(int) r3:3(int!null)
 │    │    ├── prune: (1-3)
 │    │    └── interesting orderings: (+1,+2,+3)
 │    └── filters
 │         └── is-not [type=bool, outer=(2), constraints=(/2: (/NULL - ]; tight)]
 │              ├── variable: r2:2 [type=int]
 │              └── null [type=unknown]
 ├── scan abc
 │    ├── columns: a:5(int!null) b:6(int!null) c:7(int!null)
 │    ├── key: (5-7)
 │    ├── prune: (5-7)
 │    └── interesting orderings: (+5,+6,+7)
 └── filters
      ├── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      │    ├── variable: r1:1 [type=int]
      │    └── variable: a:5 [type=int]
      ├── eq [type=bool, outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]
      │    ├── variable: r2:2 [type=int]
      │    └── variable: b:6 [type=int]
      └── eq [type=bool, outer=(3,7), constraints=(/3: (/NULL - ]; /7: (/NULL - ]), fd=(3)==(7), (7)==(3)]
           ├── variable: r3:3 [type=int]
           └── variable: c:7 [type=int]

exec-ddl
CREATE TABLE trade_type (tt_id INT PRIMARY KEY)
----

exec-ddl
CREATE TABLE exchange (ex_id INT PRIMARY KEY)
----

exec-ddl
CREATE TABLE status_type (st_id INT PRIMARY KEY)
----

exec-ddl
CREATE TABLE security (
    s_symb  INT PRIMARY KEY,
    s_st_id INT NOT NULL,
    s_ex_id INT NOT NULL,
    FOREIGN KEY (s_st_id) REFERENCES status_type (st_id),
    FOREIGN KEY (s_ex_id) REFERENCES exchange (ex_id)
)
----

exec-ddl
CREATE TABLE trade (
    t_st_id  INT NOT NULL,
    t_tt_id  INT NOT NULL,
    t_s_symb INT NOT NULL,
    FOREIGN KEY (t_st_id) REFERENCES status_type (st_id),
    FOREIGN KEY (t_tt_id) REFERENCES trade_type (tt_id),
    FOREIGN KEY (t_s_symb) REFERENCES security (s_symb)
)
----

# Regression test for #49821.
opt format=show-ruleprops
SELECT *
FROM trade, status_type, trade_type, security, exchange
WHERE st_id = t_st_id
  AND tt_id = t_tt_id
  AND s_symb = t_s_symb
  AND ex_id = s_ex_id
LIMIT 50;
----
limit
 ├── columns: t_st_id:1(int!null) t_tt_id:2(int!null) t_s_symb:3(int!null) st_id:5(int!null) tt_id:6(int!null) s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null) ex_id:10(int!null)
 ├── cardinality: [0 - 50]
 ├── fd: (7)-->(8,9), (9)==(10), (10)==(9), (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
 ├── prune: (8)
 ├── interesting orderings: (+5) (+6) (+7) (+8,+7) (+9,+7) (+10) (+1) (+2) (+3)
 ├── inner-join (hash)
 │    ├── columns: t_st_id:1(int!null) t_tt_id:2(int!null) t_s_symb:3(int!null) st_id:5(int!null) tt_id:6(int!null) s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null) ex_id:10(int!null)
 │    ├── fd: (7)-->(8,9), (9)==(10), (10)==(9), (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
 │    ├── limit hint: 50.00
 │    ├── prune: (8)
 │    ├── interesting orderings: (+5) (+6) (+7) (+8,+7) (+9,+7) (+10) (+1) (+2) (+3)
 │    ├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)
 │    ├── inner-join (cross)
 │    │    ├── columns: st_id:5(int!null) tt_id:6(int!null) s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null) ex_id:10(int!null)
 │    │    ├── key: (5-7)
 │    │    ├── fd: (7)-->(8,9), (9)==(10), (10)==(9)
 │    │    ├── prune: (5-8)
 │    │    ├── interesting orderings: (+5) (+6) (+7) (+8,+7) (+9,+7) (+10)
 │    │    ├── join-size: 4
 │    │    ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-more)
 │    │    ├── inner-join (cross)
 │    │    │    ├── columns: tt_id:6(int!null) s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null) ex_id:10(int!null)
 │    │    │    ├── key: (6,7)
 │    │    │    ├── fd: (7)-->(8,9), (9)==(10), (10)==(9)
 │    │    │    ├── prune: (6-8)
 │    │    │    ├── interesting orderings: (+6) (+7) (+8,+7) (+9,+7) (+10)
 │    │    │    ├── join-size: 3
 │    │    │    ├── scan trade_type
 │    │    │    │    ├── columns: tt_id:6(int!null)
 │    │    │    │    ├── key: (6)
 │    │    │    │    ├── prune: (6)
 │    │    │    │    └── interesting orderings: (+6)
 │    │    │    ├── inner-join (hash)
 │    │    │    │    ├── columns: s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null) ex_id:10(int!null)
 │    │    │    │    ├── key: (7)
 │    │    │    │    ├── fd: (7)-->(8,9), (9)==(10), (10)==(9)
 │    │    │    │    ├── prune: (7,8)
 │    │    │    │    ├── interesting orderings: (+7) (+8,+7) (+9,+7) (+10)
 │    │    │    │    ├── join-size: 2
 │    │    │    │    ├── multiplicity: left-rows(exactly-one), right-rows(zero-or-more)
 │    │    │    │    ├── scan security
 │    │    │    │    │    ├── columns: s_symb:7(int!null) s_st_id:8(int!null) s_ex_id:9(int!null)
 │    │    │    │    │    ├── key: (7)
 │    │    │    │    │    ├── fd: (7)-->(8,9)
 │    │    │    │    │    ├── prune: (7-9)
 │    │    │    │    │    └── interesting orderings: (+7) (+8,+7) (+9,+7)
 │    │    │    │    ├── scan exchange
 │    │    │    │    │    ├── columns: ex_id:10(int!null)
 │    │    │    │    │    ├── key: (10)
 │    │    │    │    │    ├── prune: (10)
 │    │    │    │    │    └── interesting orderings: (+10)
 │    │    │    │    └── filters
 │    │    │    │         └── eq [type=bool, outer=(9,10), constraints=(/9: (/NULL - ]; /10: (/NULL - ]), fd=(9)==(10), (10)==(9)]
 │    │    │    │              ├── variable: ex_id:10 [type=int]
 │    │    │    │              └── variable: s_ex_id:9 [type=int]
 │    │    │    └── filters (true)
 │    │    ├── scan status_type
 │    │    │    ├── columns: st_id:5(int!null)
 │    │    │    ├── key: (5)
 │    │    │    ├── prune: (5)
 │    │    │    └── interesting orderings: (+5)
 │    │    └── filters (true)
 │    ├── scan trade
 │    │    ├── columns: t_st_id:1(int!null) t_tt_id:2(int!null) t_s_symb:3(int!null)
 │    │    ├── prune: (1-3)
 │    │    └── interesting orderings: (+1) (+2) (+3)
 │    └── filters
 │         ├── eq [type=bool, outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
 │         │    ├── variable: st_id:5 [type=int]
 │         │    └── variable: t_st_id:1 [type=int]
 │         ├── eq [type=bool, outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]
 │         │    ├── variable: tt_id:6 [type=int]
 │         │    └── variable: t_tt_id:2 [type=int]
 │         └── eq [type=bool, outer=(3,7), constraints=(/3: (/NULL - ]; /7: (/NULL - ]), fd=(3)==(7), (7)==(3)]
 │              ├── variable: s_symb:7 [type=int]
 │              └── variable: t_s_symb:3 [type=int]
 └── const: 50 [type=int]