You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "rohityadav1993 (via GitHub)" <gi...@apache.org> on 2026/07/29 17:53:04 UTC
[PR] Add streaming k-way merge to SortedMailboxReceiveOperator [pinot]
rohityadav1993 opened a new pull request, #19121:
URL: https://github.com/apache/pinot/pull/19121
`SortedMailboxReceiveOperator` accumulates every row from all senders and only then sorts, even when
each sender's stream is already sorted on the collation keys — flagged as a TODO in the class today.
That defeats streaming and makes the receive stage's peak memory proportional to the whole input.
This is the second bullet of **Challenge 1** in #18667.
### Approach
When the planner can prove each sender emits sorted output, the receiver performs a k-way heap merge
across mailboxes and emits bounded sorted blocks as data arrives.
- **`BlockingMultiStreamConsumer`** gains a `StreamHandle<T>` abstraction
(`awaitDataOrTerminal()` / `poll()`) so a consumer can hold the head of each stream without
draining it — the primitive the heap merge needs. A consumer must use either the handles or
`readMseBlockBlocking()`, never both; the mode is latched.
`relieveSiblingsOnce()` does one non-blocking poll per sibling stream per refill, so a fast sender
with a disjoint key range cannot sit blocked on a full mailbox holding an MSE worker thread.
- **`SortedMailboxReceiveOperator`** implements the merge with a per-mailbox cursor that caches its
head row, and verifies the precondition at runtime: each sender's rows must be non-decreasing, and
a violation surfaces as an error block naming the offending mailbox instead of silently wrong
output.
- **`PlanFragmenter` / `PinotLogicalQueryPlanner` / `QueryEnvironment`** mark a leaf selection
`ORDER BY` sender fragment as sorted-on-sender when the plan shape and collation match.
This gate **fails closed**: `resolvesToSinglePhysicalTable()` rejects hybrid tables, logical
tables, unknown tables, and a null `TableCache`. This matters — a scan over a hybrid table compiles
into two `ServerQueryRequest`s that `LeafOperator` runs concurrently into one mailbox, producing
two independently sorted runs concatenated, not a sorted stream. Empty collations are also
rejected, so a `LIMIT` without `ORDER BY` (which compiles to a collation-less `LogicalSort`) is
never marked sorted.
- **`BaseMailboxReceiveOperator.StatKey.K_WAY_MERGE_USED`** (new) reports per receive operator, in
the response `stageStats`, whether the merge actually ran. Reporting is presence-based —
`StatMap` drops `false` booleans, so `kWayMergeUsed: true` appears on the merge path and nothing
appears on the accumulate-then-sort path. This is the only runtime discriminator between the two
paths; both render as `type: MAILBOX_RECEIVE`.
### Opt-in query options
| Option | Default | Meaning |
|---|---|---|
| `streamingSortedMailboxReceive` | `false` | Use the k-way merge when the planner has also proven senders are sorted |
| `streamingSortedMailboxReceiveBlockSize` | `10000` | Rows per emitted block |
| `sortedSelectionMergeEnabled` (from the parent PR) | `false` | Additionally required **only** for the plain leaf-selection `ORDER BY` shape, where the rel plan contains no sort exchange |
`isSortedOnSender` is set either by a rel-level sort exchange that already declares sender-side
sorting, or — for a plain leaf selection `ORDER BY` — by `PlanFragmenter` under
`sortedSelectionMergeEnabled`. Only the latter case needs both options.
### Rolling-upgrade note
`K_WAY_MERGE_USED` is appended as the **last** `StatKey` constant. `StatMap` serializes keys by
ordinal and deserializes without a bounds check, so a peer on a build predating the key cannot
decode stage stats containing it. Because BOOLEAN keys are written only when `true`, and the key is
only ever `true` when `streamingSortedMailboxReceive` is on, leaving the option off (the default)
keeps a mixed-version cluster safe. This is documented on the option constant. Bounds-checking the
ordinal in `StatMap.merge(DataInput)` is a worthwhile separate fix.
### No behaviour change when the option is off
With `streamingSortedMailboxReceive` unset, the existing accumulate-then-sort path runs unchanged and
no new stat is emitted. The planner-side marking is additionally a no-op under
`usePhysicalOptimizer`, since the v2 path does not go through `PlanFragmenter`.
### Tests
| Test class | Count |
|---|---|
| `SortedMailboxReceiveOperatorTest` (extended) | 36 |
| `PlanFragmenterTest` (new) | 42 cases — accept/reject sender shapes, hybrid / logical / unknown-table rejects, collation matching, option-off for every shape, null-cache fail-closed |
| `SortOperatorTest` (extended) | 23 |
| `BlockingMultiStreamConsumerTest` (extended) | 9 |
| full `pinot-query-planner` suite | 1449 |
| `StreamingSortedMailboxReceiveTest` (new integration test) | 4 |
The integration test asserts `kWayMergeUsed` in `stageStats` on the merge arm and its absence on the
baseline arm, so it cannot pass with the merge path deleted.
### What this buys, honestly
On a local cluster over an 87.8M-doc, 56-segment table, the merge is confirmed engaged
(`kWayMergeUsed: true` on both join-input receives) and results are identical to the
accumulate-then-sort path. **It is not a throughput win** for that workload — enabling the mailbox
merge alone was the slowest sorted variant measured. The benefit is bounded peak memory in the
receive stage and latency to first row, not wall clock. Row order among equal collation keys is
unspecified and may differ between the two paths, as with any SQL `ORDER BY`; the output multiset is
identical.
### Stacking
> Stacked on #19120. The GitHub diff for this PR includes the parent's commits until the parent merges
> — **review only the top commit.**
>
> **This PR does not compile without its parent.** `QueryEnvironment` calls
> `QueryOptionsUtils.isSortedSelectionMergeEnabled(...)`, which the parent PR adds. Please do not
> merge this one first.
Part of #18667.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Add streaming k-way merge to SortedMailboxReceiveOperator [pinot]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #19121:
URL: https://github.com/apache/pinot/pull/19121#issuecomment-5122273698
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/19121?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `82.12005%` with `140 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 57.02%. Comparing base ([`a8b207e`](https://app.codecov.io/gh/apache/pinot/commit/a8b207e78156296f686eea3a312a9cb68d08ac6a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`0f09d4f`](https://app.codecov.io/gh/apache/pinot/commit/0f09d4f3c2fb21060358b92a1990450edea728a6?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 17 commits behind head on master.
| [Files with missing lines](https://app.codecov.io/gh/apache/pinot/pull/19121?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...bine/StreamingSelectionOrderByCombineOperator.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Foperator%2Fcombine%2FStreamingSelectionOrderByCombineOperator.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9jb21iaW5lL1N0cmVhbWluZ1NlbGVjdGlvbk9yZGVyQnlDb21iaW5lT3BlcmF0b3IuamF2YQ==) | 72.41% | [39 Missing and 17 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...runtime/operator/SortedMailboxReceiveOperator.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-query-runtime%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fquery%2Fruntime%2Foperator%2FSortedMailboxReceiveOperator.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtcXVlcnktcnVudGltZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvcXVlcnkvcnVudGltZS9vcGVyYXRvci9Tb3J0ZWRNYWlsYm94UmVjZWl2ZU9wZXJhdG9yLmphdmE=) | 84.35% | [20 Missing and 8 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...rator/query/StreamingSelectionOrderByOperator.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Foperator%2Fquery%2FStreamingSelectionOrderByOperator.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9xdWVyeS9TdHJlYW1pbmdTZWxlY3Rpb25PcmRlckJ5T3BlcmF0b3IuamF2YQ==) | 88.26% | [21 Missing and 6 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...me/operator/utils/BlockingMultiStreamConsumer.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-query-runtime%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fquery%2Fruntime%2Foperator%2Futils%2FBlockingMultiStreamConsumer.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtcXVlcnktcnVudGltZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvcXVlcnkvcnVudGltZS9vcGVyYXRvci91dGlscy9CbG9ja2luZ011bHRpU3RyZWFtQ29uc3VtZXIuamF2YQ==) | 81.81% | [10 Missing and 4 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...he/pinot/query/planner/logical/PlanFragmenter.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-query-planner%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fquery%2Fplanner%2Flogical%2FPlanFragmenter.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtcXVlcnktcGxhbm5lci9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvcXVlcnkvcGxhbm5lci9sb2dpY2FsL1BsYW5GcmFnbWVudGVyLmphdmE=) | 84.44% | [4 Missing and 3 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...va/org/apache/pinot/core/plan/CombinePlanNode.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Fplan%2FCombinePlanNode.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9wbGFuL0NvbWJpbmVQbGFuTm9kZS5qYXZh) | 50.00% | [0 Missing and 4 partials :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...pinot/core/plan/maker/InstancePlanMakerImplV2.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Fplan%2Fmaker%2FInstancePlanMakerImplV2.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9wbGFuL21ha2VyL0luc3RhbmNlUGxhbk1ha2VySW1wbFYyLmphdmE=) | 66.66% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [.../org/apache/pinot/core/plan/SelectionPlanNode.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Fplan%2FSelectionPlanNode.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9wbGFuL1NlbGVjdGlvblBsYW5Ob2RlLmphdmE=) | 92.30% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...y/runtime/operator/BaseMailboxReceiveOperator.java](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&filepath=pinot-query-runtime%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fquery%2Fruntime%2Foperator%2FBaseMailboxReceiveOperator.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtcXVlcnktcnVudGltZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvcXVlcnkvcnVudGltZS9vcGVyYXRvci9CYXNlTWFpbGJveFJlY2VpdmVPcGVyYXRvci5qYXZh) | 75.00% | [1 Missing :warning: ](https://app.codecov.io/gh/apache/pinot/pull/19121?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
> :exclamation: There is a different number of reports uploaded between BASE (a8b207e) and HEAD (0f09d4f). Click for more details.
>
> <details><summary>HEAD has 16 uploads less than BASE</summary>
>
>| Flag | BASE (a8b207e) | HEAD (0f09d4f) |
>|------|------|------|
>|unittests|2|1|
>|java-25|5|1|
>|temurin|5|1|
>|unittests2|1|0|
>|integration|3|0|
>|integration1|1|0|
>|integration2|1|0|
>|custom-integration1|1|0|
></details>
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #19121 +/- ##
============================================
- Coverage 65.49% 57.02% -8.47%
+ Complexity 1423 1 -1422
============================================
Files 3430 2637 -793
Lines 218010 159128 -58882
Branches 34648 26185 -8463
============================================
- Hits 142784 90743 -52041
+ Misses 63666 60587 -3079
+ Partials 11560 7798 -3762
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [custom-integration1](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-25](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `57.02% <82.12%> (-8.47%)` | :arrow_down: |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `57.02% <82.12%> (-8.47%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `57.02% <82.12%> (-8.47%)` | :arrow_down: |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `57.02% <82.12%> (+0.15%)` | :arrow_up: |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/19121/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/pinot/pull/19121?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Add streaming k-way merge to SortedMailboxReceiveOperator [pinot]
Posted by "rohityadav1993 (via GitHub)" <gi...@apache.org>.
rohityadav1993 commented on code in PR #19121:
URL: https://github.com/apache/pinot/pull/19121#discussion_r3815196913
##########
pinot-query-planner/src/main/java/org/apache/pinot/query/planner/logical/PlanFragmenter.java:
##########
@@ -230,6 +261,103 @@ private boolean isPlanFragmentSplitter(PlanNode node) {
return ((ExchangeNode) node).getExchangeType() != PinotRelExchangeType.SUB_PLAN;
}
+ /**
+ * Returns {@code true} if the given sender fragment root represents a <i>leaf selection ORDER BY</i> over a single
+ * physical table, i.e. a {@link SortNode} whose single-input chain down to the leaf consists solely of
+ * {@link ProjectNode} and {@link TableScanNode} nodes, bottoms out at a {@link TableScanNode}, and that scan resolves
+ * to exactly one physical table (see {@link #resolvesToSinglePhysicalTable}).
+ *
+ * <p>Any branching node (input count != 1 that is not the leaf scan) or any node that breaks the single-table leaf
+ * shape (Join, Aggregate, MailboxReceive/Exchange, Window, SetOp, etc.) makes this return {@code false}. This is the
+ * shape for which the k-way merge in {@code SortedMailboxReceiveOperator} can be safely auto-activated.
+ */
+ private boolean isLeafSelectionOrderBy(PlanNode root) {
+ if (!(root instanceof SortNode)) {
+ return false;
+ }
+ PlanNode current = root;
+ while (true) {
+ if (current instanceof TableScanNode) {
+ return resolvesToSinglePhysicalTable(((TableScanNode) current).getTableName());
+ }
+ // Only SortNode (root), ProjectNode and TableScanNode are allowed in the chain.
+ if (!(current instanceof SortNode) && !(current instanceof ProjectNode)) {
Review Comment:
Self review: Handle for filter node as well.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org