Tracking issue for the memtable improvement

[evenyag]

What type of enhancement is this?

Performance

What does the enhancement do?

The default memtable implementation has the following areas for improvement:

• The active buffer doesn't have capacity limit, we might freeze it once its size reaches a threshold
• compact() and to_batch() is costly
  • Most time series data has monotonically increasing timestamps so we can avoid sorting if data is already sorted
• At each query, we need to scan each Series to see whether it matches the filter
  • We can use prefix scan if the filter matches a prefix of the primary key
  • In-memory index in the memtable?
• Dropping lots of Series is costly, we should explore the possibility of reusing Series
• The basic overhead of ValueBuilder is relative high when each time-series has only a few data points.

Implementation challenges

We might implement some benchmarks and optimize the memtable based on test results.

Implementation history

• Support building a vector without resetting the builder feat: builder to vector without resetting #2915
• Per table setting Support per-table memtable settings #3183
• Implementation
  • basic structs feat: Defines structs in the merge tree memtable #3326
  • feat: data buffer and related structs #3329
  • feat: Implement KeyDictBuilder for the merge tree memtable #3334
  • feat: replace pk index with pk_weight during freeze #3343
  • feat: merge tree data parts  #3346
  • feat: Defines more structs and methods for a partitioned merge tree #3348
  • feat: Implement write and fork for the new memtable #3357
  • feat: impl merge reader for DataParts #3361
  • refactor: Remove Item from merger's Node trait #3371
  • feat: Implement iter for the new memtable #3373
  • feat: Add freeze and fork method to the memtable #3374
  • feat: merge tree dedup reader #3375
  • feat: Implement dedup for the new memtable and expose the config #3377
  • refactor: change the receivers of merge tree components #3378
• Test and Optimize
  • fix: resets dict builder keys counter and avoid unnecessary pruning #3386
  • feat: Implement partition eviction and only add value size to write buffer size #3393
  • feat: enable zstd compression and encodings in merge tree data part #3380
  • memtable read metrics chore: add metris for memtable read path #3397
  • reduce pruning cost
    • perf: Reduce decode overhead during pruning keys in the memtable #3415
    • last_yield_pk_index doesn't help to skip already pruned keys
  • reduce cost of finding pk index
    • Replace shard level maps with a partition level map feat: Use a partition level map to look up pk index #3400
    • Maybe change the encoding of the key in the map feat: employ sparse key encoding for shard lookup #3410
• Benchmarks perf: more benchmarks for memtables #3491
• Optimize scan performance Memtable scan performance regression while time series amount < 100K #3467
• projection push down
• Reduce read-write lock contention
  • refactor: move some costly methods in DataBuffer::read out of read lock #3406
• Enable it by default refactor: make MergeTreeMemtable the default choice #3430
• Rename the memtable refactor!: Renames the new memtable to PartitionTreeMemtable #3547
• fork_dictionary_bytes should be global config

Non-Blocking

• more query tests
• Better freeze strategy

[killme2008]

What's the progress of this issue? Could we convert it to a tracking issue and split tasks? @evenyag @v0y4g3r

[evenyag]

We need some experiments and benchmarks to examine some ideas.

[evenyag]

There are some scan performance regressions of the new memtable. The fetch_next_partition is costly under some circumstances.

greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="0.005"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="0.01"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="0.05"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="0.1"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="0.5"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="1"} 0
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="5"} 10
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="10"} 10
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="60"} 10
greptime_merge_tree_read_stage_elapsed_bucket{stage="fetch_next_partition",le="+Inf"} 10
greptime_merge_tree_read_stage_elapsed_sum{stage="fetch_next_partition"} 20.881826560000004

Related to #3467

[evenyag]

I'm going to close this issue as the performance is tracked in #3467