roachtest/unoptimized-query-oracle: incorrect results for geospatial #103616

cockroach-teamcity · 2023-05-18T18:11:32Z

roachtest.unoptimized-query-oracle/disable-rules=all/rand-tables failed with artifacts on release-23.1 @ 4d53217fb2d27559257d46261badb3be91428d1a:

test artifacts and logs in: /artifacts/unoptimized-query-oracle/disable-rules=all/rand-tables/run_1
(query_comparison_util.go:252).runOneRoundQueryComparison: . 1294 statements run: expected unoptimized and optimized results to be equal
  []string(
- 	nil,
+ 	{
+ 		"BOX(-0.17596396378499507 -0.7935108588146653,1.6507331385363777 0.3892996820427791)",
+ 		"BOX(-0.44992608732063816 -0.8355313727814945,0.7592064540513982 -0.10620010400194807)",
+ 		"BOX(-0.5991572309955492 -1.0771724478708085,1.4605257094972963 0.8794544719921826)",
+ 		"BOX(-0.6567783142434518 -0.20189765997084663,-0.5427570031482938 -0.11573451853214733)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		"BOX(-0.8295263453828648 -0.12921899431101314,-0.6879662233412243 1.7261578865680827)",
+ 		...,
+ 	},
  )
sql: SELECT
	"tÂb😌389"."col2_'6" AS "coͯ
l1275"
FROM
	defaultdb.public."tabl�e2"@[0] AS "tÂb😌389"
WHERE
	(1.2345678901234566e-43:::FLOAT8 <= st_distance("tÂb😌389".c😽ol2_4::GEOGRAPHY, '0106000020E610000000000000':::GEOGRAPHY::GEOGRAPHY)::FLOAT8)

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-28097}

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

msirek · 2023-05-18T23:16:24Z

Simplified test case:

CREATE TABLE t1 (col2_4 GEOGRAPHY NULL);
insert into t1 values ('0102000020E610000000000000'::GEOGRAPHY);
SET testing_optimizer_random_seed = 656627027908814488;
SET testing_optimizer_disable_rule_probability = 0.579;
SELECT col2_4 FROM t1
WHERE
        (1.2345678901234566e-43:::FLOAT8 <= st_distance(col2_4::GEOGRAPHY, '0106000020E610000000000000':::GEOGRAPHY::GEOGRAPHY)::FLOAT8);
  col2_4
----------
(0 rows)

SET testing_optimizer_disable_rule_probability = 0.578;
SELECT col2_4 FROM t1
WHERE
        (1.2345678901234566e-43:::FLOAT8 <= st_distance(col2_4::GEOGRAPHY, '0106000020E610000000000000':::GEOGRAPHY::GEOGRAPHY)::FLOAT8);
            col2_4
------------------------------
  0102000020E610000000000000
(1 row)

msirek · 2023-05-18T23:29:27Z

Removing the release-blocker label. This problem occurs on v22.1.20 as well.

msirek · 2023-05-19T00:03:53Z

The disabled rule causing the testing discrepancy is CommuteConstInequality.

msirek · 2023-05-20T03:50:45Z

@DrewKimball
The problem in this case stems from #53066, which added the FoldCmpSTDistanceLeft and FoldCmpSTDistanceRight rules.

The assumption is that st_distance(a,b) >= x can be replaced with NOT st_dwithinexclusive(a,b,x).
The problem is that if a or b is an empty geography (i.e., SELECT st_isempty(a) returns true), the whole expression st_distance(a,b) >= x returns null, but NOT st_dwithinexclusive(a,b,x) returns true. Three-valued logic doesn't allow for equating these expressions. Even if restricting the rules to only occur on WHERE clause filters, it would only be valid if there is a single filter because combining the filter with other ANDed filters would break three-valued logic. Even the single filter case might not be safe because if other logic tries to negate that filter or combine it with other filters, the semantics will change.

