roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results #89101

rytaft · 2022-09-30T16:32:24Z

    roachtest.tlp [failed](https://teamcity.cockroachdb.com/buildConfiguration/Cockroach_Nightlies_RoachtestNightlyGceBazel/6704781?buildTab=log) with [artifacts](https://teamcity.cockroachdb.com/buildConfiguration/Cockroach_Nightlies_RoachtestNightlyGceBazel/6704781?buildTab=artifacts#/tlp) on master @ [801bfc62afd7128be180e3396d21a1e0b2daa227](https://github.com/cockroachdb/cockroach/commits/801bfc62afd7128be180e3396d21a1e0b2daa227):

		  |   	strings.Join({
		  |   		"8,-1,555f:9472:98fd:40b1:c6c6:1f2d:a321:5412/98,0000-01-01 ",
		  | - 		"18:47:50.169239",
		  | + 		"03:30:07.374522",
		  |   		" +0000 UTC,001001010101000011111001110,22205,",
		  | - 		"-1732073207,1.1667083030499676,,01060000800700000001030000800100",
		  | - 		"00000900000098BCEA849D60F3C1A07753AC59C0F2C1484BD55B9A92FD41FCC3",
		  | - 		"2CB26C1CE5C1724E65241A55F9C1304D2EE0A2B6DE41280F51299511DF419BE1",
		  | - 		"EBF4B34AFDC1BE98B74312FEE8C1A2CCFF4425AAF141F49C07D74516FEC19840",
		  | - 		"6F41B761FC4180A72A02CFC4F441E7E37B7E635AF4C12871F0B3E9B3FE41A2B4",
		  | - 		"AB41DE5CF14130EA4458B230D0C10E6292265005E3C160676C47F920FF41384D",
		  | - 		"24B62AB2EB41B09AA4006141F541F80673262FEDFE41581A9659EF8B0242F890",
		  | - 		"738CF80201C298BCEA849D60F3C1A07753AC59C0F2C1484BD55B9A92FD410103",
		  | - 		"0000800100000006000000BB0E2F5318BA01C2AE6A33F0AB62F7C15FAA54E017",
		  | - 		"8DF5C1D6163F1ECBB8E8C1A781396AD09EF5C1E42A56041CA0EF411859448810",
		  | - 		"3ED04176E06BA8B9F00142A166189193DD01C28EAB954B2AE1EEC134F6127A17",
		  | - 		"C601423846A5AD5861D4415AE888763EC8EEC1CC24F07F62EAF741A48AEADD63",
		  | - 		"8EFC41BB0E2F5318BA01C2AE6A33F0AB62F7C15FAA54E0178DF5C10103000080",
		  | - 		"010000000700000038D410D93618FCC11E9C90CF1771FBC1D006959FB163E141",
		  | - 		"2660CF17ADD8F4C1A64E9C05F1EE00C220E634232A0FC5C1CA42541590EE0142",
		  | - 		"B7CE30CB117D00C2AE352649ACB9F541005818877AD65AC1A0365B7DD18EC741",
		  | - 		"82340E3E5059F24100A7DD95D8CEC8411C8882DD0FBCFB4162E7734356CC0142",
		  | - 		"D0C5D01A234BEBC1E882BD15B972DA4198AC98C87414004238D410D93618FCC1",
		  | - 		"1E9C90CF1771FBC1D006959FB163E14101030000800100000004000000E4A472",
		  | - 		"C9C9B0D8C1CC9663122829E0C14EAE06D13DE1F841780C2F324CBBD6C18AFE58",
		  | - 		"870973F0C11615DFF4D7BDEFC1E0E7CB305CE9B441FC13A40A1DBAE041CCDD1F",
		  | - 		"8C40E9F7C1E4A472C9C9B0D8C1CC9663122829E0C14EAE06D13DE1F841010300",
		  | - 		"008001000000040000007BA7EAFBA00800C288E0D78D42EBE941A76F2C4D6C78",
		  | - 		"FCC1E8DA3894660BFC4144B017BC4838E041F0A7923F608CC8419A08CD84C2D7",
		  | - 		"E6C1188302E8604AF5416AE02704639AF8417BA7EAFBA00800C288E0D78D42EB",
		  | - 		"E941A76F2C4D6C78FCC1010300008001000000040000008D6490264149FCC19E",
		  | - 		"3CEB378898EBC1C4356B3B14AFFC41ACD49F385880E8C100A3F5B816EDB8414A",
		  | - 		"99E721782D0242E09E700AE715FAC12A04B504461DF5415457DFC4FCE6F6C18D",
		  | - 		"6490264149FCC19E3CEB378898EBC1C4356B3B14AFFC41010300008001000000",
		  | - 		"050000006328351317C4FBC12ACAF6AAAE35F9C108C3D8498B49F6C1D80673BC",
		  | - 		"7D45FA410F899374097401C2008D4B1095939841E0EC307E7E6FDFC19094B653",
		  | - 		"B1B3D3C11BF5C50069B1F2C1304806C8E4ADDFC18EFA12039D93F4C130C8EFB9",
		  | - 		"55E5D5416328351317C4FBC12ACAF6AAAE35F9C108C3D8498B49F6C1",
		  | + 		"NULL,NULL,NULL,NULL",
		  |   	}, ""),
		  | - 	"8,-1,555f:9472:98fd:40b1:c6c6:1f2d:a321:5412/98,0000-01-01 18:47:50.169239 +0000 UTC,001001010101000011111001110,22205,-1961353027,0.41112826797767454,\x06\x9d,0103000080010000000D00000029DF7B11E18C01C21E9661DCE465EFC1A4AD056E94DBE8419CBB86933A86E9C12B700FBF8121"...,
		  | - 	"8,-1,555f:9472:98fd:40b1:c6c6:1f2d:a321:5412/98,0000-01-01 18:47:50.169239 +0000 UTC,001001010101000011111001110,22205,137276772,1.2044450127928552,P\x934,01060000400500000001030000400100000006000000363AF3255445F6C17439DC43448EF0C1C8D23BD3DCBDE24138B72231D471"...,
		  | - 	"8,-1,555f:9472:98fd:40b1:c6c6:1f2d:a321:5412/98,0000-01-01 18:47:50.169239 +0000 UTC,001001010101000011111001110,22205,1604224436,0.24694248111198003,l\xe2\xf0\x9b\x98rR\v,01040000400300000001010000407855F2C5C67BE1417285D665B619F941891E8A8B5662F4C101010000405F9054D05C2"...,
		  | - 	"8,-1,555f:9472:98fd:40b1:c6c6:1f2d:a321:5412/98,0000-01-01 18:47:50.169239 +0000 UTC,001001010101000011111001110,22205,32767,-1.7001757136680231,S*\x80\x8a,0106000000050000000103000000010000000D000000400386012452A0C1E07F55C1FC57BAC1B8834182AA0BD0C160457E200B82FB"...,
		  |   	... // 12 identical, 19 removed, and 6 modified elements
		  |   }
		  | sql: (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON TRUE) UNION ALL (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON FALSE) UNION ALL (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON FALSE)
		  | (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON tab_56368.col4_4::BIT(13) NOT IN (WITH with_1336 (col_3761, col_3762) AS (SELECT * FROM (VALUES ('03:10:37.621365':::TIME, 3485430485:::OID), ('19:21:53.300099':::TIME, 245278239:::OID), ('15:23:28.038224':::TIME, NULL)) AS tab_56370 (col_3761, col_3762)), with_1337 (col_3763) AS (SELECT * FROM (VALUES ('lw':::rand_typ_1), (COALESCE('lw':::rand_typ_1, 'lw':::rand_typ_1)), ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56371 (col_3763) EXCEPT SELECT * FROM (VALUES ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56372 (col_3764)) SELECT tab_56368.col4_4::BIT(13) AS col_3765 FROM with_1337 AS cte_ref_419 WHERE true ORDER BY cte_ref_419.col_3763 LIMIT 5:::INT8)) UNION ALL (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON NOT (tab_56368.col4_4::BIT(13) NOT IN (WITH with_1336 (col_3761, col_3762) AS (SELECT * FROM (VALUES ('03:10:37.621365':::TIME, 3485430485:::OID), ('19:21:53.300099':::TIME, 245278239:::OID), ('15:23:28.038224':::TIME, NULL)) AS tab_56370 (col_3761, col_3762)), with_1337 (col_3763) AS (SELECT * FROM (VALUES ('lw':::rand_typ_1), (COALESCE('lw':::rand_typ_1, 'lw':::rand_typ_1)), ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56371 (col_3763) EXCEPT SELECT * FROM (VALUES ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56372 (col_3764)) SELECT tab_56368.col4_4::BIT(13) AS col_3765 FROM with_1337 AS cte_ref_419 WHERE true ORDER BY cte_ref_419.col_3763 LIMIT 5:::INT8))) UNION ALL (SELECT * FROM defaultdb.public.table4 AS tab_56368 LEFT JOIN defaultdb.public.table5 AS tab_56369 ON (tab_56368.col4_4::BIT(13) NOT IN (WITH with_1336 (col_3761, col_3762) AS (SELECT * FROM (VALUES ('03:10:37.621365':::TIME, 3485430485:::OID), ('19:21:53.300099':::TIME, 245278239:::OID), ('15:23:28.038224':::TIME, NULL)) AS tab_56370 (col_3761, col_3762)), with_1337 (col_3763) AS (SELECT * FROM (VALUES ('lw':::rand_typ_1), (COALESCE('lw':::rand_typ_1, 'lw':::rand_typ_1)), ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56371 (col_3763) EXCEPT SELECT * FROM (VALUES ('lw':::rand_typ_1), ('lw':::rand_typ_1)) AS tab_56372 (col_3764)) SELECT tab_56368.col4_4::BIT(13) AS col_3765 FROM with_1337 AS cte_ref_419 WHERE true ORDER BY cte_ref_419.col_3763 LIMIT 5:::INT8)) IS NULL)
		  | with args: []
		Error types: (1) *withstack.withStack (2) *errutil.leafError

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

Help

See: roachtest README

See: How To Investigate (internal)

_{This test on roachdash | Improve this report!

Originally posted by @cockroach-teamcity in #88993 (comment)
Jira issue: CRDB-20119}

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

blathers-crl · 2022-09-30T16:32:26Z

Hi @rytaft, please add a C-ategory label to your issue. Check out the label system docs.

While you're here, please consider adding an A- label to help keep our repository tidy.

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

rytaft · 2022-09-30T16:36:32Z

Here is a reproduction:

CREATE TABLE table4 (
  col4_4 INT PRIMARY KEY
);

CREATE TABLE table5 (
  col5_2 STRING PRIMARY KEY
);

INSERT INTO table4 (col4_4) VALUES (0);

INSERT INTO table5 (col5_2) VALUES ('a');

(SELECT * FROM table4 LEFT JOIN table5 ON TRUE) UNION ALL
(SELECT * FROM table4 LEFT JOIN table5 ON FALSE) UNION ALL
(SELECT * FROM table4 LEFT JOIN table5 ON FALSE);

(SELECT * FROM table4 LEFT JOIN table5 ON col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))))) UNION ALL 
(SELECT * FROM table4 LEFT JOIN table5 ON NOT (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1)))))) UNION ALL 
(SELECT * FROM table4 LEFT JOIN table5 ON (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))))) IS NULL);

