select

exec-ddl
CREATE TABLE a
(
    k INT PRIMARY KEY,
    u INT,
    v INT,
    INDEX u(u) STORING (v),
    UNIQUE INDEX v(v) STORING (u)
)
----

exec-ddl
CREATE TABLE b
(
    k INT PRIMARY KEY,
    u INT,
    v INT,
    j JSONB,
    INDEX u(u),
    UNIQUE INDEX v(v),
    INVERTED INDEX inv_idx(j)
)
----

exec-ddl
CREATE TABLE c
(
    k INT PRIMARY KEY,
    a INT[],
    INVERTED INDEX inv_idx(a)
)
----

# --------------------------------------------------
# GenerateConstrainedScans
# --------------------------------------------------

opt
SELECT k FROM a WHERE k = 1
----
scan a
 ├── columns: k:1!null
 ├── constraint: /1: [/1 - /1]
 ├── cardinality: [0 - 1]
 ├── key: ()
 └── fd: ()-->(1)

memo
SELECT k FROM a WHERE k = 1
----
memo (optimized, ~5KB, required=[presentation: k:1])
 ├── G1: (select G2 G3) (scan a,cols=(1),constrained)
 │    └── [presentation: k:1]
 │         ├── best: (scan a,cols=(1),constrained)
 │         └── cost: 1.05
 ├── G2: (scan a,cols=(1)) (scan a@u,cols=(1)) (scan a@v,cols=(1))
 │    └── []
 │         ├── best: (scan a,cols=(1))
 │         └── cost: 1040.02
 ├── G3: (filters G4)
 ├── G4: (eq G5 G6)
 ├── G5: (variable k)
 └── G6: (const 1)

opt
SELECT k FROM a WHERE v > 1
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── scan a@v
      ├── columns: k:1!null v:3!null
      ├── constraint: /3: [/2 - ]
      ├── key: (1)
      └── fd: (1)-->(3), (3)-->(1)

memo
SELECT k FROM a WHERE v > 1
----
memo (optimized, ~6KB, required=[presentation: k:1])
 ├── G1: (project G2 G3 k)
 │    └── [presentation: k:1]
 │         ├── best: (project G2 G3 k)
 │         └── cost: 350.17
 ├── G2: (select G4 G5) (scan a@v,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan a@v,cols=(1,3),constrained)
 │         └── cost: 346.86
 ├── G3: (projections)
 ├── G4: (scan a,cols=(1,3)) (scan a@u,cols=(1,3)) (scan a@v,cols=(1,3))
 │    └── []
 │         ├── best: (scan a,cols=(1,3))
 │         └── cost: 1050.02
 ├── G5: (filters G6)
 ├── G6: (gt G7 G8)
 ├── G7: (variable v)
 └── G8: (const 1)

opt
SELECT k FROM a WHERE u = 1 AND k = 5
----
project
 ├── columns: k:1!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1)
 └── scan a@u
      ├── columns: k:1!null u:2!null
      ├── constraint: /2/1: [/1/5 - /1/5]
      ├── cardinality: [0 - 1]
      ├── key: ()
      └── fd: ()-->(1,2)

memo
SELECT k FROM a WHERE u = 1 AND k = 5
----
memo (optimized, ~7KB, required=[presentation: k:1])
 ├── G1: (project G2 G3 k)
 │    └── [presentation: k:1]
 │         ├── best: (project G2 G3 k)
 │         └── cost: 1.07
 ├── G2: (select G4 G5) (select G6 G7) (scan a@u,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan a@u,cols=(1,2),constrained)
 │         └── cost: 1.05
 ├── G3: (projections)
 ├── G4: (scan a,cols=(1,2)) (scan a@u,cols=(1,2)) (scan a@v,cols=(1,2))
 │    └── []
 │         ├── best: (scan a,cols=(1,2))
 │         └── cost: 1050.02
 ├── G5: (filters G8 G9)
 ├── G6: (scan a,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan a,cols=(1,2),constrained)
 │         └── cost: 1.06
 ├── G7: (filters G8)
 ├── G8: (eq G10 G11)
 ├── G9: (eq G12 G13)
 ├── G10: (variable u)
 ├── G11: (const 1)
 ├── G12: (variable k)
 └── G13: (const 5)

