sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted #68979

cockroach-teamcity · 2021-08-16T10:31:12Z

roachtest.tlp failed with artifacts on master @ 04a41e7915f4a89dcc1d0dbd92466c6adf79ec9f:

The test failed on branch=master, cloud=gce:
test artifacts and logs in: /home/agent/work/.go/src/github.com/cockroachdb/cockroach/artifacts/tlp/run_1
	tlp.go:128,test_runner.go:777: expected unpartitioned count 3 to equal partitioned count 6
		(1) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runTLPQuery.func2
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:191
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runWithTimeout.func1
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:203
		  | runtime.goexit
		  | 	/usr/local/go/src/runtime/asm_amd64.s:1371
		Wraps: (2) expected unpartitioned count 3 to equal partitioned count 6
		  | sql: SELECT count(*) FROM defaultdb.public.table1 AS tab_2908
		  | SELECT count(*) FROM (SELECT * FROM defaultdb.public.table1 AS tab_2908 WHERE 'dcksf'::rand_typ_0 IN ('dcksf', (SELECT NULL AS col_2595 FROM defaultdb.public.table1@[0] AS tab_2909, defaultdb.public.table1@[0] AS tab_2910 CROSS JOIN defaultdb.public.table1@[0] AS tab_2911, defaultdb.public.table1@[0] AS tab_2912 ORDER BY tab_2911.col1_0 DESC, tab_2910.col1_4 ASC, tab_2909.col1_2 DESC LIMIT 1), 'r') UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_2908 WHERE NOT ('dcksf'::rand_typ_0 IN ('dcksf', (SELECT NULL AS col_2595 FROM defaultdb.public.table1@[0] AS tab_2909, defaultdb.public.table1@[0] AS tab_2910 CROSS JOIN defaultdb.public.table1@[0] AS tab_2911, defaultdb.public.table1@[0] AS tab_2912 ORDER BY tab_2911.col1_0 DESC, tab_2910.col1_4 ASC, tab_2909.col1_2 DESC LIMIT 1), 'r')) UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_2908 WHERE ('dcksf'::rand_typ_0 IN ('dcksf', (SELECT NULL AS col_2595 FROM defaultdb.public.table1@[0] AS tab_2909, defaultdb.public.table1@[0] AS tab_2910 CROSS JOIN defaultdb.public.table1@[0] AS tab_2911, defaultdb.public.table1@[0] AS tab_2912 ORDER BY tab_2911.col1_0 DESC, tab_2910.col1_4 ASC, tab_2909.col1_2 DESC LIMIT 1), 'r')) IS NULL)
		Error types: (1) *withstack.withStack (2) *errutil.leafError

Reproduce

See: roachtest README

See: CI job to stress roachtests

For the CI stress job, click the ellipsis (...) next to the Run button and fill in: * Changes / Build branch: master * Parameters / `env.TESTS`: `^tlp$` * Parameters / `env.COUNT`: <number of runs>

/cc @cockroachdb/sql-queries _{This test on roachdash | Improve this report!}

The text was updated successfully, but these errors were encountered:

mgartner · 2021-08-18T20:40:30Z

I've managed to reduce the problem, but haven't started to debug yet. Leaving a logic test below that highlights the problem so I don't lose it:

# LogicTest: local

statement ok
CREATE TABLE t (
  a CHAR,
  b CHAR,
  c VARCHAR
);

statement ok
CREATE TYPE typ AS ENUM ('foo', 'bar');

statement ok
INSERT INTO t (a, b)
VALUES ('', '');

# There is 1 row in the table.
query I
SELECT count(*) FROM t
----
1

# Unioning 2 distinct subsets of the table results in 2 rows. This is wrong.
query I
SELECT count(*) FROM (
  SELECT * FROM t
  WHERE 'bar'::typ IN ('bar', (SELECT NULL FROM t), 'foo')
  UNION ALL
  SELECT * FROM t
  WHERE ('bar'::typ IN ('bar', (SELECT NULL FROM t), 'foo')) IS NULL
)
----
2

# The expression evaluates to true.
query TTT colnames
SELECT * FROM t
WHERE 'bar'::typ IN ('bar', (SELECT NULL FROM t), 'foo')
----
a  b  c
                NULL

# The expression also IS NULL. This is wrong.
query TTT colnames
SELECT * FROM t
WHERE ('bar'::typ IN ('bar', (SELECT NULL FROM t), 'foo')) IS NULL
----
a  b  c
                NULL

rytaft · 2021-08-23T19:57:54Z

