liaoxin01 opened a new pull request, #66588:
URL: https://github.com/apache/doris/pull/66588
### What problem does this PR solve?
> **Stacked on #66545.** Until that one merges, the diff here shows its
commit as
> well. The change this PR is about is the second commit,
> `[improvement](load) sort memtable with the vectorized ColumnSorter`.
Problem Summary:
`MemTable::_sort()` ran its own multi-key sort: `pdqsort` over the row array,
with the comparator passed as a `std::function` that called the virtual
`IColumn::compare_at` once per comparison. Every comparison therefore paid an
indirect call, a virtual dispatch and two random accesses into the block
before
it could even look at the key.
The query engine already has the sort this needs. `ColumnSorter`
(`be/src/exec/sort/sort_block.h`) implements the same sort-and-tie algorithm
--
sort by a key column, mark equal ranges, refine within them using the next
key
column -- but keeps an inline copy of the key next to the row id, so a
comparison
becomes a typed, inlinable operation on a compact array instead of a chain of
random accesses.
This PR makes `_sort()` and `_sort_by_cluster_keys()` build an
`IColumn::Permutation` and run it through `ColumnSorter`.
`_sort_one_column()`
and `class Tie` have no users left and are removed. `_sort_by_cluster_keys()`
no longer needs a row object per row either: the LSN sidecar it was carrying
is
already indexed by row position, so the permutation can reorder it directly.
Measured with a micro-benchmark on 7.05M rows, one key column, Release build:
| key type | current | ColumnSorter | speedup |
| --- | --- | --- | --- |
| int32 | 13.2 s | 0.96 s | 13.7x |
| int64 | 13.3 s | 1.07 s | 12.4x |
| decimal128(20,2) | 13.7 s | 1.28 s | 10.7x |
| varchar ~4B | 19.6 s | 3.03 s | 6.5x |
| varchar ~40B | 21.9 s | 3.75 s | 5.8x |
| nullable int32 | 16.0 s | 1.04 s | 15.5x |
| nullable varchar ~4B | 25.4 s | 2.81 s | 9.0x |
Fixed-width keys gain the most because their inline value is the value
itself;
string keys still dereference the arena for the `memcmp`, so the longer the
key
the smaller the gain. No key type regressed.
The motivating case was a load whose profile showed `MemTableSortTime` at 83
s
across 7 memtables of a single tablet, with the sink blocked in
`WaitFlushLimitTime` for 45 s behind it.
### Memory
Keeping a copy of the key next to each row id costs memory in proportion to
the
key width: 8 B/row for `INT32`, 16 B for `INT64`, 24 B for a `StringRef`, 32
B
for `Decimal128` after alignment. It is a `std::vector` local to
`ColumnSorter::_sort_by_inline_permutation`, so it is released between key
columns and the peak holds one of them, plus 8 B/row for the permutation and
1 B/row for the equal flags.
That is why #66545 comes first. Against the 24 bytes per row the memtable
spends
on the rows themselves after that change, the peak of the two together is
below
what the previous sort needed, for every key type:
| key type | before both PRs | after both |
| --- | --- | --- |
| int32 | 592 MB | 288 MB |
| int64 | 592 MB | 345 MB |
| varchar | 592 MB | 401 MB |
| decimal128(20,2) | 592 MB | 458 MB |
Merging this one without #66545 would instead take the peak *up*, to 683 MB
for
an int32 key and 853 MB for a decimal128 one, which is why they are ordered.
### Tie-break
Ordering is byte-for-byte identical to before, tie-break included: rows whose
whole key is equal are stabilised on **descending** row position for
`DUP_KEYS`
and on **ascending** row position for everything else, exactly as the
previous
`is_dup ? lhs->_row_pos > rhs->_row_pos : lhs->_row_pos < rhs->_row_pos` did.
That `DUP_KEYS` direction has no semantics behind it -- it reproduces the
iteration order of the skip list MemTable used before #18686, where
`SkipList::Insert` linked a new node *ahead* of the existing equal keys, so
iterating yielded equal keys in reverse insertion order. The skip list is
long
gone and #18686, #19099 and #20392 each carried the ternary along without it
meaning anything.
Dropping it is nevertheless not free: a run of P0 with the tie-break
normalised
to ascending fails 39 cases, and only about half of those are a missing
`ORDER BY`. In the rest the *content* changes rather than the order -- which
row
wins in a `UNIQUE` table fed by an unordered `select`, which element survives
`collect_set(k, 1)`, the element order inside `array_agg`, the auto-increment
id-to-row mapping, `first_value` over a window whose `ORDER BY` has ties.
Those
can only be "fixed" by rewriting the expected output. So the direction is
kept
here, and removing it is left as its own change.
### Release note
None
### Check List (For Author)
- Test
- [x] Unit Test
- [ ] Regression test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason
The `MemTable`-driven cases in `be/test/load/memtable/memtable_sort_test.cpp`
come from #66545 and cover the ordering this change has to preserve. This PR
adds one more, for a permutation that is a single long cycle rather than the
short swaps the other cases happen to produce, since the permutation is
applied
to the row array in place by following its cycles. The tie-break case was
verified to fail when the direction is flipped, so it does discriminate.
- Behavior changed:
- [x] No.
- [ ] Yes.
- Does this need documentation?
- [x] No.
--
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]
