Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

roachtest: unoptimized-query-oracle/disable-rules=half failed #90761

Closed
cockroach-teamcity opened this issue Oct 27, 2022 · 8 comments · Fixed by #91425
Closed

roachtest: unoptimized-query-oracle/disable-rules=half failed #90761

cockroach-teamcity opened this issue Oct 27, 2022 · 8 comments · Fixed by #91425
Assignees
Labels
branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 C-test-failure Broken test (automatically or manually discovered). O-roachtest O-robot Originated from a bot. S-0-visible-logical-error Database stores inconsistent data in some cases, or queries return invalid results silently. T-sql-queries SQL Queries Team
Milestone

Comments

@cockroach-teamcity
Copy link
Member

cockroach-teamcity commented Oct 27, 2022

roachtest.unoptimized-query-oracle/disable-rules=half failed with artifacts on release-22.2 @ 4816df3a9d76d179ed135a2b1efb53babb5611a0:

		Wraps: (3) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runUnoptimizedQueryOracleImpl
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:168
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.registerUnoptimizedQueryOracle.func1.1
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:57
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runOneRoundQueryComparison
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/query_comparison_util.go:236
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runQueryComparison
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/query_comparison_util.go:66
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.registerUnoptimizedQueryOracle.func1
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:54
		  | main.(*testRunner).runTest.func2
		  | 	main/pkg/cmd/roachtest/test_runner.go:930
		  | runtime.goexit
		  | 	GOROOT/src/runtime/asm_amd64.s:1594
		Wraps: (4) expected unoptimized and optimized results to be equal
		  |   []string(
		  | - 	{
		  | - 		"-39 years -5 mons -668 days -20:19:03.089458,31,a ,\x12,1969-09-22 21:13:20 +0000 +0000,0",
		  | - 		"-39 years -5 mons -668 days -20:19:03.089458,31,a ,\x12,1981-05-11 17:02:50.000318 +0000 +0000,0",
		  | - 		"-39 years -5 mons -668 days -20:19:03.089458,31,a ,\x12,1985-11-08 11:32:06.000741 +0000 +0000,0",
		  | - 	},
		  | + 	nil,
		  |   )
		  | sql: SELECT
		  | 	'-39 years -5 mons -668 days -20:19:03.089458':::INTERVAL AS col_18662,
		  | 	31:::INT8 AS col_18663,
		  | 	'a ':::STRING AS col_18664,
		  | 	e'\x12':::STRING AS col_18665,
		  | 	tab_7925.col1_0 AS col_18666,
		  | 	0:::OID AS col_18667
		  | FROM
		  | 	defaultdb.public.table1@[0] AS tab_7919
		  | 	JOIN defaultdb.public.table1@[0] AS tab_7920
		  | 		JOIN defaultdb.public.table1@[0] AS tab_7921
		  | 			JOIN defaultdb.public.table1 AS tab_7922
		  | 				JOIN defaultdb.public.table1 AS tab_7923 ON (tab_7922.col1_2) = (tab_7923.col1_2)
		  | 				LEFT JOIN defaultdb.public.table1@[0] AS tab_7924 ON (tab_7923.col1_2) = (tab_7924.col1_2)
		  | 				LEFT JOIN defaultdb.public.table1@[0] AS tab_7925
		  | 					JOIN defaultdb.public.table1@[0] AS tab_7926 ON (tab_7925.col1_1) = (tab_7926.col1_1) ON
		  | 						(tab_7924.col1_1) = (tab_7926.col1_1) AND (tab_7924.col1_2) > (tab_7926.col1_2) ON
		  | 					(tab_7921.col1_1) = (tab_7926.col1_1) AND (tab_7921.col1_1) = (tab_7924.col1_1) ON
		  | 				(tab_7920.col1_0) = (tab_7926.col1_0)
		  | 				AND (tab_7920.crdb_internal_mvcc_timestamp) = (tab_7924.crdb_internal_mvcc_timestamp) ON
		  | 			(tab_7919.col1_0) = (tab_7920.col1_0)
		  | 			AND (tab_7919.crdb_internal_mvcc_timestamp) = (tab_7921.crdb_internal_mvcc_timestamp)
		  | ORDER BY
		  | 	tab_7921.tableoid DESC, tab_7919.crdb_internal_mvcc_timestamp
		Error types: (1) *withstack.withStack (2) *errutil.withPrefix (3) *withstack.withStack (4) *errutil.leafError

