join_order

exec-ddl
CREATE TABLE bx (
  b INT PRIMARY KEY,
  x INT
)
----

exec-ddl
CREATE TABLE cy (
  c INT PRIMARY KEY,
  y INT
)
----

exec-ddl
CREATE TABLE dz (
  d INT PRIMARY KEY,
  z INT
)
----

exec-ddl
CREATE TABLE abc (
  a INT PRIMARY KEY,
  b INT,
  c INT,
  d INT
)
----

opt join-limit=2 expect=ReorderJoins
SELECT * FROM abc, bx, cy WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c
----
inner-join (lookup cy)
 ├── columns: a:1!null b:2!null c:3!null d:4 b:7!null x:8 c:11!null y:12
 ├── key columns: [3] = [11]
 ├── lookup columns are key
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1-4,7,8,11,12), (2)==(7), (3)==(11), (11)==(3), (7)==(2)
 ├── inner-join (lookup bx)
 │    ├── columns: a:1!null abc.b:2!null abc.c:3 d:4 bx.b:7!null x:8
 │    ├── key columns: [2] = [7]
 │    ├── lookup columns are key
 │    ├── cardinality: [0 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(1-4,7,8), (7)==(2), (2)==(7)
 │    ├── scan abc
 │    │    ├── columns: a:1!null abc.b:2 abc.c:3 d:4
 │    │    ├── constraint: /1: [/1 - /1]
 │    │    ├── cardinality: [0 - 1]
 │    │    ├── key: ()
 │    │    └── fd: ()-->(1-4)
 │    └── filters (true)
 └── filters (true)

opt join-limit=2 expect=ReorderJoins
SELECT * FROM bx, abc, cy WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c
----
inner-join (lookup bx)
 ├── columns: b:1!null x:2 a:5!null b:6!null c:7!null d:8 c:11!null y:12
 ├── key columns: [6] = [1]
 ├── lookup columns are key
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1,2,5-8,11,12), (7)==(11), (1)==(6), (6)==(1), (11)==(7)
 ├── inner-join (lookup cy)
 │    ├── columns: a:5!null abc.b:6 abc.c:7!null d:8 cy.c:11!null y:12
 │    ├── key columns: [7] = [11]
 │    ├── lookup columns are key
 │    ├── cardinality: [0 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(5-8,11,12), (11)==(7), (7)==(11)
 │    ├── scan abc
 │    │    ├── columns: a:5!null abc.b:6 abc.c:7 d:8
 │    │    ├── constraint: /5: [/1 - /1]
 │    │    ├── cardinality: [0 - 1]
 │    │    ├── key: ()
 │    │    └── fd: ()-->(5-8)
 │    └── filters (true)
 └── filters (true)

opt join-limit=2 expect=ReorderJoins
SELECT * FROM bx, cy, abc WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c
----
inner-join (lookup bx)
 ├── columns: b:1!null x:2 c:5!null y:6 a:9!null b:10!null c:11!null d:12
 ├── key columns: [10] = [1]
 ├── lookup columns are key
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1,2,5,6,9-12), (5)==(11), (1)==(10), (10)==(1), (11)==(5)
 ├── inner-join (lookup cy)
 │    ├── columns: cy.c:5!null y:6 a:9!null abc.b:10 abc.c:11!null d:12
 │    ├── key columns: [11] = [5]
 │    ├── lookup columns are key
 │    ├── cardinality: [0 - 1]
 │    ├── key: ()
 │    ├── fd: ()-->(5,6,9-12), (11)==(5), (5)==(11)
 │    ├── scan abc
 │    │    ├── columns: a:9!null abc.b:10 abc.c:11 d:12
 │    │    ├── constraint: /9: [/1 - /1]
 │    │    ├── cardinality: [0 - 1]
 │    │    ├── key: ()
 │    │    └── fd: ()-->(9-12)
 │    └── filters (true)
 └── filters (true)

# Reorder subtrees of size 2.
exploretrace join-limit=2 rule=ReorderJoins format=hide-all
SELECT *
FROM bx, cy, dz, abc
WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c AND cy.c = dz.d
----
----
================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── scan cy
   │    ├── inner-join (hash)
   │    │    ├── scan dz
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters
   │    │         └── dz.d = abc.c
   │    └── filters
   │         └── cy.c = dz.d
   └── filters
        └── abc.b = bx.b

New expression 1 of 1:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── scan cy
   │    ├── inner-join (hash)
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    ├── scan dz
   │    │    └── filters
   │    │         └── dz.d = abc.c
   │    └── filters
   │         └── cy.c = dz.d
   └── filters
        └── abc.b = bx.b

================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── scan cy
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    └── filters
   │         └── cy.c = dz.d
   └── filters
        └── abc.b = bx.b

New expression 1 of 5:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    ├── scan cy
   │    └── filters
   │         └── cy.c = dz.d
   └── filters
        └── abc.b = bx.b

New expression 2 of 5:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── scan dz
   │    ├── inner-join (hash)
   │    │    ├── scan cy
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters
   │    │         └── cy.c = abc.c
   │    └── filters
   │         └── dz.d = abc.c
   └── filters
        └── abc.b = bx.b

New expression 3 of 5:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── scan cy
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters
   │    │         └── cy.c = abc.c
   │    ├── scan dz
   │    └── filters
   │         └── dz.d = abc.c
   └── filters
        └── abc.b = bx.b

New expression 4 of 5:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── scan cy
   │    │    ├── scan dz
   │    │    └── filters
   │    │         └── cy.c = dz.d
   │    ├── scan abc
   │    │    └── constraint: /13: [/1 - /1]
   │    └── filters
   │         └── dz.d = abc.c
   └── filters
        └── abc.b = bx.b

New expression 5 of 5:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (hash)
   │    ├── scan abc
   │    │    └── constraint: /13: [/1 - /1]
   │    ├── inner-join (hash)
   │    │    ├── scan cy
   │    │    ├── scan dz
   │    │    └── filters
   │    │         └── cy.c = dz.d
   │    └── filters
   │         └── dz.d = abc.c
   └── filters
        └── abc.b = bx.b

================================================================================
ReorderJoins
================================================================================
Source expression:
  inner-join (hash)
   ├── scan bx
   ├── inner-join (lookup cy)
   │    ├── lookup columns are key
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    └── filters (true)
   └── filters
        └── abc.b = bx.b

New expression 1 of 3:
  inner-join (hash)
   ├── inner-join (lookup cy)
   │    ├── lookup columns are key
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    └── filters (true)
   ├── scan bx
   └── filters
        └── abc.b = bx.b

New expression 2 of 3:
  inner-join (hash)
   ├── scan cy
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    └── filters
   │         └── abc.b = bx.b
   └── filters
        └── cy.c = dz.d

New expression 3 of 3:
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── inner-join (lookup dz)
   │    │    ├── lookup columns are key
   │    │    ├── scan abc
   │    │    │    └── constraint: /13: [/1 - /1]
   │    │    └── filters (true)
   │    └── filters
   │         └── abc.b = bx.b
   ├── scan cy
   └── filters
        └── cy.c = dz.d
----
----

# No joins should be reordered besides commutation.
memo join-limit=0 expect-not=ReorderJoins
SELECT * FROM bx, cy, abc WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c
----
memo (optimized, ~28KB, required=[presentation: b:1,x:2,c:5,y:6,a:9,b:10,c:11,d:12])
 ├── G1: (inner-join G2 G3 G4) (merge-join G2 G3 G5 inner-join,+1,+10)
 │    └── [presentation: b:1,x:2,c:5,y:6,a:9,b:10,c:11,d:12]
 │         ├── best: (merge-join G2="[ordering: +1]" G3 G5 inner-join,+1,+10)
 │         └── cost: 2151.99
 ├── G2: (scan bx,cols=(1,2))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan bx,cols=(1,2))
 │    │    └── cost: 1064.42
 │    └── []
 │         ├── best: (scan bx,cols=(1,2))
 │         └── cost: 1064.42
 ├── G3: (inner-join G6 G7 G8) (merge-join G6 G7 G5 inner-join,+5,+11) (lookup-join G9 G8 abc,keyCols=[15],outCols=(5,6,9-12))
 │    └── []
 │         ├── best: (merge-join G6="[ordering: +5]" G7 G5 inner-join,+5,+11)
 │         └── cost: 1078.54
 ├── G4: (filters G10)
 ├── G5: (filters)
 ├── G6: (scan cy,cols=(5,6))
 │    ├── [ordering: +5]
 │    │    ├── best: (scan cy,cols=(5,6))
 │    │    └── cost: 1064.42
 │    └── []
 │         ├── best: (scan cy,cols=(5,6))
 │         └── cost: 1064.42
 ├── G7: (select G11 G12) (scan abc,cols=(9-12),constrained)
 │    └── []
 │         ├── best: (scan abc,cols=(9-12),constrained)
 │         └── cost: 5.09
 ├── G8: (filters G13)
 ├── G9: (project G6 G14 c y)
 │    └── []
 │         ├── best: (project G6 G14 c y)
 │         └── cost: 1084.44
 ├── G10: (eq G15 G16)
 ├── G11: (scan abc,cols=(9-12))
 │    └── []
 │         ├── best: (scan abc,cols=(9-12))
 │         └── cost: 1104.82
 ├── G12: (filters G17)
 ├── G13: (eq G18 G19)
 ├── G14: (projections G20)
 ├── G15: (variable abc.b)
 ├── G16: (variable bx.b)
 ├── G17: (eq G21 G20)
 ├── G18: (variable abc.c)
 ├── G19: (variable cy.c)
 ├── G20: (const 1)
 └── G21: (variable a)

