apache / apache/doris

[Enhancement] Reduce memory and allocation overhead of DUP_KEYS MemTables

Open
#67,505 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
15.9k
Forks
3.9k
Avg merge
2d 23h
Merged PRs (30d)
520

Description

### Search before asking

- [x] I had searched in the [issues](https://github.com/apache/doris/issues?q=is%3Aissue) and found no similar issues.

### Description

DUP_KEYS MemTables currently create one `shared_ptr` for every inserted row, even though these rows only require their positions for sorting.

This introduces substantial per-row metadata overhead, frequent heap allocations, and unnecessary allocation churn during large data loads. The overhead becomes
especially significant when a MemTable contains a large number of rows.

We can use a more compact representation for DUP_KEYS while preserving the existing sorting semantics:

- Sort rows by key in ascending order.
- For equal keys, sort by row position in descending order.
- Keep the existing behavior for UNIQUE_KEYS and AGG_KEYS unchanged.

### Solution

Replace the per-row `shared_ptr` objects used by DUP_KEYS MemTables with a contiguous `uint32_t` row-position vector.

The row positions are reserved before rows are appended to the mutable block and populated using `std::iota`, avoiding additional allocations after the block has been
modified. The existing `RowInBlock` representation remains unchanged for UNIQUE_KEYS and AGG_KEYS because those models require aggregation state.

This optimization reduces explicit row-index metadata from at least dozens of bytes per row to 4 bytes per row, eliminates per-row object allocations, and improves
MemTable insertion efficiency without changing query or load semantics.

### Are you willing to submit PR?

- [x] Yes I am willing to submit a PR!

### Code of Conduct

- [x] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct)

Contributor guide

Open the contributing guide

Research direction

Locate the DUP_KEYS MemTable insertion and sorting entry points, then compare them with the unchanged UNIQUE_KEYS and AGG_KEYS paths. Verify that row positions are reserved and populated before the mutable block is modified, and run the relevant MemTable tests to confirm ascending key order, descending row-position order for equal keys, and unchanged behavior for the other models.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, performance
Issue type
Feature
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.