Repository navigation
Commit e493c61
authored
[improvement](be) Prioritize Parquet V2 row groups for TopN scans (apache#69646)
### What problem does this PR solve?
Problem Summary:
Parquet V2 currently visits row groups in physical file order. For a
small `ORDER BY ... LIMIT`, the best values can be near the end of a
file. Earlier groups are then decoded before the TopN sink publishes a
useful bound. Even after a bound arrives, the deferred row-group path
does not recheck the footer unless a new scan request is published; TopN
updates its bound in place. `VTopNPred` also lacks the ZoneMap interface
needed to reject whole row groups.
For example, consider four groups containing consecutive integer keys
`[300, 399]`, `[200, 299]`, `[100, 199]`, `[0, 99]` and `ORDER BY k ASC
LIMIT 3`. Reading the last group first produces a bound of `2`; the
other three groups can be rejected using their footer minimum before
dictionary/index probes, prefetch, or data decoding. The descending case
uses the footer maximum.
### Optimization approach
- Add conservative ZoneMap evaluation to `VTopNPred`. Snapshot the
current runtime bound at each evaluation, retain equality for secondary
sort keys, honor NULL ordering, and fall back when types, ranges, or
floating-point NaN information are unsuitable.
- Prioritize selected row groups by the leading TopN slot's sanitized
footer minimum/maximum. Resolve the file-local slot through the
request's column mapping. Keep execution indices separate from the
physical plans so row IDs, delete coordinates, and Condition Cache
boundaries remain valid.
- Recheck the latest TopN bound at every row-group boundary before
expensive metadata probes and I/O. Files without statistics retain the
existing path. Reordering respects row-ID fetch order and the request's
existing metadata-pruning boundary; missing or unusable statistics never
exclude a group by themselves.
### Result and evaluation contract
The optimization must preserve the final TopN result, including
secondary-key ties and NULL placement. It may avoid evaluating
expressions or materializing columns for rows that a valid TopN bound
proves cannot contribute to that result. Preserving potential exceptions
from such excluded rows is not a requirement: a DATE overflow in a
discarded row group, for example, does not require reading that group.
Existing TopN/runtime-filter pushdown eligibility and file-to-table
localization remain unchanged.
No executed error is caught, ignored, or converted to success. A
conversion that is actually needed still follows the existing
strict/non-strict rules and propagates its failure. This distinction
also applies to unprojected equality-delete keys and set-operation
inputs reduced through existing runtime filters. It does not permit
skipping candidate rows, bypassing deletes for retained rows,
re-evaluating a volatile leading key as a different value, or trusting
incompatible statistics.
Earlier follow-ups added FE expression whitelists and table-mapping
restrictions to preserve errors in rows outside the result. Those
restrictions are removed; they unnecessarily reduced existing
optimization eligibility. The production change is confined to the TopN
ZoneMap capability and Parquet scheduling. Existing metadata-pruning
boundaries and ordered row-ID fetches remain respected. Upgrade
compatibility for legacy FE requests using Parquet V1 is outside the
scope of this PR; the follow-up dedicated to that case has been
reverted.
### Eligibility and limits
- FE must already generate a TopN runtime filter for the plan and
leading-key type. Its existing selectivity check remains
`max(estimated_scan_rows, 1) * topn_filter_ratio > LIMIT + OFFSET`
(default ratio: `0.5`); existing window, CTE, nested-TopN and join-side
rules remain unchanged.
- This row-group scheduling optimization applies to Parquet V2. After
localization, the leading-key filter must reference a direct,
non-repeated primitive file column with a compatible type. Arbitrary
computed keys such as `abs(k)` are not mapped to footer bounds.
Projected or secondary-key expressions do not need a new non-throwing
proof.
- Reordering requires at least two selected row groups, at least one
usable leading-key range, no ordered row-ID fetch, and all localized
conjuncts inside the existing metadata-pruning-safe boundary. Ordering
is within the current file/split, without coordinating a global order
across files or scanners. Current-bound footer rechecks can still apply
without reordering when their own eligibility holds.
- ASC/DESC, NULL ordering, OFFSET and multiple sort keys retain their
existing semantics. Leading-key equality is retained for secondary keys.
Missing/untrusted statistics, incompatible types, or an unavailable
bound retain candidates; they cannot by themselves reject a group.
- Benefits depend on reaching promising groups before the others are
read and on having separable ranges. Overlapping ranges, many
leading-key ties, one group per split, or late feedback can
substantially reduce the gain. No new production setting is introduced.
### Measured optimization effect
The included opt-in `ParquetScanTest.TopNRowGroupOrderMicrobench`
exercises the actual Parquet V2 reader plus a bounded TopK heap and
per-block updates of the real runtime predicate. Its workload
corresponds to:
```sql
SELECT k FROM parquet_source ORDER BY k ASC LIMIT 10;
SELECT k FROM parquet_source ORDER BY k DESC LIMIT 10;
```
Fixture: one required INT32 column, 128 row groups x 4,096 rows (524,288
rows), disjoint key ranges, and the best group physically last for each
direction. Files use uncompressed PLAIN DataPageV2 with dictionary and
PageIndex disabled, isolating footer pruning. Every iteration verifies
all ten final values.
| Per reader query | Before | After |
| --- | ---: | ---: |
| Row groups decoded | 128 | 1 |
| RawRowsRead | 524,288 | 4,096 (-99.22%) |
| RowGroupsFilteredByMinMax | 0 | 127 |
| Actual local read bytes | 2,149,888 | 65,602 (-96.95%) |
| ASC median latency | 10.698 ms | 0.669 ms (~16.0x) |
| DESC median latency | 8.590 ms | 0.660 ms (~13.0x) |
Method: Clang 20 RELEASE builds, warm local filesystem cache, the same
pinned CPU, nine paired samples alternating baseline/candidate order,
and 32 reader queries per sample after warmup. These paired timings were
collected before the eligibility cleanup; the direct one-column workload
exercises the same scheduling path. Fresh reader correctness tests still
verify best-first reads and late-bound group rejection. The baseline
restores `vtopn_pred.{h,cpp}` and `parquet_scan.{h,cpp}` from the
pre-optimization base `8d2bd1e14b6d95d923d43e00857da326639cc466` while
retaining the identical benchmark harness and request plumbing; the
benchmark calls ParquetReader directly. All paired checksums match. Work
counters are identical across all samples. ASC candidate samples range
from 0.647 to 1.097 ms and DESC from 0.642 to 0.745 ms; the shared host
has timing outliers. These are reader microbenchmark results; complete
SQL gains depend on file splits, parallelism, feedback latency, and
storage.
### Validation and reproduction
- Fresh verification of the revised implementation: 497 BE tests passed
(one opt-in microbenchmark skipped in the ordinary run), and all 31 FE
tests passed across the four suites below. The three aggregation query
shapes also pass the final translated `TOPN OPT:` EXPLAIN assertion. The
output-evolution optimization test and FE filter-generation test first
failed on the preceding implementation, then passed after removal of the
unnecessary fences.
- Reader integration covers ASC/DESC, top-level/nested
DATE-to-TIMESTAMP_NS output evolution, strict cast on/off, strict
identity DATE materialization, and an unprojected Iceberg
equality-delete key. Excluded groups are skipped. The native and
hidden-delete cases include ordinary-scan and reversed-TopN controls
that still raise the original conversion error when the invalid group is
required; existing output-evolution tests also retain their overflow
checks. The tests verify all surviving keys/converted values and row
counts with real per-block TopN feedback.
- FE Checkstyle (zero violations), clang-format 16, BE build hygiene,
and changed-line clang-tidy for every affected C++ file passed.
- Existing reader tests cover exact TopK results, physical row IDs,
localized slot mapping, missing statistics, metadata-pruning boundaries,
ordered row-ID fetches, NULL placement, and equality boundaries.
- FE coverage checks that potentially throwing secondary expressions do
not disable existing TopN runtime-filter generation. The existing
`nereids_tpch_p0/tpch/topn-filter.groovy` also exposed an actual
regression: the blanket visitor stop removed `TOPN OPT` for `GROUP BY k
ORDER BY k LIMIT 1`. Restore the original visitor traversal and cover
grouped keys, aggregation with HAVING and a join, and grouping sets with
`push_topn_to_agg=false`. These cases run full FE planning and check
`TOPN OPT:` in the translated EXPLAIN fragments. The same unnecessary
expression whitelist also disabled `TOPN OPT` for a nested STRUCT order
key with an `IS NOT NULL` predicate on a sibling field, as exposed by
`nereids_rules_p0/column_pruning/topn_filter_nested_column_pruning.groovy`.
Additional translated-plan checks cover TIMESTAMPTZ, INT and DATE fields
in ASC/DESC, including the complete and predicate-only nested access
paths. Both existing regression suites and their assertions are
unchanged. FE production logic matches the pre-PR base; only an
explanatory traversal comment remains in the FE production diff.
- The earlier SQL suite asserting that all excluded-row errors must be
preserved is removed. Complete SQL performance is not claimed;
performance evidence comes from the reader microbenchmark below.
Correctness suites:
```bash
./run-be-ut.sh -j8 --run \
--filter='*Parquet*:*ColumnMapper*:*TableReader*:*Iceberg*:*EvolutionCast*:*RuntimePredicate*'
./run-fe-ut.sh --run \
org.apache.doris.nereids.postprocess.TopNRuntimeFilterTest,org.apache.doris.nereids.rules.rewrite.DateArithmeticFilterPushDownTest,org.apache.doris.nereids.postprocess.PushDownFilterThroughProjectTest,org.apache.doris.nereids.util.ExpressionUtilsTest
```
Opt-in benchmark (use a RELEASE UT build):
```bash
DORIS_TOPN_ROW_GROUP_BENCHMARK=1 BUILD_TYPE_UT=RELEASE \
./run-be-ut.sh -j8 --run --filter=ParquetScanTest.TopNRowGroupOrderMicrobench
```
For paired comparison, build and save baseline/candidate UT executables
with the same harness, then use the existing runner:
```bash
DORIS_TOPN_ROW_GROUP_BENCHMARK=1 \
DORIS_BE_UT_EXECUTABLE=build-support/run-query-engine-paired-benchmarks.py \
QUERY_ENGINE_BENCH_BASELINE=./baseline/doris_be_test \
QUERY_ENGINE_BENCH_CANDIDATE=./candidate/doris_be_test \
QUERY_ENGINE_BENCH_CPU=0 \
QUERY_ENGINE_BENCH_OUTPUT=./paired-results \
BUILD_TYPE_UT=RELEASE ./run-be-ut.sh -j8 --run \
--filter=ParquetScanTest.TopNRowGroupOrderMicrobench
```
Select an available idle CPU for `QUERY_ENGINE_BENCH_CPU`. The runner
emits paired timings/checksums; `PARQUET_TOPN_WORK` lines report
per-query raw rows, groups filtered by min/max, and actual local read
bytes.
### Release note
Improve Parquet V2 TopN scans by reading promising row groups first and
applying the latest runtime bound before opening subsequent groups.
### Check List (For Author)
- Test
- [x] Unit Test
- [x] Manual test (reader microbenchmark and commands above)
- Behavior changed:
- [x] Yes. Eligible Parquet V2 TopN scans may read row groups in a
different order and skip more groups. SQL ordering remains defined by
the TopN operator. Expressions and conversions in excluded groups may
not execute, so an exception from an excluded row may no longer be
observed.
- Does this need documentation?
- [x] No. Internal scan optimization with no new user-facing option.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label1 parent 69d0094 commit e493c61
8 files changed
Lines changed: 867 additions & 5 deletions
File tree
- be
- src
- exprs
- format_v2/parquet
- test/format_v2
- parquet
- table
- fe/fe-core/src
- main/java/org/apache/doris/nereids/processor/post
- test/java/org/apache/doris/nereids/postprocess
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
97 | 97 | | |
98 | 98 | | |
99 | 99 | | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
100 | 136 | | |
101 | 137 | | |
102 | 138 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
63 | 63 | | |
64 | 64 | | |
65 | 65 | | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
66 | 72 | | |
67 | 73 | | |
68 | 74 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
20 | 20 | | |
21 | 21 | | |
22 | 22 | | |
| 23 | + | |
23 | 24 | | |
24 | 25 | | |
25 | 26 | | |
| |||
43 | 44 | | |
44 | 45 | | |
45 | 46 | | |
| 47 | + | |
46 | 48 | | |
47 | 49 | | |
48 | 50 | | |
| |||
1230 | 1232 | | |
1231 | 1233 | | |
1232 | 1234 | | |
| 1235 | + | |
| 1236 | + | |
| 1237 | + | |
1233 | 1238 | | |
1234 | 1239 | | |
1235 | 1240 | | |
| |||
1409 | 1414 | | |
1410 | 1415 | | |
1411 | 1416 | | |
| 1417 | + | |
| 1418 | + | |
| 1419 | + | |
| 1420 | + | |
| 1421 | + | |
| 1422 | + | |
| 1423 | + | |
| 1424 | + | |
| 1425 | + | |
| 1426 | + | |
| 1427 | + | |
| 1428 | + | |
| 1429 | + | |
| 1430 | + | |
| 1431 | + | |
| 1432 | + | |
| 1433 | + | |
| 1434 | + | |
| 1435 | + | |
| 1436 | + | |
| 1437 | + | |
| 1438 | + | |
| 1439 | + | |
| 1440 | + | |
| 1441 | + | |
| 1442 | + | |
| 1443 | + | |
| 1444 | + | |
| 1445 | + | |
| 1446 | + | |
| 1447 | + | |
| 1448 | + | |
| 1449 | + | |
| 1450 | + | |
| 1451 | + | |
| 1452 | + | |
| 1453 | + | |
| 1454 | + | |
| 1455 | + | |
| 1456 | + | |
| 1457 | + | |
| 1458 | + | |
| 1459 | + | |
| 1460 | + | |
| 1461 | + | |
| 1462 | + | |
| 1463 | + | |
| 1464 | + | |
| 1465 | + | |
| 1466 | + | |
| 1467 | + | |
| 1468 | + | |
| 1469 | + | |
| 1470 | + | |
| 1471 | + | |
| 1472 | + | |
| 1473 | + | |
| 1474 | + | |
| 1475 | + | |
| 1476 | + | |
| 1477 | + | |
| 1478 | + | |
| 1479 | + | |
| 1480 | + | |
| 1481 | + | |
| 1482 | + | |
| 1483 | + | |
| 1484 | + | |
| 1485 | + | |
| 1486 | + | |
| 1487 | + | |
| 1488 | + | |
| 1489 | + | |
| 1490 | + | |
| 1491 | + | |
| 1492 | + | |
| 1493 | + | |
| 1494 | + | |
| 1495 | + | |
| 1496 | + | |
| 1497 | + | |
| 1498 | + | |
| 1499 | + | |
| 1500 | + | |
| 1501 | + | |
| 1502 | + | |
| 1503 | + | |
| 1504 | + | |
| 1505 | + | |
| 1506 | + | |
| 1507 | + | |
| 1508 | + | |
| 1509 | + | |
| 1510 | + | |
| 1511 | + | |
| 1512 | + | |
| 1513 | + | |
| 1514 | + | |
| 1515 | + | |
| 1516 | + | |
| 1517 | + | |
| 1518 | + | |
| 1519 | + | |
| 1520 | + | |
| 1521 | + | |
| 1522 | + | |
| 1523 | + | |
| 1524 | + | |
| 1525 | + | |
| 1526 | + | |
| 1527 | + | |
| 1528 | + | |
| 1529 | + | |
| 1530 | + | |
| 1531 | + | |
| 1532 | + | |
| 1533 | + | |
| 1534 | + | |
| 1535 | + | |
1412 | 1536 | | |
1413 | 1537 | | |
1414 | 1538 | | |
1415 | 1539 | | |
1416 | 1540 | | |
1417 | 1541 | | |
1418 | 1542 | | |
| 1543 | + | |
| 1544 | + | |
| 1545 | + | |
1419 | 1546 | | |
1420 | 1547 | | |
1421 | 1548 | | |
1422 | 1549 | | |
1423 | 1550 | | |
1424 | 1551 | | |
1425 | 1552 | | |
1426 | | - | |
| 1553 | + | |
| 1554 | + | |
| 1555 | + | |
| 1556 | + | |
| 1557 | + | |
1427 | 1558 | | |
1428 | 1559 | | |
1429 | 1560 | | |
| |||
1440 | 1571 | | |
1441 | 1572 | | |
1442 | 1573 | | |
| 1574 | + | |
| 1575 | + | |
| 1576 | + | |
| 1577 | + | |
| 1578 | + | |
1443 | 1579 | | |
1444 | 1580 | | |
1445 | 1581 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
239 | 239 | | |
240 | 240 | | |
241 | 241 | | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
242 | 246 | | |
243 | 247 | | |
244 | 248 | | |
| |||
287 | 291 | | |
288 | 292 | | |
289 | 293 | | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
290 | 298 | | |
291 | 299 | | |
292 | 300 | | |
| |||
0 commit comments