I'm not sure what the fix is here to preserve the ability to use inverted indexes. Maybe create new versions of functions st_dwithin and st_dwithinexclusive (with different names) which return null on empty geographic input, and use those in the transformation rules? I'm assuming we don't want to change the behavior of the original functions because we'd want to stay compatible with Postgres/PostGIS.

mgartner · 2023-06-28T16:19:53Z

@DrewKimball and I discussed this and we think we could change the rule to construct this expression instead:

st_dwithinexclusive(a, b, dist) AND NOT ((st_isempty(a) OR st_isempty(b)) AND NULL)

The RHS of the top-level AND should return NULL correctly.

mgartner · 2023-06-28T16:34:35Z

A better approach might be to add an optional st_dwithinexclusive filter when trying to build the inverted constraints, rather than altering the original filter in a normalization rule.

We think that these expressions are equivalent (in the context of a filter):

d >= st_distance(a, b)

d >= st_distance(a, b) AND st_dwithinexclusive(a, b, d)

And these two expressions are equivalent (in the context of a filter):

d <= st_disatance(a, b)

d <= st_distance(a, b) AND NOT st_dwithinexclusive(a, b, d)

We need to consider the similar rules that transform st_maxdistance too.

msirek · 2023-08-12T19:48:41Z

The ideas to generate extra terms ANDed with st_dwithinexclusive(a, b, dist) won't work in the case of negation:
NOT (st_dwithinexclusive(a, b, dist) AND any_pred) ->
NOT st_dwithinexclusive(a, b, dist) OR NOT any_pred

Even if NOT any_pred is null-preserving and evaluates to null, it's still ORed with st_dwithinexclusive(a, b, dist) which hides nulls and could cause the expression as a whole to evaluate to true, where the original expression would evaluate to null (false), even if negated.
Probably the best approach would be:

Maybe create new versions of functions st_dwithin and st_dwithinexclusive (with different names) which return null on empty geographic input, and use those in the transformation rules?

The whole point of these transformation rules is to trigger inverted index access, though, so additional work would be required to not only allow the new functions to trigger index access, but also filter out rows with null and empty geography expressions. It might not be a trivial change.

Another alternative is to get rid of the transformation rules entirely, but there may be customers depending on them for their use cases, so that might not be a practical solution.

msirek · 2023-08-15T00:20:16Z

Another idea is, instead of rewriting the predicate, push the generation of the st_distance expression into geoFilterPlanner.extractInvertedFilterConditionFromLeaf. This way we never actually replace the original predicate, or generate additional predicates which aren't semantically equivalent. The new predicate would be generated and used solely for determining the inverted filter spans to use in an inverted index scan. The logic of the 4 rewrite rules, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft, and FoldCmpSTMaxDistanceRight would be moved out of rewrite rules, and into geoFilterPlanner.extractInvertedFilterConditionFromLeaf.

@mgartner @DrewKimball What do you think of this approach?

DrewKimball · 2023-08-16T09:05:03Z

@mgartner @DrewKimball What do you think of this approach?

I agree, this seems like the right approach.

The query normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight replace binary comparison operations, =, <, >, <=, >= involving the `st_distance` or `st_maxdistance` functions with equivalent function calls which may enable inverted index scan, for example st_dwithin, and st_dfullywithin. For non-null and non-empty geographies and geometries, this rewrite is semantically equivalent, but for null or empty inputs, `st_distance` uses three-valued boolean logic and returns a null. `st_dwithin` always returns true or false, so may return a different value when the expression is negated. For example, the following test returns `true`, but should return `null`: ```sql CREATE TABLE g1 (geog GEOGRAPHY); INSERT INTO g1 VALUES (ST_GeogFromText('MULTILINESTRING EMPTY')); SELECT ST_Distance('POINT(0 0)'::GEOGRAPHY, geog) > 1 AS predicate_result FROM g1; predicate_result -------------------- t ``` The solution is to move all of the logic in the above normalization rules into `geoFilterPlanner.extractInvertedFilterConditionFromLeaf`, and use the derived predicate only for the purposes of finding inverted index scan spans. The spans will always include all rows qualified for the original predicate, but may include additional rows. The original filter is then applied to the results of the inverted index scan to filter out any results with nulls or empty geographies and geometries. Epic: none Fixes: cockroachdb#103616 Release note (bug fix): This patch fixes a bug in geospatial queries, where a query filter of the form `ST_Distance(geog1, geog2) > constant`, or `ST_MaxDistance(geom1, geom2) > constant`, where the operator is one of >, <, >=, <=, or a filter of the form `ST_Distance(geog1, geog2, false) = 0` may mistakenly evaluate to `true` when one or both of the inputs is null or an empty geography/geometry. More rows could be returned by the query than expected.