This seems to be a regression from prior releases, so leaving release-blocker label.

mgartner · 2021-08-23T23:10:33Z

An even simpler reproduction:

statement ok
CREATE TABLE t (
  a INT
)

statement ok
INSERT INTO t VALUES (0)

query B
SELECT 'b' IN ('b', (SELECT NULL FROM t), 'a') FROM t
----
NULL

I've bisected to #68289, though I don't believe that introduced the bug, it only revealed it. It looks like there's a false assumption (added in #50337) being made that values in a tuple are always normalized such that they are in order:

cockroach/pkg/sql/colexec/select_in_tmpl.go

Lines 179 to 180 in 62b3462

    
           // Filter row input is already sorted due to normalization, so we can use a 
        
           // binary search right away.

However, this is not the case if the tuple does not have all constant elements at optimization time (see this optstepsweb output for an example, look for the NormalizeInConst rule).

I'm not yet sure the best way to fix this. Some options I've thought of:

Remove the binary search and do a linear scan instead.
Check if tuple elements are ordered during fillDatumRow_TYPE. Although I'm concerned that comparing each element to the previous element will be more expensive than the savings from binary search.

Maybe @yuzefovich has some ideas?

yuzefovich · 2021-08-24T00:00:06Z

Nice find!

I think it'd be get the best of both options - keep the faster binary search when the tuple is constant (and, thus, has been normalized) and fall back to linear scan if it isn't. My understanding is that it is sufficient to simply iterate over all elements of the tuple and check whether each is tree.Datum - then we can assume that the tuple has been normalized by the optimizer, right? Note that this check would have to be performed only once, in the operator constructor (and fillDatumRow_TYPE is also called only once then).

mgartner · 2021-08-24T00:15:04Z

I'm not sure it'd be so simple. When I was debugging, the value in the middle of the tuple was already filled in with a tree.dNull when planProjectionExpr is called.

yuzefovich · 2021-08-24T00:57:41Z

I guess this was the case only because of EXPLAIN (VEC) for which we're replacing the results of the subqueries with tree.DNulls (I could be wrong though).

cockroach-teamcity · 2021-08-24T12:10:58Z

roachtest.tlp failed with artifacts on master @ 46cef2c6f0b36ba2f7d551c8ab017832c1b9d592:

The test failed on branch=master, cloud=gce:
test artifacts and logs in: /home/agent/work/.go/src/github.com/cockroachdb/cockroach/artifacts/tlp/run_1
	tlp.go:128,test_runner.go:777: expected unpartitioned count 0 to equal partitioned count 7
		(1) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runTLPQuery.func2
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:191
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runWithTimeout.func1
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:203
		  | runtime.goexit
		  | 	/usr/local/go/src/runtime/asm_amd64.s:1371
		Wraps: (2) expected unpartitioned count 0 to equal partitioned count 7
		  | sql: SELECT count(*) FROM defaultdb.public.table1 AS tab_4751
		  | SELECT count(*) FROM (SELECT * FROM defaultdb.public.table1 AS tab_4751 WHERE tab_4751.col1_9 UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_4751 WHERE NOT (tab_4751.col1_9) UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_4751 WHERE (tab_4751.col1_9) IS NULL)
		Error types: (1) *withstack.withStack (2) *errutil.leafError

Reproduce

See: roachtest README

See: CI job to stress roachtests

For the CI stress job, click the ellipsis (...) next to the Run button and fill in: * Changes / Build branch: master * Parameters / `env.TESTS`: `^tlp$` * Parameters / `env.COUNT`: <number of runs>

/cc @cockroachdb/sql-queries _{This test on roachdash | Improve this report!}

mgartner · 2021-08-24T17:47:34Z

I guess this was the case only because of EXPLAIN (VEC) for which we're replacing the results of the subqueries with tree.DNulls (I could be wrong though).

This is the case without EXPLAIN (VEC). It seems like the subquery is executed, then the NULL is filled in for the middle value of the tuple, and then we re-plan the vectorized operators. I'm not familiar with all the mechanics yet... Does that sound plausible?

mgartner · 2021-08-24T20:10:26Z

I've created an issue, #69327, for the last reported TLP bug in the comment above. It looks to be a separate bug.

yuzefovich · 2021-08-24T21:18:00Z

This is the case without EXPLAIN (VEC). It seems like the subquery is executed, then the NULL is filled in for the middle value of the tuple, and then we re-plan the vectorized operators. I'm not familiar with all the mechanics yet... Does that sound plausible?