This issue exists on 21.2 and 22.1, so this is not a release blocker.

rytaft · 2022-09-30T16:54:00Z

A simpler reproduction with the joins removed:

CREATE TABLE table4 (
  col4_4 INT PRIMARY KEY
);

INSERT INTO table4 (col4_4) VALUES (0);

SELECT * FROM table4;

(SELECT * FROM table4 WHERE col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))))) UNION ALL 
(SELECT * FROM table4 WHERE NOT (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1)))))) UNION ALL 
(SELECT * FROM table4 WHERE (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))))) IS NULL);

rytaft · 2022-09-30T17:12:55Z

This query is incorrect:

CREATE TABLE table4 (
  col4_4 INT PRIMARY KEY
);

INSERT INTO table4 (col4_4) VALUES (0);

SELECT * FROM table4 WHERE NOT (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))) as foo));

It produces 1 row when it should produce 0 rows:

> SELECT * FROM table4 WHERE NOT (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))) as foo));
  col4_4
----------
       0
(1 row)

It appears to be a bug in the optimizer, since the plan produced is a simple full table scan:

> EXPLAIN SELECT * FROM table4 WHERE NOT (col4_4 NOT IN (SELECT col4_4 FROM ((VALUES (1), (1)) EXCEPT (VALUES (1))) as foo));
                                      info
