opt, invertedexpr: inverted join may return incorrect results with additional filter

[rytaft]

There is a bug in the inverted join logic which may cause some rows to be incorrectly omitted from the output if there is an additional scalar filter that is part of the join condition. For example:

statement ok
CREATE TABLE g (
  k INT PRIMARY KEY,
  geom GEOMETRY
)

statement ok
CREATE INVERTED INDEX foo_inv ON g(geom)

statement ok
INSERT INTO g VALUES
  (1, ST_MakePolygon('LINESTRING(0 0, 0 15, 15 15, 15 0, 0 0)'::geometry)),
  (2, ST_MakePolygon('LINESTRING(0 0, 0 2, 2 2, 2 0, 0 0)'::geometry))

# This query performs an inverted join with an additional filter.
query TTT
EXPLAIN SELECT g1.k, g2.k FROM g@foo_inv AS g1, g@primary AS g2
WHERE ST_Contains(g1.geom, g2.geom)
  AND ST_Contains(g1.geom, ST_MakePolygon('LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)'::geometry))
  AND g2.k < 20
ORDER BY g1.k, g2.k
----
·                        distribution           local
·                        vectorized             true
sort                     ·                      ·
 │                       order                  +k,+k
 └── lookup join         ·                      ·
      │                  table                  g@primary
      │                  equality               (k) = (k)
      │                  equality cols are key  ·
      │                  pred                   st_contains(geom, geom) AND st_contains(geom, '010300000001000000050000000000000000000000000000000000000000000000000000000000000000001440000000000000144000000000000014400000000000001440000000000000000000000000000000000000000000000000')
      └── inverted join  ·                      ·
           │             table                  g@foo_inv
           └── scan      ·                      ·
·                        missing stats          ·
·                        table                  g@primary
·                        spans                  [ - /19]

# This query performs a cross join followed by a filter.
query TTT
EXPLAIN SELECT g1.k, g2.k FROM g@primary AS g1, g@primary AS g2
WHERE ST_Contains(g1.geom, g2.geom)
  AND ST_Contains(g1.geom, ST_MakePolygon('LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)'::geometry))
  AND g2.k < 20
ORDER BY g1.k, g2.k
----
·                    distribution   local
·                    vectorized     true
sort                 ·              ·
 │                   order          +k,+k
 └── cross join      ·              ·
      │              pred           st_contains(geom, geom)
      ├── scan       ·              ·
      │              missing stats  ·
      │              table          g@primary
      │              spans          [ - /19]
      └── filter     ·              ·
           │         filter         st_contains(geom, '010300000001000000050000000000000000000000000000000000000000000000000000000000000000001440000000000000144000000000000014400000000000001440000000000000000000000000000000000000000000000000')
           └── scan  ·              ·
·                    missing stats  ·
·                    table          g@primary
·                    spans          FULL SCAN

# This query performs an inverted join with an additional filter.
query II
SELECT g1.k, g2.k FROM g@foo_inv AS g1, g@primary AS g2
WHERE ST_Contains(g1.geom, g2.geom)
  AND ST_Contains(g1.geom, ST_MakePolygon('LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)'::geometry))
  AND g2.k < 20
ORDER BY g1.k, g2.k
----
1  1

# This query performs a cross join followed by a filter.
query II
SELECT g1.k, g2.k FROM g@primary AS g1, g@primary AS g2
WHERE ST_Contains(g1.geom, g2.geom)
  AND ST_Contains(g1.geom, ST_MakePolygon('LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)'::geometry))
  AND g2.k < 20
ORDER BY g1.k, g2.k
----
1  1
1  2

The two above queries should return exactly the same results, since the only difference is that they use different indexes. However, clearly the results are different.

[blathers-crl]

Hi @rytaft, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[blathers-crl]

Hi @rytaft, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[blathers-crl]

Hi @rytaft, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[blathers-crl]

Hi @rytaft, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[blathers-crl]

Hi @rytaft, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}