memo join-limit=2
SELECT * FROM bx, cy, abc WHERE a = 1 AND abc.b = bx.b AND abc.c = cy.c
----
memo (optimized, ~46KB, required=[presentation: b:1,x:2,c:5,y:6,a:9,b:10,c:11,d:12])
 ├── G1: (inner-join G2 G3 G4) (inner-join G3 G2 G4) (inner-join G5 G6 G7) (inner-join G6 G5 G7) (merge-join G2 G3 G8 inner-join,+1,+10) (merge-join G3 G2 G8 inner-join,+10,+1) (lookup-join G3 G8 bx,keyCols=[10],outCols=(1,2,5,6,9-12)) (merge-join G5 G6 G8 inner-join,+5,+11) (merge-join G6 G5 G8 inner-join,+11,+5) (lookup-join G6 G8 cy,keyCols=[11],outCols=(1,2,5,6,9-12))
 │    └── [presentation: b:1,x:2,c:5,y:6,a:9,b:10,c:11,d:12]
 │         ├── best: (lookup-join G3 G8 bx,keyCols=[10],outCols=(1,2,5,6,9-12))
 │         └── cost: 17.13
 ├── G2: (scan bx,cols=(1,2))
 │    ├── [ordering: +1]
 │    │    ├── best: (scan bx,cols=(1,2))
 │    │    └── cost: 1064.42
 │    └── []
 │         ├── best: (scan bx,cols=(1,2))
 │         └── cost: 1064.42
 ├── G3: (inner-join G5 G9 G7) (inner-join G9 G5 G7) (merge-join G5 G9 G8 inner-join,+5,+11) (lookup-join G10 G7 abc,keyCols=[15],outCols=(5,6,9-12)) (merge-join G9 G5 G8 inner-join,+11,+5) (lookup-join G9 G8 cy,keyCols=[11],outCols=(5,6,9-12))
 │    └── []
 │         ├── best: (lookup-join G9 G8 cy,keyCols=[11],outCols=(5,6,9-12))
 │         └── cost: 11.13
 ├── G4: (filters G11)
 ├── G5: (scan cy,cols=(5,6))
 │    ├── [ordering: +5]
 │    │    ├── best: (scan cy,cols=(5,6))
 │    │    └── cost: 1064.42
 │    └── []
 │         ├── best: (scan cy,cols=(5,6))
 │         └── cost: 1064.42
 ├── G6: (inner-join G2 G9 G4) (inner-join G9 G2 G4) (merge-join G2 G9 G8 inner-join,+1,+10) (lookup-join G12 G4 abc,keyCols=[16],outCols=(1,2,9-12)) (merge-join G9 G2 G8 inner-join,+10,+1) (lookup-join G9 G8 bx,keyCols=[10],outCols=(1,2,9-12))
 │    └── []
 │         ├── best: (lookup-join G9 G8 bx,keyCols=[10],outCols=(1,2,9-12))
 │         └── cost: 11.13
 ├── G7: (filters G13)
 ├── G8: (filters)
 ├── G9: (select G14 G15) (scan abc,cols=(9-12),constrained)
 │    └── []
 │         ├── best: (scan abc,cols=(9-12),constrained)
 │         └── cost: 5.09
 ├── G10: (project G5 G16 c y)
 │    └── []
 │         ├── best: (project G5 G16 c y)
 │         └── cost: 1084.44
 ├── G11: (eq G17 G18)
 ├── G12: (project G2 G16 b x)
 │    └── []
 │         ├── best: (project G2 G16 b x)
 │         └── cost: 1084.44
 ├── G13: (eq G19 G20)
 ├── G14: (scan abc,cols=(9-12))
 │    └── []
 │         ├── best: (scan abc,cols=(9-12))
 │         └── cost: 1104.82
 ├── G15: (filters G21)
 ├── G16: (projections G22)
 ├── G17: (variable abc.b)
 ├── G18: (variable bx.b)
 ├── G19: (variable abc.c)
 ├── G20: (variable cy.c)
 ├── G21: (eq G23 G22)
 ├── G22: (const 1)
 └── G23: (variable a)

opt join-limit=3 expect=ReorderJoins
SELECT * FROM bx, cy, dz, abc WHERE a = 1
----
inner-join (cross)
 ├── columns: b:1!null x:2 c:5!null y:6 d:9!null z:10 a:13!null b:14 c:15 d:16
 ├── key: (1,5,9)
 ├── fd: ()-->(13-16), (1)-->(2), (5)-->(6), (9)-->(10)
 ├── inner-join (cross)
 │    ├── columns: cy.c:5!null y:6 dz.d:9!null z:10 a:13!null abc.b:14 abc.c:15 abc.d:16
 │    ├── key: (5,9)
 │    ├── fd: ()-->(13-16), (5)-->(6), (9)-->(10)
 │    ├── scan cy
 │    │    ├── columns: cy.c:5!null y:6
 │    │    ├── key: (5)
 │    │    └── fd: (5)-->(6)
 │    ├── inner-join (cross)
 │    │    ├── columns: dz.d:9!null z:10 a:13!null abc.b:14 abc.c:15 abc.d:16
 │    │    ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 │    │    ├── key: (9)
 │    │    ├── fd: ()-->(13-16), (9)-->(10)
 │    │    ├── scan dz
 │    │    │    ├── columns: dz.d:9!null z:10
 │    │    │    ├── key: (9)
 │    │    │    └── fd: (9)-->(10)
 │    │    ├── scan abc
 │    │    │    ├── columns: a:13!null abc.b:14 abc.c:15 abc.d:16
 │    │    │    ├── constraint: /13: [/1 - /1]
 │    │    │    ├── cardinality: [0 - 1]
 │    │    │    ├── key: ()
 │    │    │    └── fd: ()-->(13-16)
 │    │    └── filters (true)
 │    └── filters (true)
 ├── scan bx
 │    ├── columns: bx.b:1!null x:2
 │    ├── key: (1)
 │    └── fd: (1)-->(2)
 └── filters (true)

opt join-limit=2 format=show-all
SELECT * FROM abc, bx, cy, dz WHERE a = 1
----
inner-join (cross)
 ├── columns: a:1(int!null) b:2(int) c:3(int) d:4(int) b:7(int!null) x:8(int) c:11(int!null) y:12(int) d:15(int!null) z:16(int)
 ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 ├── stats: [rows=1e+09]
 ├── cost: 32525746.2
 ├── key: (7,11,15)
 ├── fd: ()-->(1-4), (7)-->(8), (11)-->(12), (15)-->(16)
 ├── prune: (2-4,7,8,11,12,15,16)
 ├── interesting orderings: (+7) (+11) (+15)
 ├── inner-join (cross)
 │    ├── columns: t.public.bx.b:7(int!null) t.public.bx.x:8(int) t.public.cy.c:11(int!null) t.public.cy.y:12(int) t.public.dz.d:15(int!null) t.public.dz.z:16(int)
 │    ├── stats: [rows=1e+09]
 │    ├── cost: 10025741.1
 │    ├── key: (7,11,15)
 │    ├── fd: (7)-->(8), (11)-->(12), (15)-->(16)
 │    ├── prune: (7,8,11,12,15,16)
 │    ├── interesting orderings: (+7) (+11) (+15)
 │    ├── inner-join (cross)
 │    │    ├── columns: t.public.cy.c:11(int!null) t.public.cy.y:12(int) t.public.dz.d:15(int!null) t.public.dz.z:16(int)
 │    │    ├── stats: [rows=1000000]
 │    │    ├── cost: 12159.0063
 │    │    ├── key: (11,15)
 │    │    ├── fd: (11)-->(12), (15)-->(16)
 │    │    ├── prune: (11,12,15,16)
 │    │    ├── interesting orderings: (+11) (+15)
 │    │    ├── scan t.public.cy
 │    │    │    ├── columns: t.public.cy.c:11(int!null) t.public.cy.y:12(int)
 │    │    │    ├── stats: [rows=1000]
 │    │    │    ├── cost: 1064.42
 │    │    │    ├── key: (11)
 │    │    │    ├── fd: (11)-->(12)
 │    │    │    ├── prune: (11,12)
 │    │    │    ├── interesting orderings: (+11)
 │    │    │    └── unfiltered-cols: (11-14)
 │    │    ├── scan t.public.dz
 │    │    │    ├── columns: t.public.dz.d:15(int!null) t.public.dz.z:16(int)
 │    │    │    ├── stats: [rows=1000]
 │    │    │    ├── cost: 1064.42
 │    │    │    ├── key: (15)
 │    │    │    ├── fd: (15)-->(16)
 │    │    │    ├── prune: (15,16)
 │    │    │    ├── interesting orderings: (+15)
 │    │    │    └── unfiltered-cols: (15-18)
 │    │    └── filters (true)
 │    ├── scan t.public.bx
 │    │    ├── columns: t.public.bx.b:7(int!null) t.public.bx.x:8(int)
 │    │    ├── stats: [rows=1000]
 │    │    ├── cost: 1064.42
 │    │    ├── key: (7)
 │    │    ├── fd: (7)-->(8)
 │    │    ├── prune: (7,8)
 │    │    ├── interesting orderings: (+7)
 │    │    └── unfiltered-cols: (7-10)
 │    └── filters (true)
 ├── scan t.public.abc
 │    ├── columns: t.public.abc.a:1(int!null) t.public.abc.b:2(int) t.public.abc.c:3(int) t.public.abc.d:4(int)
 │    ├── constraint: /1: [/1 - /1]
 │    ├── cardinality: [0 - 1]
 │    ├── stats: [rows=1, distinct(1)=1, null(1)=0, avgsize(1)=4]
 │    ├── cost: 5.09
 │    ├── key: ()
 │    ├── fd: ()-->(1-4)
 │    └── prune: (2-4)
 └── filters (true)