# Constraint + remaining filter.
opt
SELECT k FROM a WHERE u = 1 AND k+u = 1
----
project
 ├── columns: k:1!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1)
 └── scan a@u
      ├── columns: k:1!null u:2!null
      ├── constraint: /2/1: [/1/0 - /1/0]
      ├── cardinality: [0 - 1]
      ├── key: ()
      └── fd: ()-->(1,2)

memo
SELECT k FROM a WHERE u = 1 AND k+u = 1
----
memo (optimized, ~8KB, required=[presentation: k:1])
 ├── G1: (project G2 G3 k)
 │    └── [presentation: k:1]
 │         ├── best: (project G2 G3 k)
 │         └── cost: 1.07
 ├── G2: (select G4 G5) (select G6 G7) (scan a@u,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan a@u,cols=(1,2),constrained)
 │         └── cost: 1.05
 ├── G3: (projections)
 ├── G4: (scan a,cols=(1,2)) (scan a@u,cols=(1,2)) (scan a@v,cols=(1,2))
 │    └── []
 │         ├── best: (scan a,cols=(1,2))
 │         └── cost: 1050.02
 ├── G5: (filters G8 G9)
 ├── G6: (scan a,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan a,cols=(1,2),constrained)
 │         └── cost: 1.06
 ├── G7: (filters G8)
 ├── G8: (eq G10 G11)
 ├── G9: (eq G12 G13)
 ├── G10: (variable u)
 ├── G11: (const 1)
 ├── G12: (variable k)
 └── G13: (const 0)

opt
SELECT k FROM a WHERE u = 1 AND v = 5
----
project
 ├── columns: k:1!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1)
 └── select
      ├── columns: k:1!null u:2!null v:3!null
      ├── cardinality: [0 - 1]
      ├── key: ()
      ├── fd: ()-->(1-3)
      ├── scan a@v
      │    ├── columns: k:1!null u:2 v:3!null
      │    ├── constraint: /3: [/5 - /5]
      │    ├── cardinality: [0 - 1]
      │    ├── key: ()
      │    └── fd: ()-->(1-3)
      └── filters
           └── u:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]

memo
SELECT k FROM a WHERE u = 1 AND v = 5
----
memo (optimized, ~6KB, required=[presentation: k:1])
 ├── G1: (project G2 G3 k)
 │    └── [presentation: k:1]
 │         ├── best: (project G2 G3 k)
 │         └── cost: 1.10
 ├── G2: (select G4 G5) (select G6 G7) (select G8 G9)
 │    └── []
 │         ├── best: (select G8 G9)
 │         └── cost: 1.09
 ├── G3: (projections)
 ├── G4: (scan a) (scan a@u) (scan a@v)
 │    └── []
 │         ├── best: (scan a)
 │         └── cost: 1060.02
 ├── G5: (filters G10 G11)
 ├── G6: (scan a@u,constrained)
 │    └── []
 │         ├── best: (scan a@u,constrained)
 │         └── cost: 10.61
 ├── G7: (filters G11)
 ├── G8: (scan a@v,constrained)
 │    └── []
 │         ├── best: (scan a@v,constrained)
 │         └── cost: 1.07
 ├── G9: (filters G10)
 ├── G10: (eq G12 G13)
 ├── G11: (eq G14 G15)
 ├── G12: (variable u)
 ├── G13: (const 1)
 ├── G14: (variable v)
 └── G15: (const 5)

# Only not-null constraint is pushed down.
opt
SELECT k FROM a WHERE u=v
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── select
      ├── columns: k:1!null u:2!null v:3!null
      ├── key: (1)
      ├── fd: (1)-->(2,3), (3)-->(1), (2)==(3), (3)==(2)
      ├── scan a@u
      │    ├── columns: k:1!null u:2!null v:3
      │    ├── constraint: /2/1: (/NULL - ]
      │    ├── key: (1)
      │    └── fd: (1)-->(2,3), (3)~~>(1,2)
      └── filters
           └── u:2 = v:3 [outer=(2,3), constraints=(/2: (/NULL - ]; /3: (/NULL - ]), fd=(2)==(3), (3)==(2)]

# Don't push constraint into already limited scan.
opt
SELECT k FROM (SELECT k FROM a ORDER BY u LIMIT 1) a WHERE k = 1
----
project
 ├── columns: k:1!null
 ├── cardinality: [0 - 1]
 ├── key: ()
 ├── fd: ()-->(1)
 └── select
      ├── columns: k:1!null u:2
      ├── cardinality: [0 - 1]
      ├── key: ()
      ├── fd: ()-->(1,2)
      ├── scan a@u
      │    ├── columns: k:1!null u:2
      │    ├── limit: 1
      │    ├── key: ()
      │    └── fd: ()-->(1,2)
      └── filters
           └── k:1 = 1 [outer=(1), constraints=(/1: [/1 - /1]; tight), fd=()-->(1)]

# Constraint + index-join, with no remainder filter.
opt
SELECT * FROM b WHERE v >= 1 AND v <= 10
----
index-join b
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 └── scan b@v
      ├── columns: k:1!null v:3!null
      ├── constraint: /3: [/1 - /10]
      ├── cardinality: [0 - 10]
      ├── key: (1)
      └── fd: (1)-->(3), (3)-->(1)

memo
SELECT * FROM b WHERE v >= 1 AND v <= 10
----
memo (optimized, ~3KB, required=[presentation: k:1,u:2,v:3,j:4])
 ├── G1: (select G2 G3) (index-join G4 b,cols=(1-4))
 │    └── [presentation: k:1,u:2,v:3,j:4]
 │         ├── best: (index-join G4 b,cols=(1-4))
 │         └── cost: 51.32
 ├── G2: (scan b)
 │    └── []
 │         ├── best: (scan b)
 │         └── cost: 1080.02
 ├── G3: (filters G5)
 ├── G4: (scan b@v,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan b@v,cols=(1,3),constrained)
 │         └── cost: 10.41
 ├── G5: (range G6)
 ├── G6: (and G7 G8)
 ├── G7: (ge G9 G10)
 ├── G8: (le G9 G11)
 ├── G9: (variable v)
 ├── G10: (const 1)
 └── G11: (const 10)

# Don't choose lookup join if it's not beneficial.
opt
SELECT * FROM b WHERE v > 1
----
select
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── v:3 > 1 [outer=(3), constraints=(/3: [/2 - ]; tight)]

opt
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k > 5
----
index-join b
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 └── select
      ├── columns: k:1!null v:3!null
      ├── cardinality: [0 - 10]
      ├── key: (1)
      ├── fd: (1)-->(3), (3)-->(1)
      ├── scan b@v
      │    ├── columns: k:1!null v:3!null
      │    ├── constraint: /3: [/1 - /10]
      │    ├── cardinality: [0 - 10]
      │    ├── key: (1)
      │    └── fd: (1)-->(3), (3)-->(1)
      └── filters
           └── k:1 > 5 [outer=(1), constraints=(/1: [/6 - ]; tight)]

memo
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k > 5
----
memo (optimized, ~6KB, required=[presentation: k:1,u:2,v:3,j:4])
 ├── G1: (select G2 G3) (select G4 G5) (index-join G6 b,cols=(1-4))
 │    └── [presentation: k:1,u:2,v:3,j:4]
 │         ├── best: (index-join G6 b,cols=(1-4))
 │         └── cost: 24.16
 ├── G2: (scan b)
 │    └── []
 │         ├── best: (scan b)
 │         └── cost: 1080.02
 ├── G3: (filters G7 G8)
 ├── G4: (scan b,constrained)
 │    └── []
 │         ├── best: (scan b,constrained)
 │         └── cost: 360.01
 ├── G5: (filters G7)
 ├── G6: (select G9 G10)
 │    └── []
 │         ├── best: (select G9 G10)
 │         └── cost: 10.52
 ├── G7: (range G11)
 ├── G8: (gt G12 G13)
 ├── G9: (scan b@v,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan b@v,cols=(1,3),constrained)
 │         └── cost: 10.41
 ├── G10: (filters G8)
 ├── G11: (and G14 G15)
 ├── G12: (variable k)
 ├── G13: (const 5)
 ├── G14: (ge G16 G17)
 ├── G15: (le G16 G18)
 ├── G16: (variable v)
 ├── G17: (const 1)
 └── G18: (const 10)

# Ensure the rule doesn't match at all when the first column of the index is
# not in the filter (i.e. the @v index is not matched by ConstrainScans).
exploretrace rule=GenerateConstrainedScans
SELECT k FROM a WHERE u = 1
----
----
================================================================================
GenerateConstrainedScans
================================================================================
Source expression:
  project
   ├── columns: k:1!null
   ├── key: (1)
   └── select
        ├── columns: k:1!null u:2!null
        ├── key: (1)
        ├── fd: ()-->(2)
        ├── scan a
        │    ├── columns: k:1!null u:2
        │    ├── key: (1)
        │    └── fd: (1)-->(2)
        └── filters
             └── u:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]

New expression 1 of 1:
  project
   ├── columns: k:1!null
   ├── key: (1)
   └── scan a@u
        ├── columns: k:1!null u:2!null
        ├── constraint: /2/1: [/1 - /1]
        ├── key: (1)
        └── fd: ()-->(2)
----
----

# Constraint + index join + remaining filter.
opt
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k+u = 1
----
select
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 ├── index-join b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── cardinality: [0 - 10]
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3)-->(1), (3)~~>(1,2,4)
 │    └── scan b@v
 │         ├── columns: k:1!null v:3!null
 │         ├── constraint: /3: [/1 - /10]
 │         ├── cardinality: [0 - 10]
 │         ├── key: (1)
 │         └── fd: (1)-->(3), (3)-->(1)
 └── filters
      └── (k:1 + u:2) = 1 [outer=(1,2)]

memo
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k+u = 1
----
memo (optimized, ~5KB, required=[presentation: k:1,u:2,v:3,j:4])
 ├── G1: (select G2 G3) (select G4 G5)
 │    └── [presentation: k:1,u:2,v:3,j:4]
 │         ├── best: (select G4 G5)
 │         └── cost: 51.43
 ├── G2: (scan b)
 │    └── []
 │         ├── best: (scan b)
 │         └── cost: 1080.02
 ├── G3: (filters G6 G7)
 ├── G4: (index-join G8 b,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G8 b,cols=(1-4))
 │         └── cost: 51.32
 ├── G5: (filters G7)
 ├── G6: (range G9)
 ├── G7: (eq G10 G11)
 ├── G8: (scan b@v,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan b@v,cols=(1,3),constrained)
 │         └── cost: 10.41
 ├── G9: (and G12 G13)
 ├── G10: (plus G14 G15)
 ├── G11: (const 1)
 ├── G12: (ge G16 G11)
 ├── G13: (le G16 G17)
 ├── G14: (variable k)
 ├── G15: (variable u)
 ├── G16: (variable v)
 └── G17: (const 10)

opt
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k+u = 1 AND k > 5
----
select
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 ├── index-join b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── cardinality: [0 - 10]
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3)-->(1), (3)~~>(1,2,4)
 │    └── select
 │         ├── columns: k:1!null v:3!null
 │         ├── cardinality: [0 - 10]
 │         ├── key: (1)
 │         ├── fd: (1)-->(3), (3)-->(1)
 │         ├── scan b@v
 │         │    ├── columns: k:1!null v:3!null
 │         │    ├── constraint: /3: [/1 - /10]
 │         │    ├── cardinality: [0 - 10]
 │         │    ├── key: (1)
 │         │    └── fd: (1)-->(3), (3)-->(1)
 │         └── filters
 │              └── k:1 > 5 [outer=(1), constraints=(/1: [/6 - ]; tight)]
 └── filters
      └── (k:1 + u:2) = 1 [outer=(1,2)]

memo
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k+u = 1 AND k > 5
----
memo (optimized, ~7KB, required=[presentation: k:1,u:2,v:3,j:4])
 ├── G1: (select G2 G3) (select G4 G5) (select G6 G7)
 │    └── [presentation: k:1,u:2,v:3,j:4]
 │         ├── best: (select G6 G7)
 │         └── cost: 24.21
 ├── G2: (scan b)
 │    └── []
 │         ├── best: (scan b)
 │         └── cost: 1080.02
 ├── G3: (filters G8 G9 G10)
 ├── G4: (scan b,constrained)
 │    └── []
 │         ├── best: (scan b,constrained)
 │         └── cost: 360.01
 ├── G5: (filters G8 G9)
 ├── G6: (index-join G11 b,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G11 b,cols=(1-4))
 │         └── cost: 24.16
 ├── G7: (filters G9)
 ├── G8: (range G12)
 ├── G9: (eq G13 G14)
 ├── G10: (gt G15 G16)
 ├── G11: (select G17 G18)
 │    └── []
 │         ├── best: (select G17 G18)
 │         └── cost: 10.52
 ├── G12: (and G19 G20)
 ├── G13: (plus G15 G21)
 ├── G14: (const 1)
 ├── G15: (variable k)
 ├── G16: (const 5)
 ├── G17: (scan b@v,cols=(1,3),constrained)
 │    └── []
 │         ├── best: (scan b@v,cols=(1,3),constrained)
 │         └── cost: 10.41
 ├── G18: (filters G10)
 ├── G19: (ge G22 G14)
 ├── G20: (le G22 G23)
 ├── G21: (variable u)
 ├── G22: (variable v)
 └── G23: (const 10)