Yes, totally. We run all subqueries upfront, and we store the results in subquery.result; then during the physical planning of the main query we use physicalplan.MakeExpression to possibly serialize all expressions (so that they can be sent across the network), and that method replaces the subquery nodes with the results of their evaluation. We do this subquery evaluation in all cases.

mgartner · 2021-08-24T22:39:01Z

Leaving a note here for my future self:

Tuples should already have an isSorted field.
This field should be set correctly by the optimizer.
We can use this to decide whether to do a binary or linear search.

cockroach-teamcity · 2021-08-25T11:40:06Z

roachtest.tlp failed with artifacts on master @ 967ed00f80981ce8848a5e8144ee6fbd29bc95bb:

The test failed on branch=master, cloud=gce:
test artifacts and logs in: /home/agent/work/.go/src/github.com/cockroachdb/cockroach/artifacts/tlp/run_1
	tlp.go:128,test_runner.go:777: expected unpartitioned count 7 to equal partitioned count 5
		(1) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runTLPQuery.func2
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:191
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runWithTimeout.func1
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:203
		  | runtime.goexit
		  | 	/usr/local/go/src/runtime/asm_amd64.s:1371
		Wraps: (2) expected unpartitioned count 7 to equal partitioned count 5
		  | sql: SELECT count(*) FROM defaultdb.public.table1 AS tab_1864
		  | SELECT count(*) FROM (SELECT * FROM defaultdb.public.table1 AS tab_1864 WHERE ('12.2.182.136/14'::INET >> tab_1864.col1_5::INET)::BOOL UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_1864 WHERE NOT (('12.2.182.136/14'::INET >> tab_1864.col1_5::INET)::BOOL) UNION ALL SELECT * FROM defaultdb.public.table1 AS tab_1864 WHERE (('12.2.182.136/14'::INET >> tab_1864.col1_5::INET)::BOOL) IS NULL)
		Error types: (1) *withstack.withStack (2) *errutil.leafError

Reproduce

See: roachtest README

/cc @cockroachdb/sql-queries _{This test on roachdash | Improve this report!}

cockroach-teamcity · 2021-08-30T11:15:16Z

roachtest.tlp failed with artifacts on master @ 0b57dc40deda1206d9a1c215ffdb219bbf182a39:

The test failed on branch=master, cloud=gce:
test artifacts and logs in: /home/agent/work/.go/src/github.com/cockroachdb/cockroach/artifacts/tlp/run_1
	tlp.go:128,test_runner.go:777: expected unpartitioned count 9 to equal partitioned count 0
		(1) attached stack trace
		  -- stack trace:
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runTLPQuery.func2
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:191
		  | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runWithTimeout.func1
		  | 	/home/agent/work/.go/src/github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:203
		  | runtime.goexit
		  | 	/usr/local/go/src/runtime/asm_amd64.s:1371
		Wraps: (2) expected unpartitioned count 9 to equal partitioned count 0
		  | sql: SELECT count(*) FROM defaultdb.public.table4 AS tab_1906
		  | SELECT count(*) FROM (SELECT * FROM defaultdb.public.table4 AS tab_1906 WHERE tab_1906.col4_3::GEOGRAPHY IN (SELECT '0102000020E610000008000000309D213CF99E27C01816A7214E4030C001D18DE3D87151C03FE643B9B65D47C0EA5A2C4F7EDE60C05A6AE25F77F852C0C0294B3B00FE10C062B10E2B6E3655C0543538D27BCC4C40B43074F7307954C06224E350A4336540801710FD19C9E1BFA2811011EA4F63408CD40DCD051E454014529A25417F5F401691F943FFB05240'::GEOGRAPHY AS col_2325 FROM defaultdb.public.table3@[0] AS tab_1907 LIMIT 45) UNION ALL SELECT * FROM defaultdb.public.table4 AS tab_1906 WHERE NOT (tab_1906.col4_3::GEOGRAPHY IN (SELECT '0102000020E610000008000000309D213CF99E27C01816A7214E4030C001D18DE3D87151C03FE643B9B65D47C0EA5A2C4F7EDE60C05A6AE25F77F852C0C0294B3B00FE10C062B10E2B6E3655C0543538D27BCC4C40B43074F7307954C06224E350A4336540801710FD19C9E1BFA2811011EA4F63408CD40DCD051E454014529A25417F5F401691F943FFB05240'::GEOGRAPHY AS col_2325 FROM defaultdb.public.table3@[0] AS tab_1907 LIMIT 45)) UNION ALL SELECT * FROM defaultdb.public.table4 AS tab_1906 WHERE (tab_1906.col4_3::GEOGRAPHY IN (SELECT '0102000020E610000008000000309D213CF99E27C01816A7214E4030C001D18DE3D87151C03FE643B9B65D47C0EA5A2C4F7EDE60C05A6AE25F77F852C0C0294B3B00FE10C062B10E2B6E3655C0543538D27BCC4C40B43074F7307954C06224E350A4336540801710FD19C9E1BFA2811011EA4F63408CD40DCD051E454014529A25417F5F401691F943FFB05240'::GEOGRAPHY AS col_2325 FROM defaultdb.public.table3@[0] AS tab_1907 LIMIT 45)) IS NULL)
		Error types: (1) *withstack.withStack (2) *errutil.leafError

