More `CommonSubplanOptimizer` improvements by lnkuiper · Pull Request #20168 · duckdb/duckdb

lnkuiper · 2025-12-12T12:24:55Z

This PR improves the CommonSubplanOptimizer, and should put it in "maintenance mode", at least for now, and I think I'm done improving it for a while.

Multiple Nested Matching

This PR allows multiple subplans to be matched, rather than just a single subplan, and allows nesting. Take the following query, for example:

explain
select distinct range from range(10)
union all
select distinct range from range(10)
union all
select range % 2 as range from (select distinct range from range(10)) group by range
union all
select range % 2 as range from (select distinct range from range(10)) group by range
union all
select count(*) from (select range % 2 as range from (select distinct range from range(10)) group by range)
union all
select count(*) from (select range % 2 as range from (select distinct range from range(10)) group by range);

This query unions 6 queries together. Each query occurs twice, and is nested in the next query. With the optimizer disabled, this yields the following plan:

┌───────────────────────────┐
│           UNION           ├──────────────┬────────────────────────────┬────────────────────────────┬────────────────────────────┬────────────────────────────┐
└─────────────┬─────────────┘              │                            │                            │                            │                            │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│       HASH_GROUP_BY       ││       HASH_GROUP_BY       ││         PROJECTION        ││         PROJECTION        ││    UNGROUPED_AGGREGATE    ││    UNGROUPED_AGGREGATE    │
│    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
│         Groups: #0        ││         Groups: #0        ││           range           ││           range           ││        Aggregates:        ││        Aggregates:        │
│                           ││                           ││                           ││                           ││        count_star()       ││        count_star()       │
│          ~10 rows         ││          ~10 rows         ││          ~6 rows          ││          ~6 rows          ││                           ││                           │
└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         PROJECTION        ││         PROJECTION        ││       HASH_GROUP_BY       ││       HASH_GROUP_BY       ││         PROJECTION        ││         PROJECTION        │
│    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
│           range           ││           range           ││         Groups: #0        ││         Groups: #0        ││             42            ││             42            │
│                           ││                           ││                           ││                           ││                           ││                           │
│          ~10 rows         ││          ~10 rows         ││          ~6 rows          ││          ~6 rows          ││          ~6 rows          ││          ~6 rows          │
└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│           RANGE           ││           RANGE           ││         PROJECTION        ││         PROJECTION        ││       HASH_GROUP_BY       ││       HASH_GROUP_BY       │
│    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
│      Function: RANGE      ││      Function: RANGE      ││           range           ││           range           ││         Groups: #0        ││         Groups: #0        │
│                           ││                           ││                           ││                           ││                           ││                           │
│          ~10 rows         ││          ~10 rows         ││          ~10 rows         ││          ~10 rows         ││          ~6 rows          ││          ~6 rows          │
└───────────────────────────┘└───────────────────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
                                                          ┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                          │       HASH_GROUP_BY       ││       HASH_GROUP_BY       ││         PROJECTION        ││         PROJECTION        │
                                                          │    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
                                                          │         Groups: #0        ││         Groups: #0        ││           range           ││           range           │
                                                          │                           ││                           ││                           ││                           │
                                                          │          ~10 rows         ││          ~10 rows         ││          ~10 rows         ││          ~10 rows         │
                                                          └─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
                                                          ┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                          │         PROJECTION        ││         PROJECTION        ││       HASH_GROUP_BY       ││       HASH_GROUP_BY       │
                                                          │    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
                                                          │           range           ││           range           ││         Groups: #0        ││         Groups: #0        │
                                                          │                           ││                           ││                           ││                           │
                                                          │          ~10 rows         ││          ~10 rows         ││          ~10 rows         ││          ~10 rows         │
                                                          └─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
                                                          ┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                          │           RANGE           ││           RANGE           ││         PROJECTION        ││         PROJECTION        │
                                                          │    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
                                                          │      Function: RANGE      ││      Function: RANGE      ││           range           ││           range           │
                                                          │                           ││                           ││                           ││                           │
                                                          │          ~10 rows         ││          ~10 rows         ││          ~10 rows         ││          ~10 rows         │
                                                          └───────────────────────────┘└───────────────────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
                                                                                                                    ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                                                                                    │           RANGE           ││           RANGE           │
                                                                                                                    │    ────────────────────   ││    ────────────────────   │
                                                                                                                    │      Function: RANGE      ││      Function: RANGE      │
                                                                                                                    │                           ││                           │
                                                                                                                    │          ~10 rows         ││          ~10 rows         │
                                                                                                                    └───────────────────────────┘└───────────────────────────┘

As we can see, there is a lot of redundance here. With this PR (and the optimizer enabled, of course), we get the following plan:

