mrhhsg opened a new pull request, #67628:
URL: https://github.com/apache/doris/pull/67628
### What problem does this PR solve?
Issue Number: None
Problem Summary:
`array_sort` hands the user's lambda comparator straight to `std::sort`.
libstdc++'s introsort relies on the comparator being a deterministic strict
weak ordering: its unguarded partition and unguarded insertion loops walk
past the range as soon as that contract is broken. A comparator such as
```sql
SELECT array_sort(
(x, y) -> IF(x > 100 AND y > 100, -1, IF(x < y, -1, IF(x = y, 0, 1))),
[1, ..., 10, 101, ..., 160]);
```
therefore crashes BE with SIGSEGV in `ArraySortFunction::execute` /
`std::__introsort_loop`, and the same happens for a non-deterministic
comparator like `(x, y) -> IF(random() < 0.5, -1, 1)`.
This PR adds `bounded_stable_sort`, a bottom-up merge sort in which every
element access is clamped to `[first, last)` regardless of what the
comparator answers, and uses it in `array_sort`. With a consistent comparator
the result is the same as `std::stable_sort`; with an inconsistent one the
order is unspecified but the output is always a permutation of the input and
BE stays alive. Comparison count is unchanged (O(n log n)), which is what
dominates because every comparison evaluates the lambda.
As a side effect the sort is now stable: elements the comparator reports as
equal keep their input order.
### Release note
None
### Check List (For Author)
- Test:
- Unit Test: `be/test/util/bounded_stable_sort_test.cpp` covers agreement
with `std::stable_sort` (including stability), the reported
inconsistent
comparator, always-true / always-false comparators and a random
comparator, with every index range-checked.
- Regression test: `test_array_sort_lambda_comparator` covers the
reported comparator on literal and table input, an always-less and a
random comparator, and large / nullable arrays with a consistent
comparator.
- Behavior changed: Yes. `array_sort` with a lambda comparator no longer
crashes BE on a comparator that is not a strict weak ordering, and equal
elements now keep their input order.
- Does this need documentation: No
https://claude.ai/code/session_016A7UJu7EA7j4NkGz3yjkt6
--
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]
