Late Materialization Optimizer by Mytherin · Pull Request #15692 · duckdb/duckdb

Mytherin · 2025-01-13T15:58:16Z

This PR adds the Late Materialization optimizer that enables late materialization for certain queries - in particular top-n (ORDER BY .. LIMIT ..), limit + offset, and sample queries. The optimization piggy-backs off of the row-id filter pushdown introduced in #15020 - and does the row-id rewrites mentioned there automatically.

Rewrites

Here are some examples of rewrites:

Top-N

SELECT * FROM lineitem ORDER BY l_extendedprice DESC LIMIT 5;

-- becomes

SELECT * FROM lineitem WHERE rowid IN (
    SELECT rowid FROM lineitem ORDER BY l_extendedprice DESC LIMIT 5)
ORDER BY l_extendedprice DESC;

Limit + Offset

SELECT * FROM lineitem LIMIT 1000000 OFFSET 10000000;

-- becomes


SELECT * FROM lineitem WHERE rowid IN (
    SELECT rowid FROM lineitem LIMIT 1000000 OFFSET 10000000)
ORDER BY rowid;

Performance

SELECT * FROM lineitem ORDER BY l_extendedprice DESC LIMIT 5;

v1.1.3	main	new
2.1s	0.07s	0.01s

SELECT * FROM lineitem ORDER BY l_orderkey DESC LIMIT 5;

v1.1.3	main	new
10.2s	2.8s	0.14s

SELECT * FROM lineitem LIMIT 1000000 OFFSET 10000000;

v1.1.3	main	new
0.46s	0.46s	0.07s

…sformed plan is maintained

…n running the optimizer multiple times over the same path

… table index

…for complex expressions in the Top-N)

abramk · 2025-01-13T17:33:43Z

@Mytherin I tried your PR against the following and am not seeing a speed up.

 create table tbl1(pk LONG PRIMARY KEY,
        col_long_text VARCHAR,
        col_long_text_2 VARCHAR,
        col_truncated VARCHAR,
        col_sort LONG);

 INSERT INTO tbl1 SELECT
        i AS pk,
        rpad('', 64000, 'A') AS col_long_text,
        rpad('', 64000, 'B') AS col_long_text_2,
        rpad('', 4000, 'A') AS col_truncated,
        floor(random() * 9223372036854775807)::long AS col_sort FROM generate_series(1, 50000) s(i);

I then run this query:

 select * from tbl1 order by pk desc limit 1000;

and it takes 1.477 s but when I run the transformed version manually:

select * from tbl1 where rowid in (select rowid from tbl1 order by pk desc limit 1000);

I see it takes 155ms.

I think I have your PR compiled correctly as PRAGMA profiling_mode = 'detailed' shows:

┌────────────────────────────────────────────────┐
│               Optimizer: 0.0002s               │
│┌──────────────────────────────────────────────┐│
││        Build Side Probe Side: 0.0000s        ││
││           Column Lifetime: 0.0000s           ││
││           Common Aggregate: 0.0000s          ││
││        Common Subexpressions: 0.0000s        ││
││      Compressed Materialization: 0.0000s     ││
││          Cte Filter Pusher: 0.0000s          ││
││             Deliminator: 0.0000s             ││
││           Duplicate Groups: 0.0000s          ││
││         Empty Result Pullup: 0.0000s         ││
││         Expression Rewriter: 0.0000s         ││
││              Extension: 0.0000s              ││
││            Filter Pullup: 0.0000s            ││
││           Filter Pushdown: 0.0000s           ││
││              In Clause: 0.0000s              ││
││         Join Filter Pushdown: 0.0000s        ││
││              Join Order: 0.0000s             ││
││         Late Materialization: 0.0000s        ││
││            Limit Pushdown: 0.0000s           ││
││           Materialized Cte: 0.0000s          ││
││             Regex Range: 0.0000s             ││
││            Reorder Filter: 0.0000s           ││
││          Sampling Pushdown: 0.0000s          ││
││        Statistics Propagation: 0.0000s       ││
││             Sum Rewriter: 0.0000s            ││
││                Top N: 0.0000s                ││
││           Unnest Rewriter: 0.0000s           ││
││            Unused Columns: 0.0000s           ││
│└──────────────────────────────────────────────┘│
└────────────────────────────────────────────────┘