Parameters: ROACHTEST_cloud=gce , ROACHTEST_cpu=4 , ROACHTEST_encrypted=false , ROACHTEST_ssd=0

Help

See: roachtest README

See: How To Investigate (internal)

/cc @cockroachdb/sql-queries

This test on roachdash | Improve this report!

Jira issue: CRDB-20932

@cockroach-teamcity cockroach-teamcity added branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 C-test-failure Broken test (automatically or manually discovered). O-roachtest O-robot Originated from a bot. labels Oct 27, 2022
@cockroach-teamcity cockroach-teamcity added this to the 22.2 milestone Oct 27, 2022
@blathers-crl blathers-crl bot added the T-sql-queries SQL Queries Team label Oct 27, 2022
@mgartner mgartner self-assigned this Oct 27, 2022
@mgartner
Copy link
Collaborator

mgartner commented Oct 27, 2022

Partially reduced:

CREATE TABLE table1 (col1_0 TIMESTAMP, col1_1 INTERVAL, col1_2 CHAR NOT NULL);

INSERT INTO table1 (col1_0, col1_1, col1_2)
VALUES ('1991-05-10 14:18:54.000472', '-9 years -2 mons -188 days -21:52:32.812039', '');

SET testing_optimizer_random_seed = 726585762659783634;

SET testing_optimizer_disable_rule_probability = 0.500000;

SELECT 1
FROM table1 AS tab_7919
JOIN table1 AS tab_7920
  JOIN table1 AS tab_7921
    JOIN table1 AS tab_7922
      JOIN table1 AS tab_7923 ON tab_7922.col1_2 = tab_7923.col1_2
      LEFT JOIN table1 AS tab_7924 ON tab_7923.col1_2 = tab_7924.col1_2
      LEFT JOIN table1 AS tab_7925
        JOIN table1 AS tab_7926 ON tab_7925.col1_1 = tab_7926.col1_1
      ON tab_7924.col1_1 = tab_7926.col1_1 AND tab_7924.col1_2 > tab_7926.col1_2
    ON tab_7921.col1_1 = tab_7926.col1_1 AND tab_7921.col1_1 = tab_7924.col1_1
  ON tab_7920.col1_0 = tab_7926.col1_0
    AND tab_7920.crdb_internal_mvcc_timestamp = tab_7924.crdb_internal_mvcc_timestamp
ON tab_7919.col1_0 = tab_7920.col1_0
  AND tab_7919.crdb_internal_mvcc_timestamp = tab_7921.crdb_internal_mvcc_timestamp
;

RESET testing_optimizer_random_seed;

RESET testing_optimizer_disable_rule_probability;

SELECT 1
FROM table1 AS tab_7919
JOIN table1 AS tab_7920
  JOIN table1 AS tab_7921
    JOIN table1 AS tab_7922
      JOIN table1 AS tab_7923 ON tab_7922.col1_2 = tab_7923.col1_2
      LEFT JOIN table1 AS tab_7924 ON tab_7923.col1_2 = tab_7924.col1_2
      LEFT JOIN table1 AS tab_7925
        JOIN table1 AS tab_7926 ON tab_7925.col1_1 = tab_7926.col1_1
      ON tab_7924.col1_1 = tab_7926.col1_1 AND tab_7924.col1_2 > tab_7926.col1_2
    ON tab_7921.col1_1 = tab_7926.col1_1 AND tab_7921.col1_1 = tab_7924.col1_1
  ON tab_7920.col1_0 = tab_7926.col1_0
    AND tab_7920.crdb_internal_mvcc_timestamp = tab_7924.crdb_internal_mvcc_timestamp
