github-actions[bot] commented on code in PR #67628: URL: https://github.com/apache/doris/pull/67628#discussion_r3978199456
########## 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: [P2] Make the nullable 'consistent' comparator irreflexive This CASE returns `-1` for `(NULL, NULL)` because `x IS NULL` wins before `y` is considered, so with the three NULL elements in this input `less(null, null)` is true. That is not the consistent comparator promised by the comment, and the exact expected array is again relying on behavior outside the sorting contract instead of covering the valid nullable path. Please handle `x IS NULL AND y IS NULL` first and return `0`, then keep the one-sided NULL branches. ########## 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: [P1] Avoid another ordering algorithm with the same comparator contract `make_heap`/`sort_heap` do not make an arbitrary SQL predicate safe: [C++ requires](https://eel.is/c++draft/alg.sorting.general) their comparator to induce a strict weak ordering, and [`sort_heap` additionally requires](https://eel.is/c++draft/sort.heap) `[first,last)` to already be a valid heap. The new `(x, y) -> -1` case makes `less(x, x)` true, so `make_heap` has no contract-valid postcondition and the next call violates `sort_heap`'s precondition. Current unchecked implementations happen to keep their indices bounded, but libstdc++ debug mode and libc++ debug hardening explicitly abort on this input, and other implementations are free to rely on the violated requirements. Please use a Doris-owned permutation routine whose progress, accesses, and permutation preservation are independent of comparator answers, so the no-crash guarantee does not itself rely on out-of-contract library behavior. -- 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]