┌───────────────────────┐
│          CTE          │
│    ────────────────   │
│       CTE Name:       │
│   __common_subplan_1  │
│                       ├────────────┐
│    Table Index: 79    │            │
│                       │            │
│        ~0 rows        │            │
└───────────┬───────────┘            │
┌───────────┴───────────┐┌───────────┴───────────┐
│     HASH_GROUP_BY     ││          CTE          │
│    ────────────────   ││    ────────────────   │
│       Groups: #0      ││       CTE Name:       │
│                       ││   __common_subplan_2  │
│                       ││                       ├────────────┐
│                       ││    Table Index: 86    │            │
│                       ││                       │            │
│        ~10 rows       ││        ~0 rows        │            │
└───────────┬───────────┘└───────────┬───────────┘            │
┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐
│       PROJECTION      ││     HASH_GROUP_BY     ││          CTE          │
│    ────────────────   ││    ────────────────   ││    ────────────────   │
│         range         ││       Groups: #0      ││       CTE Name:       │
│                       ││                       ││   __common_subplan_3  │
│                       ││                       ││                       ├────────────┐
│                       ││                       ││    Table Index: 91    │            │
│                       ││                       ││                       │            │
│        ~10 rows       ││        ~6 rows        ││        ~0 rows        │            │
└───────────┬───────────┘└───────────┬───────────┘└───────────┬───────────┘            │
┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐
│         RANGE         ││       PROJECTION      ││  UNGROUPED_AGGREGATE  ││         UNION         │
│    ────────────────   ││    ────────────────   ││    ────────────────   ││                       │
│    Function: RANGE    ││         range         ││      Aggregates:      ││                       ├────────────┬────────────────────────┬────────────────────────┬────────────────────────┬────────────────────────┐
│                       ││                       ││      count_star()     ││                       │            │                        │                        │                        │                        │
│        ~10 rows       ││        ~10 rows       ││                       ││                       │            │                        │                        │                        │                        │
└───────────────────────┘└───────────┬───────────┘└───────────┬───────────┘└───────────┬───────────┘            │                        │                        │                        │                        │
                         ┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐┌───────────┴───────────┐
                         │        CTE_SCAN       ││       PROJECTION      ││        CTE_SCAN       ││        CTE_SCAN       ││       PROJECTION      ││       PROJECTION      ││        CTE_SCAN       ││        CTE_SCAN       │
                         │    ────────────────   ││    ────────────────   ││    ────────────────   ││    ────────────────   ││    ────────────────   ││    ────────────────   ││    ────────────────   ││    ────────────────   │
                         │     CTE Index: 79     ││           42          ││     CTE Index: 79     ││     CTE Index: 79     ││         range         ││         range         ││     CTE Index: 91     ││     CTE Index: 91     │
                         │                       ││                       ││                       ││                       ││                       ││                       ││                       ││                       │
                         │        ~10 rows       ││        ~6 rows        ││        ~10 rows       ││        ~10 rows       ││        ~6 rows        ││        ~6 rows        ││         ~1 row        ││         ~1 row        │
                         └───────────────────────┘└───────────┬───────────┘└───────────────────────┘└───────────────────────┘└───────────┬───────────┘└───────────┬───────────┘└───────────────────────┘└───────────────────────┘
                                                  ┌───────────┴───────────┐                                                  ┌───────────┴───────────┐┌───────────┴───────────┐
                                                  │        CTE_SCAN       │                                                  │        CTE_SCAN       ││        CTE_SCAN       │
                                                  │    ────────────────   │                                                  │    ────────────────   ││    ────────────────   │
                                                  │     CTE Index: 86     │                                                  │     CTE Index: 86     ││     CTE Index: 86     │
                                                  │                       │                                                  │                       ││                       │
                                                  │        ~6 rows        │                                                  │        ~6 rows        ││        ~6 rows        │
                                                  └───────────────────────┘                                                  └───────────────────────┘└───────────────────────┘

Which has 3 CTEs, 8 CTE scans, and only 3 aggregations (instead of the original 12!).

Fuzzy Plan Matching

Something that can show up in query plans is an "almost" exact subplan match. Before this PR, an exact match was required. With this PR, we can do "fuzzy" matching, where the plan is mostly the same, save for some selected columns. If we have the following query, for example:

-- Create build table
create table build as
select range a, range * 2 b, range * 3 c, range * 4 d
from (select range::utinyint as range from range(11))
where range % 5 = 0;
-- Create probe table
create table probe as
select range e, range * 2 f, range * 3 g, range * 4 h
from (select range::utinyint as range from range(11));
-- View that joins the two
create view my_view as
from probe join build on (build.a = probe.e);
-- Select greatest of all columns, unioned with greatest of just two columns
explain
select greatest(a, b, c, d, e, f, g, h) from my_view
union all
select greatest(b, f) from my_view;

