join

exec-ddl
CREATE TABLE abc
(
    a INT,
    b INT,
    c INT,
    INDEX ab (a,b) STORING (c),
    INDEX bc (b,c) STORING (a)
)
----

exec-ddl
CREATE TABLE stu
(
    s INT,
    t INT,
    u INT,
    PRIMARY KEY (s,t,u),
    INDEX uts (u,t,s)
)
----

exec-ddl
CREATE TABLE xyz
(
    x INT,
    y INT,
    z INT,
    INDEX xy (x,y) STORING (z),
    INDEX yz (y,z) STORING (x)
)
----

exec-ddl
CREATE TABLE pqr
(
    p INT PRIMARY KEY,
    q INT,
    r INT,
    s STRING,
    t STRING,
    INDEX q (q),
    INDEX r (r),
    INDEX s (s) STORING (r),
    INDEX rs (r,s),
    INDEX ts (t,s)
)
----

exec-ddl
CREATE TABLE zz (
    a INT8 PRIMARY KEY,
    b INT8 NULL,
    c INT8 NULL,
    INDEX idx_b (b ASC),
    CONSTRAINT idx_c UNIQUE (c)
)
----

exec-ddl
CREATE TABLE zz_redundant (
    a INT8 PRIMARY KEY,
    b INT8 NULL,
    c INT8 NULL,
    INDEX idx_u (b ASC, c ASC),
    INDEX idx_v (b ASC, c ASC)
)
----

exec-ddl
CREATE TABLE large (m INT, n INT)
----

exec-ddl
CREATE TABLE medium (m INT, n INT)
----

exec-ddl
CREATE TABLE small (m INT, n INT)
----

exec-ddl
ALTER TABLE large INJECT STATISTICS '[
  {
    "columns": ["m"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 100000000000,
    "distinct_count": 100000000
  }
]'
----

exec-ddl
ALTER TABLE medium INJECT STATISTICS '[
  {
    "columns": ["m"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 100000,
    "distinct_count": 1000
  }
]'
----

exec-ddl
ALTER TABLE small INJECT STATISTICS '[
  {
    "columns": ["m"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 10,
    "distinct_count": 6
  }
]'
----

# --------------------------------------------------
# ReorderJoins
# --------------------------------------------------

exec-ddl
ALTER TABLE abc INJECT STATISTICS '[
  {
    "columns": ["a"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 1000,
    "distinct_count": 1000
  }
]'
----

exec-ddl
ALTER TABLE stu INJECT STATISTICS '[
  {
    "columns": ["s"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 10000,
    "distinct_count": 1000
  }
]'
----

exec-ddl
ALTER TABLE xyz INJECT STATISTICS '[
  {
    "columns": ["x"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 1000,
    "distinct_count": 1000
  }
]'
----

# Check that the equality condition abc.a = xyz.x is synthesized.
opt expect=ReorderJoins
SELECT * FROM abc, stu, xyz WHERE abc.a=stu.s AND stu.s=xyz.x
----
inner-join (merge)
 ├── columns: a:1!null b:2 c:3 s:6!null t:7!null u:8!null x:10!null y:11 z:12
 ├── left ordering: +6
 ├── right ordering: +10
 ├── fd: (6)==(1,10), (10)==(1,6), (1)==(6,10)
 ├── scan stu
 │    ├── columns: s:6!null t:7!null u:8!null
 │    ├── key: (6-8)
 │    └── ordering: +6
 ├── inner-join (merge)
 │    ├── columns: a:1!null b:2 c:3 x:10!null y:11 z:12
 │    ├── left ordering: +1
 │    ├── right ordering: +10
 │    ├── fd: (1)==(10), (10)==(1)
 │    ├── ordering: +(1|10) [actual: +1]
 │    ├── scan abc@ab
 │    │    ├── columns: a:1 b:2 c:3
 │    │    └── ordering: +1
 │    ├── scan xyz@xy
 │    │    ├── columns: x:10 y:11 z:12
 │    │    └── ordering: +10
 │    └── filters (true)
 └── filters (true)

memo expect=ReorderJoins
SELECT * FROM abc, stu, xyz WHERE abc.a=stu.s AND stu.s=xyz.x
----
memo (optimized, ~36KB, required=[presentation: a:1,b:2,c:3,s:6,t:7,u:8,x:10,y:11,z:12])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (inner-join G5 G6 G7) (inner-join G6 G5 G7) (inner-join G8 G9 G7) (inner-join G9 G8 G7) (merge-join G2 G3 G10 inner-join,+1,+6) (merge-join G3 G2 G10 inner-join,+6,+1) (lookup-join G3 G10 abc@ab,keyCols=[6],outCols=(1-3,6-8,10-12)) (merge-join G5 G6 G10 inner-join,+6,+10) (merge-join G6 G5 G10 inner-join,+10,+6) (lookup-join G6 G10 stu,keyCols=[10],outCols=(1-3,6-8,10-12)) (merge-join G8 G9 G10 inner-join,+6,+10) (lookup-join G8 G10 xyz@xy,keyCols=[6],outCols=(1-3,6-8,10-12)) (merge-join G9 G8 G10 inner-join,+10,+6)
 │    └── [presentation: a:1,b:2,c:3,s:6,t:7,u:8,x:10,y:11,z:12]
 │         ├── best: (merge-join G5="[ordering: +6]" G6="[ordering: +(1|10)]" G10 inner-join,+6,+10)
 │         └── cost: 12992.08
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (inner-join G5 G9 G7) (inner-join G9 G5 G7) (merge-join G5 G9 G10 inner-join,+6,+10) (lookup-join G5 G10 xyz@xy,keyCols=[6],outCols=(6-8,10-12)) (merge-join G9 G5 G10 inner-join,+10,+6) (lookup-join G9 G10 stu,keyCols=[10],outCols=(6-8,10-12))
 │    ├── [ordering: +(6|10)]
 │    │    ├── best: (merge-join G5="[ordering: +6]" G9="[ordering: +10]" G10 inner-join,+6,+10)
 │    │    └── cost: 11888.05
 │    └── []
 │         ├── best: (merge-join G5="[ordering: +6]" G9="[ordering: +10]" G10 inner-join,+6,+10)
 │         └── cost: 11888.05
 ├── G4: (filters G11)
 ├── G5: (scan stu,cols=(6-8)) (scan stu@uts,cols=(6-8))
 │    ├── [ordering: +6]
 │    │    ├── best: (scan stu,cols=(6-8))
 │    │    └── cost: 10604.02
 │    └── []
 │         ├── best: (scan stu,cols=(6-8))
 │         └── cost: 10604.02
 ├── G6: (inner-join G2 G9 G12) (inner-join G9 G2 G12) (merge-join G2 G9 G10 inner-join,+1,+10) (lookup-join G2 G10 xyz@xy,keyCols=[1],outCols=(1-3,10-12)) (merge-join G9 G2 G10 inner-join,+10,+1) (lookup-join G9 G10 abc@ab,keyCols=[10],outCols=(1-3,10-12))
 │    ├── [ordering: +(1|10)]
 │    │    ├── best: (merge-join G2="[ordering: +1]" G9="[ordering: +10]" G10 inner-join,+1,+10)
 │    │    └── cost: 2178.05
 │    └── []
 │         ├── best: (merge-join G2="[ordering: +1]" G9="[ordering: +10]" G10 inner-join,+1,+10)
 │         └── cost: 2178.05
 ├── G7: (filters G13)
 ├── G8: (inner-join G2 G5 G4) (inner-join G5 G2 G4) (merge-join G2 G5 G10 inner-join,+1,+6) (lookup-join G2 G10 stu,keyCols=[1],outCols=(1-3,6-8)) (merge-join G5 G2 G10 inner-join,+6,+1) (lookup-join G5 G10 abc@ab,keyCols=[6],outCols=(1-3,6-8))
 │    ├── [ordering: +(1|6)]
 │    │    ├── best: (merge-join G2="[ordering: +1]" G5="[ordering: +6]" G10 inner-join,+1,+6)
 │    │    └── cost: 11888.05
 │    └── []
 │         ├── best: (merge-join G2="[ordering: +1]" G5="[ordering: +6]" G10 inner-join,+1,+6)
 │         └── cost: 11888.05
 ├── G9: (scan xyz,cols=(10-12)) (scan xyz@xy,cols=(10-12)) (scan xyz@yz,cols=(10-12))
 │    ├── [ordering: +10]
 │    │    ├── best: (scan xyz@xy,cols=(10-12))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan xyz,cols=(10-12))
 │         └── cost: 1074.02
 ├── G10: (filters)
 ├── G11: (eq G14 G15)
 ├── G12: (filters G16)
 ├── G13: (eq G15 G17)
 ├── G14: (variable a)
 ├── G15: (variable s)
 ├── G16: (eq G14 G17)
 └── G17: (variable x)

# Regression test for #36226.
exec-ddl
CREATE TABLE parent1 (pid1 INT PRIMARY KEY, pa1 INT)
----

exec-ddl
CREATE TABLE child1 (
  pid1 INT,
  cid1 INT,
  ca1 INT,
  PRIMARY KEY(pid1, cid1)
)
INTERLEAVE IN PARENT parent1 (pid1)
----

exec-ddl
CREATE TABLE grandchild1 (
  pid1 INT,
  cid1 INT,
  gcid1 INT,
  gca1 INT,
  PRIMARY KEY(pid1, cid1, gcid1)
)
INTERLEAVE IN PARENT child1 (pid1, cid1)
----

opt expect=ReorderJoins join-limit=4
SELECT * FROM grandchild1
JOIN child1 USING (pid1, cid1)
JOIN parent1 USING (pid1)
ORDER BY pid1
----
project
 ├── columns: pid1:1!null cid1:2!null gcid1:3!null gca1:4 ca1:8 pa1:11
 ├── key: (1-3)
 ├── fd: (1-3)-->(4), (1,2)-->(8), (1)-->(11)
 ├── ordering: +1
 └── inner-join (lookup parent1)
      ├── columns: grandchild1.pid1:1!null grandchild1.cid1:2!null gcid1:3!null gca1:4 child1.pid1:6!null child1.cid1:7!null ca1:8 parent1.pid1:10!null pa1:11
      ├── key columns: [1] = [10]
      ├── lookup columns are key
      ├── key: (3,7,10)
      ├── fd: (1-3)-->(4), (6,7)-->(8), (1)==(6,10), (6)==(1,10), (2)==(7), (7)==(2), (10)-->(11), (10)==(1,6)
      ├── ordering: +(1|6|10) [actual: +1]
      ├── inner-join (merge)
      │    ├── columns: grandchild1.pid1:1!null grandchild1.cid1:2!null gcid1:3!null gca1:4 child1.pid1:6!null child1.cid1:7!null ca1:8
      │    ├── left ordering: +1,+2
      │    ├── right ordering: +6,+7
      │    ├── key: (3,6,7)
      │    ├── fd: (1-3)-->(4), (6,7)-->(8), (1)==(6), (6)==(1), (2)==(7), (7)==(2)
      │    ├── ordering: +(1|6) [actual: +1]
      │    ├── scan grandchild1
      │    │    ├── columns: grandchild1.pid1:1!null grandchild1.cid1:2!null gcid1:3!null gca1:4
      │    │    ├── key: (1-3)
      │    │    ├── fd: (1-3)-->(4)
      │    │    └── ordering: +1,+2
      │    ├── scan child1
      │    │    ├── columns: child1.pid1:6!null child1.cid1:7!null ca1:8
      │    │    ├── key: (6,7)
      │    │    ├── fd: (6,7)-->(8)
      │    │    └── ordering: +6,+7
      │    └── filters (true)
      └── filters (true)

memo expect=ReorderJoins join-limit=4
SELECT * FROM grandchild1
JOIN child1 USING (pid1, cid1)
JOIN parent1 USING (pid1)
ORDER BY pid1
----
memo (optimized, ~34KB, required=[presentation: pid1:1,cid1:2,gcid1:3,gca1:4,ca1:8,pa1:11] [ordering: +1])
 ├── G1: (project G2 G3 pid1 cid1 gcid1 gca1 ca1 pa1)
 │    ├── [presentation: pid1:1,cid1:2,gcid1:3,gca1:4,ca1:8,pa1:11] [ordering: +1]
 │    │    ├── best: (project G2="[ordering: +(1|6|10)]" G3 pid1 cid1 gcid1 gca1 ca1 pa1)
 │    │    └── cost: 2775.07
 │    └── []
 │         ├── best: (project G2 G3 pid1 cid1 gcid1 gca1 ca1 pa1)
 │         └── cost: 2775.07
 ├── G2: (inner-join G4 G5 G6) (inner-join G7 G8 G9) (inner-join G8 G7 G9) (inner-join G10 G11 G9) (inner-join G11 G10 G9) (inner-join G5 G4 G6) (merge-join G4 G5 G12 inner-join,+1,+10) (lookup-join G4 G12 parent1,keyCols=[1],outCols=(1-4,6-8,10,11)) (merge-join G7 G8 G12 inner-join,+1,+2,+6,+7) (merge-join G8 G7 G12 inner-join,+6,+7,+1,+2) (lookup-join G8 G12 grandchild1,keyCols=[6 7],outCols=(1-4,6-8,10,11)) (merge-join G10 G11 G12 inner-join,+6,+7,+1,+2) (merge-join G11 G10 G12 inner-join,+1,+2,+6,+7) (lookup-join G11 G12 child1,keyCols=[1 2],outCols=(1-4,6-8,10,11)) (merge-join G5 G4 G12 inner-join,+10,+1)
 │    ├── [ordering: +(1|6|10)]
 │    │    ├── best: (lookup-join G4="[ordering: +(1|6)]" G12 parent1,keyCols=[1],outCols=(1-4,6-8,10,11))
 │    │    └── cost: 2774.06
 │    └── []
 │         ├── best: (lookup-join G4 G12 parent1,keyCols=[1],outCols=(1-4,6-8,10,11))
 │         └── cost: 2774.06
 ├── G3: (projections)
 ├── G4: (inner-join G7 G10 G9) (inner-join G10 G7 G9) (merge-join G7 G10 G12 inner-join,+1,+2,+6,+7) (lookup-join G7 G12 child1,keyCols=[1 2],outCols=(1-4,6-8)) (merge-join G10 G7 G12 inner-join,+6,+7,+1,+2) (lookup-join G10 G12 grandchild1,keyCols=[6 7],outCols=(1-4,6-8))
 │    ├── [ordering: +(1|6)]
 │    │    ├── best: (merge-join G7="[ordering: +1,+2]" G10="[ordering: +6,+7]" G12 inner-join,+1,+2,+6,+7)
 │    │    └── cost: 2169.05
 │    └── []
 │         ├── best: (merge-join G7="[ordering: +1,+2]" G10="[ordering: +6,+7]" G12 inner-join,+1,+2,+6,+7)
 │         └── cost: 2169.05
 ├── G5: (scan parent1,cols=(10,11))
 │    ├── [ordering: +10]
 │    │    ├── best: (scan parent1,cols=(10,11))
 │    │    └── cost: 1044.02
 │    └── []
 │         ├── best: (scan parent1,cols=(10,11))
 │         └── cost: 1044.02
 ├── G6: (filters G13)
 ├── G7: (scan grandchild1,cols=(1-4))
 │    ├── [ordering: +1,+2]
 │    │    ├── best: (scan grandchild1,cols=(1-4))
 │    │    └── cost: 1084.02
 │    ├── [ordering: +1]
 │    │    ├── best: (scan grandchild1,cols=(1-4))
 │    │    └── cost: 1084.02
 │    └── []
 │         ├── best: (scan grandchild1,cols=(1-4))
 │         └── cost: 1084.02
 ├── G8: (inner-join G10 G5 G14) (inner-join G5 G10 G14) (merge-join G10 G5 G12 inner-join,+6,+10) (lookup-join G10 G12 parent1,keyCols=[6],outCols=(6-8,10,11)) (merge-join G5 G10 G12 inner-join,+10,+6) (lookup-join G5 G12 child1,keyCols=[10],outCols=(6-8,10,11))
 │    ├── [ordering: +(6|10),+7]
 │    │    ├── best: (sort G8)
 │    │    └── cost: 2368.34
 │    ├── [ordering: +(6|10)]
 │    │    ├── best: (merge-join G10="[ordering: +6]" G5="[ordering: +10]" G12 inner-join,+6,+10)
 │    │    └── cost: 2138.05
 │    └── []
 │         ├── best: (merge-join G10="[ordering: +6]" G5="[ordering: +10]" G12 inner-join,+6,+10)
 │         └── cost: 2138.05
 ├── G9: (filters G15 G16)
 ├── G10: (scan child1,cols=(6-8))
 │    ├── [ordering: +6,+7]
 │    │    ├── best: (scan child1,cols=(6-8))
 │    │    └── cost: 1064.02
 │    ├── [ordering: +6]
 │    │    ├── best: (scan child1,cols=(6-8))
 │    │    └── cost: 1064.02
 │    └── []
 │         ├── best: (scan child1,cols=(6-8))
 │         └── cost: 1064.02
 ├── G11: (inner-join G7 G5 G6) (inner-join G5 G7 G6) (merge-join G7 G5 G12 inner-join,+1,+10) (lookup-join G7 G12 parent1,keyCols=[1],outCols=(1-4,10,11)) (merge-join G5 G7 G12 inner-join,+10,+1) (lookup-join G5 G12 grandchild1,keyCols=[10],outCols=(1-4,10,11))
 │    ├── [ordering: +(1|10),+2]
 │    │    ├── best: (sort G11)
 │    │    └── cost: 2388.34
 │    ├── [ordering: +(1|10)]
 │    │    ├── best: (merge-join G7="[ordering: +1]" G5="[ordering: +10]" G12 inner-join,+1,+10)
 │    │    └── cost: 2158.05
 │    └── []
 │         ├── best: (merge-join G7="[ordering: +1]" G5="[ordering: +10]" G12 inner-join,+1,+10)
 │         └── cost: 2158.05
 ├── G12: (filters)
 ├── G13: (eq G17 G18)
 ├── G14: (filters G19)
 ├── G15: (eq G17 G20)
 ├── G16: (eq G21 G22)
 ├── G17: (variable grandchild1.pid1)
 ├── G18: (variable parent1.pid1)
 ├── G19: (eq G20 G18)
 ├── G20: (variable child1.pid1)
 ├── G21: (variable grandchild1.cid1)
 └── G22: (variable child1.cid1)

# Cross joins are not reordered apart from commutation.
memo
SELECT * FROM abc, stu, xyz, pqr WHERE a = 1
----
memo (optimized, ~24KB, required=[presentation: a:1,b:2,c:3,s:6,t:7,u:8,x:10,y:11,z:12,p:15,q:16,r:17,s:18,t:19])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4)
 │    └── [presentation: a:1,b:2,c:3,s:6,t:7,u:8,x:10,y:11,z:12,p:15,q:16,r:17,s:18,t:19]
 │         ├── best: (inner-join G3 G2 G4)
 │         └── cost: 325035492.19
 ├── G2: (select G5 G6) (scan abc@ab,cols=(1-3),constrained)
 │    └── []
 │         ├── best: (scan abc@ab,cols=(1-3),constrained)
 │         └── cost: 5.08
 ├── G3: (inner-join G7 G8 G4) (inner-join G8 G7 G4)
 │    └── []
 │         ├── best: (inner-join G8 G7 G4)
 │         └── cost: 100035487.08
 ├── G4: (filters)
 ├── G5: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G6: (filters G9)
 ├── G7: (scan stu,cols=(6-8)) (scan stu@uts,cols=(6-8))
 │    └── []
 │         ├── best: (scan stu,cols=(6-8))
 │         └── cost: 10604.02
 ├── G8: (inner-join G10 G11 G4) (inner-join G11 G10 G4)
 │    └── []
 │         ├── best: (inner-join G10 G11 G4)
 │         └── cost: 12208.05
 ├── G9: (eq G12 G13)
 ├── G10: (scan xyz,cols=(10-12)) (scan xyz@xy,cols=(10-12)) (scan xyz@yz,cols=(10-12))
 │    └── []
 │         ├── best: (scan xyz,cols=(10-12))
 │         └── cost: 1074.02
 ├── G11: (scan pqr,cols=(15-19))
 │    └── []
 │         ├── best: (scan pqr,cols=(15-19))
 │         └── cost: 1104.02
 ├── G12: (variable a)
 └── G13: (const 1)

# Joins that exceed reorder_joins_limit are not reordered apart from
# commutation.
memo join-limit=1
SELECT *
FROM stu, abc, xyz, pqr
WHERE u = a AND a = x AND x = p
----
memo (optimized, ~31KB, required=[presentation: s:1,t:2,u:3,a:5,b:6,c:7,x:10,y:11,z:12,p:15,q:16,r:17,s:18,t:19])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (merge-join G2 G3 G5 inner-join,+3,+5) (merge-join G3 G2 G5 inner-join,+5,+3) (lookup-join G3 G5 stu@uts,keyCols=[5],outCols=(1-3,5-7,10-12,15-19))
 │    └── [presentation: s:1,t:2,u:3,a:5,b:6,c:7,x:10,y:11,z:12,p:15,q:16,r:17,s:18,t:19]
 │         ├── best: (merge-join G2="[ordering: +3]" G3="[ordering: +(5|10|15)]" G5 inner-join,+3,+5)
 │         └── cost: 14126.11
 ├── G2: (scan stu,cols=(1-3)) (scan stu@uts,cols=(1-3))
 │    ├── [ordering: +3]
 │    │    ├── best: (scan stu@uts,cols=(1-3))
 │    │    └── cost: 10604.02
 │    └── []
 │         ├── best: (scan stu,cols=(1-3))
 │         └── cost: 10604.02
 ├── G3: (inner-join G6 G7 G8) (inner-join G7 G6 G8) (merge-join G6 G7 G5 inner-join,+5,+10) (merge-join G7 G6 G5 inner-join,+10,+5) (lookup-join G7 G5 abc@ab,keyCols=[10],outCols=(5-7,10-12,15-19))
 │    ├── [ordering: +(5|10|15)]
 │    │    ├── best: (merge-join G6="[ordering: +5]" G7="[ordering: +(10|15)]" G5 inner-join,+5,+10)
 │    │    └── cost: 3312.08
 │    └── []
 │         ├── best: (merge-join G6="[ordering: +5]" G7="[ordering: +(10|15)]" G5 inner-join,+5,+10)
 │         └── cost: 3312.08
 ├── G4: (filters G9)
 ├── G5: (filters)
 ├── G6: (scan abc,cols=(5-7)) (scan abc@ab,cols=(5-7)) (scan abc@bc,cols=(5-7))
 │    ├── [ordering: +5]
 │    │    ├── best: (scan abc@ab,cols=(5-7))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(5-7))
 │         └── cost: 1074.02
 ├── G7: (inner-join G10 G11 G12) (inner-join G11 G10 G12) (merge-join G10 G11 G5 inner-join,+10,+15) (lookup-join G10 G5 pqr,keyCols=[10],outCols=(10-12,15-19)) (merge-join G11 G10 G5 inner-join,+15,+10) (lookup-join G11 G5 xyz@xy,keyCols=[15],outCols=(10-12,15-19))
 │    ├── [ordering: +(10|15)]
 │    │    ├── best: (merge-join G10="[ordering: +10]" G11="[ordering: +15]" G5 inner-join,+10,+15)
 │    │    └── cost: 2208.05
 │    └── []
 │         ├── best: (merge-join G10="[ordering: +10]" G11="[ordering: +15]" G5 inner-join,+10,+15)
 │         └── cost: 2208.05
 ├── G8: (filters G13)
 ├── G9: (eq G14 G15)
 ├── G10: (scan xyz,cols=(10-12)) (scan xyz@xy,cols=(10-12)) (scan xyz@yz,cols=(10-12))
 │    ├── [ordering: +10]
 │    │    ├── best: (scan xyz@xy,cols=(10-12))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan xyz,cols=(10-12))
 │         └── cost: 1074.02
 ├── G11: (scan pqr,cols=(15-19))
 │    ├── [ordering: +15]
 │    │    ├── best: (scan pqr,cols=(15-19))
 │    │    └── cost: 1104.02
 │    └── []
 │         ├── best: (scan pqr,cols=(15-19))
 │         └── cost: 1104.02
 ├── G12: (filters G16)
 ├── G13: (eq G15 G17)
 ├── G14: (variable u)
 ├── G15: (variable a)
 ├── G16: (eq G17 G18)
 ├── G17: (variable x)
 └── G18: (variable p)