--------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • scan
    estimated row count: 1 (100% of the table; stats collected 16 minutes ago)
    table: table4@table4_pkey
    spans: FULL SCAN
(7 rows)

rytaft · 2022-09-30T17:33:13Z

I've found the problem. The cardinality property of EXCEPT is incorrect:

> explain (opt,verbose) (VALUES (1), (1)) EXCEPT (VALUES (1));
                         info
-------------------------------------------------------
  except
   ├── columns: column1:1
   ├── left columns: column1:1
   ├── right columns: column1:2
   ├── cardinality: [1 - 2]
   ├── stats: [rows=1, distinct(1)=1, null(1)=0]
   ├── cost: 0.1
   ├── key: (1)
   ├── distribution: us-east1
   ├── values
   │    ├── columns: column1:1
   │    ├── cardinality: [2 - 2]
   │    ├── stats: [rows=2, distinct(1)=1, null(1)=0]
   │    ├── cost: 0.03
   │    ├── distribution: us-east1
   │    ├── (1,)
   │    └── (1,)
   └── values
        ├── columns: column1:2
        ├── cardinality: [1 - 1]
        ├── stats: [rows=1, distinct(2)=1, null(2)=0]
        ├── cost: 0.02
        ├── key: ()
        ├── fd: ()-->(2)
        ├── distribution: us-east1
        └── (1,)
