Repository navigation
feat(window-topn): streaming per-partition top-K for pre-sorted input - #24629
Closed
SubhamSinghal wants to merge 3 commits into
Closed
SubhamSinghal wants to merge 3 commits into
SubhamSinghal wants to merge 3 commits into
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
Relates to the WindowTopN optimization (
ROW_NUMBER/RANK/DENSE_RANKper-partition top-K). It adds the missing already-sorted-input path.related to #24060
Rationale for this change
The
WindowTopNrule today only handles the case where the window's input is unsorted: it replaces theSortExecwith a heap-basedPartitionedTopKExec(one top-K heap per distinct partition key). That is the right trade-off when a sort would otherwise be needed, but it has two costs that make it ship default-off:When the window's input is already sorted by
(partition_keys, order_keys)— i.e.EnforceSortingelided theSortExecbecause the ordering was already satisfied — the heaps are pure waste: the data is in the exact order we need, so we can compute the per-partition rank in a single streaming pass with O(1) state and emit incrementally, dropping rows whose rank exceedsKbefore they reach the (expensive) full window.Today that already-sorted case doesn't fire at all: the rule requires a
SortExecchild, so the plan falls through to the default full-window-then-filter. This PR closes that gap.What changes are included in this PR?
A new sibling operator and a restructured rule with two cases:
StreamingPartitionedTopKExec(sorts/streaming_partitioned_topk.rs) — requires input sorted by(partition_keys, order_keys), computes the per-partition rank in one pass (carrying onlyprev_partition/prev_order/rank/count), and emits filtered batches incrementally.EmissionType::Incremental,maintains_input_order = true,required_input_ordering = (partition, order),KeyPartitioneddistribution. SupportsROW_NUMBER,RANKandDENSE_RANK(matchingWindowFnKind);.WindowTopNrule split into a shared matcher plus two classifiers:try_streaming— input already sorted (noSortExec): insert the streaming operator between the window and its child. Applied unconditionally, because it is a pure win (cull-before-window, O(1) memory, order-preserving).try_heap— input unsorted (SortExecpresent): today's behavior, replace theSortExecwithPartitionedTopKExec. Still gated onenable_window_topn.Are these changes tested?
Yes
Are there any user-facing changes?
New physical operator
StreamingPartitionedTopKExecinEXPLAINoutput for qualifying queries over pre-sorted input. Results are unchanged. Because the streaming rewrite is a pure win, it applies even whenenable_window_topnis disabled (that flag continues to gate only the heap path).