# Note the difference in memo size for with and without reorder-joins, for only four tables.
# TODO(justin): Find a way to reduce this.

memo join-limit=0
SELECT * FROM bx, cy, dz, abc WHERE x = y AND y = z AND z = a
----
memo (optimized, ~29KB, required=[presentation: b:1,x:2,c:5,y:6,d:9,z:10,a:13,b:14,c:15,d:16])
 ├── G1: (inner-join G2 G3 G4) (merge-join G2 G3 G5 inner-join,+2,+6)
 │    └── [presentation: b:1,x:2,c:5,y:6,d:9,z:10,a:13,b:14,c:15,d:16]
 │         ├── best: (inner-join G2 G3 G4)
 │         └── cost: 5635.39
 ├── G2: (scan bx,cols=(1,2))
 │    ├── [ordering: +2]
 │    │    ├── best: (sort G2)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan bx,cols=(1,2))
 │         └── cost: 1064.42
 ├── G3: (inner-join G6 G7 G8) (merge-join G6 G7 G5 inner-join,+6,+10)
 │    ├── [ordering: +(6|10|13)]
 │    │    ├── best: (merge-join G6="[ordering: +6]" G7="[ordering: +(10|13)]" G5 inner-join,+6,+10)
 │    │    └── cost: 3860.46
 │    └── []
 │         ├── best: (inner-join G6 G7 G8)
 │         └── cost: 3401.72
 ├── G4: (filters G9)
 ├── G5: (filters)
 ├── G6: (scan cy,cols=(5,6))
 │    ├── [ordering: +6]
 │    │    ├── best: (sort G6)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan cy,cols=(5,6))
 │         └── cost: 1064.42
 ├── G7: (inner-join G10 G11 G12) (merge-join G10 G11 G5 inner-join,+10,+13) (lookup-join G10 G5 abc,keyCols=[10],outCols=(9,10,13-16))
 │    ├── [ordering: +(10|13)]
 │    │    ├── best: (merge-join G10="[ordering: +10]" G11="[ordering: +13]" G5 inner-join,+10,+13)
 │    │    └── cost: 2438.64
 │    └── []
 │         ├── best: (inner-join G10 G11 G12)
 │         └── cost: 2209.31
 ├── G8: (filters G13)
 ├── G9: (eq G14 G15)
 ├── G10: (scan dz,cols=(9,10))
 │    ├── [ordering: +10]
 │    │    ├── best: (sort G10)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan dz,cols=(9,10))
 │         └── cost: 1064.42
 ├── G11: (scan abc,cols=(13-16))
 │    ├── [ordering: +13]
 │    │    ├── best: (scan abc,cols=(13-16))
 │    │    └── cost: 1104.82
 │    └── []
 │         ├── best: (scan abc,cols=(13-16))
 │         └── cost: 1104.82
 ├── G12: (filters G16)
 ├── G13: (eq G15 G17)
 ├── G14: (variable x)
 ├── G15: (variable y)
 ├── G16: (eq G17 G18)
 ├── G17: (variable z)
 └── G18: (variable a)

# This query is the worst-case scenario for join ordering because all relations
# are connected, which allows every join order to be added to the memo.
# TODO(drewk): implement branch pruning and/or a max operator limit for the
# memo.
memo join-limit=3
SELECT * FROM bx, cy, dz, abc WHERE x = y AND y = z AND z = a
----
memo (optimized, ~62KB, required=[presentation: b:1,x:2,c:5,y:6,d:9,z:10,a:13,b:14,c:15,d:16])
 ├── 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) (inner-join G10 G11 G12) (inner-join G11 G10 G12) (inner-join G13 G14 G12) (inner-join G14 G13 G12) (inner-join G15 G16 G12) (inner-join G16 G15 G12) (inner-join G17 G18 G12) (inner-join G18 G17 G12) (merge-join G3 G2 G19 inner-join,+6,+2) (merge-join G6 G5 G19 inner-join,+10,+6) (merge-join G9 G8 G19 inner-join,+10,+6) (merge-join G11 G10 G19 inner-join,+13,+10) (merge-join G14 G13 G19 inner-join,+13,+10) (merge-join G16 G15 G19 inner-join,+13,+10) (lookup-join G17 G19 abc,keyCols=[10],outCols=(1,2,5,6,9,10,13-16)) (merge-join G18 G17 G19 inner-join,+13,+10)
 │    └── [presentation: b:1,x:2,c:5,y:6,d:9,z:10,a:13,b:14,c:15,d:16]
 │         ├── best: (inner-join G3 G2 G4)
 │         └── cost: 5576.62
 ├── G2: (scan bx,cols=(1,2))
 │    ├── [ordering: +2]
 │    │    ├── best: (sort G2)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan bx,cols=(1,2))
 │         └── cost: 1064.42
 ├── G3: (inner-join G5 G9 G7) (inner-join G9 G5 G7) (inner-join G10 G14 G12) (inner-join G14 G10 G12) (inner-join G15 G18 G12) (inner-join G18 G15 G12) (merge-join G9 G5 G19 inner-join,+10,+6) (merge-join G14 G10 G19 inner-join,+13,+10) (lookup-join G15 G19 abc,keyCols=[10],outCols=(5,6,9,10,13-16)) (merge-join G18 G15 G19 inner-join,+13,+10)
 │    ├── [ordering: +(6|10|13)]
 │    │    ├── best: (merge-join G9="[ordering: +(10|13)]" G5="[ordering: +6]" G19 inner-join,+10,+6)
 │    │    └── cost: 3860.48
 │    └── []
 │         ├── best: (inner-join G5 G9 G7)
 │         └── cost: 3401.72
 ├── G4: (filters G20)
 ├── G5: (scan cy,cols=(5,6))
 │    ├── [ordering: +6]
 │    │    ├── best: (sort G5)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan cy,cols=(5,6))
 │         └── cost: 1064.42
 ├── G6: (inner-join G2 G9 G21) (inner-join G9 G2 G21) (inner-join G10 G16 G12) (inner-join G16 G10 G12) (inner-join G13 G18 G12) (inner-join G18 G13 G12) (merge-join G9 G2 G19 inner-join,+10,+2) (merge-join G16 G10 G19 inner-join,+13,+10) (lookup-join G13 G19 abc,keyCols=[10],outCols=(1,2,9,10,13-16)) (merge-join G18 G13 G19 inner-join,+13,+10)
 │    ├── [ordering: +(2|10|13)]
 │    │    ├── best: (merge-join G9="[ordering: +(10|13)]" G2="[ordering: +2]" G19 inner-join,+10,+2)
 │    │    └── cost: 3860.48
 │    └── []
 │         ├── best: (inner-join G2 G9 G21)
 │         └── cost: 3401.72
 ├── G7: (filters G22)
 ├── G8: (inner-join G2 G5 G4) (inner-join G5 G2 G4)
 │    ├── [ordering: +(2|6)]
 │    │    ├── best: (sort G8)
 │    │    └── cost: 5458.98
 │    └── []
 │         ├── best: (inner-join G2 G5 G4)
 │         └── cost: 2257.02
 ├── G9: (inner-join G10 G18 G12) (inner-join G18 G10 G12) (lookup-join G10 G19 abc,keyCols=[10],outCols=(9,10,13-16)) (merge-join G18 G10 G19 inner-join,+13,+10)
 │    ├── [ordering: +(10|13)]
 │    │    ├── best: (merge-join G18="[ordering: +13]" G10="[ordering: +10]" G19 inner-join,+13,+10)
 │    │    └── cost: 2438.64
 │    └── []
 │         ├── best: (inner-join G10 G18 G12)
 │         └── cost: 2209.31
 ├── G10: (scan dz,cols=(9,10))
 │    ├── [ordering: +10]
 │    │    ├── best: (sort G10)
 │    │    └── cost: 1303.90
 │    └── []
 │         ├── best: (scan dz,cols=(9,10))
 │         └── cost: 1064.42
 ├── G11: (inner-join G2 G14 G4) (inner-join G14 G2 G4) (inner-join G5 G16 G4) (inner-join G16 G5 G4) (inner-join G8 G18 G23) (inner-join G18 G8 G23) (merge-join G14 G2 G19 inner-join,+6,+2) (merge-join G16 G5 G19 inner-join,+2,+6) (lookup-join G8 G19 abc,keyCols=[2],outCols=(1,2,5,6,13-16)) (merge-join G18 G8 G19 inner-join,+13,+2)
 │    ├── [ordering: +(2|6|13)]
 │    │    ├── best: (merge-join G14="[ordering: +(6|13)]" G2="[ordering: +2]" G19 inner-join,+6,+2)
 │    │    └── cost: 3860.48
 │    └── []
 │         ├── best: (inner-join G2 G14 G4)
 │         └── cost: 3401.72
 ├── G12: (filters G24)
 ├── G13: (inner-join G2 G10 G21) (inner-join G10 G2 G21)
 │    ├── [ordering: +(2|10)]
 │    │    ├── best: (sort G13)
 │    │    └── cost: 5458.98
 │    └── []
 │         ├── best: (inner-join G2 G10 G21)
 │         └── cost: 2257.02
 ├── G14: (inner-join G5 G18 G25) (inner-join G18 G5 G25) (lookup-join G5 G19 abc,keyCols=[6],outCols=(5,6,13-16)) (merge-join G18 G5 G19 inner-join,+13,+6)
 │    ├── [ordering: +(6|13)]
 │    │    ├── best: (merge-join G18="[ordering: +13]" G5="[ordering: +6]" G19 inner-join,+13,+6)
 │    │    └── cost: 2438.64
 │    └── []
 │         ├── best: (inner-join G5 G18 G25)
 │         └── cost: 2209.31
 ├── G15: (inner-join G5 G10 G7) (inner-join G10 G5 G7)
 │    ├── [ordering: +(6|10)]
 │    │    ├── best: (sort G15)
 │    │    └── cost: 5458.98
 │    └── []
 │         ├── best: (inner-join G5 G10 G7)
 │         └── cost: 2257.02
 ├── G16: (inner-join G2 G18 G23) (inner-join G18 G2 G23) (lookup-join G2 G19 abc,keyCols=[2],outCols=(1,2,13-16)) (merge-join G18 G2 G19 inner-join,+13,+2)
 │    ├── [ordering: +(2|13)]
 │    │    ├── best: (merge-join G18="[ordering: +13]" G2="[ordering: +2]" G19 inner-join,+13,+2)
 │    │    └── cost: 2438.64
 │    └── []
 │         ├── best: (inner-join G2 G18 G23)
 │         └── cost: 2209.31
 ├── G17: (inner-join G2 G15 G4) (inner-join G15 G2 G4) (inner-join G5 G13 G7) (inner-join G13 G5 G7) (inner-join G8 G10 G7) (inner-join G10 G8 G7)
 │    ├── [ordering: +(2|6|10)]
 │    │    ├── best: (sort G17)
 │    │    └── cost: 45812.65
 │    └── []
 │         ├── best: (inner-join G15 G2 G4)
 │         └── cost: 4431.91
 ├── G18: (scan abc,cols=(13-16))
 │    ├── [ordering: +13]
 │    │    ├── best: (scan abc,cols=(13-16))
 │    │    └── cost: 1104.82
 │    └── []
 │         ├── best: (scan abc,cols=(13-16))
 │         └── cost: 1104.82
 ├── G19: (filters)
 ├── G20: (eq G26 G27)
 ├── G21: (filters G28)
 ├── G22: (eq G27 G29)
 ├── G23: (filters G30)
 ├── G24: (eq G29 G31)
 ├── G25: (filters G32)
 ├── G26: (variable x)
 ├── G27: (variable y)
 ├── G28: (eq G26 G29)
 ├── G29: (variable z)
 ├── G30: (eq G26 G31)
 ├── G31: (variable a)
 └── G32: (eq G27 G31)

