feat: limit push down

[lmatz]

Describe the bug

query:

select cast(UDF(CONSTANT_1, Column_1) as jsonb)  from TABLE1 where name like '%ZZZ%' limit 1;

plan:

BatchLimit { limit: 1, offset: 0 }
 └─BatchExchange { order: [], dist: Single }
   └─BatchLimit { limit: 1, offset: 0 }
     └─BatchProject { exprs: [UserDefinedFunction { ... }::Jsonb as $expr1] }
       └─BatchFilter { predicate: Like(TABLE1.name, '%ZZZ%':Varchar) }
         └─BatchScan { table: TABLE1, columns: [COLUMN1, name] }
(6 rows)

Is it a bug or is limit 1 doing what it is supposed to do?

To Reproduce

No response

Expected behavior

No response

Additional context

Reported by a design partner

[xxchan]

IIRC we don't have any "limit pushdown", but only "two phase limit"

[lmatz]

Oh, now I remembered, we count on the early termination of limit to early terminate the scan.

The scan probably did a read to fetch 1024 rows anyway in this case and udf processed them all.

[xxchan]

So are you making a feature request to pushing limit to the lowest level? 🤔

[lmatz]

Yes, not a bug but a feature request

[y-wei]

I think I've done similar things when optimizing TopN.

risingwave/src/frontend/src/optimizer/rule/top_n_on_index_rule.rs

Lines 64 to 66 in 83f1e9d

	index_scan.set_chunk_size(
	((u32::MAX as u64).min(logical_top_n.limit() + logical_top_n.offset())) as u32,
	);

Do you want more cases that set chunk_size for scan?

[xxchan]

Wow I don't know we have that 👀. But I don't think limit push down is like that. I think we just need to blindly push limit down until a leaf node 🤔

[y-wei]

Oh I see, then IIUC it's pushing down until leaf or filter?

[xxchan]

Oh yes and no... By mentioning filter you also remind me of other cases, like join or agg.

[y-wei]

I find the problem is more tricky that it might seem...

A solvable problem is the project set generates multiple rows for each row input, e.g., select generate_series(1, 1000, 1) from t limit 1;, although we can have a limit directly following the scan, we have to keep the original limit to guarantee our output is limited as desired.

A more tricky case is that, say one UDF generates 0 records for the first row in TABLE1 and generate 1 records for the second row in TABLE1, we cannot push down the limit to the scan as then no records will in the output. Generally speaking, we have to ensure the current op will generate at least 1 row(s) per input row to push down a limit, which there is no existing method to check and I think we may introduce some checks in LogicalProjectSet (or more?) to achieve it, if we do need this feature.

Therefore I find the use case where we can push the limit down could be very limited, could you please reconfirm this feature request?

[lmatz]

I think UDF always returns a single row.
But your analysis does apply to UDTF which can return 0, 1 or multiple rows.👍

[y-wei]

Cool, then we can do something. Could you please provide a runnable use case of UDF? I cannot find any in our e2e or planner tests😄

[y-wei]

Hello guys. I find my pr a bit stuck, and thus I want to followup. Since pushing down ProjectSet can be dangerous as we've agreed above, my current implementation just specifically matches the limit <- project pattern. Do you have any concerns with it? I was implementing it by a blacklist way (pushing down until some nodes), yet I found it might only left us Project😅

[xxchan]

I don't have any other concerns, but can also only imagine Limit -> Project case. 😅 So it seems too limited and ad-hoc. Wanted @lmatz to elaborate the use cases.

cc @wangrunji0408

[wangrunji0408]

Could you please provide a runnable use case of UDF?

You can find them here.

I think pushing Limit down through Project should be no concern, as Project (including UDF) always produces chunks with the same number of rows as the inputs.

[st1page]

it is not a very big optimization because the LimitExecutor can stop the stream early when the input achieves the limit row count. But generally LGTM.

[lmatz]

My input comes from one user who complains about why a query with limit 1 and UDF is so slow. That's all.

[y-wei]

completed by #8971