IntersectMBO / IntersectMBO/ouroboros-consensus

Immutable DB: use a bitvector as primary index

Open
#747 1 comment 0 reactions 0 assignees View on GitHub
🏎️ performance
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.