Reproduce

See: roachtest README

/cc @cockroachdb/sql-queries _{This test on roachdash | Improve this report!}

yuzefovich · 2021-08-30T18:21:32Z

Removing the release-blocker label since the bug with IN is not a regression in 21.2.

mgartner · 2021-08-30T18:33:24Z

Removing the release-blocker label since the bug with IN is not a regression in 21.2.

From the perspective of the specific reproduction found by TLP I think it is a regression. The repro does not result in incorrect results in 21.1. But the offending code was merged long ago, so there is a chance some other reproduction would tickle the bug.

mgartner · 2021-08-30T19:20:50Z

Leaving a note here for my future self:

Tuples should already have an isSorted field.

This field should be set correctly by the optimizer.

We can use this to decide whether to do a binary or linear search.

With a query like below, colbuilder.planProjectionExpr is called after the subquery is evaluated with a tree.Tuple, not a tree.DTuple. The sorted-ness of a tuple is known for tree.DTuples but not for tree.Tuples. So this approach might not work.

The vectorized implementation of an `element IN tuple` expression assumes that the contents of `tuple` are sorted by the optimizer. Based on this assumption, it performs a binary search instead of a linear search. However, the assumption that the optimizer sorts all tuples is incorrect. For example, there are cases where the contents of a tuple are not known at planning-time, so the tuple cannot be sorted. Performing a binary search with an unsorted tuple causes incorrect query results. Now, the vectorized engine sorts tuple contents if they are not already sorted. Fixes cockroachdb#68979 Release justification: This commit fixes a bug with the IN operator that causes incorrect results. Release note (bug fix): A bug has been fixed which caused incorrect evaluation of the `IN` operator when the tuple on the right-hand-side of the operator included a subquery, like `a IN ('foo', (SELECT s FROM t), 'bar')`.

69203: storage: update min version with store cluster version r=sumeerbhola a=jbowens Whenever the store cluster version key is updated, update the minimum storage version too. Fix #69116. Release note: None 69641: server: add SQL STATS COMPACTION to automatic job list r=maryliag,arulajmani,ajwerner a=Azhng Previously, SQL STATS COMPACTION job was not marked as automatic job. This means SQL STATS COMPACTION job would show up in the Jobs Page in DB Console and in the output of SHOW JOBS. This commit adds SQL STATS COMPACTION to a list of automatic jobs (e.g. auto table stats). This means SQL STATS COMPACTION job information would only be present in the output of SHOW AUTOMATIC JOBS. Release justification: Bug fixes and low-risk updates to new functionality Release note (sql change): SQL STATS COMPACTION job now only shows up in the output of SHOW AUTOMATIC JOBS. 69651: colexec: fix IN operator with unsorted tuple r=mgartner a=mgartner The vectorized implementation of an `element IN tuple` expression assumes that the contents of `tuple` are sorted by the optimizer. Based on this assumption, it performs a binary search instead of a linear search. However, the assumption that the optimizer sorts all tuples is incorrect. For example, there are cases where the contents of a tuple are not known at planning-time, so the tuple cannot be sorted. Performing a binary search with an unsorted tuple causes incorrect query results. Now, the vectorized engine sorts tuple contents if they are not already sorted. Fixes #68979 Release justification: This commit fixes a bug with the IN operator that causes incorrect results. Release note (bug fix): A bug has been fixed which caused incorrect evaluation of the `IN` operator when the tuple on the right-hand-side of the operator included a subquery, like `a IN ('foo', (SELECT s FROM t), 'bar')`. 69666: bazel: bazel builder image doesn't run builds as root r=jlinder a=rickystewart Adopt the same `autouseradd` script that we use in `cockroachdb/builder` to avoid creating these files as `root`. Also step down the permissions on some files that `bazci` creates -- they don't need to be so permissive any more. Closes #66162 Release justification: Non-production code change Release note: None 69681: sql: apply zone configs for copied INDEX for ALTER PK on RBR tables r=ajwerner a=otan Release justification: bug fix for existing feature Release note (bug fix): Previously, when using ALTER PRIMARY KEY on a REGIONAL BY ROW table, the copied unique index from the old PRIMARY KEY would not have the correct zone configurations applied. This commit fixes that. Users who encountered this bug should re-create the index. Co-authored-by: Jackson Owens <[email protected]> Co-authored-by: Azhng <[email protected]> Co-authored-by: Marcus Gartner <[email protected]> Co-authored-by: Ricky Stewart <[email protected]> Co-authored-by: Oliver Tan <[email protected]>