# Case where an implicit filter is used in the final plan (abc.a = pqr.p in the
# merge join).
opt expect=ReorderJoins format=hide-all
SELECT *
FROM abc,
     stu,
     xyz,
     (SELECT * FROM pqr WHERE p = 5)
WHERE a = stu.s
  AND q = y
  AND stu.s = p
----
inner-join (lookup stu)
 ├── inner-join (lookup xyz@yz)
 │    ├── inner-join (lookup abc@ab)
 │    │    ├── scan pqr
 │    │    │    └── constraint: /15: [/5 - /5]
 │    │    └── filters (true)
 │    └── filters (true)
 └── filters (true)

# The apply join at the top of the tree should not be reordered. However, the
# lower-level inner join can be reordered despite the fact that it has outer
# columns.
memo expect=ReorderJoins
SELECT *
FROM abc
INNER JOIN LATERAL (
  SELECT *
  FROM (SELECT * FROM (VALUES (a+1), (b*2)) f(v))
  INNER JOIN stu
  ON s = v
)
ON a = v
----
memo (optimized, ~13KB, required=[presentation: a:1,b:2,c:3,v:6,s:7,t:8,u:9])
 ├── G1: (inner-join-apply G2 G3 G4)
 │    └── [presentation: a:1,b:2,c:3,v:6,s:7,t:8,u:9]
 │         ├── best: (inner-join-apply G2 G3 G4)
 │         └── cost: 1168.53
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (inner-join G5 G6 G7) (inner-join G6 G5 G7) (lookup-join G5 G8 stu,keyCols=[6],outCols=(6-9)) (merge-join G6 G5 G8 inner-join,+7,+6)
 │    └── []
 │         ├── best: (lookup-join G5 G8 stu,keyCols=[6],outCols=(6-9))
 │         └── cost: 81.44
 ├── G4: (filters G9)
 ├── G5: (values G10 id=v1)
 │    ├── [ordering: +6]
 │    │    ├── best: (sort G5)
 │    │    └── cost: 0.12
 │    └── []
 │         ├── best: (values G10 id=v1)
 │         └── cost: 0.03
 ├── G6: (scan stu,cols=(7-9)) (scan stu@uts,cols=(7-9))
 │    ├── [ordering: +7]
 │    │    ├── best: (scan stu,cols=(7-9))
 │    │    └── cost: 10604.02
 │    └── []
 │         ├── best: (scan stu,cols=(7-9))
 │         └── cost: 10604.02
 ├── G7: (filters G11)
 ├── G8: (filters)
 ├── G9: (eq G12 G13)
 ├── G10: (scalar-list G14 G15)
 ├── G11: (eq G16 G13)
 ├── G12: (variable a)
 ├── G13: (variable column1)
 ├── G14: (tuple G17)
 ├── G15: (tuple G18)
 ├── G16: (variable s)
 ├── G17: (scalar-list G19)
 ├── G18: (scalar-list G20)
 ├── G19: (plus G12 G21)
 ├── G20: (mult G22 G23)
 ├── G21: (const 1)
 ├── G22: (variable b)
 └── G23: (const 2)

# Only commutation is possible for a single join.
exploretrace rule=ReorderJoins format=hide-all
SELECT * FROM abc, stu WHERE a = s
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── scan abc
   ├── scan stu
   └── filters
        └── a = s

New expression 1 of 1:
  inner-join (hash)
   ├── scan stu
   ├── scan abc
   └── filters
        └── a = s
----
----

# No-op case because the joins have join flags.
opt expect-not=ReorderJoins format=hide-all
SELECT *
FROM abc
INNER HASH JOIN stu
ON a = s
INNER MERGE JOIN xyz
ON s = x
----
inner-join (merge)
 ├── flags: force merge join
 ├── sort
 │    └── inner-join (hash)
 │         ├── flags: force hash join (store right side)
 │         ├── scan abc
 │         ├── scan stu
 │         └── filters
 │              └── a = s
 ├── scan xyz@xy
 └── filters (true)

# No-op case because InnerJoinApply is not matched.
opt expect-not=ReorderJoins format=hide-all
SELECT *
FROM abc
INNER JOIN LATERAL (SELECT * FROM (VALUES (a+1), (b*2)) f(v))
ON a = v
----
inner-join-apply
 ├── scan abc
 ├── values
 │    ├── (a + 1,)
 │    └── (b * 2,)
 └── filters
      └── a = column1

opt expect=ReorderJoins format=hide-all
SELECT *
FROM abc
LEFT JOIN stu
ON a = s
----
left-join (merge)
 ├── scan abc@ab
 ├── scan stu
 └── filters (true)

# Don't add a join between xyz and stu to the memo (because doing so would
# create a cross join).
exploretrace rule=ReorderJoins format=hide-all
SELECT *
FROM stu
INNER JOIN abc
ON s = a
INNER JOIN xyz
ON b = y
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan stu
   │    ├── scan abc
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 1:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan abc
   │    ├── scan stu
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── inner-join (merge)
   │    ├── scan stu
   │    ├── scan abc@ab
   │    └── filters (true)
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 3:
  inner-join (hash)
   ├── scan stu
   ├── inner-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   └── filters
        └── s = a

New expression 2 of 3:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   ├── scan stu
   └── filters
        └── s = a

New expression 3 of 3:
  inner-join (hash)
   ├── scan xyz
   ├── inner-join (merge)
   │    ├── scan stu
   │    ├── scan abc@ab
   │    └── filters (true)
   └── filters
        └── b = y
----
----

# Left join under an inner join. Push the inner join into the left input of the
# left join.
opt expect=ReorderJoins
SELECT *
FROM
(
  SELECT *
  FROM medium
  LEFT JOIN large ON large.m = medium.m
) medium
INNER JOIN small ON medium.n = small.n
----
right-join (hash)
 ├── columns: m:1 n:2!null m:5 n:6 m:9 n:10!null
 ├── fd: (2)==(10), (10)==(2)
 ├── scan large
 │    └── columns: large.m:5 large.n:6
 ├── inner-join (hash)
 │    ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
 │    ├── fd: (2)==(10), (10)==(2)
 │    ├── scan medium
 │    │    └── columns: medium.m:1 medium.n:2
 │    ├── scan small
 │    │    └── columns: small.m:9 small.n:10
 │    └── filters
 │         └── medium.n:2 = small.n:10 [outer=(2,10), constraints=(/2: (/NULL - ]; /10: (/NULL - ]), fd=(2)==(10), (10)==(2)]
 └── filters
      └── large.m:5 = medium.m:1 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]

# Left join under an inner join. Push the inner join into the left input of the
# left join, but leave the (small.m:9 = large.n:6) OR (large.n:6 IS NULL) filter
# on a select above the join tree. It can't be pushed into the left join because
# it originated from an inner join.
opt expect=ReorderJoins
SELECT *
FROM
(
  SELECT medium.n, large.n
  FROM medium
  LEFT JOIN large ON large.m = medium.m
) result(a, b)
INNER JOIN small
ON result.a = small.n AND (small.m = result.b OR result.b IS NULL)
----
project
 ├── columns: a:2!null b:6 m:9 n:10!null
 ├── fd: (2)==(10), (10)==(2)
 └── select
      ├── columns: medium.m:1 medium.n:2!null large.m:5 large.n:6 small.m:9 small.n:10!null
      ├── fd: (2)==(10), (10)==(2)
      ├── right-join (hash)
      │    ├── columns: medium.m:1 medium.n:2!null large.m:5 large.n:6 small.m:9 small.n:10!null
      │    ├── fd: (2)==(10), (10)==(2)
      │    ├── scan large
      │    │    └── columns: large.m:5 large.n:6
      │    ├── inner-join (hash)
      │    │    ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
      │    │    ├── fd: (2)==(10), (10)==(2)
      │    │    ├── scan medium
      │    │    │    └── columns: medium.m:1 medium.n:2
      │    │    ├── scan small
      │    │    │    └── columns: small.m:9 small.n:10
      │    │    └── filters
      │    │         └── medium.n:2 = small.n:10 [outer=(2,10), constraints=(/2: (/NULL - ]; /10: (/NULL - ]), fd=(2)==(10), (10)==(2)]
      │    └── filters
      │         └── large.m:5 = medium.m:1 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── filters
           └── (small.m:9 = large.n:6) OR (large.n:6 IS NULL) [outer=(6,9)]

# Semi join under an inner join. Push the inner join into the left input of the
# semi join.
opt expect=ReorderJoins
SELECT *
FROM
(
  SELECT medium.n
  FROM medium
  WHERE EXISTS (SELECT * FROM large WHERE medium.m = large.m)
) medium
INNER JOIN small ON small.n = medium.n
----
project
 ├── columns: n:2!null m:9 n:10!null
 ├── fd: (2)==(10), (10)==(2)
 └── semi-join (hash)
      ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
      ├── fd: (2)==(10), (10)==(2)
      ├── inner-join (hash)
      │    ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
      │    ├── fd: (2)==(10), (10)==(2)
      │    ├── scan medium
      │    │    └── columns: medium.m:1 medium.n:2
      │    ├── scan small
      │    │    └── columns: small.m:9 small.n:10
      │    └── filters
      │         └── small.n:10 = medium.n:2 [outer=(2,10), constraints=(/2: (/NULL - ]; /10: (/NULL - ]), fd=(2)==(10), (10)==(2)]
      ├── scan large
      │    └── columns: large.m:5
      └── filters
           └── medium.m:1 = large.m:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]

# Anti join under an inner join. Push the inner join into the left input of the
# anti join.
opt expect=ReorderJoins
SELECT *
FROM
(
  SELECT medium.n
  FROM medium
  WHERE NOT EXISTS (SELECT * FROM large WHERE medium.m <> large.m)
) medium
INNER JOIN small ON small.n = medium.n
----
project
 ├── columns: n:2!null m:9 n:10!null
 ├── fd: (2)==(10), (10)==(2)
 └── anti-join (cross)
      ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
      ├── fd: (2)==(10), (10)==(2)
      ├── inner-join (hash)
      │    ├── columns: medium.m:1 medium.n:2!null small.m:9 small.n:10!null
      │    ├── fd: (2)==(10), (10)==(2)
      │    ├── scan medium
      │    │    └── columns: medium.m:1 medium.n:2
      │    ├── scan small
      │    │    └── columns: small.m:9 small.n:10
      │    └── filters
      │         └── small.n:10 = medium.n:2 [outer=(2,10), constraints=(/2: (/NULL - ]; /10: (/NULL - ]), fd=(2)==(10), (10)==(2)]
      ├── scan large
      │    └── columns: large.m:5
      └── filters
           └── medium.m:1 != large.m:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ])]

# Inner join in the right input of a left join; no reordering is valid apart
# from commutation.
exploretrace rule=ReorderJoins format=hide-all
SELECT *
FROM small
LEFT JOIN
(
  SELECT large.m
  FROM large
  INNER JOIN medium
  ON large.n = medium.n
) large
ON small.m = large.m
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  project
   └── left-join (hash)
        ├── scan small
        ├── inner-join (hash)
        │    ├── scan large
        │    ├── scan medium
        │    └── filters
        │         └── large.n = medium.n
        └── filters
             └── small.m = large.m

New expression 1 of 1:
  project
   └── left-join (hash)
        ├── scan small
        ├── inner-join (hash)
        │    ├── scan medium
        │    ├── scan large
        │    └── filters
        │         └── large.n = medium.n
        └── filters
             └── small.m = large.m

================================================================================
ReorderJoins
================================================================================
Source expression:
  project
   └── left-join (hash)
        ├── scan small
        ├── inner-join (hash)
        │    ├── scan large
        │    ├── scan medium
        │    └── filters
        │         └── large.n = medium.n
        └── filters
             └── small.m = large.m

No new expressions.
----
----

exploretrace rule=ReorderJoins format=hide-all
SELECT *
FROM
(
  SELECT medium.n, large.n
  FROM medium
  LEFT JOIN large ON large.m = medium.m
) result(a, b)
INNER JOIN small
ON result.a = small.n AND (small.m = result.b OR result.b IS NULL)
INNER JOIN xyz ON True
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  project
   └── inner-join (cross)
        ├── inner-join (hash)
        │    ├── left-join (hash)
        │    │    ├── scan medium
        │    │    ├── scan large
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    ├── scan small
        │    └── filters
        │         ├── medium.n = small.n
        │         └── (small.m = large.n) OR (large.n IS NULL)
        ├── scan xyz
        └── filters (true)

No new expressions.

================================================================================
ReorderJoins
================================================================================
Source expression:
  project
   └── inner-join (cross)
        ├── inner-join (hash)
        │    ├── right-join (hash)
        │    │    ├── scan large
        │    │    ├── scan medium
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    ├── scan small
        │    └── filters
        │         ├── medium.n = small.n
        │         └── (small.m = large.n) OR (large.n IS NULL)
        ├── scan xyz
        └── filters (true)

New expression 1 of 2:
  project
   └── inner-join (cross)
        ├── select
        │    ├── left-join (hash)
        │    │    ├── inner-join (hash)
        │    │    │    ├── scan medium
        │    │    │    ├── scan small
        │    │    │    └── filters
        │    │    │         └── medium.n = small.n
        │    │    ├── scan large
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    └── filters
        │         └── (small.m = large.n) OR (large.n IS NULL)
        ├── scan xyz
        └── filters (true)

New expression 2 of 2:
  project
   └── inner-join (cross)
        ├── inner-join (hash)
        │    ├── scan small
        │    ├── right-join (hash)
        │    │    ├── scan large
        │    │    ├── scan medium
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    └── filters
        │         ├── medium.n = small.n
        │         └── (small.m = large.n) OR (large.n IS NULL)
        ├── scan xyz
        └── filters (true)

================================================================================
ReorderJoins
================================================================================
Source expression:
  project
   └── inner-join (cross)
        ├── select
        │    ├── right-join (hash)
        │    │    ├── scan large
        │    │    ├── inner-join (hash)
        │    │    │    ├── scan medium
        │    │    │    ├── scan small
        │    │    │    └── filters
        │    │    │         └── medium.n = small.n
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    └── filters
        │         └── (small.m = large.n) OR (large.n IS NULL)
        ├── scan xyz
        └── filters (true)

New expression 1 of 1:
  project
   └── inner-join (cross)
        ├── scan xyz
        ├── select
        │    ├── right-join (hash)
        │    │    ├── scan large
        │    │    ├── inner-join (hash)
        │    │    │    ├── scan medium
        │    │    │    ├── scan small
        │    │    │    └── filters
        │    │    │         └── medium.n = small.n
        │    │    └── filters
        │    │         └── large.m = medium.m
        │    └── filters
        │         └── (small.m = large.n) OR (large.n IS NULL)
        └── filters (true)
----
----

# Full join on top of a full join.
exploretrace rule=ReorderJoins format=hide-all
SELECT * FROM abc
FULL JOIN stu ON s = a
FULL JOIN xyz ON b = y
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan stu
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 1:
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan stu
   │    ├── scan abc
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

================================================================================
ReorderJoins
================================================================================
Source expression:
  full-join (hash)
   ├── full-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 3:
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   ├── scan stu
   └── filters
        └── s = a

New expression 2 of 3:
  full-join (hash)
   ├── scan stu
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   └── filters
        └── s = a

New expression 3 of 3:
  full-join (hash)
   ├── scan xyz
   ├── full-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   └── filters
        └── b = y
----
----

# Full join on top of a full join. Lower join is in right input of upper join.
exploretrace rule=ReorderJoins format=hide-all
SELECT * FROM abc
FULL JOIN
(
  SELECT * FROM stu
  FULL JOIN xyz ON t = y
) f(s, t, u, x, y, z)
ON a = x
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  full-join (hash)
   ├── scan abc
   ├── full-join (hash)
   │    ├── scan stu
   │    ├── scan xyz
   │    └── filters
   │         └── t = y
   └── filters
        └── a = x

New expression 1 of 1:
  full-join (hash)
   ├── scan abc
   ├── full-join (hash)
   │    ├── scan xyz
   │    ├── scan stu
   │    └── filters
   │         └── t = y
   └── filters
        └── a = x

================================================================================
ReorderJoins
================================================================================
Source expression:
  full-join (hash)
   ├── scan abc
   ├── full-join (hash)
   │    ├── scan stu
   │    ├── scan xyz
   │    └── filters
   │         └── t = y
   └── filters
        └── a = x

New expression 1 of 3:
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan stu
   │    ├── scan xyz
   │    └── filters
   │         └── t = y
   ├── scan abc
   └── filters
        └── a = x

New expression 2 of 3:
  full-join (hash)
   ├── scan stu
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── a = x
   └── filters
        └── t = y

New expression 3 of 3:
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── a = x
   ├── scan stu
   └── filters
        └── t = y
----
----

# Left join on top of a left join.
exploretrace rule=ReorderJoins format=hide-all
SELECT * FROM abc
LEFT JOIN stu ON s = a
LEFT JOIN xyz ON b = y
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  left-join (hash)
   ├── left-join (hash)
   │    ├── scan abc
   │    ├── scan stu
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

No new expressions.

================================================================================
ReorderJoins
================================================================================
Source expression:
  left-join (hash)
   ├── left-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 1:
  left-join (hash)
   ├── left-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   ├── scan stu
   └── filters
        └── s = a
----
----

# Left join on top of a full join.
exploretrace rule=ReorderJoins format=hide-all
SELECT * FROM abc
FULL JOIN stu ON s = a
LEFT JOIN xyz ON b = y
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  left-join (hash)
   ├── full-join (hash)
   │    ├── scan abc
   │    ├── scan stu
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 1:
  left-join (hash)
   ├── full-join (hash)
   │    ├── scan stu
   │    ├── scan abc
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── b = y

================================================================================
ReorderJoins
================================================================================
Source expression:
  left-join (hash)
   ├── full-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   ├── scan xyz
   └── filters
        └── b = y

New expression 1 of 2:
  full-join (hash)
   ├── left-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   ├── scan stu
   └── filters
        └── s = a

New expression 2 of 2:
  full-join (hash)
   ├── scan stu
   ├── left-join (hash)
   │    ├── scan abc
   │    ├── scan xyz
   │    └── filters
   │         └── b = y
   └── filters
        └── s = a
----
----

# Verify that the reversed join expressions get added to the memo, and there
# are no duplicates.
memo expect=ReorderJoins
SELECT * FROM abc JOIN xyz ON a=z
----
memo (optimized, ~10KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (merge-join G2 G3 G5 inner-join,+1,+8) (lookup-join G3 G5 abc@ab,keyCols=[8],outCols=(1-3,6-8))
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (inner-join G2 G3 G4)
 │         └── cost: 2187.96
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    ├── [ordering: +8]
 │    │    ├── best: (sort G3)
 │    │    └── cost: 1293.35
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable z)

memo expect=ReorderJoins
SELECT * FROM abc FULL OUTER JOIN xyz ON a=z
----
memo (optimized, ~9KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (full-join G2 G3 G4) (full-join G3 G2 G4) (merge-join G2 G3 G5 full-join,+1,+8)
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (full-join G2 G3 G4)
 │         └── cost: 2188.06
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    ├── [ordering: +8]
 │    │    ├── best: (sort G3)
 │    │    └── cost: 1293.35
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable z)

# Verify that we swap to get the smaller side on the right.
opt expect=ReorderJoins
SELECT * FROM abc INNER JOIN xyz ON a=c WHERE b=1
----
inner-join (cross)
 ├── columns: a:1!null b:2!null c:3!null x:6 y:7 z:8
 ├── fd: ()-->(2), (1)==(3), (3)==(1)
 ├── scan xyz
 │    └── columns: x:6 y:7 z:8
 ├── select
 │    ├── columns: a:1!null b:2!null c:3!null
 │    ├── fd: ()-->(2), (1)==(3), (3)==(1)
 │    ├── scan abc@bc
 │    │    ├── columns: a:1 b:2!null c:3!null
 │    │    ├── constraint: /2/3/4: (/1/NULL - /1]
 │    │    └── fd: ()-->(2)
 │    └── filters
 │         └── a:1 = c:3 [outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]
 └── filters (true)

# Verify that the hash join hint prevents swapping the sides.
opt expect-not=ReorderJoins
SELECT * FROM abc INNER HASH JOIN xyz ON a=c WHERE b=1
----
inner-join (cross)
 ├── columns: a:1!null b:2!null c:3!null x:6 y:7 z:8
 ├── flags: force hash join (store right side)
 ├── fd: ()-->(2), (1)==(3), (3)==(1)
 ├── select
 │    ├── columns: a:1!null b:2!null c:3!null
 │    ├── fd: ()-->(2), (1)==(3), (3)==(1)
 │    ├── scan abc@bc
 │    │    ├── columns: a:1 b:2!null c:3!null
 │    │    ├── constraint: /2/3/4: (/1/NULL - /1]
 │    │    └── fd: ()-->(2)
 │    └── filters
 │         └── a:1 = c:3 [outer=(1,3), constraints=(/1: (/NULL - ]; /3: (/NULL - ]), fd=(1)==(3), (3)==(1)]
 ├── scan xyz
 │    └── columns: x:6 y:7 z:8
 └── filters (true)

opt expect=ReorderJoins
SELECT * FROM (SELECT * FROM abc WHERE b=1) FULL OUTER JOIN xyz ON a=z
----
full-join (hash)
 ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
 ├── scan xyz
 │    └── columns: x:6 y:7 z:8
 ├── scan abc@bc
 │    ├── columns: a:1 b:2!null c:3
 │    ├── constraint: /2/3/4: [/1 - /1]
 │    └── fd: ()-->(2)
 └── filters
      └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

# Verify that commuting works correctly when there is a lookup join hint
# (specifically that it returns the original expression and flags when applied
# twice; if it didn't, we'd see more inner-join expressions).
memo expect=ReorderJoins
SELECT * FROM abc INNER LOOKUP JOIN xyz ON a=x
----
memo (optimized, ~10KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (inner-join G2 G3 G4) (lookup-join G2 G5 xyz@xy,keyCols=[1],outCols=(1-3,6-8))
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (lookup-join G2 G5 xyz@xy,keyCols=[1],outCols=(1-3,6-8))
 │         └── cost: 23154.03
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable x)

# Verify that setting the join limit to 1 allows only commutation.
exploretrace rule=ReorderJoins format=hide-all join-limit=1
SELECT * FROM abc
INNER JOIN stu ON s = a
INNER JOIN xyz ON s = x
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan abc
   │    ├── scan stu
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── s = x

New expression 1 of 1:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan stu
   │    ├── scan abc
   │    └── filters
   │         └── s = a
   ├── scan xyz
   └── filters
        └── s = x

================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── inner-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   ├── scan xyz
   └── filters
        └── s = x