# Constraint + index-join.
opt
SELECT * FROM b WHERE (u, k, v) > (1, 2, 3) AND (u, k, v) < (8, 9, 10)
----
select
 ├── columns: k:1!null u:2!null v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── index-join b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 │    └── scan b@u
 │         ├── columns: k:1!null u:2!null
 │         ├── constraint: /2/1: [/1/2 - /8/9]
 │         ├── key: (1)
 │         └── fd: (1)-->(2)
 └── filters
      ├── (u:2, k:1, v:3) > (1, 2, 3) [outer=(1-3), constraints=(/2/1/3: [/1/2/4 - ]; tight)]
      └── (u:2, k:1, v:3) < (8, 9, 10) [outer=(1-3), constraints=(/2/1/3: (/NULL - /8/9/9]; tight)]

memo
SELECT * FROM b WHERE (u, k, v) > (1, 2, 3) AND (u, k, v) < (8, 9, 10)
----
memo (optimized, ~5KB, required=[presentation: k:1,u:2,v:3,j:4])
 ├── G1: (select G2 G3) (select G4 G3)
 │    └── [presentation: k:1,u:2,v:3,j:4]
 │         ├── best: (select G4 G3)
 │         └── cost: 45.72
 ├── G2: (scan b)
 │    └── []
 │         ├── best: (scan b)
 │         └── cost: 1080.02
 ├── G3: (filters G5 G6)
 ├── G4: (index-join G7 b,cols=(1-4))
 │    └── []
 │         ├── best: (index-join G7 b,cols=(1-4))
 │         └── cost: 45.62
 ├── G5: (gt G8 G9)
 ├── G6: (lt G8 G10)
 ├── G7: (scan b@u,cols=(1,2),constrained)
 │    └── []
 │         ├── best: (scan b@u,cols=(1,2),constrained)
 │         └── cost: 9.25
 ├── G8: (tuple G11)
 ├── G9: (tuple G12)
 ├── G10: (tuple G13)
 ├── G11: (scalar-list G14 G15 G16)
 ├── G12: (scalar-list G17 G18 G19)
 ├── G13: (scalar-list G20 G21 G22)
 ├── G14: (variable u)
 ├── G15: (variable k)
 ├── G16: (variable v)
 ├── G17: (const 1)
 ├── G18: (const 2)
 ├── G19: (const 3)
 ├── G20: (const 8)
 ├── G21: (const 9)
 └── G22: (const 10)

# GenerateConstrainedScans propagates row-level locking information.
opt
SELECT k FROM a WHERE k = 1 FOR UPDATE
----
scan a
 ├── columns: k:1!null
 ├── constraint: /1: [/1 - /1]
 ├── locking: for-update
 ├── cardinality: [0 - 1]
 ├── key: ()
 └── fd: ()-->(1)

opt
SELECT * FROM b WHERE v >= 1 AND v <= 10 FOR UPDATE
----
index-join b
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 └── scan b@v
      ├── columns: k:1!null v:3!null
      ├── constraint: /3: [/1 - /10]
      ├── locking: for-update
      ├── cardinality: [0 - 10]
      ├── key: (1)
      └── fd: (1)-->(3), (3)-->(1)

opt
SELECT * FROM b WHERE v >= 1 AND v <= 10 AND k+u = 1 FOR UPDATE
----
select
 ├── columns: k:1!null u:2 v:3!null j:4
 ├── cardinality: [0 - 10]
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)-->(1,2,4)
 ├── index-join b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── cardinality: [0 - 10]
 │    ├── key: (1)
 │    ├── fd: (1)-->(2-4), (3)-->(1), (3)~~>(1,2,4)
 │    └── scan b@v
 │         ├── columns: k:1!null v:3!null
 │         ├── constraint: /3: [/1 - /10]
 │         ├── locking: for-update
 │         ├── cardinality: [0 - 10]
 │         ├── key: (1)
 │         └── fd: (1)-->(3), (3)-->(1)
 └── filters
      └── (k:1 + u:2) = 1 [outer=(1,2)]