The vectorized implementation of an `element IN tuple` expression assumes that the contents of `tuple` are sorted by the optimizer. Based on this assumption, it performs a binary search instead of a linear search. However, the assumption that the optimizer sorts all tuples is incorrect. For example, there are cases where the contents of a tuple are not known at planning-time, so the tuple cannot be sorted. Performing a binary search with an unsorted tuple causes incorrect query results. Now, the vectorized engine sorts tuple contents if they are not already sorted. Fixes cockroachdb#68979 Release justification: This commit fixes a bug with the IN operator that causes incorrect results. Release note (bug fix): A bug has been fixed which caused incorrect evaluation of the `IN` operator when the tuple on the right-hand-side of the operator included a subquery, like `a IN ('foo', (SELECT s FROM t), 'bar')`.

blathers-crl bot added the T-sql-queries SQL Queries Team label Aug 16, 2021

rytaft assigned mgartner Aug 17, 2021

rytaft added the GA-blocker label Aug 23, 2021

mgartner mentioned this issue Aug 24, 2021

sql: computed column expressions incorrectly evaluated when dependent on "char" type #69327

Closed

yuzefovich removed the release-blocker Indicates a release-blocker. Use with branch-release-2x.x label to denote which branch is blocked. label Aug 30, 2021

mgartner mentioned this issue Aug 31, 2021

colexec: fix IN operator with unsorted tuple #69651

Merged

mgartner changed the title ~~roachtest: tlp failed~~ sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted Aug 31, 2021

mgartner mentioned this issue Aug 31, 2021

sql: computed column expressions incorrectly evaluated when dependent on certain types #69665

Closed

craig bot closed this as completed in 9b36827 Sep 1, 2021

This was referenced Sep 9, 2021

release-21.1: colexec: fix IN operator with unsorted tuple #69979

Closed

release-20.2: colexec: fix IN operator with unsorted tuple #69980

Closed

mgartner added this to SQL Queries Jul 24, 2023

mgartner moved this to Done in SQL Queries Jul 24, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted #68979

sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted #68979

cockroach-teamcity commented Aug 16, 2021

mgartner commented Aug 18, 2021

rytaft commented Aug 23, 2021

mgartner commented Aug 23, 2021

yuzefovich commented Aug 24, 2021

mgartner commented Aug 24, 2021

yuzefovich commented Aug 24, 2021

cockroach-teamcity commented Aug 24, 2021

mgartner commented Aug 24, 2021

mgartner commented Aug 24, 2021

yuzefovich commented Aug 24, 2021

mgartner commented Aug 24, 2021

cockroach-teamcity commented Aug 25, 2021

cockroach-teamcity commented Aug 30, 2021

yuzefovich commented Aug 30, 2021

mgartner commented Aug 30, 2021

mgartner commented Aug 30, 2021

sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted #68979

sql: vectorized IN evaluation incorrectly assumes the RHS tuple contents are sorted #68979

Comments

cockroach-teamcity commented Aug 16, 2021

mgartner commented Aug 18, 2021

rytaft commented Aug 23, 2021

mgartner commented Aug 23, 2021

yuzefovich commented Aug 24, 2021

mgartner commented Aug 24, 2021

yuzefovich commented Aug 24, 2021

cockroach-teamcity commented Aug 24, 2021

mgartner commented Aug 24, 2021

mgartner commented Aug 24, 2021

yuzefovich commented Aug 24, 2021

mgartner commented Aug 24, 2021

cockroach-teamcity commented Aug 25, 2021

cockroach-teamcity commented Aug 30, 2021

yuzefovich commented Aug 30, 2021

mgartner commented Aug 30, 2021

mgartner commented Aug 30, 2021