New expression 1 of 1:
  inner-join (hash)
   ├── scan xyz
   ├── inner-join (merge)
   │    ├── scan abc@ab
   │    ├── scan stu
   │    └── filters (true)
   └── filters
        └── s = x
----
----

# --------------------------------------------------
# CommuteLeftJoin
# --------------------------------------------------

memo
SELECT * FROM abc LEFT OUTER JOIN xyz ON a=z
----
memo (optimized, ~9KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (left-join G2 G3 G4) (right-join G3 G2 G4) (merge-join G2 G3 G5 left-join,+1,+8)
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (left-join G2 G3 G4)
 │         └── cost: 2188.06
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    ├── [ordering: +8]
 │    │    ├── best: (sort G3)
 │    │    └── cost: 1293.35
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable z)

opt
SELECT * FROM abc LEFT OUTER JOIN xyz ON a=z WHERE b=1
----
right-join (hash)
 ├── columns: a:1 b:2!null c:3 x:6 y:7 z:8
 ├── fd: ()-->(2)
 ├── scan xyz
 │    └── columns: x:6 y:7 z:8
 ├── scan abc@bc
 │    ├── columns: a:1 b:2!null c:3
 │    ├── constraint: /2/3/4: [/1 - /1]
 │    └── fd: ()-->(2)
 └── filters
      └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

# --------------------------------------------------
# CommuteRightJoin
# --------------------------------------------------

memo
SELECT * FROM abc RIGHT OUTER JOIN xyz ON a=z
----
memo (optimized, ~10KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (left-join G2 G3 G4) (right-join G3 G2 G4) (lookup-join G2 G5 abc@ab,keyCols=[8],outCols=(1-3,6-8)) (merge-join G3 G2 G5 right-join,+1,+8)
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (left-join G2 G3 G4)
 │         └── cost: 2188.06
 ├── G2: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    ├── [ordering: +8]
 │    │    ├── best: (sort G2)
 │    │    └── cost: 1293.35
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G3: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable z)

opt
SELECT * FROM (SELECT * FROM abc WHERE b=1) RIGHT OUTER JOIN xyz ON a=z
----
left-join (hash)
 ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
 ├── scan xyz
 │    └── columns: x:6 y:7 z:8
 ├── scan abc@bc
 │    ├── columns: a:1 b:2!null c:3
 │    ├── constraint: /2/3/4: [/1 - /1]
 │    └── fd: ()-->(2)
 └── filters
      └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

# --------------------------------------------------
# GenerateMergeJoins
# --------------------------------------------------

opt
SELECT * FROM abc JOIN xyz ON a=x
----
inner-join (merge)
 ├── columns: a:1!null b:2 c:3 x:6!null y:7 z:8
 ├── left ordering: +1
 ├── right ordering: +6
 ├── fd: (1)==(6), (6)==(1)
 ├── scan abc@ab
 │    ├── columns: a:1 b:2 c:3
 │    └── ordering: +1
 ├── scan xyz@xy
 │    ├── columns: x:6 y:7 z:8
 │    └── ordering: +6
 └── filters (true)

memo
SELECT * FROM abc JOIN xyz ON a=x
----
memo (optimized, ~12KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (merge-join G2 G3 G5 inner-join,+1,+6) (lookup-join G2 G5 xyz@xy,keyCols=[1],outCols=(1-3,6-8)) (merge-join G3 G2 G5 inner-join,+6,+1) (lookup-join G3 G5 abc@ab,keyCols=[6],outCols=(1-3,6-8))
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (merge-join G2="[ordering: +1]" G3="[ordering: +6]" G5 inner-join,+1,+6)
 │         └── cost: 2178.05
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan abc@ab,cols=(1-3))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    ├── [ordering: +6]
 │    │    ├── best: (scan xyz@xy,cols=(6-8))
 │    │    └── cost: 1074.02
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G6)
 ├── G5: (filters)
 ├── G6: (eq G7 G8)
 ├── G7: (variable a)
 └── G8: (variable x)

# Verify that we don't generate merge joins if there's a hint that says otherwise.
memo
SELECT * FROM abc INNER HASH JOIN xyz ON a=x
----
memo (optimized, ~8KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (inner-join G2 G3 G4)
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (inner-join G2 G3 G4)
 │         └── cost: 2188.06
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters G5)
 ├── G5: (eq G6 G7)
 ├── G6: (variable a)
 └── G7: (variable x)

opt
SELECT * FROM abc JOIN xyz ON x=a
----
inner-join (merge)
 ├── columns: a:1!null b:2 c:3 x:6!null y:7 z:8
 ├── left ordering: +1
 ├── right ordering: +6
 ├── fd: (1)==(6), (6)==(1)
 ├── scan abc@ab
 │    ├── columns: a:1 b:2 c:3
 │    └── ordering: +1
 ├── scan xyz@xy
 │    ├── columns: x:6 y:7 z:8
 │    └── ordering: +6
 └── filters (true)

opt
SELECT * FROM abc JOIN xyz ON a=x AND a=x AND x=a
----
inner-join (merge)
 ├── columns: a:1!null b:2 c:3 x:6!null y:7 z:8
 ├── left ordering: +1
 ├── right ordering: +6
 ├── fd: (1)==(6), (6)==(1)
 ├── scan abc@ab
 │    ├── columns: a:1 b:2 c:3
 │    └── ordering: +1
 ├── scan xyz@xy
 │    ├── columns: x:6 y:7 z:8
 │    └── ordering: +6
 └── filters (true)

# Use constraints to force the choice of an index which doesn't help, and
# verify that we don't prefer a merge-join that has to sort both of its inputs.
opt
SELECT * FROM abc JOIN xyz ON a=x AND b=y WHERE b=1 AND y=1
----
inner-join (hash)
 ├── columns: a:1!null b:2!null c:3 x:6!null y:7!null z:8
 ├── fd: ()-->(2,7), (1)==(6), (6)==(1), (2)==(7), (7)==(2)
 ├── scan abc@bc
 │    ├── columns: a:1 b:2!null c:3
 │    ├── constraint: /2/3/4: [/1 - /1]
 │    └── fd: ()-->(2)
 ├── scan xyz@yz
 │    ├── columns: x:6 y:7!null z:8
 │    ├── constraint: /7/8/9: [/1 - /1]
 │    └── fd: ()-->(7)
 └── filters
      ├── a:1 = x:6 [outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]
      └── b:2 = y:7 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# Verify case where we generate multiple merge-joins.
memo
SELECT * FROM stu AS l JOIN stu AS r ON (l.s, l.t, l.u) = (r.s, r.t, r.u)
----
memo (optimized, ~15KB, required=[presentation: s:1,t:2,u:3,s:5,t:6,u:7])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (merge-join G2 G3 G5 inner-join,+1,+2,+3,+5,+6,+7) (merge-join G2 G3 G5 inner-join,+3,+2,+1,+7,+6,+5) (lookup-join G2 G5 stu,keyCols=[1 2 3],outCols=(1-3,5-7)) (lookup-join G2 G5 stu@uts,keyCols=[3 2 1],outCols=(1-3,5-7)) (merge-join G3 G2 G5 inner-join,+5,+6,+7,+1,+2,+3) (merge-join G3 G2 G5 inner-join,+7,+6,+5,+3,+2,+1) (lookup-join G3 G5 stu,keyCols=[5 6 7],outCols=(1-3,5-7)) (lookup-join G3 G5 stu@uts,keyCols=[7 6 5],outCols=(1-3,5-7))
 │    └── [presentation: s:1,t:2,u:3,s:5,t:6,u:7]
 │         ├── best: (merge-join G2="[ordering: +1,+2,+3]" G3="[ordering: +5,+6,+7]" G5 inner-join,+1,+2,+3,+5,+6,+7)
 │         └── cost: 21408.05
 ├── G2: (scan l,cols=(1-3)) (scan l@uts,cols=(1-3))
 │    ├── [ordering: +1,+2,+3]
 │    │    ├── best: (scan l,cols=(1-3))
 │    │    └── cost: 10604.02
 │    ├── [ordering: +3,+2,+1]
 │    │    ├── best: (scan l@uts,cols=(1-3))
 │    │    └── cost: 10604.02
 │    └── []
 │         ├── best: (scan l,cols=(1-3))
 │         └── cost: 10604.02
 ├── G3: (scan r,cols=(5-7)) (scan r@uts,cols=(5-7))
 │    ├── [ordering: +5,+6,+7]
 │    │    ├── best: (scan r,cols=(5-7))
 │    │    └── cost: 10604.02
 │    ├── [ordering: +7,+6,+5]
 │    │    ├── best: (scan r@uts,cols=(5-7))
 │    │    └── cost: 10604.02
 │    └── []
 │         ├── best: (scan r,cols=(5-7))
 │         └── cost: 10604.02
 ├── G4: (filters G6 G7 G8)
 ├── G5: (filters)
 ├── G6: (eq G9 G10)
 ├── G7: (eq G11 G12)
 ├── G8: (eq G13 G14)
 ├── G9: (variable l.s)
 ├── G10: (variable r.s)
 ├── G11: (variable l.t)
 ├── G12: (variable r.t)
 ├── G13: (variable l.u)
 └── G14: (variable r.u)

exploretrace rule=GenerateMergeJoins
SELECT * FROM stu AS l JOIN stu AS r ON (l.s, l.t, l.u) = (r.s, r.t, r.u)
----
----
================================================================================
GenerateMergeJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan l
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    └── key: (1-3)
   ├── scan r
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    └── key: (5-7)
   └── filters
        ├── l.s:1 = r.s:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
        ├── l.t:2 = r.t:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]
        └── l.u:3 = r.u:7 [outer=(3,7), constraints=(/3: (/NULL - ]; /7: (/NULL - ]), fd=(3)==(7), (7)==(3)]

New expression 1 of 2:
  inner-join (merge)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── left ordering: +1,+2,+3
   ├── right ordering: +5,+6,+7
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan l
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    ├── key: (1-3)
   │    └── ordering: +1,+2,+3
   ├── scan r
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    ├── key: (5-7)
   │    └── ordering: +5,+6,+7
   └── filters (true)

New expression 2 of 2:
  inner-join (merge)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── left ordering: +3,+2,+1
   ├── right ordering: +7,+6,+5
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan l@uts
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    ├── key: (1-3)
   │    └── ordering: +3,+2,+1
   ├── scan r@uts
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    ├── key: (5-7)
   │    └── ordering: +7,+6,+5
   └── filters (true)

================================================================================
GenerateMergeJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── multiplicity: left-rows(exactly-one), right-rows(exactly-one)
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan r
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    └── key: (5-7)
   ├── scan l
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    └── key: (1-3)
   └── filters
        ├── l.s:1 = r.s:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
        ├── l.t:2 = r.t:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]
        └── l.u:3 = r.u:7 [outer=(3,7), constraints=(/3: (/NULL - ]; /7: (/NULL - ]), fd=(3)==(7), (7)==(3)]

New expression 1 of 2:
  inner-join (merge)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── left ordering: +5,+6,+7
   ├── right ordering: +1,+2,+3
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan r
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    ├── key: (5-7)
   │    └── ordering: +5,+6,+7
   ├── scan l
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    ├── key: (1-3)
   │    └── ordering: +1,+2,+3
   └── filters (true)

New expression 2 of 2:
  inner-join (merge)
   ├── columns: s:1!null t:2!null u:3!null s:5!null t:6!null u:7!null
   ├── left ordering: +7,+6,+5
   ├── right ordering: +3,+2,+1
   ├── key: (5-7)
   ├── fd: (1)==(5), (5)==(1), (2)==(6), (6)==(2), (3)==(7), (7)==(3)
   ├── scan r@uts
   │    ├── columns: r.s:5!null r.t:6!null r.u:7!null
   │    ├── key: (5-7)
   │    └── ordering: +7,+6,+5
   ├── scan l@uts
   │    ├── columns: l.s:1!null l.t:2!null l.u:3!null
   │    ├── key: (1-3)
   │    └── ordering: +3,+2,+1
   └── filters (true)
----
----

# Add statistics to make table stu large (so that sorting abc is relatively cheap).
exec-ddl
ALTER TABLE stu INJECT STATISTICS '[
  {
    "columns": ["s"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 1000000,
    "distinct_count": 1000000
  }
]'
----

# The ordering is coming from the left side.
opt
SELECT * FROM stu LEFT OUTER JOIN abc ON (c,b,a) = (s,t,u)
----
left-join (merge)
 ├── columns: s:1!null t:2!null u:3!null a:5 b:6 c:7
 ├── left ordering: +3,+2,+1
 ├── right ordering: +5,+6,+7
 ├── scan stu@uts
 │    ├── columns: s:1!null t:2!null u:3!null
 │    ├── key: (1-3)
 │    └── ordering: +3,+2,+1
 ├── sort (segmented)
 │    ├── columns: a:5 b:6 c:7
 │    ├── ordering: +5,+6,+7
 │    └── scan abc@ab
 │         ├── columns: a:5 b:6 c:7
 │         └── ordering: +5,+6
 └── filters (true)

# The ordering is coming from the right side.
opt
SELECT * FROM abc RIGHT OUTER JOIN stu ON (c,b,a) = (s,t,u)
----
left-join (merge)
 ├── columns: a:1 b:2 c:3 s:6!null t:7!null u:8!null
 ├── left ordering: +8,+7,+6
 ├── right ordering: +1,+2,+3
 ├── scan stu@uts
 │    ├── columns: s:6!null t:7!null u:8!null
 │    ├── key: (6-8)
 │    └── ordering: +8,+7,+6
 ├── sort (segmented)
 │    ├── columns: a:1 b:2 c:3
 │    ├── ordering: +1,+2,+3
 │    └── scan abc@ab
 │         ├── columns: a:1 b:2 c:3
 │         └── ordering: +1,+2
 └── filters (true)

# In these cases, we shouldn't pick up equivalencies.
memo
SELECT * FROM abc JOIN xyz ON a=b
----
memo (optimized, ~13KB, required=[presentation: a:1,b:2,c:3,x:6,y:7,z:8])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4)
 │    └── [presentation: a:1,b:2,c:3,x:6,y:7,z:8]
 │         ├── best: (inner-join G3 G2 G4)
 │         └── cost: 2169.68
 ├── G2: (select G5 G6) (select G7 G6) (select G8 G6)
 │    └── []
 │         ├── best: (select G8 G6)
 │         └── cost: 1073.23
 ├── G3: (scan xyz,cols=(6-8)) (scan xyz@xy,cols=(6-8)) (scan xyz@yz,cols=(6-8))
 │    └── []
 │         ├── best: (scan xyz,cols=(6-8))
 │         └── cost: 1074.02
 ├── G4: (filters)
 ├── G5: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G6: (filters G9)
 ├── G7: (scan abc@ab,cols=(1-3),constrained)
 │    └── []
 │         ├── best: (scan abc@ab,cols=(1-3),constrained)
 │         └── cost: 1074.01
 ├── G8: (scan abc@bc,cols=(1-3),constrained)
 │    └── []
 │         ├── best: (scan abc@bc,cols=(1-3),constrained)
 │         └── cost: 1063.31
 ├── G9: (eq G10 G11)
 ├── G10: (variable a)
 └── G11: (variable b)

exec-ddl
CREATE TABLE kfloat (k FLOAT PRIMARY KEY)
----

memo
SELECT * FROM abc JOIN kfloat ON a=k
----
memo (optimized, ~10KB, required=[presentation: a:1,b:2,c:3,k:6])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4)
 │    └── [presentation: a:1,b:2,c:3,k:6]
 │         ├── best: (inner-join G2 G3 G4)
 │         └── cost: 12128.06
 ├── G2: (scan abc,cols=(1-3)) (scan abc@ab,cols=(1-3)) (scan abc@bc,cols=(1-3))
 │    └── []
 │         ├── best: (scan abc,cols=(1-3))
 │         └── cost: 1074.02
 ├── G3: (scan kfloat,cols=(6))
 │    └── []
 │         ├── best: (scan kfloat,cols=(6))
 │         └── cost: 1024.02
 ├── G4: (filters G5)
 ├── G5: (eq G6 G7)
 ├── G6: (variable a)
 └── G7: (variable k)

# We should only pick up one equivalency.
opt
SELECT * FROM abc JOIN xyz ON a=x AND a=y
----
inner-join (lookup abc@ab)
 ├── columns: a:1!null b:2 c:3 x:6!null y:7!null z:8
 ├── key columns: [6] = [1]
 ├── fd: (6)==(1,7), (7)==(1,6), (1)==(6,7)
 ├── select
 │    ├── columns: x:6!null y:7!null z:8
 │    ├── fd: (6)==(7), (7)==(6)
 │    ├── scan xyz@yz
 │    │    ├── columns: x:6 y:7!null z:8
 │    │    └── constraint: /7/8/9: (/NULL - ]
 │    └── filters
 │         └── x:6 = y:7 [outer=(6,7), constraints=(/6: (/NULL - ]; /7: (/NULL - ]), fd=(6)==(7), (7)==(6)]
 └── filters (true)

# Verify multiple merge-joins can be chained.
opt
SELECT * FROM abc JOIN xyz ON a=x AND b=y RIGHT OUTER JOIN stu ON a=s
----
left-join (merge)
 ├── columns: a:1 b:2 c:3 x:6 y:7 z:8 s:11!null t:12!null u:13!null
 ├── left ordering: +11
 ├── right ordering: +1
 ├── fd: (1)==(6), (6)==(1), (2)==(7), (7)==(2)
 ├── scan stu
 │    ├── columns: s:11!null t:12!null u:13!null
 │    ├── key: (11-13)
 │    └── ordering: +11
 ├── inner-join (merge)
 │    ├── columns: a:1!null b:2!null c:3 x:6!null y:7!null z:8
 │    ├── left ordering: +1,+2
 │    ├── right ordering: +6,+7
 │    ├── fd: (1)==(6), (6)==(1), (2)==(7), (7)==(2)
 │    ├── ordering: +(1|6) [actual: +1]
 │    ├── scan abc@ab
 │    │    ├── columns: a:1 b:2 c:3
 │    │    └── ordering: +1,+2
 │    ├── scan xyz@xy
 │    │    ├── columns: x:6 y:7 z:8
 │    │    └── ordering: +6,+7
 │    └── filters (true)
 └── filters (true)

opt
SELECT * FROM abc JOIN xyz ON a=x AND b=y RIGHT OUTER JOIN stu ON a=u AND y=t
----
left-join (merge)
 ├── columns: a:1 b:2 c:3 x:6 y:7 z:8 s:11!null t:12!null u:13!null
 ├── left ordering: +13,+12
 ├── right ordering: +1,+7
 ├── fd: (1)==(6), (6)==(1), (2)==(7), (7)==(2)
 ├── scan stu@uts
 │    ├── columns: s:11!null t:12!null u:13!null
 │    ├── key: (11-13)
 │    └── ordering: +13,+12
 ├── inner-join (merge)
 │    ├── columns: a:1!null b:2!null c:3 x:6!null y:7!null z:8
 │    ├── left ordering: +1,+2
 │    ├── right ordering: +6,+7
 │    ├── fd: (1)==(6), (6)==(1), (2)==(7), (7)==(2)
 │    ├── ordering: +(1|6),+(2|7) [actual: +1,+2]
 │    ├── scan abc@ab
 │    │    ├── columns: a:1 b:2 c:3
 │    │    └── ordering: +1,+2
 │    ├── scan xyz@xy
 │    │    ├── columns: x:6 y:7 z:8
 │    │    └── ordering: +6,+7
 │    └── filters (true)
 └── filters (true)

# Generate a merge join with two partial indexes.

exec-ddl
CREATE TABLE partial_a (a INT, INDEX (a) WHERE a > 0)
----

exec-ddl
CREATE TABLE partial_b (b INT, INDEX (b) WHERE b > 0)
----

opt
SELECT a, b FROM partial_a JOIN partial_b ON a = b WHERE a > 0 AND b > 0
----
inner-join (merge)
 ├── columns: a:1!null b:4!null
 ├── left ordering: +1
 ├── right ordering: +4
 ├── fd: (1)==(4), (4)==(1)
 ├── scan partial_a@secondary,partial
 │    ├── columns: a:1!null
 │    └── ordering: +1
 ├── scan partial_b@secondary,partial
 │    ├── columns: b:4!null
 │    └── ordering: +4
 └── filters (true)

# --------------------------------------------------
# GenerateLookupJoins
# --------------------------------------------------

exec-ddl
CREATE TABLE abcd (a INT, b INT, c INT, INDEX (a,b))
----

exec-ddl
CREATE TABLE abcde (a INT, b INT, c INT, d INT, e INT, INDEX (a,b,c))
----

# Covering case.
opt
SELECT a,b,n,m FROM small JOIN abcd ON a=m
----
inner-join (lookup abcd@secondary)
 ├── columns: a:5!null b:6 n:2 m:1!null
 ├── key columns: [1] = [5]
 ├── fd: (1)==(5), (5)==(1)
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters (true)

# Covering case, left-join.
opt
SELECT a,b,n,m FROM small LEFT JOIN abcd ON a=m
----
left-join (lookup abcd@secondary)
 ├── columns: a:5 b:6 n:2 m:1
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters (true)

# Covering case, left-join, extra filter bound by index.
opt
SELECT a,b,n,m FROM small LEFT JOIN abcd ON a=m AND b>n
----
left-join (lookup abcd@secondary)
 ├── columns: a:5 b:6 n:2 m:1
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      └── b:6 > n:2 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]

# Non-covering case.
opt
SELECT * FROM small JOIN abcd ON a=m
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2 a:5!null b:6 c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6 abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters (true)
 └── filters (true)

# Non-covering case, left join.
opt
SELECT * FROM small LEFT JOIN abcd ON a=m
----
left-join (lookup abcd)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── left-join (lookup abcd@secondary)
 │    ├── columns: m:1 n:2 a:5 b:6 abcd.rowid:8
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters (true)
 └── filters (true)

# Non-covering case, extra filter bound by index.
opt
SELECT * FROM small JOIN abcd ON a=m AND b>n
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2!null a:5!null b:6!null c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2!null a:5!null b:6!null abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 > n:2 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]
 └── filters (true)

# Non-covering case, extra filter bound by index, left join.
opt
SELECT * FROM small LEFT JOIN abcd ON a=m AND b>n
----
left-join (lookup abcd)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── left-join (lookup abcd@secondary)
 │    ├── columns: m:1 n:2 a:5 b:6 abcd.rowid:8
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 > n:2 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]
 └── filters (true)

# Non-covering case, extra filter not bound by index.
opt
SELECT * FROM small JOIN abcd ON a=m AND c>n
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2!null a:5!null b:6 c:7!null
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6 abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters (true)
 └── filters
      └── c:7 > n:2 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ])]

# Non-covering case, extra filter not bound by index, left join.
# In this case, we can't yet convert to a lookup join (see
# the GenerateLookupJoins custom func).
opt
SELECT * FROM small LEFT JOIN abcd ON a=m AND c>n
----
right-join (hash)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── scan abcd
 │    └── columns: a:5 b:6 c:7
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      ├── a:5 = m:1 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── c:7 > n:2 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ])]