This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: cockroachdb#103616 Release note: None

The query normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight replace binary comparison operations, =, <, >, <=, >= involving the `st_distance` or `st_maxdistance` functions with equivalent function calls which may enable inverted index scan, for example st_dwithin, and st_dfullywithin. For non-null and non-empty geographies and geometries, this rewrite is semantically equivalent, but for null or empty inputs, `st_distance` uses three-valued boolean logic and returns a null. `st_dwithin` always returns true or false, so may return a different value when the expression is negated. For example, the following test returns `true`, but should return `null`: ```sql CREATE TABLE g1 (geog GEOGRAPHY); INSERT INTO g1 VALUES (ST_GeogFromText('MULTILINESTRING EMPTY')); SELECT ST_Distance('POINT(0 0)'::GEOGRAPHY, geog) > 1 AS predicate_result FROM g1; predicate_result -------------------- t ``` The solution is to move all of the logic in the above normalization rules into `geoFilterPlanner.extractInvertedFilterConditionFromLeaf`, and use the derived predicate only for the purposes of finding inverted index scan spans. The spans will always include all rows qualified for the original predicate, but may include additional rows. The original filter is then applied to the results of the inverted index scan to filter out any results with nulls or empty geographies and geometries. Epic: none Fixes: cockroachdb#103616 Release note (bug fix): This patch fixes a bug in geospatial queries, where a query filter of the form `ST_Distance(geog1, geog2) > constant`, or `ST_MaxDistance(geom1, geom2) > constant`, where the operator is one of >, <, >=, <=, or a filter of the form `ST_Distance(geog1, geog2, false) = 0` may mistakenly evaluate to `true` when one or both of the inputs is null or an empty geography/geometry. More rows could be returned by the query than expected.

This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: cockroachdb#103616 Release note: None

108954: invertedidx: derive geog/geom filters which enable inverted index scan r=DrewKimball,mgartner a=msirek The query normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight replace binary comparison operations, =, <, >, <=, >= involving the `st_distance` or `st_maxdistance` functions with equivalent function calls which may enable inverted index scan, for example st_dwithin, and st_dfullywithin. For non-null and non-empty geographies and geometries, this rewrite is semantically equivalent, but for null or empty inputs, `st_distance` uses three-valued boolean logic and returns a null. `st_dwithin` always returns true or false, so may return a different value when the expression is negated. For example, the following test returns `true`, but should return `null`: ```sql CREATE TABLE g1 (geog GEOGRAPHY); INSERT INTO g1 VALUES (ST_GeogFromText('MULTILINESTRING EMPTY')); SELECT ST_Distance('POINT(0 0)'::GEOGRAPHY, geog) > 1 AS predicate_result FROM g1; predicate_result -------------------- t ``` The solution is to move all of the logic in the above normalization rules into `geoFilterPlanner.extractInvertedFilterConditionFromLeaf`, and use the derived predicate only for the purposes of finding inverted index scan spans. The spans will always include all rows qualified for the original predicate, but may include additional rows. The original filter is then applied to the results of the inverted index scan to filter out any results with nulls or empty geographies and geometries. Epic: none Fixes: #103616 Release note (bug fix): This patch fixes a bug in geospatial queries, where a query filter of the form `ST_Distance(geog1, geog2) > constant`, or `ST_MaxDistance(geom1, geom2) > constant`, where the operator is one of >, <, >=, <=, or a filter of the form `ST_Distance(geog1, geog2, false) = 0` may mistakenly evaluate to `true` when one or both of the inputs is null or an empty geography/geometry. More rows could be returned by the query than expected. ---- xform: move st_distance rules tests from norm to xform This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: #103616 Release note: None ---- invertedidx: move geospatial filter derivation functions out of norm This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: #103616 Release note: None Co-authored-by: Mark Sirek <sirek@cockroachlabs.com>