(26 rows)

We incorrectly assume that the EXCEPT produces at least one row, when in fact it can produce 0 rows. In other words,

   ├── cardinality: [1 - 2]

should be:

   ├── cardinality: [0 - 2]

89042: kvserver: decrease verbosity of replicate queue trace logging r=AlexTalks a=AlexTalks While logging of traces on replicate queue errors was recently added, logging these traces at the `WARNING` level appears to be too high, causing noisy logs. This change decreases the verbosity of these logs to the `INFO` level. Release note: None 89108: opt: fix min cardinality calculation of EXCEPT r=rytaft a=rytaft Prior to this commit, we assumed that the minimum cardinality of `EXCEPT` could never be lower than the minimum cardinality of the left side minus the maximum cardinality of the right side. However, this assumption is only true for `EXCEPT ALL`, not `EXCEPT`. For example, `VALUES (1), (1) EXCEPT VALUES (1)` produces 0 rows, even though the left side produces more rows than the right. Because of this invalid assumption, the optimizer could make some invalid transformations, resulting in incorrect results. Fixes #89101 Release note (bug fix): Fixed a bug that has existed since v2.1.0 where queries containing a subquery with `EXCEPT` could produce incorrect results. This could happen if the optimizer could guarantee that the left side of the `EXCEPT` always returned more rows than the right side. In this case, the optimizer made a faulty assupmtion that the `EXCEPT` subquery always returned at least one row, which could cause the optimizer to perform an invalid transformation, possibly causing the full query to return incorrect results. 89112: sql: correctly reset the planner in the copy shim r=yuzefovich a=yuzefovich Previously, we forgot to update the txn of the eval context of the planner. Release note: None Co-authored-by: Alex Sarkesian <[email protected]> Co-authored-by: Rebecca Taft <[email protected]> Co-authored-by: Yahor Yuzefovich <[email protected]>

