Late materialization when LIMIT prunes heavily.

[RatulDawar]

Currently ClickBench Q23 is a major outliner due to the fact that datafusion doesn't do late materialization of projected columns.

SELECT * FROM hits WHERE "URL" LIKE '%google%' ORDER BY "EventTime" LIMIT 10;

A query like this needs to scan all the columns only after all the redundant rows are prunned from output.

Some numbers that I was able to get locally showing this regression in play.

Engine	Query time
DataFusion 54 (SELECT *)	~4.0s avg
DataFusion 54 (SELECT "EventTime", "URL")	~0.9s

SortPreservingMergeExec (limit 10)
└─ SortExec TopK (EventTime), DynamicFilter [ empty ]
   └─ ProjectionExec (105 columns)
      └─ FilterExec (URL LIKE '%google%')
         └─ DataSourceExec (projection=[105 cols], 111 files)
              predicate: URL LIKE %google% AND DynamicFilter [ empty ]

EXPLAIN ANALYZE metrics (SELECT *)

DataSourceExec

Metric	Value
projection	105 columns
output_rows	97.17 M
output_bytes	137.8 GB
row_groups_pruned_statistics	325 → 325 matched
row_groups_pruned_bloom_filter	325 → 325 matched
page_index_pages_pruned	0

What duckdb does in this scenario is that it materialises the projection rows that are not needed for any computation or maybe needed in later steps as late as possilble.

But this late materialization comes at the cost of requiring a self join later on to get the other columns back, and got self join's we need row tagging.

In datafusion we can tag a row uniquely with file_row_index(), input_file_name().
But then if rows are not dynamically filtered on the basis of above two columns it will again lead to a full table scan for probe side of the join.

[RatulDawar]

Also this optimization a strictly based on the fact that the number of output rows are small, I want to understand that would it be beneficial to take over this complexity as this seems to be a very common query pattern.

[saadtajwar]

Hi @RatulDawar , happy to help with this if needed!

[RatulDawar]

Hi @RatulDawar , happy to help with this if needed!

Sure !!

[RatulDawar]

Since this largely depends on statistics here is what I propose.
ymbols (uniform per-cell cost):

Symbol	Meaning
R	rows before filtering
r	rows after filtering
C	columns projected (SELECT *)
c	columns required in phase 1 (filter cols + sort key + row ids)

Scan cost

Before optimization — filter after wide decode:

scan_before = R × C

After optimization — narrow scan, then wide fetch for survivors:

scan_after = R × c + r × C

When optimization wins

scan_before > scan_after

R × C  >  R × c + r × C

R × (C - c)  >  r × C

Same condition, rearranged:

r / R  <  (C - c) / C          (selectivity < column savings fraction)

R / r  >  C / (C - c)

Break-even (costs equal):

r* = R × (C - c) / C

Optimization wins when  r < r*

Here it's possible to determine R, C and c. But r seems a bit hard, maybe we can start with just LIMIT queries as there we have r avaliable.

@saadtajwar what do you think ?

[saadtajwar]

@RatulDawar thank you! Sorry for the delayed response, I will try to look at this in the afternoon when I get home from work in a few hours and let you know my thoughts!

[saadtajwar]

Hmm okay, @RatulDawar looking at this now - going to have to ask a few newbie questions haha:

• Am I correct in my understanding in that the problem is, for this query, DataFusion at the very start of physical execution (in the DataSourceExec node) immediately does projection of all 105 columns in the table - however projection can be deferred until much later, because only really need the URL column for the filter & EventTime for the sort & limit, and we want DataFusion to after all of those expensive computations perform the projection of all columns?
• If I'm understanding the above correctly, your proposal is to start by completing a first phase (filter/sort/limit on URL + EventTime + row IDs in this case) and a second phase that fetches the remaining columns only for the final rows, starting with LIMIT queries where r is bounded?

Please let me know if there's anything I'm missing - happy to start helping you out with implementation/continue digging if needed!