opt
SELECT * FROM bx, cy, dz, abc WHERE x = y AND y = z AND z = a
----
inner-join (hash)
 ├── columns: b:1!null x:2!null c:5!null y:6!null d:9!null z:10!null a:13!null b:14 c:15 d:16
 ├── key: (1,5,9)
 ├── fd: (1)-->(2), (5)-->(6), (9)-->(10), (13)-->(14-16), (10)==(2,6,13), (13)==(2,6,10), (6)==(2,10,13), (2)==(6,10,13)
 ├── inner-join (hash)
 │    ├── columns: cy.c:5!null y:6!null dz.d:9!null z:10!null a:13!null abc.b:14 abc.c:15 abc.d:16
 │    ├── key: (5,9)
 │    ├── fd: (5)-->(6), (9)-->(10), (13)-->(14-16), (10)==(6,13), (13)==(6,10), (6)==(10,13)
 │    ├── scan cy
 │    │    ├── columns: cy.c:5!null y:6
 │    │    ├── key: (5)
 │    │    └── fd: (5)-->(6)
 │    ├── inner-join (hash)
 │    │    ├── columns: dz.d:9!null z:10!null a:13!null abc.b:14 abc.c:15 abc.d:16
 │    │    ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 │    │    ├── key: (9)
 │    │    ├── fd: (9)-->(10), (13)-->(14-16), (10)==(13), (13)==(10)
 │    │    ├── scan dz
 │    │    │    ├── columns: dz.d:9!null z:10
 │    │    │    ├── key: (9)
 │    │    │    └── fd: (9)-->(10)
 │    │    ├── scan abc
 │    │    │    ├── columns: a:13!null abc.b:14 abc.c:15 abc.d:16
 │    │    │    ├── key: (13)
 │    │    │    └── fd: (13)-->(14-16)
 │    │    └── filters
 │    │         └── z:10 = a:13 [outer=(10,13), constraints=(/10: (/NULL - ]; /13: (/NULL - ]), fd=(10)==(13), (13)==(10)]
 │    └── filters
 │         └── y:6 = z:10 [outer=(6,10), constraints=(/6: (/NULL - ]; /10: (/NULL - ]), fd=(6)==(10), (10)==(6)]
 ├── scan bx
 │    ├── columns: bx.b:1!null x:2
 │    ├── key: (1)
 │    └── fd: (1)-->(2)
 └── filters
      └── x:2 = y:6 [outer=(2,6), constraints=(/2: (/NULL - ]; /6: (/NULL - ]), fd=(2)==(6), (6)==(2)]

# Regression test for #34795.
exec-ddl
CREATE TABLE a (id INT8 PRIMARY KEY)
----

opt join-limit=3
SELECT
    1
FROM
    a as a1
    INNER JOIN a as a2 ON 1 = a2.id
    INNER JOIN a AS a3 ON a1.id = a3.id
    CROSS JOIN a as a4
WHERE
    a4.id = 1 AND (SELECT true FROM a WHERE a1.id = 1)
----
project
 ├── columns: "?column?":17!null
 ├── fd: ()-->(17)
 ├── inner-join (cross)
 │    ├── columns: a1.id:1!null a2.id:4!null a3.id:7!null a4.id:10!null bool:16!null
 │    ├── multiplicity: left-rows(zero-or-one), right-rows(zero-or-more)
 │    ├── key: (7)
 │    ├── fd: ()-->(4,10,16), (1)==(7), (7)==(1)
 │    ├── inner-join (cross)
 │    │    ├── columns: a1.id:1!null a2.id:4!null a3.id:7!null bool:16!null
 │    │    ├── multiplicity: left-rows(zero-or-more), right-rows(zero-or-one)
 │    │    ├── key: (7)
 │    │    ├── fd: ()-->(4,16), (1)==(7), (7)==(1)
 │    │    ├── scan a [as=a2]
 │    │    │    ├── columns: a2.id:4!null
 │    │    │    ├── constraint: /4: [/1 - /1]
 │    │    │    ├── cardinality: [0 - 1]
 │    │    │    ├── key: ()
 │    │    │    └── fd: ()-->(4)
 │    │    ├── inner-join (lookup a [as=a3])
 │    │    │    ├── columns: a1.id:1!null a3.id:7!null bool:16!null
 │    │    │    ├── key columns: [1] = [7]
 │    │    │    ├── lookup columns are key
 │    │    │    ├── key: (7)
 │    │    │    ├── fd: ()-->(16), (1)==(7), (7)==(1)
 │    │    │    ├── select
 │    │    │    │    ├── columns: a1.id:1!null bool:16!null
 │    │    │    │    ├── key: (1)
 │    │    │    │    ├── fd: ()-->(16)
 │    │    │    │    ├── ensure-distinct-on
 │    │    │    │    │    ├── columns: a1.id:1!null bool:16
 │    │    │    │    │    ├── grouping columns: a1.id:1!null
 │    │    │    │    │    ├── error: "more than one row returned by a subquery used as an expression"
 │    │    │    │    │    ├── key: (1)
 │    │    │    │    │    ├── fd: (1)-->(16)
 │    │    │    │    │    ├── left-join (cross)
 │    │    │    │    │    │    ├── columns: a1.id:1!null bool:16
 │    │    │    │    │    │    ├── scan a [as=a1]
 │    │    │    │    │    │    │    ├── columns: a1.id:1!null
 │    │    │    │    │    │    │    └── key: (1)
 │    │    │    │    │    │    ├── project
 │    │    │    │    │    │    │    ├── columns: bool:16!null
 │    │    │    │    │    │    │    ├── fd: ()-->(16)
 │    │    │    │    │    │    │    ├── scan a
 │    │    │    │    │    │    │    └── projections
 │    │    │    │    │    │    │         └── true [as=bool:16]
 │    │    │    │    │    │    └── filters
 │    │    │    │    │    │         └── a1.id:1 = 1 [outer=(1), constraints=(/1: [/1 - /1]; tight), fd=()-->(1)]
 │    │    │    │    │    └── aggregations
 │    │    │    │    │         └── const-agg [as=bool:16, outer=(16)]
 │    │    │    │    │              └── bool:16
 │    │    │    │    └── filters
 │    │    │    │         └── bool:16 [outer=(16), constraints=(/16: [/true - /true]; tight), fd=()-->(16)]
 │    │    │    └── filters (true)
 │    │    └── filters (true)
 │    ├── scan a [as=a4]
 │    │    ├── columns: a4.id:10!null
 │    │    ├── constraint: /10: [/1 - /1]
 │    │    ├── cardinality: [0 - 1]
 │    │    ├── key: ()
 │    │    └── fd: ()-->(10)
 │    └── filters (true)
 └── projections
      └── 1 [as="?column?":17]