# Verify rule application when we can do a lookup join on both sides.
exploretrace rule=GenerateLookupJoins
SELECT * FROM abc JOIN xyz ON a=x AND a=y
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: a:1!null b:2 c:3 x:6!null y:7!null z:8
   ├── fd: (6)==(1,7), (7)==(1,6), (1)==(6,7)
   ├── select
   │    ├── columns: x:6!null y:7!null z:8
   │    ├── fd: (6)==(7), (7)==(6)
   │    ├── scan xyz@yz
   │    │    ├── columns: x:6 y:7!null z:8
   │    │    └── constraint: /7/8/9: (/NULL - ]
   │    └── filters
   │         └── x:6 = y:7 [outer=(6,7), constraints=(/6: (/NULL - ]; /7: (/NULL - ]), fd=(6)==(7), (7)==(6)]
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters
        └── a:1 = x:6 [outer=(1,6), constraints=(/1: (/NULL - ]; /6: (/NULL - ]), fd=(1)==(6), (6)==(1)]

New expression 1 of 1:
  inner-join (lookup abc@ab)
   ├── columns: a:1!null b:2 c:3 x:6!null y:7!null z:8
   ├── key columns: [6] = [1]
   ├── fd: (6)==(1,7), (7)==(1,6), (1)==(6,7)
   ├── select
   │    ├── columns: x:6!null y:7!null z:8
   │    ├── fd: (6)==(7), (7)==(6)
   │    ├── scan xyz@yz
   │    │    ├── columns: x:6 y:7!null z:8
   │    │    └── constraint: /7/8/9: (/NULL - ]
   │    └── filters
   │         └── x:6 = y:7 [outer=(6,7), constraints=(/6: (/NULL - ]; /7: (/NULL - ]), fd=(6)==(7), (7)==(6)]
   └── filters (true)
----
----

# Verify rule application when we can do a lookup join on the left side.
exploretrace rule=GenerateLookupJoins
SELECT * FROM abc JOIN xyz ON a=z
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: a:1!null b:2 c:3 x:6 y:7 z:8!null
   ├── fd: (1)==(8), (8)==(1)
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   └── filters
        └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

No new expressions.

================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: a:1!null b:2 c:3 x:6 y:7 z:8!null
   ├── fd: (1)==(8), (8)==(1)
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters
        └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

New expression 1 of 1:
  inner-join (lookup abc@ab)
   ├── columns: a:1!null b:2 c:3 x:6 y:7 z:8!null
   ├── key columns: [8] = [1]
   ├── fd: (1)==(8), (8)==(1)
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   └── filters (true)
----
----

exploretrace rule=GenerateLookupJoins
SELECT * FROM abc RIGHT JOIN xyz ON a=z
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  left-join (hash)
   ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters
        └── a:1 = z:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

New expression 1 of 1:
  left-join (lookup abc@ab)
   ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
   ├── key columns: [8] = [1]
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   └── filters (true)
----
----

# Verify rule application when we can do a lookup join on the right side.
exploretrace rule=GenerateLookupJoins
SELECT * FROM abc JOIN xyz ON c=x
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: a:1 b:2 c:3!null x:6!null y:7 z:8
   ├── fd: (3)==(6), (6)==(3)
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   └── filters
        └── c:3 = x:6 [outer=(3,6), constraints=(/3: (/NULL - ]; /6: (/NULL - ]), fd=(3)==(6), (6)==(3)]

New expression 1 of 1:
  inner-join (lookup xyz@xy)
   ├── columns: a:1 b:2 c:3!null x:6!null y:7 z:8
   ├── key columns: [3] = [6]
   ├── fd: (3)==(6), (6)==(3)
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters (true)

================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── columns: a:1 b:2 c:3!null x:6!null y:7 z:8
   ├── fd: (3)==(6), (6)==(3)
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters
        └── c:3 = x:6 [outer=(3,6), constraints=(/3: (/NULL - ]; /6: (/NULL - ]), fd=(3)==(6), (6)==(3)]

No new expressions.
----
----

exploretrace rule=GenerateLookupJoins
SELECT * FROM abc LEFT JOIN xyz ON c=x
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  left-join (hash)
   ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   └── filters
        └── c:3 = x:6 [outer=(3,6), constraints=(/3: (/NULL - ]; /6: (/NULL - ]), fd=(3)==(6), (6)==(3)]

New expression 1 of 1:
  left-join (lookup xyz@xy)
   ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
   ├── key columns: [3] = [6]
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters (true)
----
----

# Verify we don't generate a lookup join.
exploretrace rule=GenerateLookupJoins
SELECT * FROM abc RIGHT JOIN xyz ON c=x
----
----
================================================================================
GenerateLookupJoins
================================================================================
Source expression:
  left-join (hash)
   ├── columns: a:1 b:2 c:3 x:6 y:7 z:8
   ├── scan xyz
   │    └── columns: x:6 y:7 z:8
   ├── scan abc
   │    └── columns: a:1 b:2 c:3
   └── filters
        └── c:3 = x:6 [outer=(3,6), constraints=(/3: (/NULL - ]; /6: (/NULL - ]), fd=(3)==(6), (6)==(3)]

No new expressions.
----
----

# Verify we don't generate lookup joins if there is a hint that says otherwise.
memo
SELECT a,b,n,m FROM small INNER HASH JOIN abcd ON a=m
----
memo (optimized, ~8KB, required=[presentation: a:5,b:6,n:2,m:1])
 ├── G1: (inner-join G2 G3 G4)
 │    └── [presentation: a:5,b:6,n:2,m:1]
 │         ├── best: (inner-join G2 G3 G4)
 │         └── cost: 1087.17
 ├── G2: (scan small,cols=(1,2))
 │    └── []
 │         ├── best: (scan small,cols=(1,2))
 │         └── cost: 14.52
 ├── G3: (scan abcd,cols=(5,6)) (scan abcd@secondary,cols=(5,6))
 │    └── []
 │         ├── best: (scan abcd@secondary,cols=(5,6))
 │         └── cost: 1054.02
 ├── G4: (filters G5)
 ├── G5: (eq G6 G7)
 ├── G6: (variable a)
 └── G7: (variable m)

# Lookup semi-join with index that contains all columns in the join condition.
opt
SELECT m, n FROM small WHERE EXISTS(SELECT 1 FROM abcd WHERE m = a)
----
semi-join (lookup abcd@secondary)
 ├── columns: m:1 n:2
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters (true)

# We should not generate a lookup semi-join when the index doesn't contain all
# columns in the join condition.
opt
SELECT m, n FROM small WHERE EXISTS(SELECT 1 FROM abcd WHERE m = a AND n = c)
----
semi-join (hash)
 ├── columns: m:1 n:2
 ├── scan small
 │    └── columns: m:1 n:2
 ├── scan abcd
 │    └── columns: a:5 c:7
 └── filters
      ├── m:1 = a:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── n:2 = c:7 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# Lookup anti-join with index that contains all columns in the join condition.
opt
SELECT m, n FROM small WHERE NOT EXISTS(SELECT 1 FROM abcd WHERE m = a)
----
anti-join (lookup abcd@secondary)
 ├── columns: m:1 n:2
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters (true)

# We should not generate a lookup anti-join when the index doesn't contain all
# columns in the join condition.
opt
SELECT m, n FROM small WHERE NOT EXISTS(SELECT 1 FROM abcd WHERE m = a AND n = c)
----
anti-join (hash)
 ├── columns: m:1 n:2
 ├── scan small
 │    └── columns: m:1 n:2
 ├── scan abcd
 │    └── columns: a:5 c:7
 └── filters
      ├── m:1 = a:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── n:2 = c:7 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# --------------------------------------------------
# GenerateLookupJoinsWithFilter
# --------------------------------------------------
#
# The rule and cases are similar to GenerateLookupJoins, except that we have a
# filter that was pushed down to the lookup side (which needs to be pulled back
# into the ON condition).

# Covering case.
opt
SELECT a,b,n,m FROM small JOIN abcd ON a=m AND b>1
----
inner-join (lookup abcd@secondary)
 ├── columns: a:5!null b:6!null n:2 m:1!null
 ├── key columns: [1] = [5]
 ├── fd: (1)==(5), (5)==(1)
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]

# Covering case, left-join.
opt
SELECT a,b,n,m FROM small LEFT JOIN abcd ON a=m AND b>1
----
left-join (lookup abcd@secondary)
 ├── columns: a:5 b:6 n:2 m:1
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]

# Non-covering case.
opt
SELECT * FROM small JOIN abcd ON a=m AND b>1
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 └── filters (true)

# Non-covering case, left join.
opt
SELECT * FROM small LEFT JOIN abcd ON a=m AND b>1
----
left-join (lookup abcd)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── left-join (lookup abcd@secondary)
 │    ├── columns: m:1 n:2 a:5 b:6 abcd.rowid:8
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 └── filters (true)

# Non-covering case, extra filter bound by index.
opt
SELECT * FROM small JOIN abcd ON a=m AND b>n AND b>1
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2!null a:5!null b:6!null c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2!null a:5!null b:6!null abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         ├── b:6 > n:2 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 └── filters (true)

# Non-covering case, extra filter bound by index, left join.
opt
SELECT * FROM small LEFT JOIN abcd ON a=m AND b>n AND b>1
----
left-join (lookup abcd)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── left-join (lookup abcd@secondary)
 │    ├── columns: m:1 n:2 a:5 b:6 abcd.rowid:8
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         ├── b:6 > n:2 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ])]
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 └── filters (true)

# Non-covering case, extra filter not bound by index.
opt
SELECT * FROM small JOIN abcd ON a=m AND c>n AND b>1
----
inner-join (lookup abcd)
 ├── columns: m:1!null n:2!null a:5!null b:6!null c:7!null
 ├── key columns: [8] = [8]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcd@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null abcd.rowid:8!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (8)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 └── filters
      └── c:7 > n:2 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ])]

# Non-covering case, extra filter not bound by index, left join.
# In this case, we can't yet convert to a lookup join (see
# the GenerateLookupJoins custom func).
opt
SELECT * FROM small LEFT JOIN abcd ON a=m AND c>n AND b>1
----
right-join (hash)
 ├── columns: m:1 n:2 a:5 b:6 c:7
 ├── select
 │    ├── columns: a:5 b:6!null c:7
 │    ├── scan abcd
 │    │    └── columns: a:5 b:6 c:7
 │    └── filters
 │         └── b:6 > 1 [outer=(6), constraints=(/6: [/2 - ]; tight)]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      ├── a:5 = m:1 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── c:7 > n:2 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ])]

# Constant columns are projected and used by lookup joiner.
opt
SELECT * FROM small INNER JOIN abcde ON a=m AND b=10
----
inner-join (lookup abcde)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7 d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6), (1)==(5), (5)==(1)
 ├── inner-join (lookup abcde@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7 abcde.rowid:10!null
 │    ├── key columns: [1 12] = [5 6]
 │    ├── fd: ()-->(6), (10)-->(5,7), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null m:1 n:2
 │    │    ├── fd: ()-->(12)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         └── 10 [as="project_const_col_@6":12]
 │    └── filters (true)
 └── filters (true)

# Constant columns not projected if not prefix of an index.
opt
SELECT * FROM small INNER JOIN abcde ON a=m AND c=10
----
inner-join (lookup abcde)
 ├── columns: m:1!null n:2 a:5!null b:6 c:7!null d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(7), (1)==(5), (5)==(1)
 ├── inner-join (lookup abcde@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6 c:7!null abcde.rowid:10!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: ()-->(7), (10)-->(5,6), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── c:7 = 10 [outer=(7), constraints=(/7: [/10 - /10]; tight), fd=()-->(7)]
 └── filters (true)

# Multiple constant columns projected and used by lookup joiner.
opt
SELECT * FROM small INNER JOIN abcde ON a=m AND b=10 AND c=10
----
inner-join (lookup abcde)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6,7), (1)==(5), (5)==(1)
 ├── inner-join (lookup abcde@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null abcde.rowid:10!null
 │    ├── key columns: [1 12 13] = [5 6 7]
 │    ├── fd: ()-->(6,7), (10)-->(5), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null "project_const_col_@7":13!null m:1 n:2
 │    │    ├── fd: ()-->(12,13)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         ├── 10 [as="project_const_col_@6":12]
 │    │         └── 10 [as="project_const_col_@7":13]
 │    └── filters (true)
 └── filters (true)

# Filters are reduced properly as constant filters are extracted.
opt
SELECT * FROM small INNER JOIN abcde ON a=m AND b=10 AND c=10 AND d=10
----
inner-join (lookup abcde)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null d:8!null e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6-8), (1)==(5), (5)==(1)
 ├── inner-join (lookup abcde@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null abcde.rowid:10!null
 │    ├── key columns: [1 12 13] = [5 6 7]
 │    ├── fd: ()-->(6,7), (10)-->(5), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null "project_const_col_@7":13!null m:1 n:2
 │    │    ├── fd: ()-->(12,13)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         ├── 10 [as="project_const_col_@6":12]
 │    │         └── 10 [as="project_const_col_@7":13]
 │    └── filters (true)
 └── filters
      └── d:8 = 10 [outer=(8), constraints=(/8: [/10 - /10]; tight), fd=()-->(8)]

# Non equality filters don't trigger constant projection.
opt
SELECT * FROM small INNER JOIN abcde ON a=m AND b<10
----
inner-join (lookup abcde)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7 d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: (1)==(5), (5)==(1)
 ├── inner-join (lookup abcde@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7 abcde.rowid:10!null
 │    ├── key columns: [1] = [5]
 │    ├── fd: (10)-->(5-7), (1)==(5), (5)==(1)
 │    ├── scan small
 │    │    └── columns: m:1 n:2
 │    └── filters
 │         └── b:6 < 10 [outer=(6), constraints=(/6: (/NULL - /9]; tight)]
 └── filters (true)

# Lookup Joiner uses the constant equality columns at the same time as the explicit
# column equalities.
opt
SELECT a, b, c FROM small INNER LOOKUP JOIN abcde ON m=b AND a=10 AND c=10
----
project
 ├── columns: a:5!null b:6!null c:7!null
 ├── fd: ()-->(5,7)
 └── inner-join (lookup abcde@secondary)
      ├── columns: m:1!null a:5!null b:6!null c:7!null
      ├── flags: force lookup join (into right side)
      ├── key columns: [12 1 13] = [5 6 7]
      ├── fd: ()-->(5,7), (1)==(6), (6)==(1)
      ├── project
      │    ├── columns: "project_const_col_@5":12!null "project_const_col_@7":13!null m:1
      │    ├── fd: ()-->(12,13)
      │    ├── scan small
      │    │    └── columns: m:1
      │    └── projections
      │         ├── 10 [as="project_const_col_@5":12]
      │         └── 10 [as="project_const_col_@7":13]
      └── filters (true)

# Projection of constant columns work with non const expressions as well.
exec-ddl
CREATE TABLE bool_col (a INT, b INT, c bool, d bool, e bool, INDEX (a,b,c))
----

# Projection of constant columns work on boolean expressions.
opt
SELECT * FROM small INNER JOIN bool_col ON a=m AND b=10 AND c=true
----
inner-join (lookup bool_col)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6,7), (1)==(5), (5)==(1)
 ├── inner-join (lookup bool_col@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null bool_col.rowid:10!null
 │    ├── key columns: [1 12 13] = [5 6 7]
 │    ├── fd: ()-->(6,7), (10)-->(5), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null "project_const_col_@7":13!null m:1 n:2
 │    │    ├── fd: ()-->(12,13)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         ├── 10 [as="project_const_col_@6":12]
 │    │         └── true [as="project_const_col_@7":13]
 │    └── filters (true)
 └── filters (true)

opt
SELECT * FROM small INNER JOIN bool_col ON a=m AND b=10 AND c
----
inner-join (lookup bool_col)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6,7), (1)==(5), (5)==(1)
 ├── inner-join (lookup bool_col@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null bool_col.rowid:10!null
 │    ├── key columns: [1 12 13] = [5 6 7]
 │    ├── fd: ()-->(6,7), (10)-->(5), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null "project_const_col_@7":13!null m:1 n:2
 │    │    ├── fd: ()-->(12,13)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         ├── 10 [as="project_const_col_@6":12]
 │    │         └── true [as="project_const_col_@7":13]
 │    └── filters (true)
 └── filters (true)

opt
SELECT * FROM small INNER JOIN bool_col ON a=m AND b=10 AND NOT c
----
inner-join (lookup bool_col)
 ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null d:8 e:9
 ├── key columns: [10] = [10]
 ├── lookup columns are key
 ├── fd: ()-->(6,7), (1)==(5), (5)==(1)
 ├── inner-join (lookup bool_col@secondary)
 │    ├── columns: m:1!null n:2 a:5!null b:6!null c:7!null bool_col.rowid:10!null
 │    ├── key columns: [1 12 13] = [5 6 7]
 │    ├── fd: ()-->(6,7), (10)-->(5), (1)==(5), (5)==(1)
 │    ├── project
 │    │    ├── columns: "project_const_col_@6":12!null "project_const_col_@7":13!null m:1 n:2
 │    │    ├── fd: ()-->(12,13)
 │    │    ├── scan small
 │    │    │    └── columns: m:1 n:2
 │    │    └── projections
 │    │         ├── 10 [as="project_const_col_@6":12]
 │    │         └── false [as="project_const_col_@7":13]
 │    └── filters (true)
 └── filters (true)

exec-ddl
CREATE TABLE t(pk INT PRIMARY KEY, col0 INT, col1 INT, col2 INT, col4 INT, UNIQUE INDEX (col2))
----

# Make sure we don't generate a lookup join with no key columns (#41676).
opt
SELECT pk FROM t WHERE col4 = 1 AND col0 = 1 AND col2 IN (SELECT col0 FROM t WHERE col0 = 1 AND col2 IS NULL);
----
project
 ├── columns: pk:1!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1)
 └── semi-join (cross)
      ├── columns: pk:1!null col0:2!null col2:4!null col4:5!null
      ├── cardinality: [0 - 1]
      ├── key: ()
      ├── fd: ()-->(1,2,4,5)
      ├── select
      │    ├── columns: pk:1!null col0:2!null col2:4!null col4:5!null
      │    ├── cardinality: [0 - 1]
      │    ├── key: ()
      │    ├── fd: ()-->(1,2,4,5)
      │    ├── index-join t
      │    │    ├── columns: pk:1!null col0:2 col2:4 col4:5
      │    │    ├── cardinality: [0 - 1]
      │    │    ├── key: ()
      │    │    ├── fd: ()-->(1,2,4,5)
      │    │    └── scan t@secondary
      │    │         ├── columns: pk:1!null col2:4!null
      │    │         ├── constraint: /4: [/1 - /1]
      │    │         ├── cardinality: [0 - 1]
      │    │         ├── key: ()
      │    │         └── fd: ()-->(1,4)
      │    └── filters
      │         ├── col4:5 = 1 [outer=(5), constraints=(/5: [/1 - /1]; tight), fd=()-->(5)]
      │         └── col0:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      ├── select
      │    ├── columns: col0:8!null col2:10
      │    ├── lax-key: (10)
      │    ├── fd: ()-->(8,10)
      │    ├── index-join t
      │    │    ├── columns: col0:8 col2:10
      │    │    ├── lax-key: (8,10)
      │    │    ├── fd: ()-->(10), (10)~~>(8)
      │    │    └── scan t@secondary
      │    │         ├── columns: pk:7!null col2:10
      │    │         ├── constraint: /10: [/NULL - /NULL]
      │    │         ├── key: (7)
      │    │         └── fd: ()-->(10), (10)~~>(7)
      │    └── filters
      │         └── col0:8 = 1 [outer=(8), constraints=(/8: [/1 - /1]; tight), fd=()-->(8)]
      └── filters (true)

# Lookup semi-join with covering index.
opt
SELECT m, n FROM small WHERE EXISTS(SELECT 1 FROM abcd WHERE m = a AND a > b)
----
semi-join (lookup abcd@secondary)
 ├── columns: m:1 n:2
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      └── a:5 > b:6 [outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ])]

# We should not generate a lookup semi-join when the index is non-covering.
opt
SELECT m, n FROM small WHERE EXISTS(SELECT 1 FROM abcd WHERE m = a AND n = c AND a > b)
----
semi-join (hash)
 ├── columns: m:1 n:2
 ├── scan small
 │    └── columns: m:1 n:2
 ├── select
 │    ├── columns: a:5!null b:6!null c:7
 │    ├── scan abcd
 │    │    └── columns: a:5 b:6 c:7
 │    └── filters
 │         └── a:5 > b:6 [outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ])]
 └── filters
      ├── m:1 = a:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── n:2 = c:7 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# Lookup anti-join with covering index.
opt
SELECT m, n FROM small WHERE NOT EXISTS(SELECT 1 FROM abcd WHERE m = a AND a > b)
----
anti-join (lookup abcd@secondary)
 ├── columns: m:1 n:2
 ├── key columns: [1] = [5]
 ├── scan small
 │    └── columns: m:1 n:2
 └── filters
      └── a:5 > b:6 [outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ])]

# We should not generate a lookup semi-join when the index is non-covering.
opt
SELECT m, n FROM small WHERE NOT EXISTS(SELECT 1 FROM abcd WHERE m = a AND n = c AND a > b)
----
anti-join (hash)
 ├── columns: m:1 n:2
 ├── scan small
 │    └── columns: m:1 n:2
 ├── select
 │    ├── columns: a:5!null b:6!null c:7
 │    ├── scan abcd
 │    │    └── columns: a:5 b:6 c:7
 │    └── filters
 │         └── a:5 > b:6 [outer=(5,6), constraints=(/5: (/NULL - ]; /6: (/NULL - ])]
 └── filters
      ├── m:1 = a:5 [outer=(1,5), constraints=(/1: (/NULL - ]; /5: (/NULL - ]), fd=(1)==(5), (5)==(1)]
      └── n:2 = c:7 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# --------------------------------------------------
# GenerateLookupJoinsWithFilter + Partial Indexes
# --------------------------------------------------

exec-ddl
CREATE TABLE partial_tab (
    k INT PRIMARY KEY,
    i INT,
    s STRING
)
----

exec-ddl
ALTER TABLE partial_tab INJECT STATISTICS '[
  {
    "columns": ["i"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 10000,
    "distinct_count": 10000
  },
  {
    "columns": ["s"],
    "created_at": "2018-05-01 1:00:00.00000+00:00",
    "row_count": 10000,
    "distinct_count": 50
  }
]'
----

# Storing the index predicate column.

exec-ddl
CREATE INDEX partial_idx ON partial_tab (i) STORING (s) WHERE s IN ('foo', 'bar', 'baz')
----

# Lookup inner-join with no remaining filters.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small JOIN partial_tab ON n = i WHERE s IN ('foo', 'bar', 'baz')
----
project
 ├── columns: m:1
 └── inner-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2!null i:6!null s:7!null
      ├── key columns: [2] = [6]
      ├── fd: (2)==(6), (6)==(2)
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters (true)

# Lookup inner-join with remaining filters.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small JOIN partial_tab ON n = i WHERE s = 'foo'
----
project
 ├── columns: m:1
 └── inner-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2!null i:6!null s:7!null
      ├── key columns: [2] = [6]
      ├── fd: ()-->(7), (2)==(6), (6)==(2)
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters
           └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]

# Lookup semi-join.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE EXISTS (SELECT 1 FROM partial_tab WHERE s = 'foo' AND n = i)
----
project
 ├── columns: m:1
 └── semi-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters
           └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]

# Lookup anti-join.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE NOT EXISTS (SELECT 1 FROM partial_tab WHERE s = 'foo' AND n = i)
----
project
 ├── columns: m:1
 └── anti-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters
           └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]