ON tab_7919.col1_0 = tab_7920.col1_0
  AND tab_7919.crdb_internal_mvcc_timestamp = tab_7921.crdb_internal_mvcc_timestamp
;

@mgartner
Copy link
Collaborator

Further reduced:

CREATE TABLE t (a INT, b INT, c INT);

INSERT INTO t (a, b, c)
VALUES (0, 0, 0);

SET testing_optimizer_random_seed = 726585762659783634;

SET testing_optimizer_disable_rule_probability = 0.500000;

SELECT 1
FROM t AS t1
JOIN t AS t2
  LEFT JOIN t AS t3
    JOIN t AS t4 ON true
  ON t2.b > t4.b
ON t1.a = t4.a AND t1.c = t2.c
;

RESET testing_optimizer_random_seed;

RESET testing_optimizer_disable_rule_probability;

SELECT 1
FROM t AS t1
JOIN t AS t2
  LEFT JOIN t AS t3
    JOIN t AS t4 ON true
  ON t2.b > t4.b
ON t1.a = t4.a AND t1.c = t2.c
;

@mgartner
Copy link
Collaborator

The symptoms here look similar to #76522. The t2.b > t4.b filter is missing in first query's plan. I haven't yet determined if this is reproducible in past versions. I'm hoping that this is only reproducible with a normalization rule disabled, but I haven't confirmed that.

@mgartner mgartner removed their assignment Oct 31, 2022
@DrewKimball
Copy link
Collaborator

Yeah looks similar but with null-rejection. I'll keep digging though.

@DrewKimball DrewKimball self-assigned this Nov 1, 2022
@cockroach-teamcity

This comment was marked as off-topic.

@DrewKimball
Copy link
Collaborator

For the most recent failure - need to backport #88399

@DrewKimball DrewKimball added the S-0-visible-logical-error Database stores inconsistent data in some cases, or queries return invalid results silently. label Nov 3, 2022
@cockroach-teamcity
Copy link
Member Author

roachtest.unoptimized-query-oracle/disable-rules=half failed with artifacts on release-22.2 @ 56e0cae2dd496aee737f273f6b0a77faae4f76bd:

test artifacts and logs in: /artifacts/unoptimized-query-oracle/disable-rules=half/run_1
	query_comparison_util.go:237,query_comparison_util.go:66,unoptimized_query_oracle.go:54,test_runner.go:930: failed to set random seed. 1877 statements run: dial tcp 34.138.167.114:26257: connect: connection refused
		(1) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.(*queryComparisonHelper).makeError
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/query_comparison_util.go:345
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runUnoptimizedQueryOracleImpl
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:102
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.registerUnoptimizedQueryOracle.func1.1
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:57
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runOneRoundQueryComparison
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/query_comparison_util.go:236
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runQueryComparison
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/query_comparison_util.go:66
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.registerUnoptimizedQueryOracle.func1
		  | 	github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/unoptimized_query_oracle.go:54
		  | main.(*testRunner).runTest.func2
		  | 	main/pkg/cmd/roachtest/test_runner.go:930
		  | runtime.goexit
		  | 	GOROOT/src/runtime/asm_amd64.s:1594
		Wraps: (2) failed to set random seed. 1877 statements run
		Wraps: (3) dial tcp 34.138.167.114:26257
		Wraps: (4) connect
		Wraps: (5) connection refused
		Error types: (1) *withstack.withStack (2) *errutil.withPrefix (3) *net.OpError (4) *os.SyscallError (5) syscall.Errno

Parameters: ROACHTEST_cloud=gce , ROACHTEST_cpu=4 , ROACHTEST_encrypted=false , ROACHTEST_ssd=0

Help

See: roachtest README

See: How To Investigate (internal)

Same failure on other branches

This test on roachdash | Improve this report!

@DrewKimball
Copy link
Collaborator

Stack trace for the most recent failure:

E221107 17:12:00.157286 960 9@sql/conn_executor.go:1052 ⋮ [n1,client=104.196.50.177:40238,user=root] 19338  a SQL panic has occurred while executing the following statement:
E221107 17:12:00.157286 960 9@sql/conn_executor.go:1052 ⋮ [n1,client=104.196.50.177:40238,user=root] 19338 +‹SELECT tab_1200.col1_1 AS col_3234, tab_1202.col2_6 AS col_3235, false AS col_3236 FROM defaultdb.public.table1@[0] AS tab_1199 JOIN defaultdb.public.table1@[0] AS tab_1200 JOIN defaultdb.public.table1@[0] AS tab_1201 ON (tab_1200.crdb_internal_mvcc_timestamp) = (tab_1201.crdb_internal_mvcc_timestamp) ON ((tab_1199.crdb_internal_mvcc_timestamp) = (tab_1200.crdb_internal_mvcc_timestamp)) AND ((tab_1199.crdb_internal_mvcc_timestamp) = (tab_1201.crdb_internal_mvcc_timestamp)) LEFT JOIN defaultdb.public.table2@[0] AS tab_1202 ON (tab_1200.crdb_internal_mvcc_timestamp) = (tab_1202.crdb_internal_mvcc_timestamp) WHERE (NOT (tab_1202.col2_4::UUID IN (SELECT lag(tab_1203.col2_4::UUID) OVER (PARTITION BY tab_1203.col2_0 ORDER BY tab_1202.col2_0, tab_1199.col1_0, tab_1199.col1_1 ASC, tab_1199.crdb_internal_mvcc_timestamp, tab_1199.tableoid, tab_1200.col1_0 ASC, tab_1200.col1_1 ASC, tab_1200.crdb_internal_mvcc_timestamp ASC, tab_1200.tableoid, tab_1201.col1_0 DESC, tab_1201.col1_1 ASC, tab_1201.crdb_internal_mvcc_timestamp DESC, tab_1201.tableoid DESC, tab_1202.col2_0 ASC, tab_1202.col2_1, tab_1202.col2_2 DESC, tab_1202.col2_3 ASC, tab_1202.col2_4 DESC, tab_1202.col2_5 ASC, tab_1202.col2_6 DESC, tab_1202.col2_7 ASC, tab_1202.col2_8, tab_1202.col2_9 DESC, tab_1202.col2_10, tab_1202.col2_11 DESC, tab_1202.col2_12 ASC, tab_1202.col2_13, tab_1202.col2_14 DESC, tab_1202.col2_15 ASC, tab_1202.col2_16, tab_1202.crdb_internal_mvcc_timestamp ASC, tab_1202.tableoid DESC, tab_1203.col2_0 ASC, tab_1203.col2_1, tab_1203.col2_2, tab_1203.col2_3 DESC, tab_1203.col2_4 ASC, tab_1203.col2_5 DESC, tab_1203.col2_6 DESC, tab_1203.col2_7, tab_1203.col2_8 ASC, tab_1203.col2_9, tab_1203.col2_10 ASC, tab_1203.col2_11 DESC, tab_1203.col2_12 ASC, tab_1203.col2_13 ASC, tab_1203.col2_14 ASC, tab_1203.col2_15, tab_1203.col2_16 DESC, tab_1203.crdb_internal_mvcc_timestamp ASC, tab_1203.tableoid)::UUID::UUID AS col_3233 FROM defaultdb.public.table2@[0] AS tab_1203 ORDER BY tab_1203.col2_8, tab_1203.col2_4 ASC)))›
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339  a panic has occurred!
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +runtime error: index out of range [0] with length 0
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +(1) attached stack trace
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  -- stack trace:
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*Server).ServeConn.func1
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:826
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | [...repeated from below...]
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +Wraps: (2) while executing: SELECT _._ AS _, _._ AS _, _ AS _ FROM _@[0] AS _ JOIN _@[0] AS _ JOIN _@[0] AS _ ON (_._) = (_._) ON ((_._) = (_._)) AND ((_._) = (_._)) LEFT JOIN _@[0] AS _ ON (_._) = (_._) WHERE (NOT (_._::UUID IN (SELECT lag(_._::UUID) OVER (PARTITION BY _._ ORDER BY _._, _._, _._ ASC, _._, _._, _._ ASC, _._ ASC, _._ ASC, _._, _._ DESC, _._ ASC, _._ DESC, _._ DESC, _._ ASC, _._, _._ DESC, _._ ASC, _._ DESC, _._ ASC, _._ DESC, _._ ASC, _._, _._ DESC, _._, _._ DESC, _._ ASC, _._, _._ DESC, _._ ASC, _._, _._ ASC, _._ DESC, _._ ASC, _._, _._, _._ DESC, _._ ASC, _._ DESC, _._ DESC, _._, _._ ASC, _._, _._ ASC, _._ DESC, _._ ASC, _._ ASC, _._ ASC, _._, _._ DESC, _._ ASC, _._)::UUID::UUID AS _ FROM _@[0] AS _ ORDER BY _._, _._ ASC)))
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +Wraps: (3) attached stack trace
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  -- stack trace:
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*Server).ServeConn.func1
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:826
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | runtime.gopanic
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	GOROOT/src/runtime/panic.go:884
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | runtime.goPanicIndex
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	GOROOT/src/runtime/panic.go:113
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLReceiver).Push
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:1229
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/rowflow.(*copyingRowReceiver).Push
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/rowflow/row_based_flow.go:462
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/execinfra.Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/execinfra/base.go:189
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/execinfra.(*ProcessorBaseNoHelper).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/execinfra/processorsbase.go:735
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/flowinfra.(*FlowBase).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/flowinfra/flow.go:472
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLPlanner).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:695
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLPlanner).PlanAndRun
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:1611
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.runPlanInsidePlan
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/apply_join.go:333
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*applyJoinNode).runNextRightSideIteration
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/apply_join.go:256
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*applyJoinNode).Next
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/apply_join.go:221
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*planNodeToRowSource).Next
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/plan_node_to_row_source.go:200
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/execinfra.Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/execinfra/base.go:186
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/execinfra.(*ProcessorBaseNoHelper).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/execinfra/processorsbase.go:735
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/flowinfra.(*FlowBase).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/flowinfra/flow.go:472
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLPlanner).Run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:695
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLPlanner).PlanAndRun
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:1611
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*DistSQLPlanner).PlanAndRunAll
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/distsql_running.go:1334
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execWithDistSQLEngine
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:1542
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).dispatchToExecutionEngine
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:1178
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execStmtInOpenState
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:687
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execStmt.func1
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:129
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execWithProfiling
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:2383
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execStmt
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor_exec.go:128
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execCmd.func1
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:1920
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).execCmd
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:1924
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*connExecutor).run
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:1846
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql.(*Server).ServeConn
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/conn_executor.go:828
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | github.com/cockroachdb/cockroach/pkg/sql/pgwire.(*conn).processCommandsAsync.func1
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	github.com/cockroachdb/cockroach/pkg/sql/pgwire/conn.go:728
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | runtime.goexit
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +  | 	GOROOT/src/runtime/asm_amd64.s:1594
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +Wraps: (4) runtime error: index out of range [0] with length 0
E221107 17:12:00.157906 960 1@util/log/logcrash/crash_reporting.go:174 ⋮ [n1,client=104.196.50.177:40238,user=root] 19339 +Error types: (1) *withstack.withStack (2) *safedetails.withSafeDetails (3) *withstack.withStack (4) runtime.boundsError

DrewKimball added a commit to DrewKimball/cockroach that referenced this issue Nov 7, 2022
This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes cockroachdb#90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.
craig bot pushed a commit that referenced this issue Nov 17, 2022
91425: opt: don't drop LeftJoin filter during join ordering r=DrewKimball a=DrewKimball

**opt: use RelExpr instead of ColumnID for reorderjoins relation map**

The reorderjoins opttester directive previously maintained a map from
the first column ID of each base relation to the relation's label in
the output. This could cause a panic for relations that didn't output
any columns. This patch changes the map to use the relations themselves
as keys, which prevents the panic.

**opt: don't drop LeftJoin filter during join ordering**

This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes #90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.

Co-authored-by: DrewKimball <[email protected]>
@craig craig bot closed this as completed in e8560b1 Nov 17, 2022
blathers-crl bot pushed a commit that referenced this issue Nov 17, 2022
This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes #90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.
blathers-crl bot pushed a commit that referenced this issue Nov 17, 2022
This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes #90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.
DrewKimball added a commit to DrewKimball/cockroach that referenced this issue Nov 18, 2022
This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes cockroachdb#90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.
DrewKimball added a commit to DrewKimball/cockroach that referenced this issue Nov 24, 2022
This patch fixes a bug in the join reordering logic that can lead to
incorrect results due to a dropped filter and incorrect conversion of
a left join to an inner join. The bug can occur when the join tree
contains an inner join with a left join as an input, where the inner
join has two separate conjuncts in its ON condition that reference
both inputs of the left join. Additionally, the inner join filters
must not filter NULL values from the right side of the left join
(or alternatively null-rejection rules must be disabled).

