Repository navigation
Description
Is your feature request related to a problem or challenge?
Comparing ClickBench on DataFusion 45 and DuckDB (link)
You can see that for 23 DataFusion is almost 2x slower (around 10s where DuckDB is 5s)

You can run this query like this:
cd datafusion
cd benchmarks
# download data
./bench.sh data clickbench_partitioned
# run query with datafusion-cli (note escapes
datafusion-cli -c "SELECT * FROM 'data/hits_partitioned' WHERE \"URL\" LIKE '%google%' ORDER BY \"EventTime\" LIMIT 10;"Here is the explain plan
andrewlamb@Andrews-MacBook-Pro-2:~/Software/datafusion/benchmarks$ datafusion-cli -c "EXPLAIN SELECT * FROM 'data/hits_partitioned' WHERE \"URL\" LIKE '%google%' ORDER BY \"EventTime\" LIMIT 10;"
DataFusion CLI v46.0.0
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type | plan |
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| logical_plan | Sort: data/hits_partitioned.EventTime ASC NULLS LAST, fetch=10 |
| | Filter: CAST(data/hits_partitioned.URL AS Utf8View) LIKE Utf8View("%google%") |
| | TableScan: data/hits_partitioned projection=[WatchID, JavaEnable, Title, GoodEvent, EventTime, EventDate, CounterID, ClientIP, RegionID, UserID, CounterClass, OS, UserAgent, URL, Referer, IsRefresh, RefererCategoryID, RefererRegionID, URLCategoryID, URLRegionID, ResolutionWidth, ResolutionHeight, ResolutionDepth, FlashMajor, FlashMinor, FlashMinor2, NetMajor, NetMinor, UserAgentMajor, UserAgentMinor, CookieEnable, JavascriptEnable, IsMobile, MobilePhone, MobilePhoneModel, Params, IPNetworkID, TraficSourceID, SearchEngineID, SearchPhrase, AdvEngineID, IsArtifical, WindowClientWidth, WindowClientHeight, ClientTimeZone, ClientEventTime, SilverlightVersion1, SilverlightVersion2, SilverlightVersion3, SilverlightVersion4, PageCharset, CodeVersion, IsLink, IsDownload, IsNotBounce, FUniqID, OriginalURL, HID, IsOldCounter, IsEvent, IsParameter, DontCountHits, WithHash, HitColor, LocalEventTime, Age, Sex, Income, Interests, Robotness, RemoteIP, WindowName, OpenerName, HistoryLength, BrowserLanguage, BrowserCountry, SocialNetwork, SocialAction, HTTPError, SendTiming, DNSTiming, ConnectTiming, ResponseStartTiming, ResponseEndTiming, FetchTiming, SocialSourceNetworkID, SocialSourcePage, ParamPrice, ParamOrderID, ParamCurrency, ParamCurrencyID, OpenstatServiceName, OpenstatCampaignID, OpenstatAdID, OpenstatSourceID, UTMSource, UTMMedium, UTMCampaign, UTMContent, UTMTerm, FromTag, HasGCLID, RefererHash, URLHash, CLID], partial_filters=[CAST(data/hits_partitioned.URL AS Utf8View) LIKE Utf8View("%google%")] |
| physical_plan | SortPreservingMergeExec: [EventTime@4 ASC NULLS LAST], fetch=10 |
| | SortExec: TopK(fetch=10), expr=[EventTime@4 ASC NULLS LAST], preserve_partitioning=[true] |
| | CoalesceBatchesExec: target_batch_size=8192 |
| | FilterExec: CAST(URL@13 AS Utf8View) LIKE %google% |
| | DataSourceExec: file_groups={16 groups: [[Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_0.parquet:0..122446530, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_1.parquet:0..174965044, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_10.parquet:0..101513258, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_11.parquet:0..118419888, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_12.parquet:0..149514164, ...], [Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_14.parquet:108113265..151121699, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_15.parquet:0..103098894, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_16.parquet:0..101067219, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_17.parquet:0..116867853, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_18.parquet:0..133119589, ...], [Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_21.parquet:3887560..113455196, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_22.parquet:0..79775901, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_23.parquet:0..79631107, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_24.parquet:0..78257049, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_25.parquet:0..144169728, ...], [Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_28.parquet:106905624..162772407, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_29.parquet:0..79213288, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_3.parquet:0..192507052, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_30.parquet:0..124187913, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_31.parquet:0..123065410, ...], [Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_35.parquet:54087340..153632381, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_36.parquet:0..92487304, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_37.parquet:0..108247781, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_38.parquet:0..132005180, Users/andrewlamb/Software/datafusion/benchmarks/data/hits_partitioned/hits_39.parquet:0..103522954, ...], ...]}, projection=[WatchID, JavaEnable, Title, GoodEvent, EventTime, EventDate, CounterID, ClientIP, RegionID, UserID, CounterClass, OS, UserAgent, URL, Referer, IsRefresh, RefererCategoryID, RefererRegionID, URLCategoryID, URLRegionID, ResolutionWidth, ResolutionHeight, ResolutionDepth, FlashMajor, FlashMinor, FlashMinor2, NetMajor, NetMinor, UserAgentMajor, UserAgentMinor, CookieEnable, JavascriptEnable, IsMobile, MobilePhone, MobilePhoneModel, Params, IPNetworkID, TraficSourceID, SearchEngineID, SearchPhrase, AdvEngineID, IsArtifical, WindowClientWidth, WindowClientHeight, ClientTimeZone, ClientEventTime, SilverlightVersion1, SilverlightVersion2, SilverlightVersion3, SilverlightVersion4, PageCharset, CodeVersion, IsLink, IsDownload, IsNotBounce, FUniqID, OriginalURL, HID, IsOldCounter, IsEvent, IsParameter, DontCountHits, WithHash, HitColor, LocalEventTime, Age, Sex, Income, Interests, Robotness, RemoteIP, WindowName, OpenerName, HistoryLength, BrowserLanguage, BrowserCountry, SocialNetwork, SocialAction, HTTPError, SendTiming, DNSTiming, ConnectTiming, ResponseStartTiming, ResponseEndTiming, FetchTiming, SocialSourceNetworkID, SocialSourcePage, ParamPrice, ParamOrderID, ParamCurrency, ParamCurrencyID, OpenstatServiceName, OpenstatCampaignID, OpenstatAdID, OpenstatSourceID, UTMSource, UTMMedium, UTMCampaign, UTMContent, UTMTerm, FromTag, HasGCLID, RefererHash, URLHash, CLID], file_type=parquet, predicate=CAST(URL@13 AS Utf8View) LIKE %google% |
| | |
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
2 row(s) fetched.
Elapsed 0.056 seconds.
Something that immediately jumps out at me in the explain plan is this line
| | DataSourceExec: file_groups={16 groups: ...}, projection=[WatchID, JavaEnable, Title, GoodEvent, EventTime, EventDate, CounterID, ClientIP, RegionID, UserID, CounterClass, OS, UserAgent, URL, Referer, IsRefresh, RefererCategoryID, RefererRegionID, URLCategoryID, URLRegionID, ResolutionWidth, ResolutionHeight, ResolutionDepth, FlashMajor, FlashMinor, FlashMinor2, NetMajor, NetMinor, UserAgentMajor, UserAgentMinor, CookieEnable, JavascriptEnable, IsMobile, MobilePhone, MobilePhoneModel, Params, IPNetworkID, TraficSourceID, SearchEngineID, SearchPhrase, AdvEngineID, IsArtifical, WindowClientWidth, WindowClientHeight, ClientTimeZone, ClientEventTime, SilverlightVersion1, SilverlightVersion2, SilverlightVersion3, SilverlightVersion4, PageCharset, CodeVersion, IsLink, IsDownload, IsNotBounce, FUniqID, OriginalURL, HID, IsOldCounter, IsEvent, IsParameter, DontCountHits, WithHash, HitColor, LocalEventTime, Age, Sex, Income, Interests, Robotness, RemoteIP, WindowName, OpenerName, HistoryLength, BrowserLanguage, BrowserCountry, SocialNetwork, SocialAction, HTTPError, SendTiming, DNSTiming, ConnectTiming, ResponseStartTiming, ResponseEndTiming, FetchTiming, SocialSourceNetworkID, SocialSourcePage, ParamPrice, ParamOrderID, ParamCurrency, ParamCurrencyID, OpenstatServiceName, OpenstatCampaignID, OpenstatAdID, OpenstatSourceID, UTMSource, UTMMedium, UTMCampaign, UTMContent, UTMTerm, FromTag, HasGCLID, RefererHash, URLHash, CLID], file_type=parquet, predicate=CAST(URL@13 AS Utf8View) LIKE %google% |
"Projection" I think means that all of those columns are being read/ decoded from parquet, which makes sense as the query has a SELECT * on it.
However, in this case all but the top 10 rows are returned (out of 100M rows in the file)
So this means that most of the decoded data is decoded and thrown away immediately
Describe the solution you'd like
I would like to close the gap with DuckDB with some general purpose improvement
Describe alternatives you've considered
I think the way to improve performance here is to defer decoding ("Materializing") the other columns until we know what the top 10 rows are.
some wacky ideas:
- Push the topk / ordering into the scan somehow
- implement "late materialization"
Late materialization would look something like
- decode only the EventTime column and a
row_id - determine the top 10 row_id by sorting by EventTime
- Decode only those 10 rows from the parquet file(s)
Additional context
No response
Activity
alamb commentedon Mar 12, 2025
OOOO -- here is the duckdb plan and it shows what they are doing!
The key is this line:
What I think this is referring to is what @adriangb is describing in :
ORDER BY LIMITqueries) #15037Specifically, the Top_N operator passes down a filter into the scan. The filter is "dynamic" in the sense that
alamb commentedon Mar 12, 2025
The topk dynamic filtering is described here:
https://www.snowflake.com/en/blog/super-fast-top-k-queries/
alamb commentedon Mar 12, 2025
BTW apparently DuckDB uses the "late materialization" technique with its own native format. Here is an explain courtesy of Joe Issacs and Robert Kruszewski
suibianwanwank commentedon Mar 12, 2025
This looks cool! Very interested in this.
robert3005 commentedon Mar 12, 2025
There's two optimizations here that go together, if you check clickbench results duckdb on their own format is significantly faster than parquet. The two optimizer rules that do this is 1) TopN https://github.com/duckdb/duckdb/blob/main/src/optimizer/topn_optimizer.cpp#L105 2) Late materialization https://github.com/duckdb/duckdb/blob/main/src/optimizer/late_materialization.cpp#L180 (join back the filter result to obtain rest of the columns)
alamb commentedon Mar 12, 2025
Note that late materialization (the join / semi join rewrite) needs join operator support that DataFusion doesn't yet have (we could add it but it will take non trivial effort)
My suggested order of implementation is:
filter_pushdown) by default #3463 with @XiangpengHao (so that we can actually evaluate the topk filter during scan)ORDER BY LIMITqueries) #15037I actually think that will likely get us quite fast. I am not sure how much more improvement late materialized joins will get without a specialized file format.
I don't have time to help plan out late materializing joins at the moment, but I am quite interested in pushing along the predicate pushdown
xudong963 commentedon Mar 12, 2025
There is a similar thought named
prewhere: https://clickhouse.com/docs/sql-reference/statements/select/prewhere.Even though it aims to filter, the idea is similar, for example:
Table
thas 100 columns, one of them isa, for sql:select * from t where a = 1, it'll do the following steps:Back to topk,
select * from t order by a limit 10We can spilt the idea to the query:
alamb commentedon Mar 12, 2025
I agree -- this is what I meant by "late materialization" . Your example / explanation is much better than mine @xudong963 🙏
Dandandan commentedon Mar 20, 2025
I did not fully get this part. DF has semi join support and some rewrites to utilize it in similar cases?
The query transformation in SQL as given by @xudong963 is optimized to a SEMI join + TopK, so I think it could be implemented as logical optimization rule (i.e. adding a filter with subquery on the ids).
Dandandan commentedon Mar 20, 2025
Ah actually, the query given by @xudong963 is I think slightly off, I think it should be the following (without the explicit join).
This yields the same plan as DuckDB:
adriangb commentedon Mar 20, 2025
I think the difference is that DuckDB dynamically pushes down the current state of the TopK heap into file opening as described in #15037 and implemented in #15301
alamb commentedon Mar 20, 2025
@Dandandan --
I think it would be interesting to try and rewrite q23 manually to that pattern and see how it goes fast
I suspect (but have not measured), if we implemented this rewrite we would find it runs much more slowly than the existing code because what would happen is that the entire input file (all columns) would be decoded and all but 10 rows are thrown away
To avoid this we need to push the join filters into the scan (and get predicate pushdown on by default)
Edit: although now I say this maybe it would be much better as we have to decode all the columns now....
alamb commentedon Mar 20, 2025
I tried the rewrite into a Semi join and indeed it is over 2x slower (5.3sec vs 12sec)
Here is what I think the rewrite is
WatchID is a unique key
I also double checked the output
alamb commentedon Mar 20, 2025
I am not really sure where the time is going 🤔
output of explain analyze: explain.txt
Dandandan commentedon Mar 20, 2025
Thanks for checking @alamb !
I think a large portion is spent in the hash join (repartitioning the right side input) - I think because it runs as
Partitionedhash join, instead of realizing it could useCollectLeft(see repartition_time=55.648133838s) for the small side (10 rows).alamb commentedon Mar 20, 2025
I also think the
Url,WatchIDandEventDatecolumns will be decoded twice. To make that join go really fast we would need something like:alamb commentedon Mar 20, 2025
BTW combined with @adriangb's PR here
It will likely go crazy fast 🚀
Dandandan commentedon Mar 20, 2025
I traced this down to an issue in the planner, which uses
PartitionMode::Autoiff stats are collected (datafusion.execution.collect_statistics)We can however still use file and plan-derived statistics, so let's change that.
#15339
acking-you commentedon Apr 23, 2025
I recently took a detailed look at this optimization in ClickHouse, and it might offer you some insights @alamb .
rewrite SQL in ClickHouse
First, in ClickHouse, each row of data can be located using the two virtual columns
_partand_part_offset(this applies only to MergeTree tables).Specifically, for the optimization you mentioned, you can compare the performance of the following two queries in ClickHouse:
I measured that Q1 took 34 seconds, while Q2 only took 7.2 seconds (both cleared the page cache before running).
This performance improvement may be attributed to ClickHouse correctly utilizing the result of the subquery to filter parts and quickly pinpoint the relevant data.
However, in earlier versions of ClickHouse (such as 23.12), the aforementioned query Q2 would actually degrade in performance. But at that time, if I split Q2 into two separate statements and executed them manually, it would still work perfectly fine.
Conclusion
adriangb commentedon Apr 23, 2025
Relevant: https://clickhouse.com/blog/clickhouse-gets-lazier-and-faster-introducing-lazy-materialization
acking-you commentedon Apr 23, 2025
Thank you so much for sharing this blog link—it’s truly an excellent learning resource! I hadn’t come across it before; I was just looking at the source code of this related optimization PR and running performance tests on the hits dataset. They introduced a new type called ColumnLazy(Interestingly, the comments also mention optimizing the join process through this structure.) to implement lazy materialization of columns. However, in my testing, I’ve noticed that performance starts to degrade when the
limitvalue becomes large. For instance, degradation begins atlimit 100000when the page cache is cleared. In fully cached scenarios, performance degradation occurs as early aslimit 256. This is why they’ve set query_plan_max_limit_for_lazy_materialization=10 as the default value to determine whether to apply the optimization.However, I noticed that using the following SQL rewrite approach hardly leads to any performance degradation. I even tested it with
limit 400000while clearing the page cache, and it still maintained excellent performance. Below are the performance test results for a limit of 100,000 (clear page cache):The direct SQL rewrite approach mentioned above might still have some issues in ClickHouse at the moment. They are currently exploring the possibility of using it alongside projections (a feature in ClickHouse akin to materialized views) to create secondary indexes and similar functionalities. Relevant PR: ClickHouse/ClickHouse#78429 (comment).
I find this truly remarkable, and I’m also investigating why the direct SQL rewrite performs faster than ColumnLazy.
acking-you commentedon Apr 27, 2025
I have already discovered the reason:ClickHouse/ClickHouse#79645
EmeraldShift commentedon Apr 29, 2025
There's a follow-up PR that makes the query in that comment work consistently: ClickHouse/ClickHouse#79471
Also, I had asked for something that sounds equivalent to dynamic filter in TopK in ClickHouse in ClickHouse/ClickHouse#75098 and ClickHouse/ClickHouse#75774 (comment), so it seems like CH has yet to perform that optimization at the moment, it just has lazy materialization and soon the manual version of it via query rewriting and "projection indexes".
adriangb commentedon Oct 15, 2025
@alamb should we close this now that Q23 is 23x faster?
alamb commentedon Oct 15, 2025
YES!