# Do not generate a lookup join when the predicate is not implied by the filter.
opt
SELECT m FROM small JOIN partial_tab ON n = i WHERE s = 'not_implied'
----
project
 ├── columns: m:1
 └── inner-join (hash)
      ├── columns: m:1 n:2!null i:6!null s:7!null
      ├── fd: ()-->(7), (2)==(6), (6)==(2)
      ├── select
      │    ├── columns: i:6 s:7!null
      │    ├── fd: ()-->(7)
      │    ├── scan partial_tab
      │    │    ├── columns: i:6 s:7
      │    │    └── partial index predicates
      │    │         └── partial_idx: filters
      │    │              └── s:7 IN ('bar', 'baz', 'foo') [outer=(7), constraints=(/7: [/'bar' - /'bar'] [/'baz' - /'baz'] [/'foo' - /'foo']; tight)]
      │    └── filters
      │         └── s:7 = 'not_implied' [outer=(7), constraints=(/7: [/'not_implied' - /'not_implied']; tight), fd=()-->(7)]
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters
           └── n:2 = i:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]

exec-ddl
DROP INDEX partial_idx
----

# Not storing the index predicate column.

exec-ddl
CREATE INDEX partial_idx ON partial_tab (i) WHERE s IN ('foo', 'bar', 'baz')
----

# The remaining filters are empty when the query filters exactly match the
# partial index predicate.
#
# TODO(mgartner): The outer inner-join is not necessary here and should be
# eliminated, like in EliminateIndexJoinInsideProject.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small JOIN partial_tab ON n = i WHERE s IN ('foo', 'bar', 'baz')
----
project
 ├── columns: m:1
 └── inner-join (lookup partial_tab)
      ├── columns: m:1 n:2!null i:6!null s:7!null
      ├── key columns: [5] = [5]
      ├── lookup columns are key
      ├── fd: (2)==(6), (6)==(2)
      ├── inner-join (lookup partial_tab@partial_idx,partial)
      │    ├── columns: m:1 n:2!null k:5!null i:6!null
      │    ├── key columns: [2] = [6]
      │    ├── fd: (5)-->(6), (2)==(6), (6)==(2)
      │    ├── scan small
      │    │    └── columns: m:1 n:2
      │    └── filters (true)
      └── filters (true)

# The remaining filters are not empty when the query filters imply but do not
# exactly match the partial index predicate.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small JOIN partial_tab ON n = i WHERE s = 'foo'
----
project
 ├── columns: m:1
 └── inner-join (lookup partial_tab)
      ├── columns: m:1 n:2!null i:6!null s:7!null
      ├── key columns: [5] = [5]
      ├── lookup columns are key
      ├── fd: ()-->(7), (2)==(6), (6)==(2)
      ├── inner-join (lookup partial_tab@partial_idx,partial)
      │    ├── columns: m:1 n:2!null k:5!null i:6!null
      │    ├── key columns: [2] = [6]
      │    ├── fd: (5)-->(6), (2)==(6), (6)==(2)
      │    ├── scan small
      │    │    └── columns: m:1 n:2
      │    └── filters (true)
      └── filters
           └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]

# Generate a lookup semi-join when the index does not cover "s", but the
# reference to "s" no longer exists in the filters.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE EXISTS (SELECT 1 FROM partial_tab WHERE s IN ('foo', 'bar', 'baz') AND n = i)
----
project
 ├── columns: m:1
 └── semi-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters (true)

# We should not generate a lookup semi-join when the index does not cover "s"
# which is referenced in the remaining filter.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE EXISTS (SELECT 1 FROM partial_tab WHERE s = 'foo' AND n = i)
----
project
 ├── columns: m:1
 └── semi-join (hash)
      ├── columns: m:1 n:2
      ├── scan small
      │    └── columns: m:1 n:2
      ├── select
      │    ├── columns: i:6 s:7!null
      │    ├── fd: ()-->(7)
      │    ├── index-join partial_tab
      │    │    ├── columns: i:6 s:7
      │    │    └── scan partial_tab@partial_idx,partial
      │    │         ├── columns: k:5!null i:6
      │    │         ├── key: (5)
      │    │         └── fd: (5)-->(6)
      │    └── filters
      │         └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]
      └── filters
           └── n:2 = i:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]

# Generate a lookup anti-join when the index does not cover "s", but the
# reference to "s" no longer exists in the filters.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE NOT EXISTS (SELECT 1 FROM partial_tab WHERE s IN ('foo', 'bar', 'baz') AND n = i)
----
project
 ├── columns: m:1
 └── anti-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── scan small
      │    └── columns: m:1 n:2
      └── filters (true)

# We should not generate a lookup anti-join when the index does not cover "s"
# which is referenced in the remaining filter.
opt expect=GenerateLookupJoinsWithFilter
SELECT m FROM small WHERE NOT EXISTS (SELECT 1 FROM partial_tab WHERE s = 'foo' AND n = i)
----
project
 ├── columns: m:1
 └── anti-join (hash)
      ├── columns: m:1 n:2
      ├── scan small
      │    └── columns: m:1 n:2
      ├── select
      │    ├── columns: i:6 s:7!null
      │    ├── fd: ()-->(7)
      │    ├── index-join partial_tab
      │    │    ├── columns: i:6 s:7
      │    │    └── scan partial_tab@partial_idx,partial
      │    │         ├── columns: k:5!null i:6
      │    │         ├── key: (5)
      │    │         └── fd: (5)-->(6)
      │    └── filters
      │         └── s:7 = 'foo' [outer=(7), constraints=(/7: [/'foo' - /'foo']; tight), fd=()-->(7)]
      └── filters
           └── n:2 = i:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]

# A lookup semi-join on a partial index should have the same cost as a lookup
# semi-join on a non-partial index.
exec-ddl
CREATE INDEX full_idx ON partial_tab (i)
----

opt format=show-cost
SELECT m FROM small WHERE EXISTS (SELECT 1 FROM partial_tab WHERE n = i)
----
project
 ├── columns: m:1
 ├── cost: 234.836
 └── semi-join (lookup partial_tab@full_idx)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── cost: 234.726
      ├── scan small
      │    ├── columns: m:1 n:2
      │    └── cost: 14.52
      └── filters (true)

opt format=show-cost
SELECT m FROM small WHERE EXISTS (SELECT 1 FROM partial_tab WHERE s IN ('foo', 'bar', 'baz') AND n = i)
----
project
 ├── columns: m:1
 ├── cost: 234.836
 └── semi-join (lookup partial_tab@partial_idx,partial)
      ├── columns: m:1 n:2
      ├── key columns: [2] = [6]
      ├── cost: 234.726
      ├── scan small
      │    ├── columns: m:1 n:2
      │    └── cost: 14.52
      └── filters (true)

# -------------------------------------------------------
# GenerateInvertedJoins + GenerateInvertedJoinsFromSelect
# -------------------------------------------------------

exec-ddl
CREATE TABLE nyc_census_blocks (
  gid serial PRIMARY KEY,
  blkid varchar(15),
  popn_total float8,
  popn_white float8,
  popn_black float8,
  popn_nativ float8,
  popn_asian float8,
  popn_other float8,
  boroname varchar(32),
  geom GEOMETRY(MULTIPOLYGON,4326),
  INVERTED INDEX nyc_census_blocks_geo_idx (geom)
)
----

exec-ddl
CREATE TABLE nyc_neighborhoods (
  gid serial PRIMARY KEY,
  boroname varchar(43),
  name varchar(64),
  geom GEOMETRY(MULTIPOLYGON,4326),
  INVERTED INDEX nyc_neighborhoods_geo_idx (geom)
)
----

