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

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 dev@doris.apache.org 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

be/src/vec/core/block.cpp

+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

be/src/vec/olap/vcollect_iterator.h

+        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; ^

be/src/vec/olap/vcollect_iterator.h

be/src/vec/olap/vcollect_iterator.cpp

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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> 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 <kxiao.tiger@gmail.com> Date: Wed Feb 22 16:18:46 2023 +0800 topn sync doris order by key topn query optimization apache#15663 commit 1df514c8f0b66ae9a8438617163a31848e519949 Author: Kang <kxiao.tiger@gmail.com> Date: Wed Feb 22 15:14:43 2023 +0800 sync with doris runtime prune for topn query apache#15558

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

be/src/vec/olap/vcollect_iterator.h Outdated Show resolved Hide resolved

be/src/vec/olap/vcollect_iterator.h Outdated Show resolved Hide resolved

be/src/vec/olap/vcollect_iterator.cpp Outdated Show resolved Hide 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

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

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

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

Uh oh!

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

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

xiaokang commented Jan 5, 2023 •

edited

Loading

hello-stephen commented Jan 5, 2023 •

edited

Loading