Smaller Hash BTrees
In this one, we're talking about a somewhat niche PostgreSQL storage optimization you can apply to cryptographic data indexing.
In my experience from the past 3+ years, if you are building on top of a distributed network that involves cryptography, like ATProto or blockchains, you will probably find yourself needing to refer to data elements using an opaque slice of bytes as a key. These byte slices are usually cryptographic fingerprints derived from the data itself, public keys, etc.
Indices covering this data can be large, unfortunately, and storage space isn't free. How could we shrink them?
Example Dataset
For this example, we'll be using a dataset I assembled of 821,356,014 unique Content Identifiers (CIDs for short) of real ATProto records. Most of this data came from Phil (@bad-example.com on Bluesky), who makes some great ATProto stuff, shout out to them for the help.
Here's what our table looks like:
CREATE TABLE our_data (
-- a table that really wanted to save space might compact DIDs & NSIDs
-- using an integer mapping - we'll ignore this for our example.
did bytea NOT NULL,
nsid text NOT NULL,
rkey text NOT NULL,
PRIMARY KEY(did, nsid, rkey),
created_at timestamptz NOT NULL,
-- the subject of our post, the content ID of a record that we want to search
cid bytea NOT NULL
);
Note that we don't use the cid column as our primary key here. That's because it's not possible to use the strategy we'll be discussing here on a table's primary key, because primary keys have to be unique. More on that later.
Since cid is not our primary key, we'll need an additional index on it to search it. Let's start with the largest, most obvious index, and work our way to a smaller one.
Full Index
A standard BTree index on our cid column looks like this:
CREATE INDEX cids_bin_idx ON our_data USING btree(cid);
Since the column values we're indexing are fairly large (36 bytes for a CID, 20 bytes for an Ethereum address), an index over them can increase your table size significantly. For 821,356,014 unique CIDS of 36 bytes each, the btree index created above is ~45GB. Let's make a slight under-estimate of the size taken up by raw column storage for cid by ignoring database overhead:
(821,356,014 * 36) bytes / (1024 * 1024 * 1024) = 29.56882 GB
even if we round up to 30GB to account for some light db overhead, we can see that the full btree index is still 1.5x larger than the data it covers.
Partial Indices
The way we can make our indices smaller is by relying on the inherent distribution of hash data. Collision rates on even a small portion of the complete hashes should be very low! if this wasn't true, we'd probably have much larger problems with cryptography based systems.
We'll use a Postgres expression index with a binary SUBSTRING function to create indices that only use a small portion of the hashes, and look at collision rates for these smaller indices.
Distribution Questions
In order to make sure our data is distributed how we think it is, we'll answer some questions about the frequency of substring duplicates at various byte lengths.
- how many byte slices are duplicated when we take the last N (4 or 8, here) bytes of each CID?
- for duplicated slices, how many duplicates are there, both average and maximum?
We'll answer those questions with this query:
SELECT
COUNT(*) AS last_n_dupe_count,
ROUND(AVG(cnt)::numeric, 4) AS avg_rows_per_duped_value,
MAX(cnt) AS max_rows_per_duped_value
FROM (
SELECT
SUBSTRING(cid FROM 33 FOR 4) AS last_n_bytes,
/* for 8 byte version, use
SUBSTRING(cid FROM 29 FOR 8) AS last_n_bytes */
COUNT(*) AS cnt
FROM our_data
GROUP BY last_n_bytes
HAVING COUNT(*) > 1
) t;
Using 8 / 36 bytes
Let's make an index that uses the last 8 bytes of each CID:
CREATE INDEX cids_bin_last8_idx ON our_data
USING btree (SUBSTRING(cid FROM 29 FOR 8));
Distribution
In our dataset, there are 0 8 byte slices at the end of CIDs that happen more than once. This is pretty incredible over 821m+ rows!
Having 0 duplicates means that there is no de-duplication to be done over the index scan's result.
Using 4 / 36 bytes
Now we'll make an index that only uses the last 4 bytes to compare with our previous ones.
CREATE INDEX cids_bin_last4_idx ON our_data
USING btree (SUBSTRING(cid FROM 33 FOR 4));
Distribution
There are 69,201,662 4 byte slices at the end of CIDs that happen more than once.
With these slices that are seen more than once, they are each seen an average of 2.0658 times, and the max number of times a given slice is seen is 7.
Since the minimum amount of times a duplicated slice can be seen is 2, this means that for the vast majority of duplicated slices, there is just one duplicate.
Most 4 byte slices still have no duplicates: only ~142,956,800 out of 821,356,014, or %17.4 of rows, have a duplicate.
This might seem a lot worse than the 8 byte slices - after all, there are no duplicates there! However, we'll see that this isn't a big deal. Our rarely-encountered worst case, where we de-duplicate 7 rows, is absolutely nothing for the database, and this would still probably be the case even if our dataset was an order of magnitude larger.
Comparisons
Disk Size
How do the storage sizes for our 8 byte and 4 byte indices compare to the index over the full 36 bytes ?
WITH sizes AS (
SELECT
pg_total_relation_size('cids_bin_idx') AS f36_size,
pg_total_relation_size('cids_bin_last8_idx') AS l8_size,
pg_total_relation_size('cids_bin_last4_idx') AS l4_size
)
SELECT
*,
(l8_size::numeric / f36_size) * 100.0 AS last8_percent_size,
(l4_size::numeric / f36_size) * 100.0 AS last4_percent_size
FROM sizes;
- Full 36 byte index is 45GB
- Last 8 index is 24GB - %53.4154 of full size
- Last 4 index is 17GB - %37.28 of full size
Read Queries
Let's look at how these indices compare with each other when using them in your reads.
Query Complexity
A very minor downside of this approach is that it makes your read queries look slightly more complex.
A query using the full index looks like you'd expect normally:
SELECT * FROM our_data WHERE cid =
-- hex bytes for "bafyreibdocl6hsrd2vjoxferbzm5bh47mw3skyxd5twoegigraxpltvttu"
'\x01711220237097e3ca23d552eb94910e59d09f9f65b72562e3ecece21906882ef5ceb39d';
While a query using one of our substring indices has to specify the exact substring in the WHERE clause, or the query planner can't use that index. Here's what it looks like using the 8 byte index:
SELECT * FROM our_data
WHERE SUBSTRING(cid from 29 for 8) = '\x1906882ef5ceb39d'
AND cid =
'\x01711220237097e3ca23d552eb94910e59d09f9f65b72562e3ecece21906882ef5ceb39d';
It would work the same for the 4 byte index, just using a different substring clause:
WHERE SUBSTRING(cid from 33 for 4) = '\xf5ceb39d'
Note that we still match on the entire 36 bytes after narrowing it down using the smaller index. This ensures identical behavior to the original query by eliminating any duplicates in the index.
Performance
The extra equality check we perform after matching on a substring index is extremely cheap compared to disk I/O, so it is never really going to be a performance concern. In fact, we'll often see a minor decrease in the estimated cost for the query, because scanning an index with smaller elements takes a bit less time than an index with larger elements. We can see this if we compare the query plans for using a full index vs a substring index.
Full Index Query
The full index query shown above has the expected ideal query plan: just an index scan on the index cids_bin_idx.
Index Scan using cids_bin_idx on our_data (cost=0.70..8.72 rows=1 width=97)
Index Cond: (cid =
'\x01711220237097e3ca23d552eb94910e59d09f9f65b72562e3ecece21906882ef5ceb39d'
)
Note the cost estimate: 0.70..8.72
Substring Index Queries
Here's the query plan for the 8 byte index.
Index Scan using cids_bin_last8_idx on our_data (cost=0.57..8.59 rows=1 width=97)
Index Cond: (SUBSTRING(cid FROM 29 FOR 8) = '\x1906882ef5ceb39d')
Filter: (cid =
'\x01711220237097e3ca23d552eb94910e59d09f9f65b72562e3ecece21906882ef5ceb39d'
)
Here we have one additional step to the plan - the Filter clause that de-duplicates the results.
Despite this, note the slightly lower cost estimate: 0.57..8.59
The plan for the 4 byte index has an identical cost estimate, and only varies in the Index Cond clause as you would expect.
Last Thoughts
We've shown that you can save a lot of disk space, with an imperceptible difference in read performance, by making your btree indices over hash data use substrings of the data. This can allow you to offer search over this data more cheaply. The size of the substring you use affects the space saved and potential worst-case performance.
Some parting notes:
On Alignment
You may notice we didn't bother to try a 6-byte version of our index. This is because it comes out to be exactly the same size as a 8-byte index due to how Postgres aligns things. So, don't bother trying sizes that aren't multiples of 4 bytes.
On Security
The technique described above has not been rigorously evaluated against potential threat models.
That said - If you use an 8-byte slice of some hash data, it's fairly difficult for anyone to craft malicious inputs that would degrade the performance of your system. It would be significantly easier to do that with 4 byte slices, in theory.
In reality, it might be fairly unlikely that your system is a target someone cares enough about to try to do this to. If you are paranoid, please evaluate the risk of malicious input on your own data before using this technique.