exec-ddl
ALTER TABLE nyc_census_blocks INJECT STATISTICS '[
  {
    "columns": ["gid"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 38794,
    "distinct_count": 38794
  },
  {
    "columns": ["boroname"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 38794,
    "distinct_count": 5
  }
]'
----

exec-ddl
ALTER TABLE nyc_neighborhoods INJECT STATISTICS '[
  {
    "columns": ["gid"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 129,
    "distinct_count": 129
  },
  {
    "columns": ["boroname"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 129,
    "distinct_count": 5
  },
  {
    "columns": ["name"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 129,
    "distinct_count": 129
  }
]'
----

# This query calculates the population density of two different neighborhoods
# in New York City.
opt expect=GenerateInvertedJoins
SELECT
  n.name,
  Sum(c.popn_total) / (ST_Area(n.geom) / 1000000.0) AS popn_per_sqkm
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods AS n
ON ST_Intersects(n.geom, c.geom) AND c.boroname = n.boroname
WHERE n.name = 'Upper West Side'
OR n.name = 'Upper East Side'
GROUP BY n.name, n.geom
----
project
 ├── columns: name:15!null popn_per_sqkm:20
 ├── immutable
 ├── group-by
 │    ├── columns: name:15!null n.geom:16!null sum:19
 │    ├── grouping columns: name:15!null n.geom:16!null
 │    ├── immutable
 │    ├── key: (15,16)
 │    ├── fd: (15,16)-->(19)
 │    ├── inner-join (lookup nyc_census_blocks)
 │    │    ├── columns: popn_total:3 c.boroname:9!null c.geom:10!null n.boroname:14!null name:15!null n.geom:16!null
 │    │    ├── key columns: [1] = [1]
 │    │    ├── lookup columns are key
 │    │    ├── immutable
 │    │    ├── fd: (9)==(14), (14)==(9)
 │    │    ├── inner-join (inverted-lookup nyc_census_blocks@nyc_census_blocks_geo_idx)
 │    │    │    ├── columns: c.gid:1!null n.boroname:14 name:15!null n.geom:16
 │    │    │    ├── inverted-expr
 │    │    │    │    └── st_intersects(n.geom:16, c.geom:10)
 │    │    │    ├── select
 │    │    │    │    ├── columns: n.boroname:14 name:15!null n.geom:16
 │    │    │    │    ├── scan n
 │    │    │    │    │    └── columns: n.boroname:14 name:15 n.geom:16
 │    │    │    │    └── filters
 │    │    │    │         └── (name:15 = 'Upper West Side') OR (name:15 = 'Upper East Side') [outer=(15), constraints=(/15: [/'Upper East Side' - /'Upper East Side'] [/'Upper West Side' - /'Upper West Side']; tight)]
 │    │    │    └── filters (true)
 │    │    └── filters
 │    │         ├── st_intersects(n.geom:16, c.geom:10) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
 │    │         └── c.boroname:9 = n.boroname:14 [outer=(9,14), constraints=(/9: (/NULL - ]; /14: (/NULL - ]), fd=(9)==(14), (14)==(9)]
 │    └── aggregations
 │         └── sum [as=sum:19, outer=(3)]
 │              └── popn_total:3
 └── projections
      └── sum:19 / (st_area(n.geom:16) / 1e+06) [as=popn_per_sqkm:20, outer=(16,19), immutable]

memo expect=GenerateInvertedJoins
SELECT
  n.name,
  Sum(c.popn_total) / (ST_Area(n.geom) / 1000000.0) AS popn_per_sqkm
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods AS n
ON ST_Intersects(n.geom, c.geom) AND c.boroname = n.boroname
WHERE n.name = 'Upper West Side'
OR n.name = 'Upper East Side'
GROUP BY n.name, n.geom
----
memo (optimized, ~28KB, required=[presentation: name:15,popn_per_sqkm:20])
 ├── G1: (project G2 G3 name)
 │    └── [presentation: name:15,popn_per_sqkm:20]
 │         ├── best: (project G2 G3 name)
 │         └── cost: 7312.15
 ├── G2: (group-by G4 G5 cols=(15,16))
 │    └── []
 │         ├── best: (group-by G4 G5 cols=(15,16))
 │         └── cost: 7312.10
 ├── G3: (projections G6)
 ├── G4: (inner-join G7 G8 G9) (inner-join G8 G7 G9) (lookup-join G10 G11 nyc_neighborhoods,keyCols=[13],outCols=(3,9,10,14-16)) (lookup-join G12 G9 nyc_census_blocks,keyCols=[1],outCols=(3,9,10,14-16))
 │    └── []
 │         ├── best: (lookup-join G12 G9 nyc_census_blocks,keyCols=[1],outCols=(3,9,10,14-16))
 │         └── cost: 7305.98
 ├── G5: (aggregations G13)
 ├── G6: (div G14 G15)
 ├── G7: (scan c,cols=(3,9,10))
 │    └── []
 │         ├── best: (scan c,cols=(3,9,10))
 │         └── cost: 43841.24
 ├── G8: (select G16 G17)
 │    └── []
 │         ├── best: (select G16 G17)
 │         └── cost: 143.36
 ├── G9: (filters G18 G19)
 ├── G10: (inverted-join G7 G20 nyc_neighborhoods@nyc_neighborhoods_geo_idx)
 │    └── []
 │         ├── best: (inverted-join G7 G20 nyc_neighborhoods@nyc_neighborhoods_geo_idx)
 │         └── cost: 921811.54
 ├── G11: (filters G18 G19 G21)
 ├── G12: (inverted-join G8 G20 nyc_census_blocks@nyc_census_blocks_geo_idx)
 │    └── []
 │         ├── best: (inverted-join G8 G20 nyc_census_blocks@nyc_census_blocks_geo_idx)
 │         └── cost: 1766.17
 ├── G13: (sum G22)
 ├── G14: (variable sum)
 ├── G15: (div G23 G24)
 ├── G16: (scan n,cols=(14-16))
 │    └── []
 │         ├── best: (scan n,cols=(14-16))
 │         └── cost: 142.05
 ├── G17: (filters G21)
 ├── G18: (function G25 st_intersects)
 ├── G19: (eq G26 G27)
 ├── G20: (filters)
 ├── G21: (or G28 G29)
 ├── G22: (variable popn_total)
 ├── G23: (function G30 st_area)
 ├── G24: (const 1e+06)
 ├── G25: (scalar-list G31 G32)
 ├── G26: (variable c.boroname)
 ├── G27: (variable n.boroname)
 ├── G28: (eq G33 G34)
 ├── G29: (eq G33 G35)
 ├── G30: (scalar-list G31)
 ├── G31: (variable n.geom)
 ├── G32: (variable c.geom)
 ├── G33: (variable name)
 ├── G34: (const 'Upper West Side')
 └── G35: (const 'Upper East Side')

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DWithin(c.geom, n.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dwithin(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dwithin(c.geom:10, n.geom:16, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Same test as above, but with arguments commuted.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DWithin(n.geom, c.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dwithin(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dwithin(n.geom:16, c.geom:10, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(c.geom, n.geom)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_covers(c.geom:10, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Same test as above, but with arguments commuted.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(n.geom, c.geom)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_coveredby(c.geom:10, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_covers(n.geom:16, c.geom:10) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Case for ST_DWithinExclusive.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DWithinExclusive(c.geom, n.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dwithinexclusive(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dwithinexclusive(c.geom:10, n.geom:16, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Commuted version of previous test.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DWithinExclusive(n.geom, c.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dwithin(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dwithinexclusive(n.geom:16, c.geom:10, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Complex join filter.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(n.geom, c.geom)
  AND (ST_DWithin(c.geom, n.geom, 50) OR ST_Intersects(n.geom, 'LINESTRING ( 0 0, 0 2 )'::geometry))
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_coveredby(c.geom:10, n.geom:16) AND (st_dwithin(c.geom:10, n.geom:16, 50.0) OR st_intersects('0102000000020000000000000000000000000000000000000000000000000000000000000000000040', n.geom:16))
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           ├── st_covers(n.geom:16, c.geom:10) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
           └── st_dwithin(c.geom:10, n.geom:16, 50.0) OR st_intersects(n.geom:16, '0102000000020000000000000000000000000000000000000000000000000000000000000000000040') [outer=(10,16), immutable, constraints=(/16: (/NULL - ])]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DFullyWithin(c.geom, n.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dfullywithin(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dfullywithin(c.geom:10, n.geom:16, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_DFullyWithinExclusive(c.geom, n.geom, 50)
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_dfullywithinexclusive(c.geom:10, n.geom:16, 50.0)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── st_dfullywithinexclusive(c.geom:10, n.geom:16, 50.0) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

opt expect=GenerateInvertedJoinsFromSelect
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(c.geom, n.geom)
AND ST_Covers('LINESTRING ( 0 0, 0 2 )', n.geom)
AND ST_Covers(c.geom, 'LINESTRING ( 0 0, 0 2 )')
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_census_blocks)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [1] = [1]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_census_blocks@nyc_census_blocks_geo_idx)
      │    ├── columns: c.gid:1!null name:15 n.geom:16!null
      │    ├── inverted-expr
      │    │    └── st_coveredby(n.geom:16, c.geom:10) AND st_coveredby('0102000000020000000000000000000000000000000000000000000000000000000000000000000040', c.geom:10)
      │    ├── immutable
      │    ├── select
      │    │    ├── columns: name:15 n.geom:16!null
      │    │    ├── immutable
      │    │    ├── index-join nyc_neighborhoods
      │    │    │    ├── columns: name:15 n.geom:16
      │    │    │    └── inverted-filter
      │    │    │         ├── columns: n.gid:13!null
      │    │    │         ├── inverted expression: /18
      │    │    │         │    ├── tight: false
      │    │    │         │    └── union spans: ["B\x89", "B\xfd \x00\x00\x00\x00\x00\x00\x00")
      │    │    │         ├── pre-filterer expression
      │    │    │         │    └── st_covers('0102000000020000000000000000000000000000000000000000000000000000000000000000000040', n.geom:16)
      │    │    │         ├── key: (13)
      │    │    │         └── scan n@nyc_neighborhoods_geo_idx
      │    │    │              ├── columns: n.gid:13!null n.geom_inverted_key:18!null
      │    │    │              ├── inverted constraint: /18/13
      │    │    │              │    └── spans: ["B\x89", "B\xfd \x00\x00\x00\x00\x00\x00\x00")
      │    │    │              ├── flags: force-index=nyc_neighborhoods_geo_idx
      │    │    │              ├── key: (13)
      │    │    │              └── fd: (13)-->(18)
      │    │    └── filters
      │    │         └── st_covers('0102000000020000000000000000000000000000000000000000000000000000000000000000000040', n.geom:16) [outer=(16), immutable, constraints=(/16: (/NULL - ])]
      │    └── filters (true)
      └── filters
           ├── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
           └── st_covers(c.geom:10, '0102000000020000000000000000000000000000000000000000000000000000000000000000000040') [outer=(10), immutable, constraints=(/10: (/NULL - ])]

opt expect=GenerateInvertedJoinsFromSelect
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(c.geom, n.geom) AND c.boroname = 'Manhattan' AND n.name LIKE 'Upper%'
----
project
 ├── columns: name:15!null boroname:9!null
 ├── immutable
 ├── fd: ()-->(9)
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9!null c.geom:10!null name:15!null n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── fd: ()-->(9)
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9!null c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_covers(c.geom:10, n.geom:16)
      │    ├── fd: ()-->(9)
      │    ├── select
      │    │    ├── columns: c.boroname:9!null c.geom:10
      │    │    ├── fd: ()-->(9)
      │    │    ├── scan c
      │    │    │    └── columns: c.boroname:9 c.geom:10
      │    │    └── filters
      │    │         └── c.boroname:9 = 'Manhattan' [outer=(9), constraints=(/9: [/'Manhattan' - /'Manhattan']; tight), fd=()-->(9)]
      │    └── filters (true)
      └── filters
           ├── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
           └── name:15 LIKE 'Upper%' [outer=(15), constraints=(/15: [/'Upper' - /'Uppes'); tight)]

# It's not possible to generate an inverted join when there is an OR with a
# non-geospatial function.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON ST_Covers(c.geom, n.geom) OR n.name LIKE 'Upper%'
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (cross)
      ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
      ├── immutable
      ├── scan c
      │    └── columns: c.boroname:9 c.geom:10
      ├── scan n
      │    ├── columns: name:15 n.geom:16
      │    └── flags: force-index=nyc_neighborhoods_geo_idx
      └── filters
           └── st_covers(c.geom:10, n.geom:16) OR (name:15 LIKE 'Upper%') [outer=(10,15,16), immutable]

# Semi-joins are supported by converting them to an inner join wrapped in
# a DistinctOn and a Project.
opt expect=(GenerateInvertedJoins,ConvertSemiToInnerJoin)
SELECT *
FROM nyc_census_blocks AS c
WHERE EXISTS (
  SELECT * FROM nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n WHERE ST_Covers(c.geom, n.geom)
)
----
project
 ├── columns: gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 boroname:9 geom:10
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2-10)
 └── distinct-on
      ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10!null
      ├── grouping columns: c.gid:1!null
      ├── internal-ordering: +1
      ├── immutable
      ├── key: (1)
      ├── fd: (1)-->(2-10)
      ├── inner-join (lookup nyc_neighborhoods)
      │    ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10!null n.geom:16!null
      │    ├── key columns: [13] = [13]
      │    ├── lookup columns are key
      │    ├── immutable
      │    ├── fd: (1)-->(2-10)
      │    ├── ordering: +1
      │    ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    │    ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10 n.gid:13!null
      │    │    ├── inverted-expr
      │    │    │    └── st_covers(c.geom:10, n.geom:16)
      │    │    ├── key: (1,13)
      │    │    ├── fd: (1)-->(2-10)
      │    │    ├── ordering: +1
      │    │    ├── scan c
      │    │    │    ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10
      │    │    │    ├── key: (1)
      │    │    │    ├── fd: (1)-->(2-10)
      │    │    │    └── ordering: +1
      │    │    └── filters (true)
      │    └── filters
      │         └── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
      └── aggregations
           ├── const-agg [as=blkid:2, outer=(2)]
           │    └── blkid:2
           ├── const-agg [as=popn_total:3, outer=(3)]
           │    └── popn_total:3
           ├── const-agg [as=popn_white:4, outer=(4)]
           │    └── popn_white:4
           ├── const-agg [as=popn_black:5, outer=(5)]
           │    └── popn_black:5
           ├── const-agg [as=popn_nativ:6, outer=(6)]
           │    └── popn_nativ:6
           ├── const-agg [as=popn_asian:7, outer=(7)]
           │    └── popn_asian:7
           ├── const-agg [as=popn_other:8, outer=(8)]
           │    └── popn_other:8
           ├── const-agg [as=c.boroname:9, outer=(9)]
           │    └── c.boroname:9
           └── const-agg [as=c.geom:10, outer=(10)]
                └── c.geom:10

# Anti-joins are supported by converting them to a left join join wrapped in a
# select. The left join is later converted to an inner join.

# Anti-join in which the right-hand side is a Scan.
# In this test, all columns from the subquery (right hand side of the anti-join)
# are pruned during normalization, so ConvertAntiToLeftJoin has to add back a
# not-null column (the primary key) using EnsureNotNullCol.
opt expect=(ConvertAntiToLeftJoin,GenerateInvertedJoins)
SELECT *
FROM nyc_census_blocks AS c
WHERE NOT EXISTS (
  SELECT * FROM nyc_neighborhoods AS n WHERE ST_Covers(c.geom, n.geom)
)
----
project
 ├── columns: gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 boroname:9 geom:10
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2-10)
 └── select
      ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10 n.gid:13 n.geom:16
      ├── immutable
      ├── key: (1)
      ├── fd: ()-->(13,16), (1)-->(2-10)
      ├── left-join (lookup nyc_neighborhoods)
      │    ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10 n.gid:13 n.geom:16
      │    ├── key columns: [13] = [13]
      │    ├── lookup columns are key
      │    ├── immutable
      │    ├── key: (1,13)
      │    ├── fd: (1)-->(2-10), (13)-->(16)
      │    ├── left-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    │    ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10 n.gid:13 continuation:39
      │    │    ├── inverted-expr
      │    │    │    └── st_covers(c.geom:10, n.geom:16)
      │    │    ├── key: (1,13)
      │    │    ├── fd: (1)-->(2-10), (13)-->(39)
      │    │    ├── scan c
      │    │    │    ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10
      │    │    │    ├── key: (1)
      │    │    │    └── fd: (1)-->(2-10)
      │    │    └── filters (true)
      │    └── filters
      │         └── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]
      └── filters
           └── n.gid:13 IS NOT DISTINCT FROM CAST(NULL AS INT8) [outer=(13), constraints=(/13: [/NULL - /NULL]; tight), fd=()-->(13)]

# TODO: why is this not causing the paired joins -- we can evaluate the
# n.name LIKE 'Upper%' in the lookup join.

# Anti-join in which the right-hand side is a Scan wrapped in a Select.
# In this test, the nyc_neighborhoods.name column is needed for the predicate.
# Since n.name LIKE 'Upper%' is a null-rejecting predicate, there is no need to
# add another not-null column to the right-hand side (so EnsureNotNullCol is a
# no-op).
opt expect=(ConvertAntiToLeftJoin,GenerateInvertedJoinsFromSelect)
SELECT boroname
FROM nyc_census_blocks AS c
WHERE NOT EXISTS (
  SELECT 1 FROM nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n WHERE ST_Covers(c.geom, n.geom)
  AND c.boroname = 'Manhattan' AND n.name LIKE 'Upper%'
)
----
project
 ├── columns: boroname:9
 ├── immutable
 └── project
      ├── columns: c.boroname:9 c.geom:10
      ├── immutable
      └── select
           ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
           ├── immutable
           ├── fd: ()-->(15)
           ├── with &1
           │    ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
           │    ├── immutable
           │    ├── project
           │    │    ├── columns: gid:20!null boroname:21 geom:22
           │    │    ├── key: (20)
           │    │    ├── fd: (20)-->(21,22)
           │    │    ├── scan c
           │    │    │    ├── columns: c.gid:1!null c.boroname:9 c.geom:10
           │    │    │    ├── key: (1)
           │    │    │    └── fd: (1)-->(9,10)
           │    │    └── projections
           │    │         ├── c.gid:1 [as=gid:20, outer=(1)]
           │    │         ├── c.boroname:9 [as=boroname:21, outer=(9)]
           │    │         └── c.geom:10 [as=geom:22, outer=(10)]
           │    └── project
           │         ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
           │         ├── immutable
           │         └── left-join (hash)
           │              ├── columns: c.gid:1!null c.boroname:9 c.geom:10 name:15 n.geom:16 gid:23 boroname:24 geom:25
           │              ├── multiplicity: left-rows(one-or-more), right-rows(zero-or-one)
           │              ├── immutable
           │              ├── fd: (1)-->(9,10), (23)-->(25)
           │              ├── with-scan &1
           │              │    ├── columns: c.gid:1!null c.boroname:9 c.geom:10
           │              │    ├── mapping:
           │              │    │    ├──  gid:20 => c.gid:1
           │              │    │    ├──  boroname:21 => c.boroname:9
           │              │    │    └──  geom:22 => c.geom:10
           │              │    ├── key: (1)
           │              │    └── fd: (1)-->(9,10)
           │              ├── inner-join (lookup nyc_neighborhoods)
           │              │    ├── columns: name:15!null n.geom:16!null gid:23!null boroname:24!null geom:25!null
           │              │    ├── key columns: [13] = [13]
           │              │    ├── lookup columns are key
           │              │    ├── immutable
           │              │    ├── fd: ()-->(24), (23)-->(25)
           │              │    ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
           │              │    │    ├── columns: n.gid:13!null gid:23!null boroname:24!null geom:25
           │              │    │    ├── inverted-expr
           │              │    │    │    └── st_covers(geom:25, n.geom:16)
           │              │    │    ├── key: (13,23)
           │              │    │    ├── fd: ()-->(24), (23)-->(25)
           │              │    │    ├── select
           │              │    │    │    ├── columns: gid:23!null boroname:24!null geom:25
           │              │    │    │    ├── key: (23)
           │              │    │    │    ├── fd: ()-->(24), (23)-->(25)
           │              │    │    │    ├── with-scan &1
           │              │    │    │    │    ├── columns: gid:23!null boroname:24 geom:25
           │              │    │    │    │    ├── mapping:
           │              │    │    │    │    │    ├──  gid:20 => gid:23
           │              │    │    │    │    │    ├──  boroname:21 => boroname:24
           │              │    │    │    │    │    └──  geom:22 => geom:25
           │              │    │    │    │    ├── key: (23)
           │              │    │    │    │    └── fd: (23)-->(24,25)
           │              │    │    │    └── filters
           │              │    │    │         └── boroname:24 = 'Manhattan' [outer=(24), constraints=(/24: [/'Manhattan' - /'Manhattan']; tight), fd=()-->(24)]
           │              │    │    └── filters (true)
           │              │    └── filters
           │              │         ├── st_covers(geom:25, n.geom:16) [outer=(16,25), immutable, constraints=(/16: (/NULL - ]; /25: (/NULL - ])]
           │              │         └── name:15 LIKE 'Upper%' [outer=(15), constraints=(/15: [/'Upper' - /'Uppes'); tight)]
           │              └── filters
           │                   └── c.gid:1 = gid:23 [outer=(1,23), constraints=(/1: (/NULL - ]; /23: (/NULL - ]), fd=(1)==(23), (23)==(1)]
           └── filters
                └── name:15 IS NOT DISTINCT FROM CAST(NULL AS VARCHAR(64)) [outer=(15), constraints=(/15: [/NULL - /NULL]; tight), fd=()-->(15)]

# Left joins are supported by converting them to an inner join wrapped in a
# left join.
opt expect=(GenerateInvertedJoins,ConvertLeftToInnerJoin)
SELECT *
FROM nyc_census_blocks AS c
LEFT JOIN nyc_neighborhoods AS n ON ST_Covers(c.geom, n.geom)
----
left-join (lookup nyc_neighborhoods)
 ├── columns: gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 boroname:9 geom:10 gid:13 boroname:14 name:15 geom:16
 ├── key columns: [13] = [13]
 ├── lookup columns are key
 ├── immutable
 ├── key: (1,13)
 ├── fd: (1)-->(2-10), (13)-->(14-16)
 ├── left-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
 │    ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10 n.gid:13 continuation:39
 │    ├── inverted-expr
 │    │    └── st_covers(c.geom:10, n.geom:16)
 │    ├── key: (1,13)
 │    ├── fd: (1)-->(2-10), (13)-->(39)
 │    ├── scan c
 │    │    ├── columns: c.gid:1!null c.blkid:2 c.popn_total:3 c.popn_white:4 c.popn_black:5 c.popn_nativ:6 c.popn_asian:7 c.popn_other:8 c.boroname:9 c.geom:10
 │    │    ├── key: (1)
 │    │    └── fd: (1)-->(2-10)
 │    └── filters (true)
 └── filters
      └── st_covers(c.geom:10, n.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# Case with a CTE and GROUP BY wrapping the left join.
opt expect=(GenerateInvertedJoins,ConvertLeftToInnerJoin)
WITH q AS (
  SELECT * FROM nyc_census_blocks WHERE boroname = 'Manhattan'
)
SELECT count(*), (SELECT count(*) FROM q) FROM (
  SELECT n.boroname
  FROM q
  LEFT JOIN nyc_neighborhoods AS n ON ST_Intersects(q.geom, n.geom)
) GROUP BY boroname
----
with &1 (q)
 ├── columns: count:29!null count:41
 ├── immutable
 ├── fd: ()-->(41)
 ├── select
 │    ├── columns: nyc_census_blocks.gid:1!null nyc_census_blocks.blkid:2 nyc_census_blocks.popn_total:3 nyc_census_blocks.popn_white:4 nyc_census_blocks.popn_black:5 nyc_census_blocks.popn_nativ:6 nyc_census_blocks.popn_asian:7 nyc_census_blocks.popn_other:8 nyc_census_blocks.boroname:9!null nyc_census_blocks.geom:10
 │    ├── key: (1)
 │    ├── fd: ()-->(9), (1)-->(2-8,10)
 │    ├── scan nyc_census_blocks
 │    │    ├── columns: nyc_census_blocks.gid:1!null nyc_census_blocks.blkid:2 nyc_census_blocks.popn_total:3 nyc_census_blocks.popn_white:4 nyc_census_blocks.popn_black:5 nyc_census_blocks.popn_nativ:6 nyc_census_blocks.popn_asian:7 nyc_census_blocks.popn_other:8 nyc_census_blocks.boroname:9 nyc_census_blocks.geom:10
 │    │    ├── key: (1)
 │    │    └── fd: (1)-->(2-10)
 │    └── filters
 │         └── nyc_census_blocks.boroname:9 = 'Manhattan' [outer=(9), constraints=(/9: [/'Manhattan' - /'Manhattan']; tight), fd=()-->(9)]
 └── project
      ├── columns: count:41 count_rows:29!null
      ├── immutable
      ├── fd: ()-->(41)
      ├── group-by
      │    ├── columns: n.boroname:24 count_rows:29!null
      │    ├── grouping columns: n.boroname:24
      │    ├── immutable
      │    ├── key: (24)
      │    ├── fd: (24)-->(29)
      │    ├── left-join (lookup nyc_neighborhoods)
      │    │    ├── columns: geom:22 n.boroname:24 n.geom:26
      │    │    ├── key columns: [23] = [23]
      │    │    ├── lookup columns are key
      │    │    ├── immutable
      │    │    ├── left-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    │    │    ├── columns: geom:22 n.gid:23 continuation:47
      │    │    │    ├── inverted-expr
      │    │    │    │    └── st_intersects(geom:22, n.geom:26)
      │    │    │    ├── fd: (23)-->(47)
      │    │    │    ├── with-scan &1 (q)
      │    │    │    │    ├── columns: geom:22
      │    │    │    │    └── mapping:
      │    │    │    │         └──  nyc_census_blocks.geom:10 => geom:22
      │    │    │    └── filters (true)
      │    │    └── filters
      │    │         └── st_intersects(geom:22, n.geom:26) [outer=(22,26), immutable, constraints=(/22: (/NULL - ]; /26: (/NULL - ])]
      │    └── aggregations
      │         └── count-rows [as=count_rows:29]
      └── projections
           └── subquery [as=count:41, subquery]
                └── scalar-group-by
                     ├── columns: count_rows:40!null
                     ├── cardinality: [1 - 1]
                     ├── key: ()
                     ├── fd: ()-->(40)
                     ├── with-scan &1 (q)
                     │    └── mapping:
                     └── aggregations
                          └── count-rows [as=count_rows:40]

# No-op due to inner join on the right side.
opt expect-not=ConvertLeftToInnerJoin
SELECT *
FROM nyc_census_blocks AS c
LEFT JOIN (
  SELECT n1.*, n2.name FROM nyc_neighborhoods n1 JOIN nyc_neighborhoods n2 ON n1.boroname LIKE n2.boroname
) AS n ON ST_Covers(c.geom, n.geom)
----
project
 ├── columns: gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 boroname:9 geom:10 gid:13 boroname:14 name:15 geom:16 name:21
 ├── immutable
 ├── fd: (1)-->(2-10), (13)-->(14-16)
 └── left-join (cross)
      ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10 n1.gid:13 n1.boroname:14 n1.name:15 n1.geom:16 n2.boroname:20 n2.name:21
      ├── immutable
      ├── fd: (1)-->(2-10), (13)-->(14-16)
      ├── scan c
      │    ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10
      │    ├── key: (1)
      │    └── fd: (1)-->(2-10)
      ├── inner-join (cross)
      │    ├── columns: n1.gid:13!null n1.boroname:14!null n1.name:15 n1.geom:16 n2.boroname:20!null n2.name:21
      │    ├── fd: (13)-->(14-16)
      │    ├── scan n1
      │    │    ├── columns: n1.gid:13!null n1.boroname:14 n1.name:15 n1.geom:16
      │    │    ├── key: (13)
      │    │    └── fd: (13)-->(14-16)
      │    ├── scan n2
      │    │    └── columns: n2.boroname:20 n2.name:21
      │    └── filters
      │         └── n1.boroname:14 LIKE n2.boroname:20 [outer=(14,20), constraints=(/14: (/NULL - ]; /20: (/NULL - ])]
      └── filters
           └── st_covers(c.geom:10, n1.geom:16) [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# No-op due to lack of geospatial function in the ON condition.
opt expect-not=(ConvertLeftToInnerJoin)
SELECT *
FROM nyc_census_blocks AS c
LEFT JOIN nyc_neighborhoods AS n ON c.boroname LIKE n.boroname
----
left-join (cross)
 ├── columns: gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 boroname:9 geom:10 gid:13 boroname:14 name:15 geom:16
 ├── key: (1,13)
 ├── fd: (1)-->(2-10), (13)-->(14-16)
 ├── scan c
 │    ├── columns: c.gid:1!null blkid:2 popn_total:3 popn_white:4 popn_black:5 popn_nativ:6 popn_asian:7 popn_other:8 c.boroname:9 c.geom:10
 │    ├── key: (1)
 │    └── fd: (1)-->(2-10)
 ├── scan n
 │    ├── columns: n.gid:13!null n.boroname:14 name:15 n.geom:16
 │    ├── key: (13)
 │    └── fd: (13)-->(14-16)
 └── filters
      └── c.boroname:9 LIKE n.boroname:14 [outer=(9,14), constraints=(/9: (/NULL - ]; /14: (/NULL - ])]

# Bounding box operations.
opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON c.geom::box2d && n.geom
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_intersects(c.geom:10::BOX2D::GEOMETRY, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── c.geom:10::BOX2D && n.geom:16 [outer=(10,16), immutable]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON c.geom::box2d ~ n.geom
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_covers(c.geom:10::BOX2D::GEOMETRY, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── c.geom:10::BOX2D ~ n.geom:16 [outer=(10,16), immutable]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON n.geom ~ c.geom::box2d
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10 name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_coveredby(c.geom:10::BOX2D::GEOMETRY, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── n.geom:16 ~ c.geom:10::BOX2D [outer=(10,16), immutable, constraints=(/16: (/NULL - ])]

opt expect=GenerateInvertedJoins
SELECT
  n.name, c.boroname
FROM nyc_census_blocks AS c
JOIN nyc_neighborhoods@nyc_neighborhoods_geo_idx AS n
ON n.geom ~ c.geom
----
project
 ├── columns: name:15 boroname:9
 ├── immutable
 └── inner-join (lookup nyc_neighborhoods)
      ├── columns: c.boroname:9 c.geom:10!null name:15 n.geom:16!null
      ├── key columns: [13] = [13]
      ├── lookup columns are key
      ├── immutable
      ├── inner-join (inverted-lookup nyc_neighborhoods@nyc_neighborhoods_geo_idx)
      │    ├── columns: c.boroname:9 c.geom:10 n.gid:13!null
      │    ├── inverted-expr
      │    │    └── st_coveredby(c.geom:10, n.geom:16)
      │    ├── scan c
      │    │    └── columns: c.boroname:9 c.geom:10
      │    └── filters (true)
      └── filters
           └── n.geom:16 ~ c.geom:10 [outer=(10,16), immutable, constraints=(/10: (/NULL - ]; /16: (/NULL - ])]

# --------------------------------------------------
# GenerateZigZagJoins
# --------------------------------------------------

# Simple zigzag case - where all requested columns are in the indexes being
# joined.
opt
SELECT q,r FROM pqr WHERE q = 1 AND r = 2
----
inner-join (zigzag pqr@q pqr@r)
 ├── columns: q:2!null r:3!null
 ├── eq columns: [1] = [1]
 ├── left fixed columns: [2] = [1]
 ├── right fixed columns: [3] = [2]
 ├── fd: ()-->(2,3)
 └── filters
      ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      └── r:3 = 2 [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]

opt
SELECT q,r FROM pqr WHERE q = 1 AND r IS NULL
----
inner-join (zigzag pqr@q pqr@r)
 ├── columns: q:2!null r:3
 ├── eq columns: [1] = [1]
 ├── left fixed columns: [2] = [1]
 ├── right fixed columns: [3] = [NULL]
 ├── fd: ()-->(2,3)
 └── filters
      ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      └── r:3 IS NULL [outer=(3), constraints=(/3: [/NULL - /NULL]; tight), fd=()-->(3)]

memo
SELECT q,r FROM pqr WHERE q = 1 AND r = 2
----
memo (optimized, ~13KB, required=[presentation: q:2,r:3])
 ├── G1: (select G2 G3) (zigzag-join G3 pqr@q pqr@r) (select G4 G5) (select G6 G7) (select G8 G7)
 │    └── [presentation: q:2,r:3]
 │         ├── best: (zigzag-join G3 pqr@q pqr@r)
 │         └── cost: 1.93
 ├── G2: (scan pqr,cols=(2,3))
 │    └── []
 │         ├── best: (scan pqr,cols=(2,3))
 │         └── cost: 1074.02
 ├── G3: (filters G9 G10)
 ├── G4: (index-join G11 pqr,cols=(2,3))
 │    └── []
 │         ├── best: (index-join G11 pqr,cols=(2,3))
 │         └── cost: 75.12
 ├── G5: (filters G10)
 ├── G6: (index-join G12 pqr,cols=(2,3))
 │    └── []
 │         ├── best: (index-join G12 pqr,cols=(2,3))
 │         └── cost: 75.12
 ├── G7: (filters G9)
 ├── G8: (index-join G13 pqr,cols=(2,3))
 │    └── []
 │         ├── best: (index-join G13 pqr,cols=(2,3))
 │         └── cost: 75.22
 ├── G9: (eq G14 G15)
 ├── G10: (eq G16 G17)
 ├── G11: (scan pqr@q,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan pqr@q,cols=(1,2),constrained)
 │         └── cost: 14.41
 ├── G12: (scan pqr@r,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@r,cols=(1,3),constrained)
 │         └── cost: 14.41
 ├── G13: (scan pqr@rs,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@rs,cols=(1,3),constrained)
 │         └── cost: 14.51
 ├── G14: (variable q)
 ├── G15: (const 1)
 ├── G16: (variable r)
 └── G17: (const 2)

# Case where the fixed columns are extracted from a complicated expression.
opt
SELECT q,r FROM pqr WHERE q = 1 AND ((r < 1 AND r > 1) OR (r >= 2 AND r <= 2))
----
inner-join (zigzag pqr@q pqr@r)
 ├── columns: q:2!null r:3!null
 ├── eq columns: [1] = [1]
 ├── left fixed columns: [2] = [1]
 ├── right fixed columns: [3] = [2]
 ├── fd: ()-->(2,3)
 └── filters
      ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      └── ((r:3 < 1) AND (r:3 > 1)) OR ((r:3 >= 2) AND (r:3 <= 2)) [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]

# Nested zigzag case - zigzag join needs to be wrapped in a lookup join to
# satisfy required columns.
opt
SELECT q,r,s FROM pqr WHERE q = 1 AND r = 2
----
inner-join (lookup pqr)
 ├── columns: q:2!null r:3!null s:4
 ├── key columns: [1] = [1]
 ├── lookup columns are key
 ├── fd: ()-->(2,3)
 ├── inner-join (zigzag pqr@q pqr@r)
 │    ├── columns: p:1!null q:2!null r:3!null
 │    ├── eq columns: [1] = [1]
 │    ├── left fixed columns: [2] = [1]
 │    ├── right fixed columns: [3] = [2]
 │    ├── fd: ()-->(2,3)
 │    └── filters
 │         ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
 │         └── r:3 = 2 [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]
 └── filters (true)

memo
SELECT q,r,s FROM pqr WHERE q = 1 AND r = 2
----
memo (optimized, ~15KB, required=[presentation: q:2,r:3,s:4])
 ├── G1: (select G2 G3) (lookup-join G4 G5 pqr,keyCols=[1],outCols=(2-4)) (select G6 G7) (select G8 G9) (select G10 G9)
 │    └── [presentation: q:2,r:3,s:4]
 │         ├── best: (lookup-join G4 G5 pqr,keyCols=[1],outCols=(2-4))
 │         └── cost: 7.48
 ├── G2: (scan pqr,cols=(2-4))
 │    └── []
 │         ├── best: (scan pqr,cols=(2-4))
 │         └── cost: 1084.02
 ├── G3: (filters G11 G12)
 ├── G4: (zigzag-join G3 pqr@q pqr@r)
 │    └── []
 │         ├── best: (zigzag-join G3 pqr@q pqr@r)
 │         └── cost: 1.94
 ├── G5: (filters)
 ├── G6: (index-join G13 pqr,cols=(2-4))
 │    └── []
 │         ├── best: (index-join G13 pqr,cols=(2-4))
 │         └── cost: 75.22
 ├── G7: (filters G12)
 ├── G8: (index-join G14 pqr,cols=(2-4))
 │    └── []
 │         ├── best: (index-join G14 pqr,cols=(2-4))
 │         └── cost: 75.22
 ├── G9: (filters G11)
 ├── G10: (index-join G15 pqr,cols=(2-4))
 │    └── []
 │         ├── best: (index-join G15 pqr,cols=(2-4))
 │         └── cost: 75.32
 ├── G11: (eq G16 G17)
 ├── G12: (eq G18 G19)
 ├── G13: (scan pqr@q,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan pqr@q,cols=(1,2),constrained)
 │         └── cost: 14.41
 ├── G14: (scan pqr@r,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@r,cols=(1,3),constrained)
 │         └── cost: 14.41
 ├── G15: (scan pqr@rs,cols=(1,3,4),constrained)
 │    └── []
 │         ├── best: (scan pqr@rs,cols=(1,3,4),constrained)
 │         └── cost: 14.61
 ├── G16: (variable q)
 ├── G17: (const 1)
 ├── G18: (variable r)
 └── G19: (const 2)

# Zigzag with fixed columns of different types.
opt
SELECT q,s FROM pqr WHERE q = 1 AND s = 'foo'
----
inner-join (zigzag pqr@q pqr@s)
 ├── columns: q:2!null s:4!null
 ├── eq columns: [1] = [1]
 ├── left fixed columns: [2] = [1]
 ├── right fixed columns: [4] = ['foo']
 ├── fd: ()-->(2,4)
 └── filters
      ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      └── s:4 = 'foo' [outer=(4), constraints=(/4: [/'foo' - /'foo']; tight), fd=()-->(4)]

memo
SELECT q,s FROM pqr WHERE q = 1 AND s = 'foo'
----
memo (optimized, ~11KB, required=[presentation: q:2,s:4])
 ├── G1: (select G2 G3) (zigzag-join G3 pqr@q pqr@s) (select G4 G5) (select G6 G7)
 │    └── [presentation: q:2,s:4]
 │         ├── best: (zigzag-join G3 pqr@q pqr@s)
 │         └── cost: 1.94
 ├── G2: (scan pqr,cols=(2,4))
 │    └── []
 │         ├── best: (scan pqr,cols=(2,4))
 │         └── cost: 1074.02
 ├── G3: (filters G8 G9)
 ├── G4: (index-join G10 pqr,cols=(2,4))
 │    └── []
 │         ├── best: (index-join G10 pqr,cols=(2,4))
 │         └── cost: 75.12
 ├── G5: (filters G9)
 ├── G6: (index-join G11 pqr,cols=(2,4))
 │    └── []
 │         ├── best: (index-join G11 pqr,cols=(2,4))
 │         └── cost: 75.22
 ├── G7: (filters G8)
 ├── G8: (eq G12 G13)
 ├── G9: (eq G14 G15)
 ├── G10: (scan pqr@q,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan pqr@q,cols=(1,2),constrained)
 │         └── cost: 14.41
 ├── G11: (scan pqr@s,cols=(1,4),constrained)
 │    └── []
 │         ├── best: (scan pqr@s,cols=(1,4),constrained)
 │         └── cost: 14.51
 ├── G12: (variable q)
 ├── G13: (const 1)
 ├── G14: (variable s)
 └── G15: (const 'foo')

# Zigzag with implicit equality column in addition to primary key:
# indexes on (r,s) and (t,s) should be chosen even though s is not being fixed
# in the ON clause.
opt
SELECT r,t FROM pqr WHERE r = 1 AND t = 'foo'
----
inner-join (zigzag pqr@rs pqr@ts)
 ├── columns: r:3!null t:5!null
 ├── eq columns: [4 1] = [4 1]
 ├── left fixed columns: [3] = [1]
 ├── right fixed columns: [5] = ['foo']
 ├── fd: ()-->(3,5)
 └── filters
      ├── r:3 = 1 [outer=(3), constraints=(/3: [/1 - /1]; tight), fd=()-->(3)]
      └── t:5 = 'foo' [outer=(5), constraints=(/5: [/'foo' - /'foo']; tight), fd=()-->(5)]

memo
SELECT r,t FROM pqr WHERE r = 1 AND t = 'foo'
----
memo (optimized, ~13KB, required=[presentation: r:3,t:5])
 ├── G1: (select G2 G3) (zigzag-join G3 pqr@rs pqr@ts) (select G4 G5) (select G6 G5) (select G7 G8)
 │    └── [presentation: r:3,t:5]
 │         ├── best: (zigzag-join G3 pqr@rs pqr@ts)
 │         └── cost: 1.95
 ├── G2: (scan pqr,cols=(3,5))
 │    └── []
 │         ├── best: (scan pqr,cols=(3,5))
 │         └── cost: 1074.02
 ├── G3: (filters G9 G10)
 ├── G4: (index-join G11 pqr,cols=(3,5))
 │    └── []
 │         ├── best: (index-join G11 pqr,cols=(3,5))
 │         └── cost: 75.12
 ├── G5: (filters G10)
 ├── G6: (index-join G12 pqr,cols=(3,5))
 │    └── []
 │         ├── best: (index-join G12 pqr,cols=(3,5))
 │         └── cost: 75.22
 ├── G7: (index-join G13 pqr,cols=(3,5))
 │    └── []
 │         ├── best: (index-join G13 pqr,cols=(3,5))
 │         └── cost: 75.22
 ├── G8: (filters G9)
 ├── G9: (eq G14 G15)
 ├── G10: (eq G16 G17)
 ├── G11: (scan pqr@r,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@r,cols=(1,3),constrained)
 │         └── cost: 14.41
 ├── G12: (scan pqr@rs,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@rs,cols=(1,3),constrained)
 │         └── cost: 14.51
 ├── G13: (scan pqr@ts,cols=(1,5),constrained)
 │    └── []
 │         ├── best: (scan pqr@ts,cols=(1,5),constrained)
 │         └── cost: 14.51
 ├── G14: (variable r)
 ├── G15: (const 1)
 ├── G16: (variable t)
 └── G17: (const 'foo')

# Zigzag with choice between indexes for multiple equality predicates.
opt
SELECT p,q,r,s FROM pqr WHERE q = 1 AND r = 1 AND s = 'foo'
----
inner-join (zigzag pqr@q pqr@s)
 ├── columns: p:1!null q:2!null r:3!null s:4!null
 ├── eq columns: [1] = [1]
 ├── left fixed columns: [2] = [1]
 ├── right fixed columns: [4] = ['foo']
 ├── key: (1)
 ├── fd: ()-->(2-4)
 └── filters
      ├── q:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
      ├── r:3 = 1 [outer=(3), constraints=(/3: [/1 - /1]; tight), fd=()-->(3)]
      └── s:4 = 'foo' [outer=(4), constraints=(/4: [/'foo' - /'foo']; tight), fd=()-->(4)]

# Don't generate a zigzag which has the PK as its equality columns against
# nullable unique indexes where the primary key is not part of the indexed
# columns.

# Regression test for #36051: prior to fixing this, we would try to use the PK
# as the equality column here, but it's not actually part of the key so we
# can't zigzag on it.
opt
SELECT * FROM zz WHERE b IS NULL AND c = 2
----
select
 ├── columns: a:1!null b:2 c:3!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1-3)
 ├── index-join zz
 │    ├── columns: a:1!null b:2 c:3
 │    ├── cardinality: [0 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(1-3)
 │    └── scan zz@idx_c
 │         ├── columns: a:1!null c:3!null
 │         ├── constraint: /3: [/2 - /2]
 │         ├── cardinality: [0 - 1]
 │         ├── key: ()
 │         └── fd: ()-->(1,3)
 └── filters
      └── b:2 IS NULL [outer=(2), constraints=(/2: [/NULL - /NULL]; tight), fd=()-->(2)]

memo
SELECT p,q,r,s FROM pqr WHERE q = 1 AND r = 1 AND s = 'foo'
----
memo (optimized, ~31KB, required=[presentation: p:1,q:2,r:3,s:4])
 ├── G1: (select G2 G3) (lookup-join G4 G5 pqr,keyCols=[1],outCols=(1-4)) (zigzag-join G3 pqr@q pqr@s) (zigzag-join G3 pqr@q pqr@rs) (lookup-join G6 G7 pqr,keyCols=[1],outCols=(1-4)) (select G8 G9) (select G10 G11) (select G12 G7) (select G13 G7)
 │    └── [presentation: p:1,q:2,r:3,s:4]
 │         ├── best: (zigzag-join G3 pqr@q pqr@s)
 │         └── cost: 1.95
 ├── G2: (scan pqr,cols=(1-4))
 │    └── []
 │         ├── best: (scan pqr,cols=(1-4))
 │         └── cost: 1094.02
 ├── G3: (filters G14 G15 G16)
 ├── G4: (zigzag-join G17 pqr@q pqr@r)
 │    └── []
 │         ├── best: (zigzag-join G17 pqr@q pqr@r)
 │         └── cost: 1.94
 ├── G5: (filters G16)
 ├── G6: (zigzag-join G9 pqr@r pqr@s)
 │    └── []
 │         ├── best: (zigzag-join G9 pqr@r pqr@s)
 │         └── cost: 1.95
 ├── G7: (filters G14)
 ├── G8: (index-join G18 pqr,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G18 pqr,cols=(1-4))
 │         └── cost: 75.22
 ├── G9: (filters G15 G16)
 ├── G10: (index-join G19 pqr,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G19 pqr,cols=(1-4))
 │         └── cost: 75.22
 ├── G11: (filters G14 G16)
 ├── G12: (index-join G20 pqr,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G20 pqr,cols=(1-4))
 │         └── cost: 21.76
 ├── G13: (index-join G21 pqr,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G21 pqr,cols=(1-4))
 │         └── cost: 10.51
 ├── G14: (eq G22 G23)
 ├── G15: (eq G24 G23)
 ├── G16: (eq G25 G26)
 ├── G17: (filters G14 G15)
 ├── G18: (scan pqr@q,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan pqr@q,cols=(1,2),constrained)
 │         └── cost: 14.41
 ├── G19: (scan pqr@r,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan pqr@r,cols=(1,3),constrained)
 │         └── cost: 14.41
 ├── G20: (select G27 G28)
 │    └── []
 │         ├── best: (select G27 G28)
 │         └── cost: 14.73
 ├── G21: (scan pqr@rs,cols=(1,3,4),constrained)
 │    └── []
 │         ├── best: (scan pqr@rs,cols=(1,3,4),constrained)
 │         └── cost: 4.98
 ├── G22: (variable q)
 ├── G23: (const 1)
 ├── G24: (variable r)
 ├── G25: (variable s)
 ├── G26: (const 'foo')
 ├── G27: (scan pqr@s,cols=(1,3,4),constrained)
 │    └── []
 │         ├── best: (scan pqr@s,cols=(1,3,4),constrained)
 │         └── cost: 14.61
 └── G28: (filters G15)

# Zigzag joins cannot be planned for indexes where equality columns do not
# immediately follow fixed columns. Here, the only index on t is (t,s,p) and
# s is not a fixed or equal column, so a zigzag join shouldn't be planned.
opt
SELECT q,t FROM pqr WHERE q = 1 AND t = 'foo'
----
select
 ├── columns: q:2!null t:5!null
 ├── fd: ()-->(2,5)
 ├── index-join pqr
 │    ├── columns: q:2 t:5
 │    ├── fd: ()-->(2)
 │    └── scan pqr@q
 │         ├── columns: p:1!null q:2!null
 │         ├── constraint: /2/1: [/1 - /1]
 │         ├── key: (1)
 │         └── fd: ()-->(2)
 └── filters
      └── t:5 = 'foo' [outer=(5), constraints=(/5: [/'foo' - /'foo']; tight), fd=()-->(5)]

memo
SELECT q,t FROM pqr WHERE q = 1 AND t = 'foo'
----
memo (optimized, ~9KB, required=[presentation: q:2,t:5])
 ├── G1: (select G2 G3) (select G4 G5) (select G6 G7)
 │    └── [presentation: q:2,t:5]
 │         ├── best: (select G4 G5)
 │         └── cost: 75.24
 ├── G2: (scan pqr,cols=(2,5))
 │    └── []
 │         ├── best: (scan pqr,cols=(2,5))
 │         └── cost: 1074.02
 ├── G3: (filters G8 G9)
 ├── G4: (index-join G10 pqr,cols=(2,5))
 │    └── []
 │         ├── best: (index-join G10 pqr,cols=(2,5))
 │         └── cost: 75.12
 ├── G5: (filters G9)
 ├── G6: (index-join G11 pqr,cols=(2,5))
 │    └── []
 │         ├── best: (index-join G11 pqr,cols=(2,5))
 │         └── cost: 75.22
 ├── G7: (filters G8)
 ├── G8: (eq G12 G13)
 ├── G9: (eq G14 G15)
 ├── G10: (scan pqr@q,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan pqr@q,cols=(1,2),constrained)
 │         └── cost: 14.41
 ├── G11: (scan pqr@ts,cols=(1,5),constrained)
 │    └── []
 │         ├── best: (scan pqr@ts,cols=(1,5),constrained)
 │         └── cost: 14.51
 ├── G12: (variable q)
 ├── G13: (const 1)
 ├── G14: (variable t)
 └── G15: (const 'foo')

# Don't zigzag on two identical indexes.
memo
SELECT c FROM zz_redundant WHERE b = 1
----
memo (optimized, ~6KB, required=[presentation: c:3])
 ├── G1: (project G2 G3 c)
 │    └── [presentation: c:3]
 │         ├── best: (project G2 G3 c)
 │         └── cost: 14.62
 ├── G2: (select G4 G5) (scan zz_redundant@idx_u,cols=(2,3),constrained) (scan zz_redundant@idx_v,cols=(2,3),constrained)
 │    └── []
 │         ├── best: (scan zz_redundant@idx_u,cols=(2,3),constrained)
 │         └── cost: 14.51
 ├── G3: (projections)
 ├── G4: (scan zz_redundant,cols=(2,3)) (scan zz_redundant@idx_u,cols=(2,3)) (scan zz_redundant@idx_v,cols=(2,3))
 │    └── []
 │         ├── best: (scan zz_redundant,cols=(2,3))
 │         └── cost: 1054.02
 ├── G5: (filters G6)
 ├── G6: (eq G7 G8)
 ├── G7: (variable b)
 └── G8: (const 1)

# GenerateZigzagJoins is disabled in the presence of a row-level locking clause.
opt
SELECT q,r FROM pqr WHERE q = 1 AND r = 2 FOR UPDATE
----
select
 ├── columns: q:2!null r:3!null
 ├── volatile
 ├── fd: ()-->(2,3)
 ├── index-join pqr
 │    ├── columns: q:2 r:3
 │    ├── volatile
 │    ├── fd: ()-->(2)
 │    └── scan pqr@q
 │         ├── columns: p:1!null q:2!null
 │         ├── constraint: /2/1: [/1 - /1]
 │         ├── locking: for-update
 │         ├── volatile
 │         ├── key: (1)
 │         └── fd: ()-->(2)
 └── filters
      └── r:3 = 2 [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]

# --------------------------------------------------
# GenerateInvertedIndexZigzagJoins
# --------------------------------------------------

exec-ddl
CREATE TABLE t5 (
    a INT PRIMARY KEY,
    b JSONB,
    c INT,
    INVERTED INDEX b_idx(b)
)
----

# One path. Should generate a scan constrained on the inverted index.
opt
SELECT b,a FROM t5 WHERE b @> '{"a":1}'
----
index-join t5
 ├── columns: b:2!null a:1!null
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2)
 └── scan t5@b_idx
      ├── columns: a:1!null
      ├── constraint: /2/1: [/'{"a": 1}' - /'{"a": 1}']
      └── key: (1)

opt
SELECT b,a FROM t5 WHERE b @> '{"a":[[{"b":{"c":[{"d":"e"}]}}]]}'
----
index-join t5
 ├── columns: b:2!null a:1!null
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2)
 └── scan t5@b_idx
      ├── columns: a:1!null
      ├── constraint: /2/1: [/'{"a": [[{"b": {"c": [{"d": "e"}]}}]]}' - /'{"a": [[{"b": {"c": [{"d": "e"}]}}]]}']
      └── key: (1)

# Two paths. Should generate a zigzag join.
opt
SELECT b,a FROM t5 WHERE b @> '{"a":1, "c":2}'
----
inner-join (lookup t5)
 ├── columns: b:2!null a:1!null
 ├── key columns: [1] = [1]
 ├── lookup columns are key
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2)
 ├── inner-join (zigzag t5@b_idx t5@b_idx)
 │    ├── columns: a:1!null
 │    ├── eq columns: [1] = [1]
 │    ├── left fixed columns: [2] = ['{"a": 1}']
 │    ├── right fixed columns: [2] = ['{"c": 2}']
 │    └── filters (true)
 └── filters
      └── b:2 @> '{"a": 1, "c": 2}' [outer=(2), immutable, constraints=(/2: (/NULL - ])]

memo
SELECT a FROM t5 WHERE b @> '{"a":1, "c":2}'
----
memo (optimized, ~14KB, required=[presentation: a:1])
 ├── G1: (project G2 G3 a)
 │    └── [presentation: a:1]
 │         ├── best: (project G2 G3 a)
 │         └── cost: 100.53
 ├── G2: (select G4 G5) (lookup-join G6 G5 t5,keyCols=[1],outCols=(1,2)) (select G7 G5)
 │    └── []
 │         ├── best: (lookup-join G6 G5 t5,keyCols=[1],outCols=(1,2))
 │         └── cost: 100.40
 ├── G3: (projections)
 ├── G4: (scan t5,cols=(1,2))
 │    └── []
 │         ├── best: (scan t5,cols=(1,2))
 │         └── cost: 1054.02
 ├── G5: (filters G8)
 ├── G6: (zigzag-join G9 t5@b_idx t5@b_idx)
 │    └── []
 │         ├── best: (zigzag-join G9 t5@b_idx t5@b_idx)
 │         └── cost: 25.69
 ├── G7: (index-join G10 t5,cols=(1,2))
 │    └── []
 │         ├── best: (index-join G10 t5,cols=(1,2))
 │         └── cost: 782.82
 ├── G8: (contains G11 G12)
 ├── G9: (filters)
 ├── G10: (scan t5@b_idx,cols=(1),constrained)
 │    └── []
 │         ├── best: (scan t5@b_idx,cols=(1),constrained)
 │         └── cost: 117.31
 ├── G11: (variable b)
 └── G12: (const '{"a": 1, "c": 2}')

# Three or more paths. Should generate zigzag joins.
opt
SELECT b,a FROM t5 WHERE b @> '{"a":[{"b":"c", "d":3}, 5]}'
----
inner-join (lookup t5)
 ├── columns: b:2!null a:1!null
 ├── key columns: [1] = [1]
 ├── lookup columns are key
 ├── immutable
 ├── key: (1)
 ├── fd: (1)-->(2)
 ├── inner-join (zigzag t5@b_idx t5@b_idx)
 │    ├── columns: a:1!null
 │    ├── eq columns: [1] = [1]
 │    ├── left fixed columns: [2] = ['{"a": [{"b": "c"}]}']
 │    ├── right fixed columns: [2] = ['{"a": [{"d": 3}]}']
 │    └── filters (true)
 └── filters
      └── b:2 @> '{"a": [{"b": "c", "d": 3}, 5]}' [outer=(2), immutable, constraints=(/2: (/NULL - ])]

# Regression test for issue where zero-column expressions could exist multiple
# times in the tree, causing collisions.
opt
SELECT 1 FROM (VALUES (1), (1)) JOIN (VALUES (1), (1), (1)) ON true
UNION ALL
SELECT 1 FROM (VALUES (1), (1), (1)) JOIN (VALUES (1), (1)) ON true
----
union-all
 ├── columns: "?column?":7!null
 ├── left columns: "?column?":3
 ├── right columns: "?column?":6
 ├── cardinality: [12 - 12]
 ├── project
 │    ├── columns: "?column?":3!null
 │    ├── cardinality: [6 - 6]
 │    ├── fd: ()-->(3)
 │    ├── inner-join (cross)
 │    │    ├── cardinality: [6 - 6]
 │    │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 │    │    ├── values
 │    │    │    ├── cardinality: [3 - 3]
 │    │    │    ├── ()
 │    │    │    ├── ()
 │    │    │    └── ()
 │    │    ├── values
 │    │    │    ├── cardinality: [2 - 2]
 │    │    │    ├── ()
 │    │    │    └── ()
 │    │    └── filters (true)
 │    └── projections
 │         └── 1 [as="?column?":3]
 └── project
      ├── columns: "?column?":6!null
      ├── cardinality: [6 - 6]
      ├── fd: ()-->(6)
      ├── inner-join (cross)
      │    ├── cardinality: [6 - 6]
      │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
      │    ├── values
      │    │    ├── cardinality: [3 - 3]
      │    │    ├── ()
      │    │    ├── ()
      │    │    └── ()
      │    ├── values
      │    │    ├── cardinality: [2 - 2]
      │    │    ├── ()
      │    │    └── ()
      │    └── filters (true)
      └── projections
           └── 1 [as="?column?":6]

memo
SELECT 1 FROM (VALUES (1), (1)) JOIN (VALUES (1), (1), (1)) ON true
UNION ALL
SELECT 1 FROM (VALUES (1), (1), (1)) JOIN (VALUES (1), (1)) ON true
----
memo (optimized, ~18KB, required=[presentation: ?column?:7])
 ├── G1: (union-all G2 G3)
 │    └── [presentation: ?column?:7]
 │         ├── best: (union-all G2 G3)
 │         └── cost: 0.82
 ├── G2: (project G4 G5)
 │    └── []
 │         ├── best: (project G4 G5)
 │         └── cost: 0.34
 ├── G3: (project G6 G5)
 │    └── []
 │         ├── best: (project G6 G5)
 │         └── cost: 0.34
 ├── G4: (inner-join G7 G8 G9) (inner-join G8 G7 G9)
 │    └── []
 │         ├── best: (inner-join G8 G7 G9)
 │         └── cost: 0.21
 ├── G5: (projections G10)
 ├── G6: (inner-join G11 G12 G9) (inner-join G12 G11 G9)
 │    └── []
 │         ├── best: (inner-join G11 G12 G9)
 │         └── cost: 0.21
 ├── G7: (values G13 id=v1)
 │    └── []
 │         ├── best: (values G13 id=v1)
 │         └── cost: 0.03
 ├── G8: (values G14 id=v2)
 │    └── []
 │         ├── best: (values G14 id=v2)
 │         └── cost: 0.04
 ├── G9: (filters)
 ├── G10: (const 1)
 ├── G11: (values G14 id=v3)
 │    └── []
 │         ├── best: (values G14 id=v3)
 │         └── cost: 0.04
 ├── G12: (values G13 id=v4)
 │    └── []
 │         ├── best: (values G13 id=v4)
 │         └── cost: 0.03
 ├── G13: (scalar-list G15 G15)
 ├── G14: (scalar-list G15 G15 G15)
 ├── G15: (tuple G16)
 └── G16: (scalar-list)

opt join-limit=3
SELECT
    false
FROM
    abc AS x JOIN [INSERT INTO abc (a) SELECT 1 FROM abc RETURNING 1] JOIN abc AS y ON true ON false
----
with &1
 ├── columns: bool:26!null
 ├── cardinality: [0 - 0]
 ├── volatile, mutations
 ├── key: ()
 ├── fd: ()-->(26)
 ├── project
 │    ├── columns: "?column?":19!null
 │    ├── volatile, mutations
 │    ├── fd: ()-->(19)
 │    ├── insert abc
 │    │    ├── columns: abc.rowid:9!null
 │    │    ├── insert-mapping:
 │    │    │    ├── "?column?":16 => abc.a:6
 │    │    │    ├── column17:17 => abc.b:7
 │    │    │    ├── column17:17 => abc.c:8
 │    │    │    └── column18:18 => abc.rowid:9
 │    │    ├── volatile, mutations
 │    │    └── project
 │    │         ├── columns: column17:17 column18:18 "?column?":16!null
 │    │         ├── volatile
 │    │         ├── fd: ()-->(16,17)
 │    │         ├── scan abc
 │    │         └── projections
 │    │              ├── CAST(NULL AS INT8) [as=column17:17]
 │    │              ├── unique_rowid() [as=column18:18, volatile]
 │    │              └── 1 [as="?column?":16]
 │    └── projections
 │         └── 1 [as="?column?":19]
 └── values
      ├── columns: bool:26!null
      ├── cardinality: [0 - 0]
      ├── key: ()
      └── fd: ()-->(26)

opt join-limit=3
SELECT 1 FROM ((VALUES (1), (1)) JOIN ((VALUES (1), (1), (1)) JOIN (VALUES (1), (1), (1), (1)) ON true) ON true)
UNION ALL
SELECT 1 FROM ((VALUES (1), (1)) JOIN (VALUES (1), (1), (1)) ON true) JOIN (VALUES (1), (1), (1), (1)) ON true
----
union-all
 ├── columns: "?column?":9!null
 ├── left columns: "?column?":4
 ├── right columns: "?column?":8
 ├── cardinality: [48 - 48]
 ├── project
 │    ├── columns: "?column?":4!null
 │    ├── cardinality: [24 - 24]
 │    ├── fd: ()-->(4)
 │    ├── inner-join (cross)
 │    │    ├── cardinality: [24 - 24]
 │    │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 │    │    ├── inner-join (cross)
 │    │    │    ├── cardinality: [12 - 12]
 │    │    │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 │    │    │    ├── values
 │    │    │    │    ├── cardinality: [4 - 4]
 │    │    │    │    ├── ()
 │    │    │    │    ├── ()
 │    │    │    │    ├── ()
 │    │    │    │    └── ()
 │    │    │    ├── values
 │    │    │    │    ├── cardinality: [3 - 3]
 │    │    │    │    ├── ()
 │    │    │    │    ├── ()
 │    │    │    │    └── ()
 │    │    │    └── filters (true)
 │    │    ├── values
 │    │    │    ├── cardinality: [2 - 2]
 │    │    │    ├── ()
 │    │    │    └── ()
 │    │    └── filters (true)
 │    └── projections
 │         └── 1 [as="?column?":4]
 └── project
      ├── columns: "?column?":8!null
      ├── cardinality: [24 - 24]
      ├── fd: ()-->(8)
      ├── inner-join (cross)
      │    ├── cardinality: [24 - 24]
      │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
      │    ├── inner-join (cross)
      │    │    ├── cardinality: [6 - 6]
      │    │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
      │    │    ├── values
      │    │    │    ├── cardinality: [3 - 3]
      │    │    │    ├── ()
      │    │    │    ├── ()
      │    │    │    └── ()
      │    │    ├── values
      │    │    │    ├── cardinality: [2 - 2]
      │    │    │    ├── ()
      │    │    │    └── ()
      │    │    └── filters (true)
      │    ├── values
      │    │    ├── cardinality: [4 - 4]
      │    │    ├── ()
      │    │    ├── ()
      │    │    ├── ()
      │    │    └── ()
      │    └── filters (true)
      └── projections
           └── 1 [as="?column?":8]

opt
SELECT 1 FROM (VALUES (1), (1)) LEFT JOIN (VALUES (1), (1), (1)) ON random() = 0
UNION ALL
SELECT 1 FROM (VALUES (1), (1), (1)) RIGHT JOIN (VALUES (1), (1)) ON random() = 0
----
union-all
 ├── columns: "?column?":7!null
 ├── left columns: "?column?":3
 ├── right columns: "?column?":6
 ├── cardinality: [4 - 12]
 ├── volatile
 ├── project
 │    ├── columns: "?column?":3!null
 │    ├── cardinality: [2 - 6]
 │    ├── volatile
 │    ├── fd: ()-->(3)
 │    ├── left-join (cross)
 │    │    ├── cardinality: [2 - 6]
 │    │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
 │    │    ├── volatile
 │    │    ├── values
 │    │    │    ├── cardinality: [2 - 2]
 │    │    │    ├── ()
 │    │    │    └── ()
 │    │    ├── select
 │    │    │    ├── cardinality: [0 - 3]
 │    │    │    ├── volatile
 │    │    │    ├── values
 │    │    │    │    ├── cardinality: [3 - 3]
 │    │    │    │    ├── ()
 │    │    │    │    ├── ()
 │    │    │    │    └── ()
 │    │    │    └── filters
 │    │    │         └── random() = 0.0 [volatile]
 │    │    └── filters (true)
 │    └── projections
 │         └── 1 [as="?column?":3]
 └── project
      ├── columns: "?column?":6!null
      ├── cardinality: [2 - 6]
      ├── volatile
      ├── fd: ()-->(6)
      ├── left-join (cross)
      │    ├── cardinality: [2 - 6]
      │    ├── multiplicity: left-rows(one-or-more), right-rows(one-or-more)
      │    ├── volatile
      │    ├── values
      │    │    ├── cardinality: [2 - 2]
      │    │    ├── ()
      │    │    └── ()
      │    ├── select
      │    │    ├── cardinality: [0 - 3]
      │    │    ├── volatile
      │    │    ├── values
      │    │    │    ├── cardinality: [3 - 3]
      │    │    │    ├── ()
      │    │    │    ├── ()
      │    │    │    └── ()
      │    │    └── filters
      │    │         └── random() = 0.0 [volatile]
      │    └── filters (true)
      └── projections
           └── 1 [as="?column?":6]

exec-ddl
CREATE TABLE def (d INT, e INT, f INT, PRIMARY KEY (d, e));
----

exec-ddl
ALTER TABLE abc INJECT STATISTICS '[
  {
    "columns": ["a"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 100,
    "distinct_count": 100
  },
  {
    "columns": ["b"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 100,
    "distinct_count": 100
  }
]'
----

exec-ddl
ALTER TABLE def INJECT STATISTICS '[
  {
    "columns": ["d"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 10000,
    "distinct_count": 10000
  },
  {
    "columns": ["e"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 10000,
    "distinct_count": 10000
  }
]'
----

# Test the CommuteSemiJoinRule creates an appropriate inner join.
opt
SELECT * from abc WHERE EXISTS (SELECT * FROM def WHERE a=f)
----
semi-join (hash)
 ├── columns: a:1 b:2 c:3
 ├── scan abc
 │    └── columns: a:1 b:2 c:3
 ├── scan def
 │    └── columns: f:8
 └── filters
      └── a:1 = f:8 [outer=(1,8), constraints=(/1: (/NULL - ]; /8: (/NULL - ]), fd=(1)==(8), (8)==(1)]

# Test that we don't commute a SemiJoin when the On conditions are not
# equalities. For example, in this test we have a Lt condition.
opt expect-not=CommuteSemiJoin
SELECT * from abc WHERE EXISTS (SELECT * FROM def WHERE a < e)
----
semi-join (cross)
 ├── columns: a:1 b:2 c:3
 ├── scan abc
 │    └── columns: a:1 b:2 c:3
 ├── scan def
 │    └── columns: e:7!null
 └── filters
      └── a:1 < e:7 [outer=(1,7), constraints=(/1: (/NULL - ]; /7: (/NULL - ])]

# Test that we don't commute a SemiJoin when the On conditions are not
# equalities. For example, in this test we have an Or condition.
opt expect-not=CommuteSemiJoin
SELECT * from abc WHERE EXISTS (SELECT * FROM def WHERE a=d OR c=e)
----
semi-join (cross)
 ├── columns: a:1 b:2 c:3
 ├── scan abc
 │    └── columns: a:1 b:2 c:3
 ├── scan def
 │    ├── columns: d:6!null e:7!null
 │    └── key: (6,7)
 └── filters
      └── (a:1 = d:6) OR (c:3 = e:7) [outer=(1,3,6,7)]

opt disable=CommuteSemiJoin format=show-all
SELECT * from abc WHERE EXISTS (SELECT * FROM def WHERE a=d AND c=e)
----
semi-join (lookup def)
 ├── columns: a:1(int) b:2(int) c:3(int)
 ├── key columns: [1 3] = [6 7]
 ├── lookup columns are key
 ├── stats: [rows=100, distinct(1)=100, null(1)=0, distinct(3)=10, null(3)=0]
 ├── cost: 511.050394
 ├── prune: (2)
 ├── interesting orderings: (+1,+2) (+2,+3)
 ├── scan t.public.abc
 │    ├── columns: t.public.abc.a:1(int) t.public.abc.b:2(int) t.public.abc.c:3(int)
 │    ├── stats: [rows=100, distinct(1)=100, null(1)=0, distinct(3)=10, null(3)=1]
 │    ├── cost: 111.02
 │    ├── prune: (1-3)
 │    ├── interesting orderings: (+1,+2) (+2,+3)
 │    └── unfiltered-cols: (1-5)
 └── filters (true)

# TODO(rytaft): See stats/join tests. Since we don't collect the stats properly
# for SemiJoins, we prefer the InnerJoin plan over the SemiJoin one more times
# than necessary.
opt format=show-all
SELECT * from abc WHERE EXISTS (SELECT * FROM def WHERE a=d AND c=e)
----
semi-join (lookup def)
 ├── columns: a:1(int) b:2(int) c:3(int)
 ├── key columns: [1 3] = [6 7]
 ├── lookup columns are key
 ├── stats: [rows=100, distinct(1)=100, null(1)=0, distinct(3)=10, null(3)=0]
 ├── cost: 511.050394
 ├── prune: (2)
 ├── interesting orderings: (+1,+2) (+2,+3)
 ├── scan t.public.abc
 │    ├── columns: t.public.abc.a:1(int) t.public.abc.b:2(int) t.public.abc.c:3(int)
 │    ├── stats: [rows=100, distinct(1)=100, null(1)=0, distinct(3)=10, null(3)=1]
 │    ├── cost: 111.02
 │    ├── prune: (1-3)
 │    ├── interesting orderings: (+1,+2) (+2,+3)
 │    └── unfiltered-cols: (1-5)
 └── filters (true)

exec-ddl
CREATE TABLE customers (id INT PRIMARY KEY, name STRING)
----

exec-ddl
CREATE TABLE orders (id INT PRIMARY KEY, cust_id INT REFERENCES customers (id), order_date DATE, INDEX (order_date) STORING (cust_id))
----

exec-ddl
ALTER TABLE customers INJECT STATISTICS '[
  {
    "columns": ["id"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 100000,
    "distinct_count": 100000
  }
]'
----

exec-ddl
ALTER TABLE orders INJECT STATISTICS '[
  {
    "columns": ["id"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 1000000,
    "distinct_count": 1000000
  },
  {
    "columns": ["cust_id"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 1000000,
    "distinct_count": 10000000
  },
  {
    "columns": ["order_date"],
    "created_at": "2018-01-01 1:00:00.00000+00:00",
    "row_count": 1000000,
    "distinct_count": 1000000
  }
]'
----

opt disable=CommuteSemiJoin
SELECT *
FROM customers c
WHERE EXISTS(SELECT * FROM orders o WHERE o.cust_id=c.id AND o.order_date='2019-01-01')
----
semi-join (merge)
 ├── columns: id:1!null name:2
 ├── left ordering: +1
 ├── right ordering: +5
 ├── key: (1)
 ├── fd: (1)-->(2)
 ├── scan c
 │    ├── columns: c.id:1!null name:2
 │    ├── key: (1)
 │    ├── fd: (1)-->(2)
 │    └── ordering: +1
 ├── sort
 │    ├── columns: cust_id:5 order_date:6!null
 │    ├── fd: ()-->(6)
 │    ├── ordering: +5 opt(6) [actual: +5]
 │    └── scan o@secondary
 │         ├── columns: cust_id:5 order_date:6!null
 │         ├── constraint: /6/4: [/'2019-01-01' - /'2019-01-01']
 │         └── fd: ()-->(6)
 └── filters (true)

# The CommuteSemiJoin rule allows a much better plan because we can use
# a lookup join.
opt
SELECT *
FROM customers c
WHERE EXISTS(SELECT * FROM orders o WHERE o.cust_id=c.id AND o.order_date='2019-01-01')
----
project
 ├── columns: id:1!null name:2
 ├── key: (1)
 ├── fd: (1)-->(2)
 └── inner-join (lookup customers)
      ├── columns: c.id:1!null name:2 cust_id:5!null
      ├── key columns: [5] = [1]
      ├── lookup columns are key
      ├── key: (5)
      ├── fd: (1)-->(2), (1)==(5), (5)==(1)
      ├── distinct-on
      │    ├── columns: cust_id:5
      │    ├── grouping columns: cust_id:5
      │    ├── key: (5)
      │    └── scan o@secondary
      │         ├── columns: cust_id:5 order_date:6!null
      │         ├── constraint: /6/4: [/'2019-01-01' - /'2019-01-01']
      │         └── fd: ()-->(6)
      └── filters (true)

# GenerateInvertedIndexZigzagJoins is disabled in the presence of a row-level
# locking clause.
opt
SELECT b,a FROM t5 WHERE b @> '{"a":1, "c":2}' FOR UPDATE
----
select
 ├── columns: b:2!null a:1!null
 ├── volatile
 ├── key: (1)
 ├── fd: (1)-->(2)
 ├── index-join t5
 │    ├── columns: a:1!null b:2
 │    ├── volatile
 │    ├── key: (1)
 │    ├── fd: (1)-->(2)
 │    └── scan t5@b_idx
 │         ├── columns: a:1!null
 │         ├── constraint: /2/1: [/'{"a": 1}' - /'{"a": 1}']
 │         ├── locking: for-update
 │         ├── volatile
 │         └── key: (1)
 └── filters
      └── b:2 @> '{"a": 1, "c": 2}' [outer=(2), immutable, constraints=(/2: (/NULL - ])]

# -----------------------------------------------------
# ConvertSemiToInnerJoin
# -----------------------------------------------------

# This rule applies when the On conditions are not equalities. For example,
# in this test we have a Lt condition. It allows us to use a lookup join even
# though the index is not covering.
opt expect=ConvertSemiToInnerJoin
SELECT * from pqr WHERE EXISTS (SELECT * FROM zz WHERE a = 0 AND q = b AND r < c)
----
project
 ├── columns: p:1!null q:2 r:3 s:4 t:5
 ├── key: (1)
 ├── fd: (1)-->(2-5)
 └── project
      ├── columns: p:1!null q:2!null r:3!null s:4 t:5
      ├── key: (1)
      ├── fd: ()-->(2), (1)-->(3-5)
      └── inner-join (lookup pqr)
           ├── columns: p:1!null q:2!null r:3!null s:4 t:5 a:7!null b:8!null c:9!null
           ├── key columns: [1] = [1]
           ├── lookup columns are key
           ├── key: (1)
           ├── fd: ()-->(2,7-9), (1)-->(3-5), (2)==(8), (8)==(2)
           ├── inner-join (lookup pqr@q)
           │    ├── columns: p:1!null q:2!null a:7!null b:8!null c:9
           │    ├── key columns: [8] = [2]
           │    ├── key: (1)
           │    ├── fd: ()-->(2,7-9), (2)==(8), (8)==(2)
           │    ├── scan zz
           │    │    ├── columns: a:7!null b:8 c:9
           │    │    ├── constraint: /7: [/0 - /0]
           │    │    ├── cardinality: [0 - 1]
           │    │    ├── key: ()
           │    │    └── fd: ()-->(7-9)
           │    └── filters (true)
           └── filters
                └── r:3 < c:9 [outer=(3,9), constraints=(/3: (/NULL - ]; /9: (/NULL - ])]

# In this test we have an Or condition.
opt expect=ConvertSemiToInnerJoin
SELECT * from pqr WHERE EXISTS (SELECT * FROM zz WHERE a = 0 AND q = b AND (p = a OR r = c))
----
project
 ├── columns: p:1!null q:2 r:3 s:4 t:5
 ├── key: (1)
 ├── fd: (1)-->(2-5)
 └── project
      ├── columns: p:1!null q:2!null r:3 s:4 t:5
      ├── key: (1)
      ├── fd: ()-->(2), (1)-->(3-5)
      └── inner-join (lookup pqr)
           ├── columns: p:1!null q:2!null r:3 s:4 t:5 a:7!null b:8!null c:9
           ├── key columns: [1] = [1]
           ├── lookup columns are key
           ├── key: (1)
           ├── fd: ()-->(2,7-9), (1)-->(3-5), (2)==(8), (8)==(2)
           ├── inner-join (lookup pqr@q)
           │    ├── columns: p:1!null q:2!null a:7!null b:8!null c:9
           │    ├── key columns: [8] = [2]
           │    ├── key: (1)
           │    ├── fd: ()-->(2,7-9), (2)==(8), (8)==(2)
           │    ├── scan zz
           │    │    ├── columns: a:7!null b:8 c:9
           │    │    ├── constraint: /7: [/0 - /0]
           │    │    ├── cardinality: [0 - 1]
           │    │    ├── key: ()
           │    │    └── fd: ()-->(7-9)
           │    └── filters (true)
           └── filters
                └── (p:1 = 0) OR (r:3 = c:9) [outer=(1,3,9)]

# In this case we need to add the key back to zz since it was pruned during
# normalization.
opt expect=ConvertSemiToInnerJoin
SELECT b, c from zz WHERE EXISTS (SELECT * FROM pqr WHERE p = 0 AND q = b AND (p = c OR r = c))
----
project
 ├── columns: b:2 c:3
 ├── lax-key: (2,3)
 ├── fd: (3)~~>(2)
 └── project
      ├── columns: a:1!null b:2!null c:3!null
      ├── key: (1)
      ├── fd: ()-->(2), (1)-->(3), (3)-->(1)
      └── inner-join (lookup zz)
           ├── columns: a:1!null b:2!null c:3!null p:5!null q:6!null r:7
           ├── key columns: [1] = [1]
           ├── lookup columns are key
           ├── key: (1)
           ├── fd: ()-->(2,5-7), (1)-->(3), (3)-->(1), (2)==(6), (6)==(2)
           ├── inner-join (lookup zz@idx_b)
           │    ├── columns: a:1!null b:2!null p:5!null q:6!null r:7
           │    ├── key columns: [6] = [2]
           │    ├── key: (1)
           │    ├── fd: ()-->(2,5-7), (2)==(6), (6)==(2)
           │    ├── scan pqr
           │    │    ├── columns: p:5!null q:6 r:7
           │    │    ├── constraint: /5: [/0 - /0]
           │    │    ├── cardinality: [0 - 1]
           │    │    ├── key: ()
           │    │    └── fd: ()-->(5-7)
           │    └── filters (true)
           └── filters
                └── (c:3 = 0) OR (r:7 = c:3) [outer=(3,7), constraints=(/3: (/NULL - ])]

# --------------------------------------------------
# PushJoinIntoIndexJoin
# --------------------------------------------------

opt expect=PushJoinIntoIndexJoin
SELECT * FROM abc INNER JOIN (SELECT * FROM pqr ORDER BY q LIMIT 5) ON a=q
----
inner-join (lookup pqr)
 ├── columns: a:1!null b:2 c:3 p:6!null q:7!null r:8 s:9 t:10
 ├── key columns: [6] = [6]
 ├── lookup columns are key
 ├── fd: (6)-->(7-10), (1)==(7), (7)==(1)
 ├── inner-join (lookup abc@ab)
 │    ├── columns: a:1!null b:2 c:3 p:6!null q:7!null
 │    ├── key columns: [7] = [1]
 │    ├── fd: (6)-->(7), (1)==(7), (7)==(1)
 │    ├── scan pqr@q
 │    │    ├── columns: p:6!null q:7
 │    │    ├── limit: 5
 │    │    ├── key: (6)
 │    │    └── fd: (6)-->(7)
 │    └── filters (true)
 └── filters (true)

# Cross join case. The plan produced by PushJoinIntoIndexJoin isn't chosen
# because the cross join doesn't filter rows.
opt expect=PushJoinIntoIndexJoin
SELECT * FROM abc CROSS JOIN (SELECT * FROM pqr ORDER BY q LIMIT 5)
----
inner-join (cross)
 ├── columns: a:1 b:2 c:3 p:6!null q:7 r:8 s:9 t:10
 ├── fd: (6)-->(7-10)
 ├── scan abc
 │    └── columns: a:1 b:2 c:3
 ├── index-join pqr
 │    ├── columns: p:6!null q:7 r:8 s:9 t:10
 │    ├── cardinality: [0 - 5]
 │    ├── key: (6)
 │    ├── fd: (6)-->(7-10)
 │    └── scan pqr@q
 │         ├── columns: p:6!null q:7
 │         ├── limit: 5
 │         ├── key: (6)
 │         └── fd: (6)-->(7)
 └── filters (true)

# No-op case because the index join is the right input of the LeftJoin.
opt expect-not=PushJoinIntoIndexJoin
SELECT * FROM abc LEFT JOIN (SELECT * FROM pqr ORDER BY q LIMIT 5) ON a=q
----
left-join (merge)
 ├── columns: a:1 b:2 c:3 p:6 q:7 r:8 s:9 t:10
 ├── left ordering: +1
 ├── right ordering: +7
 ├── fd: (6)-->(7-10)
 ├── scan abc@ab
 │    ├── columns: a:1 b:2 c:3
 │    └── ordering: +1
 ├── index-join pqr
 │    ├── columns: p:6!null q:7 r:8 s:9 t:10
 │    ├── cardinality: [0 - 5]
 │    ├── key: (6)
 │    ├── fd: (6)-->(7-10)
 │    ├── ordering: +7
 │    └── scan pqr@q
 │         ├── columns: p:6!null q:7
 │         ├── limit: 5
 │         ├── key: (6)
 │         ├── fd: (6)-->(7)
 │         └── ordering: +7
 └── filters (true)

# No-op case because the InnerJoin has join hints.
opt expect-not=PushJoinIntoIndexJoin
SELECT * FROM (SELECT * FROM pqr ORDER BY q LIMIT 5) INNER HASH JOIN abc ON a=q
----
inner-join (hash)
 ├── columns: p:1!null q:2!null r:3 s:4 t:5 a:7!null b:8 c:9
 ├── flags: force hash join (store right side)
 ├── fd: (1)-->(2-5), (2)==(7), (7)==(2)
 ├── index-join pqr
 │    ├── columns: p:1!null q:2 r:3 s:4 t:5
 │    ├── cardinality: [0 - 5]
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-5)
 │    └── scan pqr@q
 │         ├── columns: p:1!null q:2
 │         ├── limit: 5
 │         ├── key: (1)
 │         └── fd: (1)-->(2)
 ├── scan abc
 │    └── columns: a:7 b:8 c:9
 └── filters
      └── a:7 = q:2 [outer=(2,7), constraints=(/2: (/NULL - ]; /7: (/NULL - ]), fd=(2)==(7), (7)==(2)]

# No-op case because the ON condition references a column that doesn't come from
# the input of the index join or the right side of the InnerJoin.
opt expect-not=PushJoinIntoIndexJoin
SELECT * FROM (SELECT * FROM pqr ORDER BY q LIMIT 5) INNER JOIN abc ON a=r
----
inner-join (lookup abc@ab)
 ├── columns: p:1!null q:2 r:3!null s:4 t:5 a:7!null b:8 c:9
 ├── key columns: [3] = [7]
 ├── fd: (1)-->(2-5), (3)==(7), (7)==(3)
 ├── index-join pqr
 │    ├── columns: p:1!null q:2 r:3 s:4 t:5
 │    ├── cardinality: [0 - 5]
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-5)
 │    └── scan pqr@q
 │         ├── columns: p:1!null q:2
 │         ├── limit: 5
 │         ├── key: (1)
 │         └── fd: (1)-->(2)
 └── filters (true)

# No-op case because the right side of the InnerJoin has outer columns.
opt expect-not=PushJoinIntoIndexJoin disable=(TryDecorrelateProject)
SELECT * 
FROM stu
INNER JOIN LATERAL (
   SELECT *
   FROM (SELECT * FROM pqr ORDER BY q LIMIT 5)
   INNER JOIN (SELECT *, a*s FROM abc)
   ON a=q
)
ON True
----
inner-join-apply
 ├── columns: s:1!null t:2!null u:3!null p:5!null q:6!null r:7 s:8 t:9 a:11!null b:12 c:13 "?column?":16
 ├── immutable
 ├── fd: (1-3,5)-->(6-9), (1-3,11)-->(16), (6)==(11), (11)==(6)
 ├── scan stu
 │    ├── columns: stu.s:1!null stu.t:2!null u:3!null
 │    └── key: (1-3)
 ├── inner-join (merge)
 │    ├── columns: p:5!null q:6!null r:7 pqr.s:8 pqr.t:9 a:11!null b:12 c:13 "?column?":16
 │    ├── left ordering: +6
 │    ├── right ordering: +11
 │    ├── outer: (1)
 │    ├── immutable
 │    ├── fd: (5)-->(6-9), (11)-->(16), (6)==(11), (11)==(6)
 │    ├── index-join pqr
 │    │    ├── columns: p:5!null q:6 r:7 pqr.s:8 pqr.t:9
 │    │    ├── cardinality: [0 - 5]
 │    │    ├── key: (5)
 │    │    ├── fd: (5)-->(6-9)
 │    │    ├── ordering: +6
 │    │    └── scan pqr@q
 │    │         ├── columns: p:5!null q:6
 │    │         ├── limit: 5
 │    │         ├── key: (5)
 │    │         ├── fd: (5)-->(6)
 │    │         └── ordering: +6
 │    ├── project
 │    │    ├── columns: "?column?":16 a:11 b:12 c:13
 │    │    ├── outer: (1)
 │    │    ├── immutable
 │    │    ├── fd: (11)-->(16)
 │    │    ├── ordering: +11
 │    │    ├── scan abc@ab
 │    │    │    ├── columns: a:11 b:12 c:13
 │    │    │    └── ordering: +11
 │    │    └── projections
 │    │         └── a:11 * stu.s:1 [as="?column?":16, outer=(1,11), immutable]
 │    └── filters (true)
 └── filters (true)