cockroachdb / cockroachdb/pebble

colblk: experiment with potential performance improvements

Open
#4,022 1 comment 0 reactions 0 assignees View on GitHub
A-storage C-performance T-storage
Dominant language
Go
Stars
6k
Forks
584
Avg merge
16h 35m
Merged PRs (30d)
5

Description

This issue is meant to be a running list of ideas to improve performance in the columnar format.

- [x] ~Don't separate suffix into wall time / logical time / untyped version. The hypothesis is that the current comparison code is too complex and a simple bytes.Compare might be faster~ [radu] Experimented with this and saw 10-30% regressions in `CockroachDataBlockIterShort`.
- [x] Add a version-is-not-timestamp column to data blocks and have a fast path for blocks or regions that only have timestamps. This column would be empty for all sql table data. [radu] Added a per-block property indicating what types of suffixes it contains.
- [ ] Separate prefix and suffix in index blocks and use compressed prefix encoding. The seeking should be faster and we'd be able to use a single-level index in more cases.
- [ ] Expose a PrevPrefix operation that uses the prefix changed bitmap to quickly jump to the previous key. The expectation is that this would reduce CPU during reverse scans. I believe MVCC GC currently scans in reverse and could benefit.
- [ ] In `PrefixBytes.Search` try to compare a single byte before calling `bytes.Compare`.
- [ ] Use KeySeeker.SearchDir to perform try-seek-using-next optimizations #5054
- [ ] Move block properties into BlockPropertyCollector-defined columns. This can allow more compact encoding of properties (eg, MVCC timestamps may benefit from uint delta encoding). Likely a minor benefit, but we would additionally avoid decoding O(_n_) varints where _n_ is the number of BlockPropertyCollectors
- [x] Stash block decoders in the table cache to avoid the initial parsing of the structure of a block on block cache hits
- [ ] Automatically switch between using bundles in prefix bytes (if bundles don't save a lot of space, use bundle size of 1 which is more efficient to search)
- [ ] Move prefix-changed bitmap into PrefixBytes (and perhaps RawBytes), so it can be used by that code as well
- [ ] Enable use of [TrySeekUsingNext](https://github.com/cockroachdb/pebble/blob/2da617a0a886eba8087bd91bb9a1238515b1c3fc/sstable/colblk/data_block.go#L1202-L1204) as a signal to constrain the search space. Currently the sstable iterator [never propagates the flag to the data block iterator](https://github.com/cockroachdb/pebble/blob/2da617a0a886eba8087bd91bb9a1238515b1c3fc/sstable/reader_iter_single_lvl.go#L829).
- [ ] Implement and use colblk.DataBlockIter.SeekPrefixGE
- [ ] Uint 'column families,' that apply the width-reduction but store the values of a family together for better cache efficiency. This would apply in the context of the index block, allowing the offset and length to be accessed together. It would however require access to _not_ be simple aligned memory loads, but use explicit little endian gets.
- [ ] Loading an inline-encoded value to call `base.MakeInPlaceValue` is cheap, but we will do it for every internal iterator positioned. Most of these values will not be used. We could consider making all values follow a 'lazy' retrieval process, which in the case of inlined values would just call `Value()` on the `DataBlockIter`.

Jira issue: PEBBLE-273

Contributor guide

No contributing guide indexed for this repository

Research direction

This is a running list rather than a scoped task; start by selecting one unchecked item and reading the relevant colblk code. The issue points to sstable/colblk/data_block.go and sstable/reader_iter_single_lvl.go, including TrySeekUsingNext, and mentions PrefixBytes.Search and colblk.DataBlockIter.SeekPrefixGE. Done requires a separately scoped optimization with benchmark evidence and tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.