# An edge for b = d should be added to the graph.
reorderjoins format=hide-all
SELECT * FROM bx
INNER JOIN cy ON b = c
INNER JOIN (SELECT * FROM dz WHERE z > 0) ON c = d
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── b = c
Vertexes
  A: scan bx
  B: scan cy
Edges
  b = c [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── b = c
   ├── select
   │    ├── scan dz
   │    └── filters
   │         └── z > 0
   └── filters
        └── c = d
Vertexes
  A: scan bx
  B: scan cy
  C: select
   ├── scan dz
   └── filters
        └── z > 0
Edges
  b = c [inner, ses=AB, tes=AB, rules=()]
  c = d [inner, ses=BC, tes=BC, rules=()]
  b = d [inner, ses=AC, tes=AC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  B AC [inner, refs=AB]
  AC B [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joins Considered: 12
================================================================================
Final Plan
================================================================================
inner-join (merge)
 ├── scan bx
 ├── inner-join (merge)
 │    ├── scan cy
 │    ├── select
 │    │    ├── scan dz
 │    │    └── filters
 │    │         └── z > 0
 │    └── filters (true)
 └── filters (true)

reorderjoins format=hide-all
SELECT * FROM bx
INNER JOIN cy ON b = c
INNER JOIN (SELECT max(z) AS m FROM dz) ON y = m
INNER JOIN abc ON m = a
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── bx.b = cy.c
Vertexes
  A: scan bx
  B: scan cy
Edges
  bx.b = cy.c [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── bx.b = cy.c
   ├── scalar-group-by
   │    ├── scan dz
   │    └── aggregations
   │         └── max
   │              └── z
   └── filters
        └── y = max
Vertexes
  A: scan bx
  B: scan cy
  C: scalar-group-by
   ├── scan dz
   └── aggregations
        └── max
             └── z
Edges
  bx.b = cy.c [inner, ses=AB, tes=AB, rules=()]
  y = max [inner, ses=BC, tes=BC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joins Considered: 8
--------------------------------------------------------------------------------
Join Tree #3
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── scan bx
   │    │    ├── scan cy
   │    │    └── filters
   │    │         └── bx.b = cy.c
   │    ├── scalar-group-by
   │    │    ├── scan dz
   │    │    └── aggregations
   │    │         └── max
   │    │              └── z
   │    └── filters
   │         └── y = max
   ├── scan abc
   └── filters
        └── max = a
Vertexes
  A: scan bx
  B: scan cy
  C: scalar-group-by
   ├── scan dz
   └── aggregations
        └── max
             └── z
  D: scan abc
Edges
  bx.b = cy.c [inner, ses=AB, tes=AB, rules=()]
  y = max [inner, ses=BC, tes=BC, rules=()]
  max = a [inner, ses=CD, tes=CD, rules=()]
  y = a [inner, ses=BD, tes=BD, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joining BD
  B D [inner, refs=BD]
  D B [inner, refs=BD]
Joining ABD
  A BD [inner, refs=AB]
  BD A [inner, refs=AB]
  AB D [inner, refs=BD]
  D AB [inner, refs=BD]
Joining CD
  C D [inner, refs=CD]
  D C [inner, refs=CD]
Joining BCD
  B CD [inner, refs=BC]
  CD B [inner, refs=BC]
  C BD [inner, refs=BC]
  BD C [inner, refs=BC]
  BC D [inner, refs=CD]
  D BC [inner, refs=CD]
Joining ABCD
  A BCD [inner, refs=AB]
  BCD A [inner, refs=AB]
  AB CD [inner, refs=BC]
  CD AB [inner, refs=BC]
  C ABD [inner, refs=BC]
  ABD C [inner, refs=BC]
  ABC D [inner, refs=CD]
  D ABC [inner, refs=CD]
Joins Considered: 30
================================================================================
Final Plan
================================================================================
inner-join (lookup bx)
 ├── lookup columns are key
 ├── inner-join (hash)
 │    ├── scan cy
 │    ├── inner-join (lookup abc)
 │    │    ├── lookup columns are key
 │    │    ├── scalar-group-by
 │    │    │    ├── scan dz
 │    │    │    └── aggregations
 │    │    │         └── max
 │    │    │              └── z
 │    │    └── filters (true)
 │    └── filters
 │         └── y = max
 └── filters (true)

# Treat the join with hints as a base relation. Note that the implicit edges
# x = a and y = a are added to the join graph. The x = y filter is not an edge
# because it comes from the join with hints. However, it can still be used in
# calculating transitive closure.
reorderjoins format=hide-all
SELECT * FROM bx
INNER HASH JOIN cy ON x = y
INNER JOIN dz ON y = z
INNER JOIN abc ON z = a
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── flags: force hash join (store right side)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── x = y
   ├── scan dz
   └── filters
        └── y = z
Vertexes
  A: inner-join (hash)
   ├── flags: force hash join (store right side)
   ├── scan bx
   ├── scan cy
   └── filters
        └── x = y
  B: scan dz
Edges
  y = z [inner, ses=AB, tes=AB, rules=()]
  x = z [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── flags: force hash join (store right side)
   │    │    ├── scan bx
   │    │    ├── scan cy
   │    │    └── filters
   │    │         └── x = y
   │    ├── scan dz
   │    └── filters
   │         └── y = z
   ├── scan abc
   └── filters
        └── z = a
Vertexes
  A: inner-join (hash)
   ├── flags: force hash join (store right side)
   ├── scan bx
   ├── scan cy
   └── filters
        └── x = y
  B: scan dz
  C: scan abc
Edges
  y = z [inner, ses=AB, tes=AB, rules=()]
  z = a [inner, ses=BC, tes=BC, rules=()]
  x = z [inner, ses=AB, tes=AB, rules=()]
  x = a [inner, ses=AC, tes=AC, rules=()]
  y = a [inner, ses=AC, tes=AC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  B AC [inner, refs=AB]
  AC B [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joins Considered: 12
================================================================================
Final Plan
================================================================================
inner-join (hash)
 ├── inner-join (hash)
 │    ├── flags: force hash join (store right side)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters
 │         └── x = y
 ├── inner-join (hash)
 │    ├── scan dz
 │    ├── scan abc
 │    └── filters
 │         └── z = a
 └── filters
      └── y = z

# Ignore the apply join. However, all other joins can be reordered despite the
# presence of outer columns.
reorderjoins format=hide-all
SELECT * FROM bx
INNER JOIN LATERAL
(
  SELECT * FROM (VALUES (x))
  INNER JOIN cy ON True
  INNER JOIN dz ON y = z
  INNER JOIN abc ON z = a
)
ON x = y
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan cy
   ├── scan dz
   └── filters
        └── y = z
Vertexes
  A: scan cy
  B: scan dz
Edges
  y = z [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan cy
   │    ├── scan dz
   │    └── filters
   │         └── y = z
   ├── scan abc
   └── filters
        └── z = a
Vertexes
  A: scan cy
  B: scan dz
  C: scan abc
Edges
  y = z [inner, ses=AB, tes=AB, rules=()]
  z = a [inner, ses=BC, tes=BC, rules=()]
  y = a [inner, ses=AC, tes=AC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  B AC [inner, refs=AB]
  AC B [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joins Considered: 12
--------------------------------------------------------------------------------
Join Tree #3
--------------------------------------------------------------------------------
  inner-join (cross)
   ├── values
   │    └── (x,)
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── scan cy
   │    │    ├── scan dz
   │    │    └── filters
   │    │         └── y = z
   │    ├── scan abc
   │    └── filters
   │         └── z = a
   └── filters (true)
Vertexes
  D: values
   └── (x,)
  A: scan cy
  B: scan dz
  C: scan abc
Edges
  y = z [inner, ses=AB, tes=AB, rules=()]
  z = a [inner, ses=BC, tes=BC, rules=()]
  cross [inner, ses=, tes=DABC, rules=()]
  y = a [inner, ses=AC, tes=AC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=AB]
  BC A [inner, refs=AB]
  B AC [inner, refs=AB]
  AC B [inner, refs=AB]
  AB C [inner, refs=BC]
  C AB [inner, refs=BC]
Joining DABC
  D ABC [inner, refs=]
  ABC D [inner, refs=]
Joins Considered: 14
================================================================================
Final Plan
================================================================================
inner-join-apply
 ├── scan bx
 ├── inner-join (cross)
 │    ├── inner-join (hash)
 │    │    ├── scan cy
 │    │    ├── inner-join (hash)
 │    │    │    ├── scan dz
 │    │    │    ├── scan abc
 │    │    │    └── filters
 │    │    │         └── z = a
 │    │    └── filters
 │    │         └── y = z
 │    ├── values
 │    │    └── (x,)
 │    └── filters (true)
 └── filters
      └── x = y

reorderjoins format=hide-all
SELECT * FROM
(
  SELECT b AS bx_b, c AS cy_c
  FROM bx
  INNER JOIN cy ON x = y
)
INNER JOIN
(
  SELECT b AS abc_b, c AS abc_c
  FROM abc
  INNER JOIN dz ON a = z
)
ON abc_b = bx_b AND abc_c = cy_c
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── x = y
Vertexes
  A: scan bx
  B: scan cy
Edges
  x = y [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan abc
   ├── scan dz
   └── filters
        └── a = z
Vertexes
  C: scan abc
  D: scan dz
Edges
  a = z [inner, ses=CD, tes=CD, rules=()]
Joining CD
  C D [inner, refs=CD]
  D C [inner, refs=CD]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #3
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── x = y
   ├── inner-join (hash)
   │    ├── scan abc
   │    ├── scan dz
   │    └── filters
   │         └── a = z
   └── filters
        ├── abc.b = bx.b
        └── abc.c = cy.c
Vertexes
  A: scan bx
  B: scan cy
  C: scan abc
  D: scan dz
Edges
  x = y [inner, ses=AB, tes=AB, rules=()]
  a = z [inner, ses=CD, tes=CD, rules=()]
  abc.b = bx.b [inner, ses=AC, tes=AC, rules=()]
  abc.c = cy.c [inner, ses=BC, tes=BC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining BC
  B C [inner, refs=BC]
  C B [inner, refs=BC]
Joining ABC
  A BC [inner, refs=ABC]
  BC A [inner, refs=ABC]
  B AC [inner, refs=ABC]
  AC B [inner, refs=ABC]
  AB C [inner, refs=ABC]
  C AB [inner, refs=ABC]
Joining CD
  C D [inner, refs=CD]
  D C [inner, refs=CD]
Joining ACD
  A CD [inner, refs=AC]
  CD A [inner, refs=AC]
  AC D [inner, refs=CD]
  D AC [inner, refs=CD]
Joining BCD
  B CD [inner, refs=BC]
  CD B [inner, refs=BC]
  BC D [inner, refs=CD]
  D BC [inner, refs=CD]
Joining ABCD
  A BCD [inner, refs=ABC]
  BCD A [inner, refs=ABC]
  B ACD [inner, refs=ABC]
  ACD B [inner, refs=ABC]
  AB CD [inner, refs=ABC]
  CD AB [inner, refs=ABC]
  ABC D [inner, refs=CD]
  D ABC [inner, refs=CD]
Joins Considered: 30
================================================================================
Final Plan
================================================================================
project
 └── inner-join (hash)
      ├── scan dz
      ├── inner-join (hash)
      │    ├── scan bx
      │    ├── inner-join (hash)
      │    │    ├── scan cy
      │    │    ├── scan abc
      │    │    └── filters
      │    │         └── abc.c = cy.c
      │    └── filters
      │         ├── x = y
      │         └── abc.b = bx.b
      └── filters
           └── a = z

reorderjoins format=hide-all
SELECT *
FROM bx
INNER JOIN cy ON b = c
LEFT JOIN dz ON x = z
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── b = c
Vertexes
  A: scan bx
  B: scan cy
Edges
  b = c [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  left-join (hash)
   ├── inner-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── b = c
   ├── scan dz
   └── filters
        └── x = z
Vertexes
  A: scan bx
  B: scan cy
  C: scan dz
Edges
  b = c [inner, ses=AB, tes=AB, rules=()]
  x = z [left, ses=AC, tes=AC, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining AC
  A C [left, refs=AC]
Joining ABC
  B AC [inner, refs=AB]
  AC B [inner, refs=AB]
  AB C [left, refs=AC]
Joins Considered: 6
================================================================================
Final Plan
================================================================================
left-join (hash)
 ├── inner-join (merge)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters (true)
 ├── scan dz
 └── filters
      └── x = z

# Left-asscom property for left joins.
reorderjoins format=hide-all
SELECT *
FROM bx
LEFT JOIN cy ON b = c
LEFT JOIN dz ON x = z
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  left-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── b = c
Vertexes
  A: scan bx
  B: scan cy
Edges
  b = c [left, ses=AB, tes=AB, rules=()]
Joining AB
  A B [left, refs=AB]
Joins Considered: 1
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  left-join (hash)
   ├── left-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── b = c
   ├── scan dz
   └── filters
        └── x = z
Vertexes
  A: scan bx
  B: scan cy
  C: scan dz
Edges
  b = c [left, ses=AB, tes=AB, rules=()]
  x = z [left, ses=AC, tes=AC, rules=()]
Joining AB
  A B [left, refs=AB]
Joining AC
  A C [left, refs=AC]
Joining ABC
  AC B [left, refs=AB]
  AB C [left, refs=AC]
Joins Considered: 4
================================================================================
Final Plan
================================================================================
left-join (hash)
 ├── left-join (merge)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters (true)
 ├── scan dz
 └── filters
      └── x = z

# Left-asscom property does not apply when the upper left join references the
# right side of the lower. However, associative property does apply when the
# predicate of the upper join rejects nulls on the right input of the lower
# join.
reorderjoins format=hide-all
SELECT *
FROM bx
LEFT JOIN cy ON b = c
LEFT JOIN dz ON y = z
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  left-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── b = c
Vertexes
  A: scan bx
  B: scan cy
Edges
  b = c [left, ses=AB, tes=AB, rules=()]
Joining AB
  A B [left, refs=AB]
Joins Considered: 1
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  left-join (hash)
   ├── left-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── b = c
   ├── scan dz
   └── filters
        └── y = z
Vertexes
  A: scan bx
  B: scan cy
  C: scan dz
Edges
  b = c [left, ses=AB, tes=AB, rules=()]
  y = z [left, ses=BC, tes=BC, rules=()]
Joining AB
  A B [left, refs=AB]
Joining BC
  B C [left, refs=BC]
Joining ABC
  A BC [left, refs=AB]
  AB C [left, refs=BC]
Joins Considered: 4
================================================================================
Final Plan
================================================================================
left-join (hash)
 ├── left-join (merge)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters (true)
 ├── scan dz
 └── filters
      └── y = z

# Left, semi and anti join tree. Multiple applications of left-asscom are
# possible. Note that the inner join results from commuting the semi join.
reorderjoins format=hide-all
SELECT *
FROM bx
LEFT JOIN cy ON bx.b = cy.c
WHERE
EXISTS (SELECT * FROM dz WHERE bx.b = dz.d) AND
NOT EXISTS (SELECT * FROM abc WHERE bx.b = abc.a)
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  anti-join (hash)
   ├── scan bx
   ├── scan abc
   └── filters
        └── bx.b = a
Vertexes
  A: scan bx
  B: scan abc
Edges
  bx.b = a [anti, ses=AB, tes=AB, rules=()]
Joining AB
  A B [anti, refs=AB]
Joins Considered: 1
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  semi-join (hash)
   ├── anti-join (hash)
   │    ├── scan bx
   │    ├── scan abc
   │    └── filters
   │         └── bx.b = a
   ├── scan dz
   └── filters
        └── bx.b = dz.d
Vertexes
  A: scan bx
  B: scan abc
  C: scan dz
Edges
  bx.b = a [anti, ses=AB, tes=AB, rules=()]
  bx.b = dz.d [semi, ses=AC, tes=AC, rules=()]
Joining AB
  A B [anti, refs=AB]
Joining AC
  A C [semi, refs=AC]
Joining ABC
  AC B [anti, refs=AB]
  AB C [semi, refs=AC]
Joins Considered: 4
--------------------------------------------------------------------------------
Join Tree #3
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── anti-join (hash)
   │    ├── scan bx
   │    ├── scan abc
   │    └── filters
   │         └── bx.b = a
   ├── scan dz
   └── filters
        └── bx.b = dz.d
Vertexes
  A: scan bx
  B: scan abc
  C: scan dz
Edges
  bx.b = a [anti, ses=AB, tes=AB, rules=()]
  bx.b = dz.d [inner, ses=AC, tes=AC, rules=()]
Joining AB
  A B [anti, refs=AB]
Joining AC
  A C [inner, refs=AC]
  C A [inner, refs=AC]
Joining ABC
  AC B [anti, refs=AB]
  AB C [inner, refs=AC]
  C AB [inner, refs=AC]
Joins Considered: 6
--------------------------------------------------------------------------------
Join Tree #4
--------------------------------------------------------------------------------
  left-join (hash)
   ├── semi-join (hash)
   │    ├── anti-join (hash)
   │    │    ├── scan bx
   │    │    ├── scan abc
   │    │    └── filters
   │    │         └── bx.b = a
   │    ├── scan dz
   │    └── filters
   │         └── bx.b = dz.d
   ├── scan cy
   └── filters
        └── bx.b = cy.c
Vertexes
  A: scan bx
  B: scan abc
  C: scan dz
  D: scan cy
Edges
  bx.b = a [anti, ses=AB, tes=AB, rules=()]
  bx.b = dz.d [semi, ses=AC, tes=AC, rules=()]
  bx.b = cy.c [left, ses=AD, tes=AD, rules=()]
Joining AB
  A B [anti, refs=AB]
Joining AC
  A C [semi, refs=AC]
Joining ABC
  AC B [anti, refs=AB]
  AB C [semi, refs=AC]
Joining AD
  A D [left, refs=AD]
Joining ABD
  AD B [anti, refs=AB]
  AB D [left, refs=AD]
Joining ACD
  AD C [semi, refs=AC]
  AC D [left, refs=AD]
Joining ABCD
  ACD B [anti, refs=AB]
  ABD C [semi, refs=AC]
  ABC D [left, refs=AD]
Joins Considered: 12
================================================================================
Final Plan
================================================================================
semi-join (lookup dz)
 ├── lookup columns are key
 ├── left-join (lookup cy)
 │    ├── lookup columns are key
 │    ├── anti-join (merge)
 │    │    ├── scan bx
 │    │    ├── scan abc
 │    │    └── filters (true)
 │    └── filters (true)
 └── filters (true)

# Join tree with only cross joins.
reorderjoins format=hide-all
SELECT * FROM bx
INNER JOIN cy ON True
INNER JOIN dz ON True
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  inner-join (cross)
   ├── scan bx
   ├── scan cy
   └── filters (true)
Vertexes
  A: scan bx
  B: scan cy
Edges
  cross [inner, ses=, tes=AB, rules=()]
Joining AB
  A B [inner, refs=]
  B A [inner, refs=]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (cross)
   ├── inner-join (cross)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters (true)
   ├── scan dz
   └── filters (true)
Vertexes
  A: scan bx
  B: scan cy
  C: scan dz
Edges
  cross [inner, ses=, tes=AB, rules=()]
  cross [inner, ses=, tes=ABC, rules=()]
Joining AB
  A B [inner, refs=]
  B A [inner, refs=]
Joining ABC
  AB C [inner, refs=]
  C AB [inner, refs=]
Joins Considered: 4
================================================================================
Final Plan
================================================================================
inner-join (cross)
 ├── inner-join (cross)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters (true)
 ├── scan dz
 └── filters (true)

reorderjoins format=hide-all
SELECT *
FROM bx
FULL JOIN cy ON b = c
FULL JOIN dz ON y = z
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  full-join (hash)
   ├── scan bx
   ├── scan cy
   └── filters
        └── b = c
Vertexes
  A: scan bx
  B: scan cy
Edges
  b = c [full, ses=AB, tes=AB, rules=()]
Joining AB
  A B [full, refs=AB]
  B A [full, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  full-join (hash)
   ├── full-join (hash)
   │    ├── scan bx
   │    ├── scan cy
   │    └── filters
   │         └── b = c
   ├── scan dz
   └── filters
        └── y = z
Vertexes
  A: scan bx
  B: scan cy
  C: scan dz
Edges
  b = c [full, ses=AB, tes=AB, rules=()]
  y = z [full, ses=BC, tes=BC, rules=()]
Joining AB
  A B [full, refs=AB]
  B A [full, refs=AB]
Joining BC
  B C [full, refs=BC]
  C B [full, refs=BC]
Joining ABC
  A BC [full, refs=AB]
  BC A [full, refs=AB]
  AB C [full, refs=BC]
  C AB [full, refs=BC]
Joins Considered: 8
================================================================================
Final Plan
================================================================================
full-join (hash)
 ├── full-join (merge)
 │    ├── scan bx
 │    ├── scan cy
 │    └── filters (true)
 ├── scan dz
 └── filters
      └── y = z

# Iteratively reorder subtrees of up to size 2.
reorderjoins join-limit=2 format=hide-all
SELECT * FROM abc AS a1
INNER JOIN abc AS a2 ON a1.a = a2.a
LEFT JOIN abc AS a3 ON a2.b = a3.b
INNER JOIN abc AS a4 ON a3.a = a4.a
WHERE EXISTS (SELECT * FROM abc AS a5 WHERE a2.c = a5.c)
----
--------------------------------------------------------------------------------
Join Tree #1
--------------------------------------------------------------------------------
  semi-join (hash)
   ├── scan abc [as=a2]
   ├── scan abc [as=a5]
   └── filters
        └── a2.c = a5.c
Vertexes
  A: scan abc [as=a2]
  B: scan abc [as=a5]
Edges
  a2.c = a5.c [semi, ses=AB, tes=AB, rules=()]
Joining AB
  A B [semi, refs=AB]
Joins Considered: 1
--------------------------------------------------------------------------------
Join Tree #2
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan abc [as=a2]
   ├── distinct-on
   │    └── scan abc [as=a5]
   └── filters
        └── a2.c = a5.c
Vertexes
  A: scan abc [as=a2]
  B: distinct-on
   └── scan abc [as=a5]
Edges
  a2.c = a5.c [inner, ses=AB, tes=AB, rules=()]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joins Considered: 2
--------------------------------------------------------------------------------
Join Tree #3
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan abc [as=a1]
   ├── semi-join (hash)
   │    ├── scan abc [as=a2]
   │    ├── scan abc [as=a5]
   │    └── filters
   │         └── a2.c = a5.c
   └── filters
        └── a1.a = a2.a
Vertexes
  C: scan abc [as=a1]
  A: scan abc [as=a2]
  B: scan abc [as=a5]
Edges
  a2.c = a5.c [semi, ses=AB, tes=AB, rules=()]
  a1.a = a2.a [inner, ses=CA, tes=CA, rules=()]
Joining CA
  C A [inner, refs=CA]
  A C [inner, refs=CA]
Joining AB
  A B [semi, refs=AB]
Joining CAB
  C AB [inner, refs=CA]
  AB C [inner, refs=CA]
  CA B [semi, refs=AB]
Joins Considered: 6
--------------------------------------------------------------------------------
Join Tree #4
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── scan abc [as=a1]
   ├── inner-join (hash)
   │    ├── scan abc [as=a2]
   │    ├── distinct-on
   │    │    └── scan abc [as=a5]
   │    └── filters
   │         └── a2.c = a5.c
   └── filters
        └── a1.a = a2.a
Vertexes
  C: scan abc [as=a1]
  A: scan abc [as=a2]
  B: distinct-on
   └── scan abc [as=a5]
Edges
  a2.c = a5.c [inner, ses=AB, tes=AB, rules=()]
  a1.a = a2.a [inner, ses=CA, tes=CA, rules=()]
Joining CA
  C A [inner, refs=CA]
  A C [inner, refs=CA]
Joining AB
  A B [inner, refs=AB]
  B A [inner, refs=AB]
Joining CAB
  C AB [inner, refs=CA]
  AB C [inner, refs=CA]
  CA B [inner, refs=AB]
  B CA [inner, refs=AB]
Joins Considered: 8
--------------------------------------------------------------------------------
Join Tree #5
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── scan abc [as=a1]
   │    ├── semi-join (hash)
   │    │    ├── scan abc [as=a2]
   │    │    ├── scan abc [as=a5]
   │    │    └── filters
   │    │         └── a2.c = a5.c
   │    └── filters
   │         └── a1.a = a2.a
   ├── scan abc [as=a3]
   └── filters
        └── a2.b = a3.b
Vertexes
  C: scan abc [as=a1]
  A: semi-join (hash)
   ├── scan abc [as=a2]
   ├── scan abc [as=a5]
   └── filters
        └── a2.c = a5.c
  D: scan abc [as=a3]
Edges
  a1.a = a2.a [inner, ses=CA, tes=CA, rules=()]
  a2.b = a3.b [inner, ses=AD, tes=AD, rules=()]
Joining CA
  C A [inner, refs=CA]
  A C [inner, refs=CA]
Joining AD
  A D [inner, refs=AD]
  D A [inner, refs=AD]
Joining CAD
  C AD [inner, refs=CA]
  AD C [inner, refs=CA]
  CA D [inner, refs=AD]
  D CA [inner, refs=AD]
Joins Considered: 8
--------------------------------------------------------------------------------
Join Tree #6
--------------------------------------------------------------------------------
  inner-join (hash)
   ├── inner-join (hash)
   │    ├── inner-join (hash)
   │    │    ├── scan abc [as=a1]
   │    │    ├── semi-join (hash)
   │    │    │    ├── scan abc [as=a2]
   │    │    │    ├── scan abc [as=a5]
   │    │    │    └── filters
   │    │    │         └── a2.c = a5.c
   │    │    └── filters
   │    │         └── a1.a = a2.a
   │    ├── scan abc [as=a3]
   │    └── filters
   │         └── a2.b = a3.b
   ├── scan abc [as=a4]
   └── filters
        └── a3.a = a4.a
Vertexes
  C: inner-join (hash)
   ├── scan abc [as=a1]
   ├── semi-join (hash)
   │    ├── scan abc [as=a2]
   │    ├── scan abc [as=a5]
   │    └── filters
   │         └── a2.c = a5.c
   └── filters
        └── a1.a = a2.a
  D: scan abc [as=a3]
  E: scan abc [as=a4]
Edges
  a2.b = a3.b [inner, ses=CD, tes=CD, rules=()]
  a3.a = a4.a [inner, ses=DE, tes=DE, rules=()]
Joining CD
  C D [inner, refs=CD]
  D C [inner, refs=CD]
Joining DE
  D E [inner, refs=DE]
  E D [inner, refs=DE]
Joining CDE
  C DE [inner, refs=CD]
  DE C [inner, refs=CD]
  CD E [inner, refs=DE]
  E CD [inner, refs=DE]
Joins Considered: 8
================================================================================
Final Plan
================================================================================
inner-join (hash)
 ├── project
 │    └── inner-join (hash)
 │         ├── inner-join (merge)
 │         │    ├── scan abc [as=a1]
 │         │    ├── scan abc [as=a2]
 │         │    └── filters (true)
 │         ├── distinct-on
 │         │    └── scan abc [as=a5]
 │         └── filters
 │              └── a2.c = a5.c
 ├── inner-join (merge)
 │    ├── scan abc [as=a3]
 │    ├── scan abc [as=a4]
 │    └── filters (true)
 └── filters
      └── a2.b = a3.b

# Regression test for #59076. Do not reorder on the inner join produced by
# CommuteSemiJoin when it matches on an already-reordered semi join because
# doing so can lead to an exponential blowup in the size of the memo.
check-size rule-limit=200 group-limit=100
SELECT * FROM cy
WHERE EXISTS (SELECT 1 FROM dz WHERE z = y)
AND EXISTS (SELECT 1 FROM bx WHERE x = y)
AND EXISTS (SELECT 1 FROM abc WHERE a = y)
----
Rules Applied: 148
Groups Added: 80


# Regression test for #76522. Do not produce query plans where some of the
# original filters have been omitted.

exec-ddl
CREATE TABLE t76522_1 (
	a INT NOT NULL,
	b INT NOT NULL,
	PRIMARY KEY (a ASC, b ASC)
)
----

exec-ddl
CREATE TABLE t76522_2 (
	a INT NOT NULL,
	c INT,
	should_not_be_eliminated INT,
	PRIMARY KEY (a ASC)
)
----

exec-ddl
CREATE TABLE t76522_3 (
	a INT NOT NULL,
	d INT NOT NULL,
	f INT,
	g INT,
	PRIMARY KEY (a ASC, d ASC)
)
----

exec-ddl
CREATE TABLE t76522_4 (
	e INT NOT NULL,
	f INT,
	g INT,
	PRIMARY KEY (e ASC)
)
----

exec-ddl
CREATE TABLE t76522_5 (
	h INT NOT NULL,
	f INT NOT NULL,
	g INT NOT NULL,
	b INT,
	should_not_be_eliminated INT,
	c INT,
	PRIMARY KEY (h ASC, f ASC, g ASC)
)
----

# Give t76522_1 many rows where a has many distincts.
exec-ddl
ALTER TABLE t76522_1 INJECT STATISTICS '[
    {
        "columns": [
            "a"
        ],
        "created_at": "2022-01-17 12:51:38.433911",
        "distinct_count": 9161427,
        "null_count": 0,
        "row_count": 44484238
    }
]'
----

# Give t76522_2 many rows where a has many distincts.
exec-ddl
ALTER TABLE t76522_2 INJECT STATISTICS '[
    {
        "columns": [
            "a"
        ],
        "created_at": "2022-01-17 12:51:38.433911",
        "distinct_count": 17014025,
        "null_count": 0,
        "row_count": 17024553
    }
]'
----

# Give t76522_3 many rows where a has many distincts.
exec-ddl
ALTER TABLE t76522_3 INJECT STATISTICS '[
    {
        "columns": [
            "a"
        ],
        "created_at": "2022-01-17 12:51:38.433911",
        "distinct_count": 17187349,
        "null_count": 0,
        "row_count": 18138540
    }
]'
----

# Give t76522_4 many rows where e has many distincts.
exec-ddl
ALTER TABLE t76522_4 INJECT STATISTICS '[
    {
        "columns": [
            "e"
        ],
        "created_at": "2022-01-17 12:51:38.433911",
        "distinct_count": 346919,
        "null_count": 0,
        "row_count": 346109
    }
]';
----

# Give t5 few rows.
exec-ddl
ALTER TABLE t76522_5 INJECT STATISTICS '[
    {
        "columns": [
            "h"
        ],
        "created_at": "2022-01-17 12:51:38.433911",
        "distinct_count": 119,
        "null_count": 0,
        "row_count": 119
    }
]'
----

# Prior to the fix, these filters were missing from the query plan:
#
#   t5.c = t2.c
#   t2.should_not_be_eliminated = t5.should_not_be_eliminated
#
opt
SELECT
  t2.a
FROM
  t76522_1 AS t1
  INNER JOIN t76522_2 AS t2 ON t1.a = t2.a
  INNER JOIN t76522_3 AS t3 ON t1.a = t3.a
  INNER JOIN t76522_4 AS t4 ON t3.d = t4.e
  INNER JOIN t76522_5 AS t5 ON
      t4.f = t5.f
      AND t4.g = t5.g
      AND t5.b = t1.b
      AND t5.c = t2.c
WHERE
  t1.a = 123456 AND t2.should_not_be_eliminated = t5.should_not_be_eliminated;
----
project
 ├── columns: a:5!null
 ├── fd: ()-->(5)
 └── inner-join (lookup t76522_1 [as=t1])
      ├── columns: t1.a:1!null t1.b:2!null t2.a:5!null t2.c:6!null t2.should_not_be_eliminated:7!null t3.a:10!null d:11!null e:16!null t4.f:17!null t4.g:18!null t5.f:22!null t5.g:23!null t5.b:24!null t5.should_not_be_eliminated:25!null t5.c:26!null
      ├── key columns: [5 24] = [1 2]
      ├── lookup columns are key
      ├── fd: ()-->(1,5-7,10,25,26), (1)==(5,10), (5)==(1,10), (10)==(1,5), (16)-->(17,18), (11)==(16), (16)==(11), (17)==(22), (22)==(17), (18)==(23), (23)==(18), (2)==(24), (24)==(2), (6)==(26), (26)==(6), (7)==(25), (25)==(7)
      ├── inner-join (lookup t76522_2 [as=t2])
      │    ├── columns: t2.a:5!null t2.c:6!null t2.should_not_be_eliminated:7!null t3.a:10!null d:11!null e:16!null t4.f:17!null t4.g:18!null t5.f:22!null t5.g:23!null t5.b:24 t5.should_not_be_eliminated:25!null t5.c:26!null
      │    ├── key columns: [10] = [5]
      │    ├── lookup columns are key
      │    ├── fd: ()-->(5-7,10,25,26), (16)-->(17,18), (17)==(22), (22)==(17), (18)==(23), (23)==(18), (11)==(16), (16)==(11), (6)==(26), (26)==(6), (7)==(25), (25)==(7), (5)==(10), (10)==(5)
      │    ├── inner-join (hash)
      │    │    ├── columns: t3.a:10!null d:11!null e:16!null t4.f:17!null t4.g:18!null t5.f:22!null t5.g:23!null t5.b:24 t5.should_not_be_eliminated:25 t5.c:26
      │    │    ├── fd: ()-->(10), (16)-->(17,18), (17)==(22), (22)==(17), (18)==(23), (23)==(18), (11)==(16), (16)==(11)
      │    │    ├── scan t76522_5 [as=t5]
      │    │    │    └── columns: t5.f:22!null t5.g:23!null t5.b:24 t5.should_not_be_eliminated:25 t5.c:26
      │    │    ├── inner-join (lookup t76522_4 [as=t4])
      │    │    │    ├── columns: t3.a:10!null d:11!null e:16!null t4.f:17 t4.g:18
      │    │    │    ├── key columns: [11] = [16]
      │    │    │    ├── lookup columns are key
      │    │    │    ├── key: (16)
      │    │    │    ├── fd: ()-->(10), (16)-->(17,18), (11)==(16), (16)==(11)
      │    │    │    ├── scan t76522_3 [as=t3]
      │    │    │    │    ├── columns: t3.a:10!null d:11!null
      │    │    │    │    ├── constraint: /10/11: [/123456 - /123456]
      │    │    │    │    ├── key: (11)
      │    │    │    │    └── fd: ()-->(10)
      │    │    │    └── filters (true)
      │    │    └── filters
      │    │         ├── t4.f:17 = t5.f:22 [outer=(17,22), constraints=(/17: (/NULL - ]; /22: (/NULL - ]), fd=(17)==(22), (22)==(17)]
      │    │         └── t4.g:18 = t5.g:23 [outer=(18,23), constraints=(/18: (/NULL - ]; /23: (/NULL - ]), fd=(18)==(23), (23)==(18)]
      │    └── filters
      │         ├── t5.c:26 = t2.c:6 [outer=(6,26), constraints=(/6: (/NULL - ]; /26: (/NULL - ]), fd=(6)==(26), (26)==(6)]
      │         ├── t2.should_not_be_eliminated:7 = t5.should_not_be_eliminated:25 [outer=(7,25), constraints=(/7: (/NULL - ]; /25: (/NULL - ]), fd=(7)==(25), (25)==(7)]
      │         └── t2.a:5 = 123456 [outer=(5), constraints=(/5: [/123456 - /123456]; tight), fd=()-->(5)]
      └── filters
           └── t1.a:1 = 123456 [outer=(1), constraints=(/1: [/123456 - /123456]; tight), fd=()-->(1)]