# --------------------------------------------------
# GenerateInvertedIndexScans
# --------------------------------------------------
# TODO(justin): these can be serviced without an index join.
# Query only the primary key with no remaining filter.
opt
SELECT k FROM b WHERE j @> '{"a": "b"}'
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── index-join b
      ├── columns: k:1!null j:4
      ├── key: (1)
      ├── fd: (1)-->(4)
      └── scan b@inv_idx
           ├── columns: k:1!null
           ├── constraint: /4/1: [/'{"a": "b"}' - /'{"a": "b"}']
           └── key: (1)

memo
SELECT k FROM b WHERE j @> '{"a": "b"}'
----
memo (optimized, ~6KB, required=[presentation: k:1])
 ├── G1: (project G2 G3 k)
 │    └── [presentation: k:1]
 │         ├── best: (project G2 G3 k)
 │         └── cost: 567.81
 ├── G2: (select G4 G5) (index-join G6 b,cols=(1,4))
 │    └── []
 │         ├── best: (index-join G6 b,cols=(1,4))
 │         └── cost: 566.69
 ├── G3: (projections)
 ├── G4: (scan b,cols=(1,4))
 │    └── []
 │         ├── best: (scan b,cols=(1,4))
 │         └── cost: 1060.02
 ├── G5: (filters G7)
 ├── G6: (scan b@inv_idx,cols=(1),constrained)
 │    └── []
 │         ├── best: (scan b@inv_idx,cols=(1),constrained)
 │         └── cost: 114.45
 ├── G7: (contains G8 G9)
 ├── G8: (variable j)
 └── G9: (const '{"a": "b"}')

# Query only the primary key with a remaining filter. 2+ paths in containment
# query should favor zigzag joins.
opt
SELECT k FROM b WHERE j @> '{"a": "b", "c": "d"}'
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── inner-join (lookup b)
      ├── columns: k:1!null j:4
      ├── key columns: [1] = [1]
      ├── lookup columns are key
      ├── key: (1)
      ├── fd: (1)-->(4)
      ├── inner-join (zigzag b@inv_idx b@inv_idx)
      │    ├── columns: k:1!null
      │    ├── eq columns: [1] = [1]
      │    ├── left fixed columns: [4] = ['{"a": "b"}']
      │    ├── right fixed columns: [4] = ['{"c": "d"}']
      │    └── filters (true)
      └── filters
           └── j:4 @> '{"a": "b", "c": "d"}' [outer=(4)]

# Query requiring an index join with no remaining filter.
opt
SELECT u, k FROM b WHERE j @> '{"a": "b"}'
----
project
 ├── columns: u:2 k:1!null
 ├── key: (1)
 ├── fd: (1)-->(2)
 └── index-join b
      ├── columns: k:1!null u:2 j:4
      ├── key: (1)
      ├── fd: (1)-->(2,4)
      └── scan b@inv_idx
           ├── columns: k:1!null
           ├── constraint: /4/1: [/'{"a": "b"}' - /'{"a": "b"}']
           └── key: (1)

opt
SELECT j, k FROM b WHERE j @> '{"a": "b"}'
----
index-join b
 ├── columns: j:4 k:1!null
 ├── key: (1)
 ├── fd: (1)-->(4)
 └── scan b@inv_idx
      ├── columns: k:1!null
      ├── constraint: /4/1: [/'{"a": "b"}' - /'{"a": "b"}']
      └── key: (1)

opt
SELECT * FROM b WHERE j @> '{"a": "b"}'
----
index-join b
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── scan b@inv_idx
      ├── columns: k:1!null
      ├── constraint: /4/1: [/'{"a": "b"}' - /'{"a": "b"}']
      └── key: (1)

# Query requiring a zigzag join with a remaining filter.
# TODO(itsbilal): remove filter from index join if zigzag join covers it.
opt
SELECT j, k FROM b WHERE j @> '{"a": "b", "c": "d"}'
----
inner-join (lookup b)
 ├── columns: j:4 k:1!null
 ├── key columns: [1] = [1]
 ├── lookup columns are key
 ├── key: (1)
 ├── fd: (1)-->(4)
 ├── inner-join (zigzag b@inv_idx b@inv_idx)
 │    ├── columns: k:1!null
 │    ├── eq columns: [1] = [1]
 │    ├── left fixed columns: [4] = ['{"a": "b"}']
 │    ├── right fixed columns: [4] = ['{"c": "d"}']
 │    └── filters (true)
 └── filters
      └── j:4 @> '{"a": "b", "c": "d"}' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '{"a": {"b": "c", "d": "e"}, "f": "g"}'