The query normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight replace binary comparison operations, =, <, >, <=, >= involving the `st_distance` or `st_maxdistance` functions with equivalent function calls which may enable inverted index scan, for example st_dwithin, and st_dfullywithin. For non-null and non-empty geographies and geometries, this rewrite is semantically equivalent, but for null or empty inputs, `st_distance` uses three-valued boolean logic and returns a null. `st_dwithin` always returns true or false, so may return a different value when the expression is negated. For example, the following test returns `true`, but should return `null`: ```sql CREATE TABLE g1 (geog GEOGRAPHY); INSERT INTO g1 VALUES (ST_GeogFromText('MULTILINESTRING EMPTY')); SELECT ST_Distance('POINT(0 0)'::GEOGRAPHY, geog) > 1 AS predicate_result FROM g1; predicate_result -------------------- t ``` The solution is to move all of the logic in the above normalization rules into `geoFilterPlanner.extractInvertedFilterConditionFromLeaf`, and use the derived predicate only for the purposes of finding inverted index scan spans. The spans will always include all rows qualified for the original predicate, but may include additional rows. The original filter is then applied to the results of the inverted index scan to filter out any results with nulls or empty geographies and geometries. Epic: none Fixes: cockroachdb#103616 Release note (bug fix): This patch fixes a bug in geospatial queries, where a query filter of the form `ST_Distance(geog1, geog2) > constant`, or `ST_MaxDistance(geom1, geom2) > constant`, where the operator is one of >, <, >=, <=, or a filter of the form `ST_Distance(geog1, geog2, false) = 0` may mistakenly evaluate to `true` when one or both of the inputs is null or an empty geography/geometry. More rows could be returned by the query than expected.

This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: cockroachdb#103616 Release note: None

The query normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight replace binary comparison operations, =, <, >, <=, >= involving the `st_distance` or `st_maxdistance` functions with equivalent function calls which may enable inverted index scan, for example st_dwithin, and st_dfullywithin. For non-null and non-empty geographies and geometries, this rewrite is semantically equivalent, but for null or empty inputs, `st_distance` uses three-valued boolean logic and returns a null. `st_dwithin` always returns true or false, so may return a different value when the expression is negated. For example, the following test returns `true`, but should return `null`: ```sql CREATE TABLE g1 (geog GEOGRAPHY); INSERT INTO g1 VALUES (ST_GeogFromText('MULTILINESTRING EMPTY')); SELECT ST_Distance('POINT(0 0)'::GEOGRAPHY, geog) > 1 AS predicate_result FROM g1; predicate_result -------------------- t ``` The solution is to move all of the logic in the above normalization rules into `geoFilterPlanner.extractInvertedFilterConditionFromLeaf`, and use the derived predicate only for the purposes of finding inverted index scan spans. The spans will always include all rows qualified for the original predicate, but may include additional rows. The original filter is then applied to the results of the inverted index scan to filter out any results with nulls or empty geographies and geometries. Epic: none Fixes: cockroachdb#103616 Release note (bug fix): This patch fixes a bug in geospatial queries, where a query filter of the form `ST_Distance(geog1, geog2) > constant`, or `ST_MaxDistance(geom1, geom2) > constant`, where the operator is one of >, <, >=, <=, or a filter of the form `ST_Distance(geog1, geog2, false) = 0` may mistakenly evaluate to `true` when one or both of the inputs is null or an empty geography/geometry. More rows could be returned by the query than expected.

