[Improvement](topn) order by key topn query optimization by xiaokang · Pull Request #15663 · apache/doris

xiaokang · 2023-01-05T16:51:39Z

Proposed changes

Issue Number: close #xxx

Problem summary

Describe your changes.

Optimize for order by key topn query like SELECT * FROM table1 ORDER BY k1, k2 LIMIT n in which k1 and k2 is the prefix of table sort key.

This optimization is only for table with DUP_KEYS and UNQIUE_KEYS with merge on write.

Checklist(Required)

Does it affect the original behavior:
- Yes
- No
- I don't know
Has unit tests been added:
- Yes
- No
- No Need
Has document been added or modified:
- Yes
- No
- No Need
Does it need to update dependencies:
- Yes
- No
Are there any changes that cannot be rolled back:
- Yes (If Yes, please explain WHY)
- 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 · 2023-01-05T16:58:28Z

clang-tidy review says "All clean, LGTM! 👍"

hello-stephen · 2023-01-05T19:45:34Z

TeamCity pipeline, clickbench performance test result:
the sum of best hot time: 35.1 seconds
load time: 476 seconds
storage size: 17172148092 Bytes
https://doris-community-test-1308700295.cos.ap-hongkong.myqcloud.com/tmp/20230202144437_clickbench_pr_89579.html

github-actions

clang-tidy made some suggestions

github-actions · 2023-01-06T08:44:14Z

