Skip to content

Commit 4e1e0ce

Browse files
authored
[bugfix](topn) fix topn optimzation wrong result for NULL values (apache#18121)
1. add PassNullPredicate to fix topn wrong result for NULL values 2. refactor RuntimePredicate to avoid using TCondition 3. refactor using ordering_exprs in fe and vsort_node
1 parent 8be4385 commit 4e1e0ce

369 files changed

Lines changed: 3193 additions & 161 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#pragma once
19+
20+
#include <cstdint>
21+
22+
#include "olap/column_predicate.h"
23+
#include "olap/rowset/segment_v2/bloom_filter.h"
24+
#include "olap/rowset/segment_v2/inverted_index_reader.h"
25+
#include "olap/wrapper_field.h"
26+
#include "vec/columns/column_dictionary.h"
27+
28+
namespace doris {
29+
30+
/**
31+
* A wrapper predicate that delegate to nested predicate
32+
* but pass (set/return true) for NULL value rows.
33+
*
34+
* At parent, it's used for topn runtime predicate.
35+
*/
36+
class AcceptNullPredicate : public ColumnPredicate {
37+
public:
38+
AcceptNullPredicate(ColumnPredicate* nested)
39+
: ColumnPredicate(nested->column_id(), nested->opposite()), _nested {nested} {}
40+
41+
PredicateType type() const override { return _nested->type(); }
42+
43+
Status evaluate(BitmapIndexIterator* iterator, uint32_t num_rows,
44+
roaring::Roaring* roaring) const override {
45+
return _nested->evaluate(iterator, num_rows, roaring);
46+
}
47+
48+
Status evaluate(const Schema& schema, InvertedIndexIterator* iterator, uint32_t num_rows,
49+
roaring::Roaring* bitmap) const override {
50+
return _nested->evaluate(schema, iterator, num_rows, bitmap);
51+
}
52+
53+
uint16_t evaluate(const vectorized::IColumn& column, uint16_t* sel,
54+
uint16_t size) const override {
55+
LOG(FATAL) << "evaluate without flags not supported";
56+
// return _nested->evaluate(column, sel, size);
57+
}
58+
59+
void evaluate_and(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
60+
bool* flags) const override {
61+
if (column.has_null()) {
62+
// copy original flags
63+
bool* original_flags = new bool[size];
64+
memcpy(original_flags, flags, size * sizeof(bool));
65+
66+
// call evaluate_and and restore true for NULL rows
67+
_nested->evaluate_and(column, sel, size, flags);
68+
for (uint16_t i = 0; i < size; ++i) {
69+
uint16_t idx = sel[i];
70+
if (original_flags[idx] && !flags[idx] && column.is_null_at(idx)) {
71+
flags[i] = true;
72+
}
73+
}
74+
} else {
75+
_nested->evaluate_and(column, sel, size, flags);
76+
}
77+
}
78+
79+
void evaluate_or(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
80+
bool* flags) const override {
81+
if (column.has_null()) {
82+
// call evaluate_or and set true for NULL rows
83+
_nested->evaluate_or(column, sel, size, flags);
84+
for (uint16_t i = 0; i < size; ++i) {
85+
uint16_t idx = sel[i];
86+
if (!flags[idx] && column.is_null_at(idx)) {
87+
flags[i] = true;
88+
}
89+
}
90+
} else {
91+
_nested->evaluate_or(column, sel, size, flags);
92+
}
93+
}
94+
95+
bool evaluate_and(const std::pair<WrapperField*, WrapperField*>& statistic) const override {
96+
// there is null in range, accept it
97+
if (statistic.first->is_null() || statistic.second->is_null()) {
98+
return true;
99+
}
100+
return _nested->evaluate_and(statistic);
101+
}
102+
103+
bool evaluate_del(const std::pair<WrapperField*, WrapperField*>& statistic) const override {
104+
return _nested->evaluate_del(statistic);
105+
}
106+
107+
bool evaluate_and(const BloomFilter* bf) const override { return _nested->evaluate_and(bf); }
108+
109+
bool can_do_bloom_filter() const override { return _nested->can_do_bloom_filter(); }
110+
111+
void evaluate_vec(const vectorized::IColumn& column, uint16_t size,
112+
bool* flags) const override {
113+
_nested->evaluate_vec(column, size, flags);
114+
if (column.has_null()) {
115+
for (uint16_t i = 0; i < size; ++i) {
116+
if (!flags[i] && column.is_null_at(i)) {
117+
// set true for NULL rows
118+
flags[i] = true;
119+
}
120+
}
121+
}
122+
}
123+
124+
void evaluate_and_vec(const vectorized::IColumn& column, uint16_t size,
125+
bool* flags) const override {
126+
if (column.has_null()) {
127+
// copy original flags
128+
bool* original_flags = new bool[size];
129+
memcpy(original_flags, flags, size * sizeof(bool));
130+
131+
// call evaluate_and_vec and restore true for NULL rows
132+
_nested->evaluate_and_vec(column, size, flags);
133+
for (uint16_t i = 0; i < size; ++i) {
134+
if (original_flags[i] && !flags[i] && column.is_null_at(i)) {
135+
flags[i] = true;
136+
}
137+
}
138+
} else {
139+
_nested->evaluate_and_vec(column, size, flags);
140+
}
141+
}
142+
143+
std::string get_search_str() const override { return _nested->get_search_str(); }
144+
145+
std::string debug_string() const override {
146+
return "passnull predicate for " + _nested->debug_string();
147+
}
148+
149+
/// Some predicates need to be cloned for each segment.
150+
bool need_to_clone() const override { return _nested->need_to_clone(); }
151+
152+
void clone(ColumnPredicate** to) const override {
153+
if (need_to_clone()) {
154+
ColumnPredicate* clone_nested;
155+
_nested->clone(&clone_nested);
156+
*to = new AcceptNullPredicate(clone_nested);
157+
}
158+
}
159+
160+
private:
161+
std::string _debug_string() const override {
162+
return "passnull predicate for " + _nested->debug_string();
163+
}
164+
165+
ColumnPredicate* _nested;
166+
};
167+
168+
} //namespace doris

‎be/src/olap/column_predicate.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -187,6 +187,8 @@ class ColumnPredicate {
187187
}
188188
uint32_t column_id() const { return _column_id; }
189189

190+
bool opposite() const { return _opposite; }
191+
190192
virtual std::string debug_string() const {
191193
return _debug_string() + ", column_id=" + std::to_string(_column_id) +
192194
", opposite=" + (_opposite ? "true" : "false");

‎be/src/runtime/runtime_predicate.cpp‎

Lines changed: 33 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -17,19 +17,22 @@
1717

1818
#include "runtime/runtime_predicate.h"
1919

20+
#include "olap/accept_null_predicate.h"
2021
#include "olap/predicate_creator.h"
2122

2223
namespace doris {
2324

2425
namespace vectorized {
2526

26-
Status RuntimePredicate::init(const PrimitiveType type) {
27+
Status RuntimePredicate::init(const PrimitiveType type, const bool nulls_first) {
2728
std::unique_lock<std::shared_mutex> wlock(_rwlock);
2829

2930
if (_inited) {
3031
return Status::OK();
3132
}
3233

34+
_nulls_first = nulls_first;
35+
3336
_predicate_arena.reset(new Arena());
3437

3538
// set get value function
@@ -111,6 +114,11 @@ Status RuntimePredicate::init(const PrimitiveType type) {
111114
}
112115

113116
Status RuntimePredicate::update(const Field& value, const String& col_name, bool is_reverse) {
117+
// skip null value
118+
if (value.is_null()) {
119+
return Status::OK();
120+
}
121+
114122
std::unique_lock<std::shared_mutex> wlock(_rwlock);
115123

116124
// TODO why null
@@ -139,18 +147,31 @@ Status RuntimePredicate::update(const Field& value, const String& col_name, bool
139147
return Status::OK();
140148
}
141149

142-
TCondition condition;
143-
condition.__set_column_name(col_name);
144-
condition.__set_column_unique_id(_tablet_schema->column(col_name).unique_id());
145-
condition.__set_condition_op(is_reverse ? ">=" : "<=");
146-
147-
// get value string from _orderby_extrem and push back to condition_values
148-
condition.condition_values.push_back(_get_value_fn(_orderby_extrem));
149-
150-
VLOG_DEBUG << "update runtime predicate condition " << condition;
151-
152150
// update _predictate
153-
_predictate.reset(parse_to_predicate(_tablet_schema, condition, _predicate_arena.get(), false));
151+
int32_t col_unique_id = _tablet_schema->column(col_name).unique_id();
152+
const TabletColumn& column = _tablet_schema->column_by_uid(col_unique_id);
153+
uint32_t index = _tablet_schema->field_index(col_unique_id);
154+
auto val = _get_value_fn(_orderby_extrem);
155+
ColumnPredicate* pred = nullptr;
156+
if (is_reverse) {
157+
// For DESC sort, create runtime predicate col_name >= min_top_value
158+
// since values that < min_top_value are less than any value in current topn values
159+
pred = create_comparison_predicate<PredicateType::GE>(column, index, val, false,
160+
_predicate_arena.get());
161+
} else {
162+
// For ASC sort, create runtime predicate col_name <= max_top_value
163+
// since values that > min_top_value are large than any value in current topn values
164+
pred = create_comparison_predicate<PredicateType::LE>(column, index, val, false,
165+
_predicate_arena.get());
166+
}
167+
168+
// For NULLS FIRST, wrap a AcceptNullPredicate to return true for NULL
169+
// since ORDER BY ASC/DESC should get NULL first but pred returns NULL
170+
// and NULL in where predicate will be treated as FALSE
171+
if (_nulls_first) {
172+
pred = new AcceptNullPredicate(pred);
173+
}
174+
_predictate.reset(pred);
154175

155176
return Status::OK();
156177
}

‎be/src/runtime/runtime_predicate.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ class RuntimePredicate {
4545
public:
4646
RuntimePredicate() = default;
4747

48-
Status init(const PrimitiveType type);
48+
Status init(const PrimitiveType type, const bool nulls_first);
4949

5050
bool inited() {
5151
std::unique_lock<std::shared_mutex> wlock(_rwlock);
@@ -71,6 +71,7 @@ class RuntimePredicate {
7171
TabletSchemaSPtr _tablet_schema;
7272
std::unique_ptr<Arena> _predicate_arena;
7373
std::function<std::string(const Field&)> _get_value_fn;
74+
bool _nulls_first = true;
7475
bool _inited = false;
7576

7677
static std::string get_bool_value(const Field& field) {

‎be/src/vec/exec/scan/new_olap_scanner.cpp‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -347,6 +347,8 @@ Status NewOlapScanner::_init_tablet_reader_params(
347347

348348
if (!_state->skip_storage_engine_merge()) {
349349
TOlapScanNode& olap_scan_node = ((NewOlapScanNode*)_parent)->_olap_scan_node;
350+
// order by table keys optimization for topn
351+
// will only read head/tail of data file since it's already sorted by keys
350352
if (olap_scan_node.__isset.sort_info && olap_scan_node.sort_info.is_asc_order.size() > 0) {
351353
_limit = _parent->_limit_per_scanner;
352354
_tablet_reader_params.read_orderby_key = true;

‎be/src/vec/exec/vsort_node.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,17 +53,17 @@ Status VSortNode::init(const TPlanNode& tnode, RuntimeState* state) {
5353
// init runtime predicate
5454
if (_use_topn_opt) {
5555
auto query_ctx = state->get_query_fragments_ctx();
56-
auto first_sort_expr_node = tnode.sort_node.sort_info.sort_tuple_slot_exprs[0].nodes[0];
56+
auto first_sort_expr_node = tnode.sort_node.sort_info.ordering_exprs[0].nodes[0];
5757
if (first_sort_expr_node.node_type == TExprNodeType::SLOT_REF) {
5858
auto first_sort_slot = first_sort_expr_node.slot_ref;
59-
for (auto tuple_desc : row_desc.tuple_descriptors()) {
59+
for (auto tuple_desc : this->row_desc().tuple_descriptors()) {
6060
if (tuple_desc->id() != first_sort_slot.tuple_id) {
6161
continue;
6262
}
6363
for (auto slot : tuple_desc->slots()) {
6464
if (slot->id() == first_sort_slot.slot_id) {
65-
RETURN_IF_ERROR(
66-
query_ctx->get_runtime_predicate().init(slot->type().type));
65+
RETURN_IF_ERROR(query_ctx->get_runtime_predicate().init(
66+
slot->type().type, _nulls_first[0]));
6767
break;
6868
}
6969
}

‎fe/fe-core/src/main/java/org/apache/doris/planner/OlapScanNode.java‎

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1004,7 +1004,9 @@ public boolean checkPushSort(SortNode sortNode) {
10041004
// olap order by key: a.b.c.d
10051005
// sort key: (a) (a,b) (a,b,c) (a,b,c,d) is ok
10061006
// (a,c) (a,c,d), (a,c,b) (a,c,f) (a,b,c,d,e)is NOT ok
1007-
List<Expr> sortExprs = sortNode.getSortInfo().getMaterializedOrderingExprs();
1007+
List<Expr> sortExprs = sortNode.getSortInfo().getOrigOrderingExprs();
1008+
List<Boolean> nullsFirsts = sortNode.getSortInfo().getNullsFirst();
1009+
List<Boolean> isAscOrders = sortNode.getSortInfo().getIsAscOrder();
10081010
if (sortExprs.size() > olapTable.getDataSortInfo().getColNum()) {
10091011
return false;
10101012
}
@@ -1013,7 +1015,18 @@ public boolean checkPushSort(SortNode sortNode) {
10131015
Column tableKey = olapTable.getFullSchema().get(i);
10141016
// sort slot.
10151017
Expr sortExpr = sortExprs.get(i);
1016-
if (!(sortExpr instanceof SlotRef) || !tableKey.equals(((SlotRef) sortExpr).getColumn())) {
1018+
if (sortExpr instanceof SlotRef) {
1019+
SlotRef slotRef = (SlotRef) sortExpr;
1020+
if (tableKey.equals(slotRef.getColumn())) {
1021+
// ORDER BY DESC NULLS FIRST can not be optimized to only read file tail,
1022+
// since NULLS is at file head but data is at tail
1023+
if (tableKey.isAllowNull() && nullsFirsts.get(i) && !isAscOrders.get(i)) {
1024+
return false;
1025+
}
1026+
} else {
1027+
return false;
1028+
}
1029+
} else {
10171030
return false;
10181031
}
10191032
}

‎fe/fe-core/src/main/java/org/apache/doris/planner/OriginalPlanner.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -603,8 +603,8 @@ private void checkAndSetTopnOpt(PlanNode node) {
603603
if (child instanceof OlapScanNode && sortNode.getLimit() > 0
604604
&& ConnectContext.get() != null && ConnectContext.get().getSessionVariable() != null
605605
&& sortNode.getLimit() <= ConnectContext.get().getSessionVariable().topnOptLimitThreshold
606-
&& sortNode.getSortInfo().getMaterializedOrderingExprs().size() > 0) {
607-
Expr firstSortExpr = sortNode.getSortInfo().getMaterializedOrderingExprs().get(0);
606+
&& sortNode.getSortInfo().getOrigOrderingExprs().size() > 0) {
607+
Expr firstSortExpr = sortNode.getSortInfo().getOrigOrderingExprs().get(0);
608608
if (firstSortExpr instanceof SlotRef && !firstSortExpr.getType().isStringType()
609609
&& !firstSortExpr.getType().isFloatingPointType()) {
610610
OlapScanNode scanNode = (OlapScanNode) child;
Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
-- This file is automatically generated. You should know what you did if you want to edit this
22
-- !dup_key_topn_q01_asc --
3+
\N \N \N \N \N \N \N \N \N \N \N \N \N \N \N \N \N
4+
\N \N \N \N \N \N \N \N \N \N \N \N \N \N \N \N \N
35
2022-01-10T16:04:49 -744222108 64562066838726736.278 false 85 25637 -21148 -593493650 -11450.651 -1.167904321387118E9 32585085266732240.402 2022-09-10 2022-08-08T18:00:04 2022-11-03 54.143.193.60 [email protected] Ruskin Court 16
46
2022-01-10T16:06:02 1769095688 95858385508825939.586 false -61 -24768 8981 -1811059535 26550.553 1.898948089429888E9 6302075696085095.930 2022-04-12 2022-05-06T18:56:26 2022-01-18 70.75.107.213 [email protected] Schlimgen Way 58
57
2022-01-10T16:11:53 1906472648 30323570439371776.353 true -64 23204 -27723 1753599187 -28017.578 -8.7412093534361E7 34175877199258167.909 2023-01-07 2022-07-02T15:40:57 2022-10-09 60.230.5.23 [email protected] Summit Plaza 70
@@ -8,6 +10,4 @@
810
2022-01-10T16:19:43 -331752585 78238523737497869.470 true 0 -18857 26728 -1593527511 -3940.6157 1.011426330009696E9 30383576870508748.746 2022-10-18 2022-12-13T04:03:22 2022-04-25 114.191.125.61 [email protected] Merchant Circle 4
911
2022-01-10T16:26:01 694891812 89716246258986314.603 false -81 -31141 -32045 -1462025516 1286.6216 1.408000357577549E9 82173119133223782.614 2022-06-28 2022-08-30T06:48:08 2022-06-16 6.202.144.1 [email protected] Barnett Drive 12
1012
2022-01-10T16:34:44 1969608603 60215082108365548.380 true 77 10466 7024 -1111293463 -3119.6628 -1.98697170405241E9 47421181841164225.577 2022-01-27 2022-06-05T03:27:17 2022-05-18 150.153.19.134 [email protected] Onsgard Trail 10
11-
2022-01-10T16:38:44 397842904 11471760929161672.212 false 48 22098 -23304 -647850805 -28931.523 -2.2117236773336E8 45351058658553553.851 2022-11-28 2022-08-13T12:22:09 2022-03-18 142.44.9.89 [email protected] Iowa Lane 43
12-
2022-01-10T16:42:51 -914436742 2714763078802815.280 true -77 30692 -23058 1557401365 -25909.229 1.807346678696413E9 68043251987061973.806 2022-11-09 2022-08-04T09:16:13 2022-04-17 88.83.49.144 [email protected] Macpherson Center 25
1313

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !dup_key_topn_q01_asc_nulls_last --
3+
2022-01-10T16:04:49 -744222108 64562066838726736.278 false 85 25637 -21148 -593493650 -11450.651 -1.167904321387118E9 32585085266732240.402 2022-09-10 2022-08-08T18:00:04 2022-11-03 54.143.193.60 [email protected] Ruskin Court 16
4+
2022-01-10T16:06:02 1769095688 95858385508825939.586 false -61 -24768 8981 -1811059535 26550.553 1.898948089429888E9 6302075696085095.930 2022-04-12 2022-05-06T18:56:26 2022-01-18 70.75.107.213 [email protected] Schlimgen Way 58
5+
2022-01-10T16:11:53 1906472648 30323570439371776.353 true -64 23204 -27723 1753599187 -28017.578 -8.7412093534361E7 34175877199258167.909 2023-01-07 2022-07-02T15:40:57 2022-10-09 60.230.5.23 [email protected] Summit Plaza 70
6+
2022-01-10T16:13:51 2105767399 29408006992196347.603 true 86 18588 13544 -679723410 21493.826 1.885770666296631E9 85804384237665278.429 2023-01-07 2022-04-09T20:48:14 2022-06-22 98.145.190.138 [email protected] Southridge Street 43
7+
2022-01-10T16:17:55 1863090100 90399389135889759.150 false -45 1656 -29181 -40413678 -32730.72 4.51575752697888E8 33932341853184569.730 2022-05-23 2022-04-24T13:12:53 2022-05-06 31.182.27.9 [email protected] Glendale Park 70
8+
2022-01-10T16:19:43 -331752585 78238523737497869.470 true 0 -18857 26728 -1593527511 -3940.6157 1.011426330009696E9 30383576870508748.746 2022-10-18 2022-12-13T04:03:22 2022-04-25 114.191.125.61 [email protected] Merchant Circle 4
9+
2022-01-10T16:26:01 694891812 89716246258986314.603 false -81 -31141 -32045 -1462025516 1286.6216 1.408000357577549E9 82173119133223782.614 2022-06-28 2022-08-30T06:48:08 2022-06-16 6.202.144.1 [email protected] Barnett Drive 12
10+
2022-01-10T16:34:44 1969608603 60215082108365548.380 true 77 10466 7024 -1111293463 -3119.6628 -1.98697170405241E9 47421181841164225.577 2022-01-27 2022-06-05T03:27:17 2022-05-18 150.153.19.134 [email protected] Onsgard Trail 10
11+
2022-01-10T16:38:44 397842904 11471760929161672.212 false 48 22098 -23304 -647850805 -28931.523 -2.2117236773336E8 45351058658553553.851 2022-11-28 2022-08-13T12:22:09 2022-03-18 142.44.9.89 [email protected] Iowa Lane 43
12+
2022-01-10T16:42:51 -914436742 2714763078802815.280 true -77 30692 -23058 1557401365 -25909.229 1.807346678696413E9 68043251987061973.806 2022-11-09 2022-08-04T09:16:13 2022-04-17 88.83.49.144 [email protected] Macpherson Center 25
13+

0 commit comments

Comments
 (0)