----
inner-join (lookup b)
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key columns: [1] = [1]
 ├── lookup columns are key
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── inner-join (zigzag b@inv_idx b@inv_idx)
 │    ├── columns: k:1!null
 │    ├── eq columns: [1] = [1]
 │    ├── left fixed columns: [4] = ['{"a": {"b": "c"}}']
 │    ├── right fixed columns: [4] = ['{"a": {"d": "e"}}']
 │    └── filters (true)
 └── filters
      └── j:4 @> '{"a": {"b": "c", "d": "e"}, "f": "g"}' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '{}'
----
select
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── j:4 @> '{}' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '[]'
----
select
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── j:4 @> '[]' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '2'
----
index-join b
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── scan b@inv_idx
      ├── columns: k:1!null
      ├── constraint: /4/1
      │    ├── [/'2' - /'2']
      │    └── [/'[2]' - /'[2]']
      └── key: (1)

opt
SELECT * FROM b WHERE j @> '[{}]'
----
select
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── j:4 @> '[{}]' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '{"a": {}}'
----
select
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── j:4 @> '{"a": {}}' [outer=(4)]

opt
SELECT * FROM b WHERE j @> '{"a": []}'
----
select
 ├── columns: k:1!null u:2 v:3 j:4
 ├── key: (1)
 ├── fd: (1)-->(2-4), (3)~~>(1,2,4)
 ├── scan b
 │    ├── columns: k:1!null u:2 v:3 j:4
 │    ├── key: (1)
 │    └── fd: (1)-->(2-4), (3)~~>(1,2,4)
 └── filters
      └── j:4 @> '{"a": []}' [outer=(4)]

# GenerateInvertedIndexScans propagates row-level locking information.
opt
SELECT k FROM b WHERE j @> '{"a": "b"}' FOR UPDATE
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── index-join b
      ├── columns: k:1!null j:4
      ├── key: (1)
      ├── fd: (1)-->(4)
      └── scan b@inv_idx
           ├── columns: k:1!null
           ├── constraint: /4/1: [/'{"a": "b"}' - /'{"a": "b"}']
           ├── locking: for-update
           └── key: (1)

# Write some tests for array inverted indexes.

opt
SELECT k FROM c WHERE a @> ARRAY[1]
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── index-join c
      ├── columns: k:1!null a:2
      ├── key: (1)
      ├── fd: (1)-->(2)
      └── scan c@inv_idx
           ├── columns: k:1!null
           ├── constraint: /2/1: [/ARRAY[1] - /ARRAY[1]]
           └── key: (1)

opt
SELECT k FROM c WHERE a @> ARRAY[1,3,1,5]
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── inner-join (lookup c)
      ├── columns: k:1!null a:2
      ├── key columns: [1] = [1]
      ├── lookup columns are key
      ├── key: (1)
      ├── fd: (1)-->(2)
      ├── inner-join (zigzag c@inv_idx c@inv_idx)
      │    ├── columns: k:1!null
      │    ├── eq columns: [1] = [1]
      │    ├── left fixed columns: [2] = [ARRAY[1]]
      │    ├── right fixed columns: [2] = [ARRAY[3]]
      │    └── filters (true)
      └── filters
           └── a:2 @> ARRAY[1,3,1,5] [outer=(2)]

opt
SELECT k FROM c WHERE a @> ARRAY[]::INT[]
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── select
      ├── columns: k:1!null a:2
      ├── key: (1)
      ├── fd: (1)-->(2)
      ├── scan c
      │    ├── columns: k:1!null a:2
      │    ├── key: (1)
      │    └── fd: (1)-->(2)
      └── filters
           └── a:2 @> ARRAY[] [outer=(2)]

opt
SELECT k FROM c WHERE a IS NULL
----
project
 ├── columns: k:1!null
 ├── key: (1)
 └── select
      ├── columns: k:1!null a:2
      ├── key: (1)
      ├── fd: ()-->(2)
      ├── scan c
      │    ├── columns: k:1!null a:2
      │    ├── key: (1)
      │    └── fd: (1)-->(2)
      └── filters
           └── a:2 IS NULL [outer=(2), constraints=(/2: [/NULL - /NULL]; tight), fd=()-->(2)]