IntersectMBO / IntersectMBO/ouroboros-consensus
Immutable DB: use a bitvector as primary index
- Dominant language
- Haskell
- Stars
- 67
- Forks
- 43
- Avg merge
- 5d 13h
- Merged PRs (30d)
- 43
Description
In input-output-hk/ouroboros-network#1191, the primary index is a dense index that stores the offset in the secondary index file for each slot. If the slot is empty, the offset of the slot before it is repeated. Each offset is a `Word32`. So the size of the primary index is epoch size * 4 bytes. For Byron, this will be 84 kB. For Shelley, this will be 843 kB.
As the size of the entries in the secondary index is fixed, we could make this more compact: use a bitvector to indicate whether each slot is filled. To find the offset in the secondary index file for a slot, we'd need to find out the number of filled slots (number of 1s) before the given index and multiply that number with the size of each entry. We'd only need a single bit per slot for this format. So the size of this primary index would be (epoch size / 8) bytes. For Byron, this will be 2.6kB. For Shelley, this will be 2.64 kB.
In terms of disk size, the second index format definitely wins, and I expect the offset computation to be reasonably too, especially if we can use `popcount`.
Contributor guide
Assessment
This issue has not been assessed yet.