The incorrect transformation looks something like this:
```
(INNER JOIN xy (LEFT JOIN ab (INNER JOIN uv wz ON v = w) ON b = v) ON a = x AND u = x)
```
=>
```
(INNER JOIN ab (INNER JOIN xy (INNER JOIN uv wz ON v = w) ON u = x) ON a = x)
```
Notice how `xy` has been "pushed" into the right side of the left
join and the left join's `b = v` filter (and the left join itself)
dropped in the process.

To understand what causes the bug, it is necessary to understand three
points about the join reordering algorithm:
1. Cross products are never introduced in the enumerated plans. So, for
   two sub-plans, a join is only considered between them if there is an
   applicable edge between those sub-plans.
2. The original paper associates each join with exactly one edge in the
   hypergraph that encodes "reorderability" properties.
3. The `JoinOrderBuilder` departs from the paper by associating each
   inner join *conjunct* with a hypergraph edge. This allows each
   conjunct to be independently reordered from the others. See the
   `Special handling of inner joins` section in the `JoinOrderBuilder`
   comment for more details.

(1) combined with (2) implies that a reordered join tree is only
considered if every edge in the hypergraph could be applied to form joins
in the join tree. This allows the original algorithm to prevent invalid
orderings by making just a single edge inapplicable. However, because
of (3) the same is no longer true for the `JoinOrderBuilder`. In the
example given above, the left join fails the applicability check,
indicating an invalid plan. However, the inner join's `a = x` filter
passes the check and ends up replacing the left join. This prevents
the the check in (1) from catching the invalid plan.

This patch fixes the bug by keeping track of the edges that *should*
be applied somewhere in each join tree based on the TES of each edge.
This is then compared against the actual edges that are applied in
the construction of the join tree. If the edge sets aren't equal,
the plan is invalid and cannot be added to the memo. This allows the
`JoinOrderBuilder` to recover the property that an inapplicable edge
invalidates an enumerated plan.

Fixes cockroachdb#90761

Release note (bug fix): Fixed a bug existing since 20.2 that could
cause incorrect results in rare cases for queries with inner joins
and left joins. For the bug to occur, the left join had to be in
the input of the inner join and the inner join filters had to
reference both inputs of the left join, and not filter NULL values
from the right input of the left join. Additionally, the right input
of the left join had to contain at least one join, with one input not
referenced by the left join's ON condition.
@mgartner mgartner moved this to Done in SQL Queries Jul 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
branch-release-22.2 Used to mark GA and release blockers, technical advisories, and bugs for 22.2 C-test-failure Broken test (automatically or manually discovered). O-roachtest O-robot Originated from a bot. S-0-visible-logical-error Database stores inconsistent data in some cases, or queries return invalid results silently. T-sql-queries SQL Queries Team
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

3 participants