cockroachdb / cockroachdb/pebble
colblk: experiment with potential performance improvements
- 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