This commit moves the tests for the old normalization rules FoldEqZeroSTDistance, FoldCmpSTDistanceLeft, FoldCmpSTDistanceRight, FoldCmpSTMaxDistanceLeft and FoldCmpSTMaxDistanceRight from norm into xform. The tests now check whether the derived filter triggers the GenerateInvertedIndexScans rule. Epic: none Informs: cockroachdb#103616 Release note: None

This commit moves functions previously associated with normalization rules, but now associated with exploration-time geospatial filter derivation out of the norm package. Epic: none Informs: cockroachdb#103616 Release note: None

We have already fixed cockroachdb#103616 in 23.2, but are choosing to revert the backport to 23.1 to reduce risk. Add the involved optimizer rules to the essential rule list to try and prevent duplicate failures of the test in release-23.1. Informs: cockroachdb#103616 Release note: None

We have already fixed #103616 in 23.2, but are choosing to revert the backport to 23.1 to reduce risk. Add the involved optimizer rules to the essential rule list to try and prevent duplicate failures of the test in release-23.1. Informs: #103616 Release note: None

cockroach-teamcity added this to the 23.1 milestone May 18, 2023

blathers-crl bot added the T-sql-queries SQL Queries Team label May 18, 2023

msirek removed the release-blocker Indicates a release-blocker. Use with branch-release-2x.x label to denote which branch is blocked. label May 18, 2023

cockroach-teamcity mentioned this issue May 22, 2023

roachtest: unoptimized-query-oracle false positive due to window function ordering #103714

Closed

yuzefovich changed the title ~~roachtest: unoptimized-query-oracle/disable-rules=all/rand-tables failed~~ roachtest/unoptimized-query-oracle: incorrect results for geospatial Jun 2, 2023

DrewKimball self-assigned this Jun 28, 2023

mgartner added this to SQL Queries Jul 24, 2023

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

michae2 assigned msirek and unassigned DrewKimball Aug 11, 2023

craig bot closed this as completed in 0918300 Aug 24, 2023

github-project-automation bot moved this from Active to Done in SQL Queries Aug 24, 2023

msirek mentioned this issue Aug 24, 2023

release-23.1: invertedidx: derive geog/geom filters which enable inverted index scan #109393

Merged

msirek mentioned this issue Aug 24, 2023

release-23.1.9-rc: invertedidx: derive geog/geom filters which enable inverted index scan #109395

Merged

michae2 mentioned this issue Sep 21, 2023

sql: revert two backports deemed too risky for a patch update #111077

Merged

michae2 mentioned this issue Sep 21, 2023

sql: revert two backports deemed too risky for a patch update #111083

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

roachtest/unoptimized-query-oracle: incorrect results for geospatial #103616

roachtest/unoptimized-query-oracle: incorrect results for geospatial #103616

cockroach-teamcity commented May 18, 2023 •

edited by cockroach-jira-scripts

Loading

msirek commented May 18, 2023

msirek commented May 18, 2023

msirek commented May 19, 2023

msirek commented May 20, 2023

mgartner commented Jun 28, 2023

mgartner commented Jun 28, 2023

msirek commented Aug 12, 2023 •

edited

Loading

msirek commented Aug 15, 2023 •

edited

Loading

DrewKimball commented Aug 16, 2023

roachtest/unoptimized-query-oracle: incorrect results for geospatial #103616

roachtest/unoptimized-query-oracle: incorrect results for geospatial #103616

Comments

cockroach-teamcity commented May 18, 2023 • edited by cockroach-jira-scripts Loading

msirek commented May 18, 2023

msirek commented May 18, 2023

msirek commented May 19, 2023

msirek commented May 20, 2023

mgartner commented Jun 28, 2023

mgartner commented Jun 28, 2023

msirek commented Aug 12, 2023 • edited Loading

msirek commented Aug 15, 2023 • edited Loading

DrewKimball commented Aug 16, 2023

cockroach-teamcity commented May 18, 2023 •

edited by cockroach-jira-scripts

Loading

msirek commented Aug 12, 2023 •

edited

Loading

msirek commented Aug 15, 2023 •

edited

Loading