cockroachdb / cockroachdb/cockroach

opt: suboptimal generic query plans for queries with conditional equality filters

Open
#154,134 6 comments 1 reaction 1 assignee Claimed by @ZhouXing19 View on GitHub
A-generic-query-plans C-enhancement O-support P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

The optimizer may choose a generic query plan that is less optimal than its custom counterpart when a query conditionally filters a column with an equality. Below is an example.

```sql
CREATE TABLE t (
k INT PRIMARY KEY,
a INT,
b INT,
c INT,
INDEX (a, b, c)
);

PREPARE p AS
SELECT k FROM t WHERE a = $1 AND b = $2 AND
CASE WHEN $2 > 0 THEN c = $3 ELSE true END;

EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
-- info
-- --------------------------------------------
-- distribution: local
-- vectorized: true
-- plan type: custom
--
-- • scan
-- table: t@t_a_b_c_idx
-- spans: [/1/2/3 - /1/2/3]

-- Run the query 5 more times to get the generic query plan, which is only
-- attempted after 5 runs of custom plans.
EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
EXPLAIN ANALYZE EXECUTE p(1, 2, 3);
-- info
-- ----------------------------------------------------------
-- distribution: local
-- vectorized: true
-- plan type: generic, re-optimized
--
-- • lookup join
-- │ table: t@t_a_b_c_idx
-- │ equality: ($1, $2) = (a, b)
-- │ pred: CASE WHEN "$2" > 0 THEN c = "$3" ELSE true END
-- │
-- └── • values
-- size: 3 columns, 1 row
```

In the generic query plan, the `CASE` expression cannot be folded to `c = $3` or `true` at optimization-time because `$2 > 0` cannot be evaluated. So the `CASE` expression is applied after the look-ups in the lookup join, meaning that the generic query plan may fetch more rows than the custom query plan.

## Work-arounds

The known work-arounds for this issue are:

1. Disabling generic query plans with `SET plan_cache_mode=force_custom_plan`.
2. "Pulling" the `CASE` expression into application code by splitting it into a different query for each branch, and having the application dynamically pick the query to use. In the example above, the two new queries would be `SELECT k FROM t WHERE a = $1 AND b = $2 AND c = $3` and `SELECT k FROM t WHERE a = $1 AND b = $2`.

## Possible Solutions

A couple possible solutions come to mind:

1. As a quick fix for this specific issue, we could avoid choosing the generic query plan if its lookup join uses the same index as the custom plan's scan, but has fewer constrained columns. This wouldn't apply to a more general case, however, I don't yet know if there _is_ a more general case of this issue, so maybe this would be sufficient.
2. Allow the lookup join to craft a more constrained lookup span from `pred` if it can be partially evaluated. The generic query plan would remain more-or-less the same, and at execbuild-time or during lookup join execution we'd try to build a better lookup span.
3. Optimizing a generic query plan for each branch of the `CASE` and conditionally selecting the correct one at execution-time.

Jira issue: CRDB-54750

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.