mrhhsg commented on code in PR #67628:
URL: https://github.com/apache/doris/pull/67628#discussion_r4069563169
##########
be/src/exprs/lambda_function/varray_sort_function.cpp:
##########
@@ -202,33 +203,43 @@ class ArraySortFunction : public LambdaFunction {
};
const int lambda_result_base =
static_cast<int>(lambda_block.columns());
- for (int row = 0; row < input_rows; ++row) {
- auto start = off_data[row - 1];
- auto end = off_data[row];
- std::sort(&permutation[start], &permutation[end],
[&](size_t i, size_t j) {
- prepare_lambda_input(i, 0);
- prepare_lambda_input(j, 1);
- int lambda_res_id = lambda_result_base;
- auto status =
- children[0]->execute(context,
&lambda_block, &lambda_res_id);
- if (!status.ok()) [[unlikely]] {
- throw Exception(Status::InternalError(
- "when execute array_sort lambda
function: {}",
- status.to_string()));
- }
+ // Returns true when element i sorts before element j
according to the
+ // user's lambda.
+ auto less = [&](size_t i, size_t j) {
+ prepare_lambda_input(i, 0);
+ prepare_lambda_input(j, 1);
+ int lambda_res_id = lambda_result_base;
+ auto status = children[0]->execute(context,
&lambda_block, &lambda_res_id);
+ if (!status.ok()) [[unlikely]] {
+ throw Exception(Status::InternalError(
+ "when execute array_sort lambda function:
{}",
+ status.to_string()));
+ }
- // raw_res_col maybe columnVector or ColumnConst
- ColumnPtr raw_res_col =
-
lambda_block.get_by_position(lambda_res_id).column;
- ColumnPtr full_res_col =
raw_res_col->convert_to_full_column_if_const();
+ // raw_res_col maybe columnVector or ColumnConst
+ ColumnPtr raw_res_col =
lambda_block.get_by_position(lambda_res_id).column;
+ ColumnPtr full_res_col =
raw_res_col->convert_to_full_column_if_const();
- // only -1, 0, 1
- long cmp = assert_cast<const
ColumnInt8*>(full_res_col.get())
- ->get_data()[0];
- lambda_block.erase_tail(lambda_result_base);
+ // only -1, 0, 1
+ long cmp =
+ assert_cast<const
ColumnInt8*>(full_res_col.get())->get_data()[0];
+ lambda_block.erase_tail(lambda_result_base);
- return cmp < 0;
- });
+ return cmp < 0;
+ };
+
+ for (int row = 0; row < input_rows; ++row) {
+ auto start = off_data[row - 1];
+ auto end = off_data[row];
+ // The comparator is user SQL and may violate strict
weak ordering, or
+ // even be non-deterministic. std::sort relies on the
comparator to stop
+ // its unguarded loops and reads outside the range
when it is broken,
+ // which crashes BE. Heap sort bounds every access by
the range length
+ // and only uses the comparator to pick which element
to move, so it is
+ // safe with any comparator; an inconsistent
comparator yields an
+ // unspecified order instead of a crash.
Review Comment:
Done in 76ed1d6. Replaced `std::make_heap`/`std::sort_heap` with a
Doris-owned bottom-up merge sort, `sort_with_untrusted_comparator`
(`be/src/util/untrusted_comparator_sort.h`). Every loop bound and access
depends only on the range length; the comparator only picks which in-range
element is copied next, so for any comparator it terminates within `n *
ceil(log2 n)` calls, never reads outside the range and yields a permutation.
For a consistent comparator it is a stable sort with fewer lambda evaluations
than the heap sort (and O(n) for already sorted input).
`UntrustedComparatorSortTest` covers consistent, always-less, never-less,
partially reflexive and random comparators plus exception propagation.
##########
regression-test/suites/query_p0/sql_functions/array_functions/test_array_sort_lambda_comparator.groovy:
##########
@@ -0,0 +1,85 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+suite("test_array_sort_lambda_comparator") {
+ // A comparator that is not a strict weak ordering must not crash BE.
Every pair of values
+ // above 100 compares as "less" in both directions, and there are far more
than the
+ // insertion-sort threshold of such values. Only the cardinality is
asserted because the
+ // resulting order is unspecified for such a comparator.
+ order_qt_inconsistent_comparator_literal """
+ SELECT cardinality(array_sort(
+ (x, y) -> IF(x > 100 AND y > 100, -1, IF(x < y, -1, IF(x = y, 0,
1))),
+ [1,2,3,4,5,6,7,8,9,10,101,102,103,104,105,106,107,108,109,110,
+
111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,
+
131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,
+ 151,152,153,154,155,156,157,158,159,160]))
+ """
+
+ // A comparator that says "less" for every pair.
+ order_qt_always_less_comparator """
+ SELECT cardinality(array_sort((x, y) -> -1, array_range(1, 200)))
+ """
+
+ // A non-deterministic comparator changes its answer between calls on the
same pair.
+ order_qt_random_comparator """
+ SELECT cardinality(array_sort((x, y) -> IF(random() < 0.5, -1, 1),
array_range(1, 200)))
+ """
+
+ // Consistent comparators on arrays larger than the insertion-sort
threshold still sort.
+ order_qt_large_desc """
+ SELECT array_sort((x, y) -> IF(x < y, 1, IF(x = y, 0, -1)),
array_range(1, 100))
+ """
+ order_qt_large_with_null """
+ SELECT array_sort((x, y) -> CASE WHEN x IS NULL THEN -1
Review Comment:
Done in 76ed1d6. The CASE now handles `x IS NULL AND y IS NULL` first and
returns 0, keeping the one-sided NULL branches, and the `.out` was regenerated.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