You can see the Late Materialization filter in the list.

Mytherin · 2025-01-13T17:42:28Z

That's because of the limit size. The late materialization optimizer only triggers when the limit is <= 50 at this point (see max_row_count in the code). I can make this configurable in a follow-up PR.

carlopi · 2025-01-14T08:26:50Z

Minor, also to be done on as subsequent PR, there are 3 warnings turned errors in the amalgamation run (OSX Debug):

-----------------------
-- Writing src/amalgamation/duckdb.hpp --
-----------------------
------------------------
-- Writing src/amalgamation/duckdb.cpp --
------------------------
duckdb.cpp:253075:11: error: redundant move in return statement [-Werror,-Wredundant-move]
                        return std::move(op);
                               ^
duckdb.cpp:253075:11: note: remove std::move call here
                        return std::move(op);
                               ^~~~~~~~~~  ~
duckdb.cpp:2[53](https://github.com/Mytherin/duckdb/actions/runs/12753535210/job/35545445957#step:10:54)086:11: error: redundant move in return statement [-Werror,-Wredundant-move]
                        return std::move(op);
                               ^
duckdb.cpp:253086:11: note: remove std::move call here
                        return std::move(op);
                               ^~~~~~~~~~  ~
duckdb.cpp:253099:11: error: redundant move in return statement [-Werror,-Wredundant-move]
                        return std::move(op);
                               ^
duckdb.cpp:253099:11: note: remove std::move call here
                        return std::move(op);
                               ^~~~~~~~~~  ~
3 errors generated.

@abramk

…e the threshold at which late materialization is triggered (#15697) Follow-up from #15692 This PR adds the `late_materialization_max_rows` setting that allows you to configure the threshold at which late materialization is triggered. The default value is `50`. Example usage: ```sql SET late_materialization_max_rows=1000; explain SELECT * FROM lineitem ORDER BY l_orderkey DESC LIMIT 1000; ``` The exact best setting is hard to determine - essentially the row-id pushdown has two components to it (1) the OR filter push-down, which is done for up to `dynamic_or_filter_threshold` rows (defaults to 50) and the min-max filter pushdown. The row-id rewrite generally always provides performance improvements for up to `dynamic_or_filter_threshold` which is why we select that as a default. Beyond that, it depends on the locality of the rows. If the min-max filter on row-ids is selective (i.e. the rows we select are close together physically in the table) the row-id rewrite is effective. If the rows are spread out, the rewrite can worsen performance. CC @abramk

Late Materialization Optimizer (duckdb/duckdb#15692) Clean up temporary test directory in `run_tests_one_by_one.py` even if test segfaults (duckdb/duckdb#15688) Reduce test size so CI is less likely to fail (duckdb/duckdb#15689)

YuweiXiao · 2025-02-06T03:59:09Z

hey! wondering if this optimization applies for non-duckdb table, e.g., a delta lake table. Thanks!

…(*)` directly in the multi file reader (#17325) This PR generalizes the late materialization optimizer introduced in #15692 - allowing it to be used for the Parquet reader. In particular, the `TableFunction` is extended with an extra callback that allows specifying the relevant row-id columns: ```cpp typedef vector<column_t> (*table_function_get_row_id_columns)(ClientContext &context, optional_ptr<FunctionData> bind_data); ``` This is then used by the Parquet reader to specify the two row-id columns: `file_index` (#17144) and `file_row_number` (#16979). Top-N , sample and limit/offset queries are then transformed into a join on the relevant row-id columns. For example: ```sql SELECT * FROM lineitem.parquet ORDER BY l_extendedprice DESC LIMIT 5; -- becomes SELECT * FROM lineitem.parquet WHERE (file_index, file_row_number) IN ( SELECT file_index, file_row_number FROM lineitem.parquet ORDER BY l_extendedprice DESC LIMIT 5) ORDER BY l_extendedprice DESC; ``` ### Performance ```sql SELECT * FROM lineitem.parquet ORDER BY l_extendedprice DESC LIMIT 5; ``` | v1.2.1 | main | new | |--------|--------|--------| | 0.19s | 0.14s | 0.06s | ```sql SELECT * FROM lineitem.parquet ORDER BY l_orderkey DESC LIMIT 5; ``` | v1.2.1 | main | new | |--------|-------|-------| | 0.73s | 0.53s | 0.06s | ```sql SELECT * FROM lineitem.parquet LIMIT 1000000 OFFSET 10000000; ``` | v1.2.1 | main | new | |--------|-------|-------| | 1.6s | 1.2s | 0.14s | ### Refactor I've also moved the `ParquetMultiFileInfo` to a separate file as part of this PR - which is most of the changes here.

Mytherin added 20 commits December 14, 2024 13:24

WIP: Late materialization optimizer

d275050

WIP late materialization optimizer

d14c976

Merge branch 'main' into latematerialization

21f4e39

Initial optimizer construction sort of working

3ac73c4

Rewrite references on LHS, mostly working

8988d8f

Late materialization - ensure the table index at the root of the tran…

22c2112

…sformed plan is maintained

Enable the actual column pruning

c6b451b

Remove unused columns - clear projection ids to prevent conflicts whe…

55c5a7b

…n running the optimizer multiple times over the same path

Scan into correct vector in row group filter pushdown of row id

fd27012

We need to replace the top-level table index, not necessarily the get…

a64be6d

… table index

Limit late materialization to direct projections for now (no support …

58f09da

…for complex expressions in the Top-N)

Generate enum

812a21f

Merge branch 'main' into latematerialization

9533e5f

Merge conflict

4f80210

Late materialization working with expressions

3d3ef49

Add missing includes

bd6e3e6

Another test + format fix

1ae01c7

Tidy fixes

9de1a94

Use row-id pushdown for limit + offset as well

6d9a657

Disable optimizer for this test

ba0232b

duckdb-draftbot marked this pull request as draft January 13, 2025 16:48

Mytherin marked this pull request as ready for review January 13, 2025 17:09

Only perform late materialization for DuckDB tables currently

ce1635c

duckdb-draftbot marked this pull request as draft January 13, 2025 18:20

Mytherin marked this pull request as ready for review January 13, 2025 18:20

Mytherin merged commit 2a1d5e2 into duckdb:main Jan 14, 2025

Mytherin mentioned this pull request Jan 14, 2025

Add late_materialization_max_rows setting that allows you to configure the threshold at which late materialization is triggered #15697

Merged

Mytherin deleted the latematerialization branch January 16, 2025 16:53

Mytherin mentioned this pull request May 1, 2025

Support late materialization in the Parquet reader, and handle COUNT(*) directly in the multi file reader #17325

Merged

zhuqi-lucas mentioned this pull request Jul 7, 2026

Late materialization when LIMIT prunes heavily. apache/datafusion#23263

Closed

Navigation Menu

Repository navigation

Late Materialization Optimizer - #15692

Late Materialization Optimizer#15692
Mytherin merged 21 commits into
duckdb:mainfrom
Mytherin:latematerialization

Mytherin commented Jan 13, 2025

Uh oh!

abramk commented Jan 13, 2025

Uh oh!

Mytherin commented Jan 13, 2025

Uh oh!

carlopi commented Jan 14, 2025

Uh oh!

YuweiXiao commented Feb 6, 2025

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

Mytherin commented Jan 13, 2025

Rewrites

Top-N

Limit + Offset

Performance

Uh oh!

abramk commented Jan 13, 2025

Uh oh!

Mytherin commented Jan 13, 2025

Uh oh!

carlopi commented Jan 14, 2025

Uh oh!

YuweiXiao commented Feb 6, 2025

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants