You are viewing a plain text version of this content. The canonical link for it is here.

Posted to commits@pinot.apache.org by "arunkumarucet (via GitHub)" <gi...@apache.org> on 2026/10/15 08:52:56 UTC

[PR] Materialize non-order-by columns late on the sorted order-by path [pinot]

arunkumarucet opened a new pull request, #19879:
URL: https://github.com/apache/pinot/pull/19879

   Fixes #19761
   
   ## Problem
   
   `SELECT <wide projection> ... ORDER BY <sorted column> DESC LIMIT k` reads **every selected column for every document in the match set**, then keeps `k` rows. Cost scales with match-set size times projection width, not with `LIMIT`.
   
   Pinot already avoids this on the *unsorted* order-by path — `SelectionPlanNode` projects only the order-by expressions there and `SelectionOrderByOperator` fetches the rest for the top-k doc ids. The sorted-column path, which is otherwise the faster one, did not.
   
   ## Change
   
   In the `sortedColumnsPrefixSize > 0` branch, project only the order-by expressions, carry the doc id in the row at index `numOrderByExpressions`, and once the limit has been applied fetch the remaining expressions through `BitmapDocIdSetOperator.ascending` → `ProjectionOperator` → `TransformOperator` — the mechanism `SelectionOrderByOperator` already uses. The late fetch lives in `LinearSelectionOrderByOperator`, so both subclasses get it.
   
   **It is gated to where it actually pays.** The linear operator stops as soon as the list builder is full, which with a fully sorted order-by prefix is after `limit + offset` documents; deferring there saves no reads and only adds a bitmap and a transform operator. So late materialization is enabled only when the scan is *not* bounded by the limit:
   
   - `SelectionPartiallyOrderedByDescOperation` — no reverse cursor, so it must read the whole match set;
   - an unsorted order-by suffix — which removes the limit bound on the scan.
   
   A test asserts the entries read are *exactly equal* in the skipped case, so the gating cannot silently rot.
   
   The project operator is built **exactly once**. Constructing one resolves a `DataSource` and a `ColumnContext` per selected column, and some implementations begin prefetching those columns in the constructor — so a build-and-discard probe to decide which operator will run would read exactly the columns this change exists to avoid reading. Whether the scan can iterate in query order is instead predicted from the order direction and `allowReverseOrder`; being wrong only costs the optimization, never correctness, because the operator choice still comes from the project operator itself.
   
   Kill switch: `SET lateMaterializeSortedOrderBy = false` restores the previous behaviour.
   
   ## Measurements
   
   SereneDB [SearchBench](https://github.com/serenedb/searchbench) `otel_logs`, 100M rows in 250 segments, single node. These are the suite's `recent` queries — "show me the N most recent matching log lines". Stock and patched builds interleaved over 4 cycles, medians reported, because the combine operator prunes segments by min/max once it has enough rows and single-shot latency is noisy.
   
   | Query | stock p50 | this PR | speedup | stock entries post-filter | this PR | reduction |
   |---|---|---|---|---|---|---|
   | Q70 | 32.77 ms | 8.05 ms | **4.07x** | 1,343,488 | 359,414 | 3.7x |
   | Q75 | 23.00 ms | 6.70 ms | **3.43x** | 927,720 | 275,467 | 3.4x |
   | Q74 | 24.68 ms | 7.65 ms | **3.23x** | 978,264 | 247,266 | 4.0x |
   | Q72 | 27.25 ms | 9.34 ms | **2.92x** | 436,302 | 144,162 | 3.0x |
   | Q71 | 25.05 ms | 12.75 ms | **1.97x** | 490,896 | 135,252 | 3.6x |
   | Q68 | 83.77 ms | 43.84 ms | **1.91x** | 118,900 | 71,350 | 1.7x |
   | Q69 | 34.03 ms | 25.37 ms | 1.34x | 1,078,624 | 272,056 | 4.0x |
   | Q76–Q83 (no `ORDER BY`) | — | — | **~1.00x** | 2,400 | 2,400 | 1.0x |
   | **total** | **291.8 ms** | **152.7 ms** | **1.91x** | **5,390,994** | **1,521,767** | **3.5x** |
   
   Entries post-filter goes from `numDocsScanned × 4` to `numDocsScanned × 1` plus the late fetch for the rows that survive the limit. The seven queries without an `ORDER BY` take a different operator and are the control: unchanged on both metrics. Row counts are identical throughout.
   
   ## Tests
   
   Six new tests in `InnerSegmentSelectionSingleValueQueriesTest` run the same query with the option on and off and assert identical rows and schema, strictly fewer entries where late materialization applies and exactly equal entries where it is correctly skipped. They cover ASC, DESC in doc-id order, DESC in reverse order, `OFFSET`+`LIMIT`, an unsorted order-by suffix, a function in the projection (the late fetch builds its own `TransformOperator`, so the expression must resolve for both its values and its schema type) and null handling.
   
   Null handling has its own test in `NullHandlingEnabledQueriesTest`, because `BaseSingleValueQueriesTest` has no null vectors and an assertion there would never reach the null branches. It uses a sorted, non-null order-by column and a deferred column containing nulls, and asserts the deferred nulls survive — mutating the late fetch's bitmap index makes it fail with `null` replaced by the INT default.
   
   `testSelectionOrderBySingleSortedColumnDescDidOrder` previously asserted `numEntriesScannedPostFilter == 90000` (`30000 × 3` columns) — the exact waste this removes. It now asserts `30000 + 20`, and its row and schema assertions are unchanged.
   
   Full `pinot-core` suite: **495 classes, 8,183 tests, 0 failures**.
   


-- 
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