Skip to content

optimize topn query if order by columns is prefix of sort keys of table - #10694

Merged
yiguolei merged 17 commits into
apache:masterfrom
xiaokang:key_topn_opt2
Aug 9, 2022
Merged

yiguolei merged 17 commits into
apache:masterfrom
xiaokang:key_topn_opt2

Conversation

@xiaokang

@xiaokang xiaokang commented Jul 8, 2022 •

Copy link
Copy Markdown
Contributor

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.

  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.

Checklist(Required)

  1. Does it affect the original behavior: (No)
  2. Has unit tests been added: (No)
  3. Has document been added or modified: (No Need)
  4. Does it need to update dependencies: (No)
  5. Are there any changes that cannot be rolled back: (No)

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

@github-actions github-actions Bot added area/planner Issues or PRs related to the query planner area/vectorization labels Jul 8, 2022
@xiaokang xiaokang changed the title Key topn opt2 optimize topn query if order by columns is prefix of sort keys of table Jul 8, 2022
Comment thread be/src/olap/reader.cpp Resolved
Comment thread be/src/vec/olap/vcollect_iterator.h Resolved
@xiaokang

Copy link
Copy Markdown
Contributor Author

we test in a log matching senario, runtime of the following SQL drops significantly from 1.8s to 0.1s

SELECT * FROM log_table WHERE timestamp > t1 ORDER BY timestamp DESC LIMIT 100

Comment thread be/src/vec/olap/vcollect_iterator.cpp Resolved
Comment thread be/src/vec/olap/vcollect_iterator.cpp Resolved
Comment thread be/src/vec/olap/vgeneric_iterators.cpp Resolved
@xiaokang

Copy link
Copy Markdown
Contributor Author

Thansk @HappenLee @jackwener for careful review. The problem is fixed as we discuss.

jackwener and others added 11 commits August 2, 2022 16:37
 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

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't quite understand the intent here? Can you explain it in detail?

@xiaokang xiaokang Aug 4, 2022 •

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

HappenLee
HappenLee previously approved these changes Aug 4, 2022

@HappenLee HappenLee left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@github-actions github-actions Bot added the approved Indicates a PR has been approved by one committer. label Aug 4, 2022
@github-actions

github-actions Bot commented Aug 4, 2022

Copy link
Copy Markdown
Contributor

PR approved by at least one committer and no changes requested.

@github-actions

github-actions Bot commented Aug 4, 2022

Copy link
Copy Markdown
Contributor

PR approved by anyone and no changes requested.

jackwener
jackwener previously approved these changes Aug 4, 2022

@jackwener jackwener left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@xiaokang
xiaokang dismissed stale reviews from jackwener and HappenLee via 7d9b269 August 8, 2022 11:42
@github-actions github-actions Bot removed the approved Indicates a PR has been approved by one committer. label Aug 8, 2022

@yiguolei yiguolei left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@yiguolei
yiguolei merged commit f9b1517 into apache:master Aug 9, 2022
csun5285 added a commit to csun5285/doris that referenced this pull request Oct 28, 2026
… 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]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

area/planner Issues or PRs related to the query planner area/vectorization reviewed

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[Feature] Push sort to the olapscan.

4 participants