Here, one of the unioned queries selects all columns, and the other selects just two columns. As we can see, the join (coming from the view) in the second query is "contained" in the join in first query, as the first query selects all columns that the second query needs.

We currently get the following plan (the optimizer doesn't trigger):

┌───────────────────────────┐
│           UNION           ├───────────────────────────────────────────┐
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│         PROJECTION        │                             │         PROJECTION        │
│    ────────────────────   │                             │    ────────────────────   │
│ greatest(a, b, c, d, e, f,│                             │       greatest(b, f)      │
│            g, h)          │                             │                           │
│                           │                             │                           │
│          ~3 rows          │                             │          ~3 rows          │
└─────────────┬─────────────┘                             └─────────────┬─────────────┘
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│         PROJECTION        │                             │         HASH_JOIN         │
│    ────────────────────   │                             │    ────────────────────   │
│             e             │                             │      Join Type: INNER     │
│             f             │                             │     Conditions: e = a     │
│             g             │                             │                           │
│             h             │                             │                           │
│             a             │                             │                           ├──────────────┐
│             b             │                             │                           │              │
│             c             │                             │                           │              │
│             d             │                             │                           │              │
│                           │                             │                           │              │
│          ~3 rows          │                             │          ~3 rows          │              │
└─────────────┬─────────────┘                             └─────────────┬─────────────┘              │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         HASH_JOIN         │                             │         SEQ_SCAN          ││         SEQ_SCAN          │
│    ────────────────────   │                             │    ────────────────────   ││    ────────────────────   │
│      Join Type: INNER     │                             │        Table: probe       ││        Table: build       │
│     Conditions: e = a     │                             │   Type: Sequential Scan   ││   Type: Sequential Scan   │
│                           │                             │                           ││                           │
│                           ├──────────────┐              │        Projections:       ││        Projections:       │
│                           │              │              │             e             ││             a             │
│                           │              │              │             f             ││             b             │
│                           │              │              │                           ││                           │
│          ~3 rows          │              │              │          ~11 rows         ││          ~3 rows          │
└─────────────┬─────────────┘              │              └───────────────────────────┘└───────────────────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││         SEQ_SCAN          │
│    ────────────────────   ││    ────────────────────   │
│        Table: probe       ││        Table: build       │
│   Type: Sequential Scan   ││   Type: Sequential Scan   │
│                           ││                           │
│        Projections:       ││        Projections:       │
│             e             ││             a             │
│             f             ││             b             │
│             g             ││             c             │
│             h             ││             d             │
│                           ││                           │
│          ~11 rows         ││          ~3 rows          │
└───────────────────────────┘└───────────────────────────┘

With the improvements to the optimizer in this PR, we now get this plan:

┌───────────────────────────┐
│            CTE            │
│    ────────────────────   │
│         CTE Name:         │
│     __common_subplan_1    │
│                           ├───────────────────────────────────────────┐
│      Table Index: 29      │                                           │
│                           │                                           │
│          ~0 rows          │                                           │
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│         HASH_JOIN         │                             │           UNION           │
│    ────────────────────   │                             │                           │
│      Join Type: INNER     │                             │                           │
│     Conditions: e = a     ├──────────────┐              │                           ├──────────────┐
│                           │              │              │                           │              │
│          ~3 rows          │              │              │                           │              │
└─────────────┬─────────────┘              │              └─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││         SEQ_SCAN          ││         PROJECTION        ││         PROJECTION        │
│    ────────────────────   ││    ────────────────────   ││    ────────────────────   ││    ────────────────────   │
│        Table: probe       ││        Table: build       ││ greatest(a, b, c, d, e, f,││       greatest(b, f)      │
│   Type: Sequential Scan   ││   Type: Sequential Scan   ││            g, h)          ││                           │
│                           ││                           ││                           ││                           │
│        Projections:       ││        Projections:       ││                           ││                           │
│             e             ││             a             ││                           ││                           │
│             f             ││             b             ││                           ││                           │
│             g             ││             c             ││                           ││                           │
│             h             ││             d             ││                           ││                           │
│                           ││                           ││                           ││                           │
│          ~11 rows         ││          ~3 rows          ││          ~3 rows          ││          ~3 rows          │
└───────────────────────────┘└───────────────────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘
                                                          ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                          │         PROJECTION        ││         PROJECTION        │
                                                          │    ────────────────────   ││    ────────────────────   │
                                                          │             e             ││             #1            │
                                                          │             f             ││             #4            │
                                                          │             g             ││                           │
                                                          │             h             ││                           │
                                                          │             a             ││                           │
                                                          │             b             ││                           │
                                                          │             c             ││                           │
                                                          │             d             ││                           │
                                                          │                           ││                           │
                                                          │          ~3 rows          ││          ~0 rows          │
                                                          └─────────────┬─────────────┘└─────────────┬─────────────┘
                                                          ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
                                                          │          CTE_SCAN         ││          CTE_SCAN         │
                                                          │    ────────────────────   ││    ────────────────────   │
                                                          │       CTE Index: 29       ││       CTE Index: 29       │
                                                          │                           ││                           │
                                                          │          ~3 rows          ││          ~3 rows          │
                                                          └───────────────────────────┘└───────────────────────────┘

As we can see, the join is materialized as a CTE, and scanned twice. Columns that aren't needed are projected out after the CTE scan.

Benchmark Improvements

With the changes, we now trigger more subplan elimination on TPC-DS and TPC-H. Here are some results that I collected on my laptop.

TPC-DS SF100 improvements:
Q61: 0.61s -> 0.33s (~1.8x)
Q70: 0.81s -> 0.55s (~1.5x)

TPC-H SF100 improvements:
Q11: 0.16s -> 0.12s (~1.3x)

Notes

I needed a lot of indirection to get the column bindings to match with the fuzzy plan matching, which required a lot of unordered_maps. To avoid doing so many allocations, I've also implemented arena_unordered_map, so that the number of allocations grow logarithmically. I'm not sure how much this helped, but it's just something I wanted to do as we are trying to reduce allocations. Overall, this optimizer now takes ~10% of total optimization time.

…mon subplan optimizer in filter pullup test so it still tests the right behaviour

More `CommonSubplanOptimizer` improvements (duckdb/duckdb#20168)

More `CommonSubplanOptimizer` improvements (duckdb/duckdb#20168) Co-authored-by: krlmlr <krlmlr@users.noreply.github.com>

Laurens Kuiper added 30 commits November 11, 2025 14:16

towards flexible column selection in CommonSubplanOptimizer

5f51f61

temporarily remove projection ids

76406f3

tpc-h q11 fuzzy matching subplan elimination working now

21a7f6f

Merge branch 'main' into common_subplan

10983a4

test slow

70ae481

more robust table index verification for CommonSubplanOptimizer

c16d48c

don't support empty results

04bb2b4

bail out for virtual columns

87fba65

fix virtual columns and projection ids

d5b4729

move this up

eb680ae

Merge branch 'main' into common_subplan

a44ad0a

check for mark join here now that it emits table indices

6c3f9db

merge with main

8fb52b9

Merge branch 'main' into common_subplan

304f759

Merge branch 'main' into common_subplan

0af9e77

robustly take projection maps into account

9722edf

Merge branch 'main' into common_subplan

bd5775f

put subplans together and properly index the max subplan

49c8607

bail on nested subplans

ff89be3

61 also improves apparently

167a3cd

Merge branch 'main' into common_subplan

402e324

handle projection map for more operator types

9131454

convert all subplans to CTEs

2ac2d46

iterate through common subplans in predictable order, and disable com…

b76bdd4

…mon subplan optimizer in filter pullup test so it still tests the right behaviour

better subplan containment check

48e9715

Merge branch 'main' into common_subplan

5be1d24

ensure common subplans are placed in the query plan in the correct order

ffa5b16

Merge branch 'main' into common_subplan

1cddc34

Merge branch 'main' into common_subplan

32e854d

fix cte ordering and indexing

956d84c

Laurens Kuiper added 4 commits December 11, 2025 13:29

Merge branch 'main' into common_subplan

d987cf9

remove rogue loc

68673cb

Merge branch 'main' into common_subplan

5a5c498

last tweaks (i hope)

32bf7de

lnkuiper merged commit c68ff72 into duckdb:main Dec 15, 2025
56 checks passed

lnkuiper deleted the common_subplan branch December 29, 2025 13:09

github-actions bot pushed a commit to duckdb/duckdb-r that referenced this pull request Feb 24, 2026

vendor: Update vendored sources to duckdb/duckdb@c68ff72

d32bc6f

More `CommonSubplanOptimizer` improvements (duckdb/duckdb#20168)

github-actions bot mentioned this pull request Feb 24, 2026

vendor: Update vendored sources to duckdb/duckdb@c68ff72a1c79c115be0b01d8e24cca6f406f0f73 duckdb/duckdb-r#2066

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

More `CommonSubplanOptimizer` improvements#20168

More `CommonSubplanOptimizer` improvements#20168
lnkuiper merged 34 commits intoduckdb:mainfrom
lnkuiper:common_subplan

lnkuiper commented Dec 12, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Conversation

lnkuiper commented Dec 12, 2025

Multiple Nested Matching

Fuzzy Plan Matching

Benchmark Improvements

Notes

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant