liaoxin01 opened a new pull request, #66545:
URL: https://github.com/apache/doris/pull/66545
### What problem does this PR solve?
Problem Summary:
`MemTable::_sort()` ran its own multi-key sort: `pdqsort` over a
`vector<shared_ptr<RowInBlock>>`, 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
pointer
chases 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.
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.
### Behaviour change
Rows whose whole key is equal are now stabilised on **ascending** row
position
for every keys type. `DUP_KEYS` previously ordered them descending.
That descending order reproduced the iteration order of the skip list
MemTable
used before #18686: `SkipList::Insert` linked a new node *ahead* of the
existing
equal keys (`FindGreaterOrEqual` returns the first node >= key, and the new
node
is linked after `prev`), so iterating yielded equal keys in reverse insertion
order. The skip list is long gone; #18686, #19099 and #20392 each carried the
ternary along without it corresponding to any semantics.
Contents are unaffected -- DUP tables deduplicate nothing -- but rows
sharing the
key columns now keep insertion order inside a segment instead of being
reversed,
so a query without `ORDER BY` may return them in a different order.
If reviewers prefer to keep the old order, the direction is a one-line
change in
`_sort_permutation_by_key_columns()`; I removed it because nothing appears to
depend on it and it was the only reason `_sort()` needed to know its keys
type.
### 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
`be/test/load/memtable/memtable_sort_test.cpp` previously only covered
`class Tie`. It now drives a `MemTable` through `insert()`/`to_block()` and
covers multi-column key ordering, nullable key ordering (NULL first),
insertion
order on equal keys, independence from how rows are split across `insert()`
calls, `UNIQUE_KEYS` last-writer-wins and `AGG_KEYS` aggregation.
The two ordering tests were verified to fail when the tie-break direction is
flipped back to descending, so they do discriminate rather than just pass.
Regression tests have **not** been run for the ordering change above; that
needs
a cluster and is the part reviewers should weigh most.
- Behavior changed:
- [ ] No.
- [x] Yes. Equal keys in a DUP table keep insertion order instead of
being
reversed; see the section above.
- 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]