+std::string MutableBlock::dump_names() const {
+    std::stringstream out;
+    for (auto it = _names.begin(); it != _names.end(); ++it) {
+        if (it != _names.begin()) out << ", ";


warning: statement should be inside braces [readability-braces-around-statements]

Suggested change

if (it != _names.begin()) out << ", ";

if (it != _names.begin()) { out << ", ";

}

github-actions · 2023-01-07T14:52:53Z

clang-tidy review says "All clean, LGTM! 👍"

github-actions

clang-tidy made some suggestions

github-actions · 2023-01-16T09:48:31Z

+        const MutableBlock* _mutable_block = nullptr;
+        const std::vector<uint32_t>* _compare_columns;
+        // reverse the compare order
+        const bool _is_reverse = false;


warning: private field '_is_reverse' is not used [clang-diagnostic-unused-private-field]

const bool _is_reverse = false; ^

github-actions · 2023-02-01T16:07:48Z

clang-tidy review says "All clean, LGTM! 👍"

github-actions · 2023-02-01T16:09:44Z

clang-tidy review says "All clean, LGTM! 👍"

* delete setting read_options.block_row_max to key topn limit * fix core by delete rs_reader _empty logic

since key is already sorted and topn_next only need first N rows from each segment, but runtime predicate will filter some rows and read more than N rows. should add add for order by none-key column, since none-key column is not sorted and all rows should be read, so runtime predicate will reduce rows for topn node

github-actions · 2023-02-02T09:03:45Z

clang-tidy review says "All clean, LGTM! 👍"

Gabriel39

LGTM

Issue Number: close http://jira.selectdb-in.cc/browse/CORE-1462 Describe the overview of changes. commit e1697741a82f875ca42b0d18caa7972eaa225bee Author: Kang <[email protected]> Date: Thu Jan 19 22:59:29 2023 +0800 [opt](test) scalar_types_p0 use 100k lines dataset and scalar_types_p2 use 1000k (apache#16104) commit 33a47e8d02644123ffd8c5c4353653c1c175e96a Author: Kang <[email protected]> Date: Wed Jan 18 14:17:24 2023 +0800 [testcase](bitmap index)bitmap index testcase (apache#15975) * add bitmap index testcases for all scalar types commit 260a631441834ca7e23da4b77c922eb818eddca7 Author: Kang <[email protected]> Date: Mon Jan 16 16:49:59 2023 +0800 [regression-test](topn)add test cases for nonkey topn query for each scalar type (apache#15790) related to apache#15558 apache#15693 1. dup key table with 17 scalar datatypes 2. unique key table with mow enabled 3. unique key table with mow disabled commit 81cea5219ae86df950f10aa123072df78c7cdf23 Author: Kang <[email protected]> Date: Sun Feb 19 23:28:33 2023 +0800 [bugfix](topn) fix topn read_orderby_key_columns nullptr (apache#16896) The SQL `SELECT nationkey FROM regression_test_query_p0_limit.tpch_tiny_nation ORDER BY nationkey DESC LIMIT 5` make be core dump since dereference a nullptr `read_orderby_key_columns in VCollectIterator::_topn_next`, triggered by skipping _colname_to_value_range init in apache#16818 . This PR makes two changes: 1. avoid read_orderby_key_columns nullptr in TabletReader::_init_orderby_keys_param 2. return error if read_orderby_key_columns is nullptr unexpected in VCollectIterator::_topn_next to avoid core dump commit 2fee1d1d79942e49eddaafdc2b49e49b0651b109 Author: Kang <[email protected]> Date: Fri Feb 10 12:56:33 2023 +0800 [Improvement](topn) add limit threashold session variable and fuzzy for topn optimizations (apache#16514) 1. add limit threshold for topn runtime pushdown and key topn optimization 2. use unified session variable topn_opt_limit_threshold for all topn optimizations 3. add fuzzy support for topn_opt_limit_threshold commit 1696bed39129fcc891f32f64ff1fb43f9531fcd4 Author: Kang <[email protected]> Date: Thu Feb 2 09:13:32 2023 +0800 [bugfix](topn) fix topn runtime predicate getting value bug for decimal type (apache#16331) * fix topn runtime predicate getting value bug for decimal type * fix cast_to_string bug for TYPE_DECIMALV2 commit d70cdf61521a23417c9bc734a3cdb668265a15b0 Author: Kang <[email protected]> Date: Wed Feb 22 16:18:46 2023 +0800 topn sync doris order by key topn query optimization apache#15663 commit 1df514c8f0b66ae9a8438617163a31848e519949 Author: Kang <[email protected]> Date: Wed Feb 22 15:14:43 2023 +0800 sync with doris runtime prune for topn query apache#15558

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

…y prefix ### What problem does this PR solve? Issue Number: None Related PR: apache#15663 Problem Summary: Follow-up from review: the fix stays the one decision in BetaRowsetReader (do not skip rows equal on the ORDER BY key prefix, even for UNIQUE_KEYS), with a one-line comment. The extra check in VMergeIterator's compare contract that rejected is_unique together with read_orderby_key_columns, its comment on new_merge_iterator and its unit test are removed: no caller passes that combination any more, and the change is meant to stay a one-line fix that backports as is. ### Release note None ### Check List (For Author) - Test: Unit Test / Regression test - BetaRowsetTest and VGenericIteratorsTest: 23 pass. - fault_injection_p0/test_mow_topn_key_prefix_overlapping_segments passes. - Behavior changed: No - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>

### What problem does this PR solve? Issue Number: None Related PR: apache#15663 Problem Summary: Comment only: the condition in BetaRowsetReader now says why the merge of a storage TopN must not drop the older versions of a key (it merges by the ORDER BY key prefix, on which rows of different keys compare equal) and why no duplicate key comes back (it only reads merge-on-write tables, whose delete bitmap already filters the older versions). ### Release note None ### Check List (For Author) - Test: Unit Test - BetaRowsetTest and VGenericIteratorsTest: 23 pass; BE builds. - Behavior changed: No - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>

…rite storage TopN ### What problem does this PR solve? Issue Number: None Related PR: apache#15663 Problem Summary: Storage TopN on a merge-on-write table merged overlapping segments by the ORDER BY key prefix but still dropped "same key" rows (`is_unique`), so `ORDER BY <key prefix> LIMIT n` lost rows that share the prefix; now the merge drops rows only when it compares the whole key, since the delete bitmap already filters older versions. ### Release note Fix `ORDER BY <key prefix> LIMIT n` on a merge-on-write UNIQUE KEY table returning wrong rows when one load wrote rows sharing that prefix into several segments of one rowset. ### Check List (For Author) - Test: Unit Test / Regression test - New UT in BetaRowsetTest; new regression fault_injection_p0/test_mow_topn_key_prefix_overlapping_segments (fails before the fix). - Behavior changed: Yes, the fix above. - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>

github-actions Bot added area/planner Issues or PRs related to the query planner area/vectorization labels Jan 5, 2023

morningman added the dev/1.2.1 label Jan 6, 2023

github-actions Bot reviewed Jan 6, 2023

View reviewed changes

morningman added dev/1.2.2 and removed dev/1.2.1 labels Jan 10, 2023

xiaokang force-pushed the key_topn_opt branch from bcd9089 to 809e555 Compare January 16, 2023 09:41

github-actions Bot reviewed Jan 16, 2023

View reviewed changes

Gabriel39 reviewed Jan 17, 2023

View reviewed changes

Comment thread be/src/vec/olap/vcollect_iterator.h Resolved

Comment thread be/src/vec/olap/vcollect_iterator.h Resolved

Comment thread be/src/vec/olap/vcollect_iterator.cpp Resolved

morningman removed the dev/1.2.2 label Jan 30, 2023

xiaokang force-pushed the key_topn_opt branch from 809e555 to 5961ee2 Compare February 1, 2023 15:54

xiaokang and others added 14 commits February 2, 2023 16:54

limit use_topn_opt to DUP_KEYS and UNIQUE_KEYS with merge on write

c85d152

pick topn opt for order by keys prefix

6f8ce82

clean up comment and log

e7f38f8

enable topn opt only in vectorized mode

1b14410

delete setting read_options.block_row_max to key topn limit (apache#896)

3d70545

fix key topn opt rs empty core (apache#899)

37acd56

* delete setting read_options.block_row_max to key topn limit * fix core by delete rs_reader _empty logic

fix order by key limit n coredump (apache#1037)

d519995

fix merge error

5ca941c

[feature-dynamic-table](vec/block) add names to MutableBlock

40af5ea

fix pick error

0c855d0

fix mutable block names in vcollect_iterator

68e1689

clang format

9e7973e

fix core in UNIQUE_KEYS with merge_on_write

0678681

xiaokang added 8 commits February 2, 2023 16:54

clang format

ee84f2e

support order by multiple key columns

d087ef2

fix BlockRowposComparator::operator() _is_reverse

dd1f18d

fix merge conflict

4545c62

check use_topn_next() instead of limit > 0

57e8dd7

avoid tablet_schema nullptr

960ee96

fix review comments and 2 key topn compare bug

9d7a5a6

clang format

deae14c

xiaokang force-pushed the key_topn_opt branch from 0e6c0ea to deae14c Compare February 2, 2023 08:54

Gabriel39 approved these changes Feb 6, 2023

View reviewed changes

Gabriel39 merged commit 737c73d into apache:master Feb 6, 2023

Navigation Menu

Repository navigation

[Improvement](topn) order by key topn query optimization - #15663

[Improvement](topn) order by key topn query optimization#15663
Gabriel39 merged 22 commits into
apache:masterfrom
xiaokang:key_topn_opt

xiaokang commented Jan 5, 2023 •

edited

Loading

Uh oh!

github-actions Bot commented Jan 5, 2023

Uh oh!

hello-stephen commented Jan 5, 2023 •

edited

Loading

Uh oh!

github-actions Bot left a comment

Uh oh!

github-actions Bot Jan 6, 2023

Uh oh!

github-actions Bot commented Jan 7, 2023

Uh oh!

github-actions Bot left a comment

Uh oh!

github-actions Bot Jan 16, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

github-actions Bot commented Feb 1, 2023

Uh oh!

github-actions Bot commented Feb 1, 2023

Uh oh!

github-actions Bot commented Feb 2, 2023

Uh oh!

Gabriel39 left a comment

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

	if (it != _names.begin()) out << ", ";
	if (it != _names.begin()) { out << ", ";
	}

Conversation

xiaokang commented Jan 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Proposed changes

Problem summary

Checklist(Required)

Further comments

Uh oh!

github-actions Bot commented Jan 5, 2023

Uh oh!

hello-stephen commented Jan 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot left a comment

Choose a reason for hiding this comment

Uh oh!

github-actions Bot Jan 6, 2023

Choose a reason for hiding this comment

Uh oh!

github-actions Bot commented Jan 7, 2023

Uh oh!

github-actions Bot left a comment

Choose a reason for hiding this comment

Uh oh!

github-actions Bot Jan 16, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

github-actions Bot commented Feb 1, 2023

Uh oh!

github-actions Bot commented Feb 1, 2023

Uh oh!

github-actions Bot commented Feb 2, 2023

Uh oh!

Gabriel39 left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

xiaokang commented Jan 5, 2023 •

edited

Loading

hello-stephen commented Jan 5, 2023 •

edited

Loading