sql: internal error: lookup join with no lookup columns

[yuzefovich]

When running SQLite logic tests with --crdb_test flag (which is currently not added in CI due to #58089) with

./dev testlogic sqlite --ignore-cache --config=local --files=slt_good_22 -- --test_env=COCKROACH_RANDOM_SEED='-6676986672122001987'

        /private/var/tmp/_bazel_yahor/e311b1c2454b7c301a6b73bddff450e7/sandbox/darwin-sandbox/2421/execroot/com_github_cockroachdb_cockroach/bazel-out/darwin-fastbuild/bin/pkg/sql/sqlitelogictest/tests/local/local_test_/local_test.runfiles/com_github_cockroachdb_cockroach/external/com_github_cockroachdb_sqllogictest/test/index/commute/10/slt_good_22.test:14596: SELECT pk FROM tab3 WHERE (col3 < 12 OR col0 BETWEEN 5 AND 30 AND (col1 >= 76.11) OR col3 = 95 OR col4 < 73.16 AND col1 IN (SELECT col4 FROM tab3 WHERE (col1 = 29.20 OR (((col0 > 3 AND ((col4 IS NULL AND (col3 IN (36,23,85,48,2,81)))))) OR col3 <= 2) AND col3 > 91 AND (col3 <= 54))) OR (col0 = 56) OR ((col4 <= 59.52)) OR col4 IN (29.33,64.35))
        expected success, but found
        (XX000) internal error: lookup join with no lookup columns
        check_expr.go:225: in CheckExpr()
        DETAIL: stack trace:
        github.com/cockroachdb/cockroach/pkg/sql/opt/memo/check_expr.go:225: CheckExpr()
        github.com/cockroachdb/cockroach/bazel-out/darwin-fastbuild/bin/pkg/sql/opt/memo/expr.og.go:24495: AddLookupJoinToGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/join_funcs.go:667: func1()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/scan_index_iter.go:306: ForEachStartingAfter()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/scan_index_iter.go:209: ForEach()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/join_funcs.go:392: generateLookupJoinsImpl()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/join_funcs.go:260: GenerateLookupJoins()
        github.com/cockroachdb/cockroach/bazel-out/darwin-fastbuild/bin/pkg/sql/opt/xform/explorer.og.go:1967: exploreSemiJoin()
        github.com/cockroachdb/cockroach/bazel-out/darwin-fastbuild/bin/pkg/sql/opt/xform/explorer.og.go:34: exploreGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/explorer.go:182: exploreGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:529: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:291: optimizeExpr()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:571: optimizeGroupMember()
        github.com/cockroachdb/cockroach/pkg/sql/opt/xform/optimizer.go:516: optimizeGroup()

seems likely it's related to recent work by @mgartner, so I'm adding a release blocker label.

Jira issue: CRDB-19263

[mgartner]

Reduced reproduction:

statement ok
CREATE TABLE t (
  a INT,
  b INT,
  c INT,
  INDEX (a, c)
);

statement ok
SELECT NULL
FROM t
WHERE a IN (
  SELECT c FROM t
  WHERE a = 0 OR b IN (0) AND b > 0
)

[mgartner]

This occurs on v22.1.6, so this is not a release blocker.

[mgartner]

The problem is that we incorrectly determine that an index used for a lookup join is non-covering when a column in the ON filter is not in the index and conditions on that column form a contradiction that was not eliminated by normalization rules in the canonical expression. This causes us to unnecessarily plan a paired joiner to fetch the column from the primary index. As far as I can tell, there is no correctness issue here, but it does create inefficient plans with paired joiners that could be planned with just a single lookup join.

As an example, consider the reproduction above. The secondary index, INDEX (a, c), cannot provide column b so a paired joiner is planned to fetch b from the primary index after performing the lookup join with the secondary index. However, we don't actually need b—b IN (0) AND b > 0 is a contradiction. The lookup join logic assumes that we do need b because this contradiction hasn't been eliminated before the lookup join is generated (our contradiction detection relies on constraints which have difficulty fully describing disjunctions; in other words, our rules can't see the contradiction inside the OR to eliminate it). The contradiction is eliminated once the a = 0 filter is removed from the ON condition (this part of the filter is replaced with a projection of a 0 value column and lookup join key columns). We're left with a paired joiner that fetches no columns - hence the check_expr.go assertion failure.

[yuzefovich]

Is there some easy way to adjust check_expr.go to not fire until this issue is fixed so that #58089 could be resolved?

[mgartner]

This is easier to fix than I originally thought. Will have a PR up momentarily.