Prior to this commit, we assumed that the minimum cardinality of EXCEPT could never be lower than the minimum cardinality of the left side minus the maximum cardinality of the right side. However, this assumption is only true for EXCEPT ALL, not EXCEPT. For example, VALUES (1), (1) EXCEPT VALUES (1) produces 0 rows, even though the left side produces more rows than the right. Because of this invalid assumption, the optimizer could make some invalid transformations, resulting in incorrect results. Fixes #89101 Release note (bug fix): Fixed a bug that has existed since v2.1.0 where queries containing a subquery with EXCEPT could produce incorrect results. This could happen if the optimizer could guarantee that the left side of the EXCEPT always returned more rows than the right side. In this case, the optimizer made a faulty assupmtion that the EXCEPT subquery always returned at least one row, which could cause the optimizer to perform an invalid transformation, possibly causing the full query to return incorrect results.

rytaft mentioned this issue Sep 30, 2022

roachtest: tlp failed: SplitLimitedSelectIntoUnionSelects makes incorrect transformation #88993

Closed

rytaft added C-test-failure Broken test (automatically or manually discovered). O-roachtest branch-master Failures and bugs on the master branch. labels Sep 30, 2022

blathers-crl bot added the T-sql-queries SQL Queries Team label Sep 30, 2022

rytaft changed the title ~~roachtest.tlp failed: issue with left apply join~~ roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results Sep 30, 2022

rytaft added S-0-visible-logical-error Database stores inconsistent data in some cases, or queries return invalid results silently. S-3-erroneous-edge-case Database produces or stores erroneous data without visible error/warning, in rare edge cases. labels Sep 30, 2022

rytaft mentioned this issue Sep 30, 2022

opt: fix min cardinality calculation of EXCEPT #89108

Merged

craig bot closed this as completed in 7ca5fa1 Sep 30, 2022

This was referenced Sep 30, 2022

release-21.2: opt: fix min cardinality calculation of EXCEPT #89132

Merged

release-22.1: opt: fix min cardinality calculation of EXCEPT #89134

Merged

blathers-crl bot mentioned this issue Sep 30, 2022

release-22.2: opt: fix min cardinality calculation of EXCEPT #89135

Merged

blathers-crl bot mentioned this issue Oct 4, 2022

release-22.2.0: opt: fix min cardinality calculation of EXCEPT #89305

Merged

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

roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results #89101

roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results #89101

rytaft commented Sep 30, 2022 •

edited by cockroach-jira-scripts

Loading

blathers-crl bot commented Sep 30, 2022

rytaft commented Sep 30, 2022

rytaft commented Sep 30, 2022

rytaft commented Sep 30, 2022 •

edited

Loading

rytaft commented Sep 30, 2022

roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results #89101

roachtest.tlp failed: incorrect cardinality of EXCEPT produces incorrect results #89101

Comments

rytaft commented Sep 30, 2022 • edited by cockroach-jira-scripts Loading

blathers-crl bot commented Sep 30, 2022

rytaft commented Sep 30, 2022

rytaft commented Sep 30, 2022

rytaft commented Sep 30, 2022 • edited Loading

rytaft commented Sep 30, 2022

rytaft commented Sep 30, 2022 •

edited by cockroach-jira-scripts

Loading

rytaft commented Sep 30, 2022 •

edited

Loading