Repository navigation
optimize topn query if order by columns is prefix of sort keys of table - #10694
Conversation
|
we test in a log matching senario, runtime of the following SQL drops significantly from 1.8s to 0.1s
|
|
Thansk @HappenLee @jackwener for careful review. The problem is fixed as we discuss. |
0243fa4 to
28d1fce
Compare
and read_orderby_key_reverse for olap scanner
eg. SELECT * from t_log WHERE t>t1 AND t<t2 ORDER BY t DESC LIMIT 100
If the ORDER BY columns is the prefix of the sort key of table, it can
be greatly optimized to read much fewer data instead of read all data
between t1 and t2.
By leveraging the same order of ORDER BY columns and sort key of table,
just read the LIMIT N rows for each related segment and merge N rows.
1. set read_orderby_key to true for read_params and _reader_context
if olap_scan_node's sort info is set.
2. set read_orderby_key_reverse to true for read_params and _reader_context
if is_asc_order is false.
3. rowset reader force merge read segments if read_orderby_key is true.
4. block reader and tablet reader force merge read rowsets if read_orderby_key is true.
5. for ORDER BY DESC, read and compare in reverse order
5.1 segment iterator read backward using a new BackwardBitmapRangeIterator and
reverse the result block before return to caller.
5.2 VCollectIterator::LevelIteratorComparator, VMergeIteratorContext return
opposite result for _is_reverse order in its compare function.
| nrows_read += rows_to_read; | ||
| } | ||
| } while (nrows_read < nrows_read_limit); | ||
| // if _opts.read_orderby_key_reverse is true, only read one range for fast reverse purpose |
There was a problem hiding this comment.
I don't quite understand the intent here? Can you explain it in detail?
There was a problem hiding this comment.
OK. It's related to the code 'reverse block row order' at the end of SegmentIterator::next_batch.
If we read more than one range in reverse order here, such as range10 with rows 9000 ~ 10000 and range9 with rows 8000 ~ 9000, the block will contain non-continous ordered rows 9000 ~ 10000,8000 ~ 9000. Then the reverse block at the end of next_batch will get rows 9000 ~ 8000,10000 ~ 9000. It's not totally in reversed order.
|
PR approved by at least one committer and no changes requested. |
|
PR approved by anyone and no changes requested. |
… storage TopN fix ### What problem does this PR solve? Issue Number: None Related PR: apache#15663 Problem Summary: Follow-up to the previous commit, from its review: - The regression test also covers `ORDER BY k1 DESC LIMIT 10` and a cluster key table read by `ORDER BY <cluster key prefix> LIMIT 10`, which lost rows the same way (on the unfixed BE they return k1 = 19..10 and v = 0..9 once each), checks with explain that the TopN reaches the scan, and adds a table whose two segments hold the same full keys: the storage TopN no longer drops rows itself, and the delete bitmap of the merge-on-write table hides the older row of each key, so every key comes back once with the newest value. The needless `SET batch_size = 4064` is gone; the `.out` is regenerated on the fixed build. - The compare contract error names the condition it checks, `is_unique with read_orderby_key_columns set`, and the unit test matches it; the comments say rows equal on the ORDER BY columns may be different keys, not that they are. - The rowset writing helper of BetaRowsetTest stops at the first failed step and prints its status. Corrections to the previous commit message: the bug came with apache#15663 (2023-02-06), which extended the storage TopN to merge-on-write tablets; apache#10694 had introduced the merge by the ORDER BY columns for DUP tablets only, which drop nothing. The query returns wrong rows: the rows equal on the prefix are lost and rows of later prefixes take their place, so it is short only when too few rows remain. Every branch since apache#15663 has the bug (branch-2.0 to branch-4.2 by reading the code); a backport takes the BetaRowsetReader change only, since the release branches have no compare contract check and `enable_segment_limit_pushdown` exists only on branch-4.2 and master. ### Release note None ### Check List (For Author) - Test: Unit Test / Regression test - BetaRowsetTest and VGenericIteratorsTest: 24 pass. - fault_injection_p0/test_mow_topn_key_prefix_overlapping_segments passes on the fixed BE; on an unfixed BE the prefix, DESC and cluster key queries return the wrong rows above, and the same-key table returns one row per key with the newest value. - clang-format 16 and clang-tidy clean on the changed lines; build hygiene passes. - Behavior changed: No - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>
Proposed changes
Issue Number: close #10646
BE part for #10646. The FE part is #10647.
Problem Summary:
Describe the overview of changes.
There is a common query pattern to find latest time serials data.
eg. SELECT * from t_log WHERE t>t1 AND t<t2 ORDER BY t DESC LIMIT 100
If the ORDER BY columns is the prefix of the sort key of table, it can
be greatly optimized to read much fewer data instead of read all data
between t1 and t2.
By leveraging the same order of ORDER BY columns and sort key of table,
just read the LIMIT N rows for each related segment and merge N rows.
set read_orderby_key to true for read_params and _reader_context
if olap_scan_node's sort info is set.
set read_orderby_key_reverse to true for read_params and _reader_context
if is_asc_order is false.
rowset reader force merge read segments if read_orderby_key is true.
block reader and tablet reader force merge read rowsets if read_orderby_key is true.
for ORDER BY DESC, read and compare in reverse order
5.1 segment iterator read backward using a new BackwardBitmapRangeIterator and
reverse the result block before return to caller.
5.2 VCollectIterator::LevelIteratorComparator, VMergeIteratorContext return
opposite result for _is_reverse order in its compare function.
Checklist(Required)
Further comments
If this is a relatively large or complex change, kick off the discussion at [email protected] by explaining why you chose the solution you did and what alternatives you considered, etc...