roachtest/costfuzz: join reordering issue #88659
Assignees
Labels
branch-master
Failures and bugs on the master branch.
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.
S-3-erroneous-edge-case
Database produces or stores erroneous data without visible error/warning, in rare edge cases.
T-sql-queries
SQL Queries Team
Milestone
Comments
cockroach-teamcity
added
branch-master
This comment was marked as off-topic.
This comment was marked as off-topic.
This comment was marked as duplicate.
This comment was marked as duplicate.
|
Created #88710 to track the last (hidden) failure. |
|
CREATE TABLE table1 (
col1_0 FLOAT8 NOT NULL,
col1_1 FLOAT8 NOT NULL,
PRIMARY KEY (col1_0 ASC),
INDEX (col1_1 DESC),
UNIQUE ((col1_1 + col1_0) ASC) STORING (col1_1),
UNIQUE (col1_0 ASC) WHERE table1.col1_1 > (-1.0):::FLOAT8
);
ALTER TABLE table1 INJECT STATISTICS '[{"avg_size": 4, "columns": ["col1_1"], "created_at": "2000-01-01 00:00:00+00:00", "distinct_count": 1319231781637867192, "histo_buckets": [{"distinct_range": 0, "num_eq": 900000, "num_range": 0, "upper_bound": "-0.9022742731095619"}, {"distinct_range": 0, "num_eq": 0, "num_range": 200000000, "upper_bound": "-0.03298270844476303"}, {"distinct_range": 90000000, "num_eq": 800000000, "num_range": 90000000, "upper_bound": "0.1759378487060853"}, {"distinct_range": 8000000000, "num_eq": 2493550396308236629, "num_range": 8000000000, "upper_bound": "1.0648625381898507"}], "histo_col_type": "FLOAT8", "name": "__auto__", "null_count": 0, "row_count": 5164449749148844825}, {"avg_size": 5, "columns": ["col1_0"], "created_at": "2000-01-01 00:00:00+00:00", "distinct_count": 2103359280294413962, "histo_buckets": [{"distinct_range": 0, "num_eq": 40, "num_range": 0, "upper_bound": "-1.143144685560062"}, {"distinct_range": 1000000, "num_eq": 6858931304526079805, "num_range": 1000000, "upper_bound": "1.4729149128589558"}], "histo_col_type": "FLOAT8", "name": "__auto__", "null_count": 0, "row_count": 5164449749148844825}]':::JSONB;
SET unconstrained_non_covering_index_scan_enabled = true;
INSERT INTO table1 AS tab_841 (col1_0, col1_1)
VALUES (1.2345678901234566e-49:::FLOAT8, 0.5956640437568941:::FLOAT8);
INSERT INTO table1 AS tab_842 (col1_0, col1_1)
VALUES (1.2345678901234566e-20:::FLOAT8, 1.2345678901234557e+48:::FLOAT8);
UPDATE table1 AS tab_845 SET col1_1 = tab_845.col1_0 WHERE true ORDER BY tab_845.col1_0 LIMIT 20:::INT8;
INSERT INTO table1 AS tab_866 (col1_0, col1_1)
VALUES (1.7976931348623157e+308:::FLOAT8, 1.2345678901234566e-20:::FLOAT8);
SELECT 1
FROM
table1 AS tab_27922
RIGHT JOIN table1 AS tab_27923 ON
(tab_27922.col1_1) = (tab_27923.col1_1)
AND (tab_27922.crdb_internal_mvcc_timestamp) >= (tab_27923.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27923.col1_0)
JOIN table1 AS tab_27924 ON
(tab_27923.col1_0) = (tab_27924.col1_0) AND (tab_27923.col1_1) = (tab_27924.col1_0)
JOIN table1 AS tab_27925 ON
(tab_27923.col1_0) = (tab_27925.col1_0)
AND (tab_27924.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27925.col1_0)
AND (tab_27922.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27924.col1_0) = (tab_27925.col1_0)
AND (tab_27924.col1_1) = (tab_27925.col1_1)
JOIN table1 AS tab_27926 ON
AND (tab_27924.col1_1) = (tab_27926.col1_0)
AND (tab_27924.col1_0) = (tab_27926.col1_0);
SET testing_optimizer_random_seed = 2758112374651167630;
SET testing_optimizer_cost_perturbation = 1.0;
SELECT 1
FROM
table1 AS tab_27922
RIGHT JOIN table1 AS tab_27923 ON
(tab_27922.col1_1) = (tab_27923.col1_1)
AND (tab_27922.crdb_internal_mvcc_timestamp) >= (tab_27923.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27923.col1_0)
JOIN table1 AS tab_27924 ON
(tab_27923.col1_0) = (tab_27924.col1_0) AND (tab_27923.col1_1) = (tab_27924.col1_0)
JOIN table1 AS tab_27925 ON
(tab_27923.col1_0) = (tab_27925.col1_0)
AND (tab_27924.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27925.col1_0)
AND (tab_27922.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27924.col1_0) = (tab_27925.col1_0)
AND (tab_27924.col1_1) = (tab_27925.col1_1)
JOIN table1 AS tab_27926 ON
AND (tab_27924.col1_1) = (tab_27926.col1_0)
AND (tab_27924.col1_0) = (tab_27926.col1_0); |
|
Reduced a bit more below. I'm trying to figure out if the joins can be reduced or not... CREATE TABLE table1 (
col1_0 INT PRIMARY KEY,
col1_1 INT NOT NULL,
INDEX (col1_1 DESC),
UNIQUE ((col1_1 + col1_0) ASC) STORING (col1_1)
);
ALTER TABLE table1 INJECT STATISTICS '[{"columns": ["col1_1"], "created_at": "2000-01-01 00:00:00+00:00", "distinct_count": 999999999, "name": "__auto__", "null_count": 0, "row_count": 999999999999}]':::JSONB;
SET unconstrained_non_covering_index_scan_enabled = true;
INSERT INTO table1 AS tab_841 (col1_0, col1_1) VALUES (1, 1), (3, 3);
INSERT INTO table1 AS tab_866 (col1_0, col1_1) VALUES (5, 3);
SELECT 1
FROM
table1 AS tab_27922
RIGHT JOIN table1 AS tab_27923 ON
(tab_27922.col1_1) = (tab_27923.col1_1)
AND (tab_27922.crdb_internal_mvcc_timestamp) >= (tab_27923.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27923.col1_0)
JOIN table1 AS tab_27924 ON
(tab_27923.col1_0) = (tab_27924.col1_0) AND (tab_27923.col1_1) = (tab_27924.col1_0)
JOIN table1 AS tab_27925 ON
(tab_27923.col1_0) = (tab_27925.col1_0)
AND (tab_27924.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27925.col1_0)
AND (tab_27922.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27924.col1_0) = (tab_27925.col1_0)
AND (tab_27924.col1_1) = (tab_27925.col1_1)
JOIN table1 AS tab_27926 ON
(tab_27925.col1_0) = (tab_27926.col1_1)
AND (tab_27924.col1_1) = (tab_27926.col1_0)
AND (tab_27924.col1_0) = (tab_27926.col1_0);
SET testing_optimizer_random_seed = 2758112374651167630;
SET testing_optimizer_cost_perturbation = 1.0;
SELECT 1
FROM
table1 AS tab_27922
RIGHT JOIN table1 AS tab_27923 ON
(tab_27922.col1_1) = (tab_27923.col1_1)
AND (tab_27922.crdb_internal_mvcc_timestamp) >= (tab_27923.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27923.col1_0)
JOIN table1 AS tab_27924 ON
(tab_27923.col1_0) = (tab_27924.col1_0) AND (tab_27923.col1_1) = (tab_27924.col1_0)
JOIN table1 AS tab_27925 ON
(tab_27923.col1_0) = (tab_27925.col1_0)
AND (tab_27924.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27922.col1_1) = (tab_27925.col1_0)
AND (tab_27922.crdb_internal_mvcc_timestamp) = (tab_27925.crdb_internal_mvcc_timestamp)
AND (tab_27924.col1_0) = (tab_27925.col1_0)
AND (tab_27924.col1_1) = (tab_27925.col1_1)
JOIN table1 AS tab_27926 ON
(tab_27925.col1_0) = (tab_27926.col1_1)
AND (tab_27924.col1_1) = (tab_27926.col1_0)
AND (tab_27924.col1_0) = (tab_27926.col1_0); |
This comment was marked as duplicate.
This comment was marked as duplicate.
|
I'm having trouble reducing it further. Updating the queries to: CREATE TABLE t (
a INT PRIMARY KEY,
b INT NOT NULL,
c INT,
INDEX idx (b DESC),
UNIQUE INDEX uniq ((b + a) ASC) STORING (b),
FAMILY (a, b)
);
ALTER TABLE t INJECT STATISTICS '[{"columns": ["b"], "created_at": "2000-01-01 00:00:00+00:00", "distinct_count": 999999999, "name": "__auto__", "null_count": 0, "row_count": 999999999999}]':::JSONB;
SET unconstrained_non_covering_index_scan_enabled = true;
INSERT INTO t AS tab_841 (a, b, c) VALUES (1, 1, 0), (3, 3, 0);
INSERT INTO t AS tab_866 (a, b, c) VALUES (5, 3, 100000);
SELECT 1, t0.a, t0.crdb_internal_mvcc_timestamp, t2.a, t2.crdb_internal_mvcc_timestamp, t3.a, t3.crdb_internal_mvcc_timestamp
FROM
t AS t0
RIGHT JOIN t AS t1 ON
(t0.c) >= (t1.c)
JOIN t AS t2 ON
(t1.b) = (t2.a)
JOIN t AS t3 ON
(t1.a) = (t3.a)
AND (t2.crdb_internal_mvcc_timestamp) = (t3.crdb_internal_mvcc_timestamp)
AND (t0.b) = (t3.a)
AND (t0.crdb_internal_mvcc_timestamp) = (t3.crdb_internal_mvcc_timestamp)
AND (t2.a) = (t3.a)
AND (t2.b) = (t3.b)
JOIN t AS t4 ON
(t3.a) = (t4.b)
AND (t2.b) = (t4.a)
AND (t2.a) = (t4.a);
SET testing_optimizer_random_seed = 2758112374651167630;
SET testing_optimizer_cost_perturbation = 1.0;
SELECT 1, t0.a, t0.crdb_internal_mvcc_timestamp, t2.a, t2.crdb_internal_mvcc_timestamp, t3.a, t3.crdb_internal_mvcc_timestamp
FROM
t AS t0
RIGHT JOIN t AS t1 ON
(t0.c) >= (t1.c)
JOIN t AS t2 ON
(t1.b) = (t2.a)
JOIN t AS t3 ON
(t1.a) = (t3.a)
AND (t2.crdb_internal_mvcc_timestamp) = (t3.crdb_internal_mvcc_timestamp)
AND (t0.b) = (t3.a)
AND (t0.crdb_internal_mvcc_timestamp) = (t3.crdb_internal_mvcc_timestamp)
AND (t2.a) = (t3.a)
AND (t2.b) = (t3.b)
JOIN t AS t4 ON
(t3.a) = (t4.b)
AND (t2.b) = (t4.a)
AND (t2.a) = (t4.a);yields: It looks like the latter result is incorrect. All three of the The query plan shows that the |
|
Slight reduction by using a DECIMAL column instead of CREATE TABLE t (
a INT PRIMARY KEY,
b INT NOT NULL,
c DECIMAL,
INDEX idx (b DESC),
UNIQUE INDEX uniq ((b + a) ASC) STORING (b),
FAMILY (a, b)
);
ALTER TABLE t INJECT STATISTICS '[{"columns": ["b"], "created_at": "2000-01-01 00:00:00+00:00", "distinct_count": 999999999, "name": "__auto__", "null_count": 0, "row_count": 999999999999}]':::JSONB;
SET unconstrained_non_covering_index_scan_enabled = true;
INSERT INTO t AS tab_841 (a, b, c) VALUES (1, 1, 1.0), (3, 3, 1.0);
INSERT INTO t AS tab_866 (a, b, c) VALUES (5, 3, 3.0);
SELECT 1, t0.a, t0.c, t2.a, t2.c, t3.a, t3.c
FROM
t AS t0
RIGHT JOIN t AS t1 ON
(t0.c) >= (t1.c)
JOIN t AS t2 ON
(t1.b) = (t2.a)
JOIN t AS t3 ON
(t1.a) = (t3.a)
AND (t2.c) = (t3.c)
AND (t0.b) = (t3.a)
AND (t0.c) = (t3.c)
AND (t2.a) = (t3.a)
AND (t2.b) = (t3.b)
JOIN t AS t4 ON
(t3.a) = (t4.b)
AND (t2.b) = (t4.a)
AND (t2.a) = (t4.a);
SET testing_optimizer_random_seed = 2758112374651167630;
SET testing_optimizer_cost_perturbation = 1.0;
SELECT 1, t0.a, t0.c, t2.a, t2.c, t3.a, t3.c
FROM
t AS t0
RIGHT JOIN t AS t1 ON
(t0.c) >= (t1.c)
JOIN t AS t2 ON
(t1.b) = (t2.a)
JOIN t AS t3 ON
(t1.a) = (t3.a)
AND (t2.c) = (t3.c)
AND (t0.b) = (t3.a)
AND (t0.c) = (t3.c)
AND (t2.a) = (t3.a)
AND (t2.b) = (t3.b)
JOIN t AS t4 ON
(t3.a) = (t4.b)
AND (t2.b) = (t4.a)
AND (t2.a) = (t4.a); |
|
This might be related to join reordering. I noticed that when reordering the joins, a filter holding This smells a lot like #76522. |
I don't see 3=15 or 3=21 being omitted there, maybe you're missing the 3=21 in the merge join? |
|
I'm getting |
Ok, this problem seems unrelated. The optsteps tool effectively disables all rules once the required number of steps has been reached for an iteration, which the |
|
Something is amiss: |
The change looks ok to me, but it's not a merge join -- is that what you're concerned by? |
Yes, is that expected? |
|
Does seem odd... |
|
Ok, I think I've got it: the joinorderbuilder expects filters to have been pushed down as far as possible in the original join tree, but we aren't doing that for 3=15 in this case. We end up adding a join tree with the 3=15 filter to a group that doesn't have it (but joins the same base relations). |
|
So the filters are missing, correct? Just not in the last example I posted, because I missed them in the merge join. Correct? |
|
Yes. So this is a real bug, not just a testing problem. |
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Sep 27, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up, and expects filters to be pushed down as far as possible at each step. It also reuses the original matched joins when possible, to avoid duplicate work. This could previously cause filters to be dropped in the case when they weren't pushed all the way down. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes cockroachdb#88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan in rare cases.
|
Since this is present on older versions, I'm removing the release blocker label. |
mgartner
removed
release-blocker
yuzefovich
changed the title
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Sep 30, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so wouldn't add it later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially correct. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes cockroachdb#88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases.
craig bot
pushed a commit
that referenced
this issue
Oct 2, 2022
88779: opt: don't add reordered join with extra filters to original memo group r=DrewKimball a=DrewKimball The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so it wouldn't be added later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially the problem fixed by this commit. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes #88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases. Co-authored-by: DrewKimball <[email protected]>
blathers-crl bot
pushed a commit
that referenced
this issue
Oct 2, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so it wouldn't be added later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially the problem fixed by this commit. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes #88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases.
rytaft
added
S-0-visible-logical-error
blathers-crl bot
pushed a commit
that referenced
this issue
Oct 4, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so it wouldn't be added later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially the problem fixed by this commit. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes #88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases.
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Nov 11, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so it wouldn't be added later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially the problem fixed by this commit. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes cockroachdb#88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases.
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Nov 17, 2022
The `JoinOrderBuilder` builds reordered join plans from the bottom up. It expects filters to be pushed down as far as possible at each step, and that transitive closure has been calculated over Inner Join equality filters (e.g. `a=b` and `b=c` => `a=c`). It also reuses the original matched joins when possible to avoid duplicate work by adding to the original memo groups. This could previously cause filters to be dropped in the case when the original join tree did not compute transitive closure and push filters down as far as possible. More specifically, the `JoinOrderBuilder` could add new reordered joins with new filters synthesized and pushed down as far as possible to an original memo group that didn't have one of those filters. Subsequent joins would then expect the filter to be part of the memo group, and so it wouldn't be added later on in the plan. In the rare case when the expression without the filter was chosen, this could manifest as a dropped filter in the final plan. This was rare because dropping a filter usually does not produce a lower-cost plan. As an example, take this original join tree: ``` (xy join ab on true) join uv on x = u and a = u; ``` Here it is possible to sythesize and push down a `x = a` filter, and so the `JoinOrderBuilder` would do this and add it to the group: ``` group (xy join ab on true), (xy join ab on x = a) ``` Later joins would use this group as an input, an expect the `x = a` filter to be present. If costing happened to choose the first expression in the group, we would end up choosing a plan like this: ``` (xy join ab on true) join uv on x = u ``` Where the `a = u` filter isn't included in the top-level join because it would be redundant to add it when `x = u` and `x = a` are already present. This is a bit of a simplification, but is essentially the problem fixed by this commit. This commit adds a check to the `JoinOrderBuilder` to identify cases where filters (including ones sythesized from the transitive closure) weren't pushed all the way down in the original join tree. When this is true, none of the originally matched joins can be reused when reordered joins are built except for the root join. This solution may perform some duplicate work when filters aren't pushed down, but it shouldn't matter because this case is rare (and should be avoided whenever possible). Fixes cockroachdb#88659 Release note (bug fix): Fixed a bug introduced in 20.2 that could cause filters to be dropped from a query plan with many joins in rare cases.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
roachtest.costfuzz failed with artifacts on master @ 89f4ad907a1756551bd6864c3e8516eeff6b0e0a:
Parameters:
ROACHTEST_cloud=gce,ROACHTEST_cpu=4,ROACHTEST_encrypted=false,ROACHTEST_ssd=0Help
See: roachtest README
See: How To Investigate (internal)
Same failure on other branches
This test on roachdash | Improve this report!
Jira issue: CRDB-19846
The text was updated successfully, but these errors were encountered: