4 ms·
Question for the Postgres developers who I know are lurking around here ... What's the disk usage of hash indexes v.s. regular btrees? Does it depend on the u
by koolba 10y ago
Question for the Postgres developers who I know are lurking around here ...
What's the disk usage of hash indexes v.s. regular btrees?
Does it depend on the underlying type or is it a fixed size regardless of the key fields?
How's this compare to the poor man's hash index, i.e. BTREE(HASH(keys...))?
EDIT: I got curious so I ran a test of building btrees vs hash indexes. This is done on 9.6 (not HEAD with the new WAL logging supported hash indexes). Looks like the sweet spot is when the key size is around 20 bytes. After that the fixed size of the hash index gives it a win (on space usage) v.s. the btree which would have to repeatedly store the key values.
CREATE TABLE IF NOT EXISTS hash_test_results (
key_size int,
btree_size bigint,
hash_size bigint
);
CREATE OR REPLACE FUNCTION pg_temp.test_hash_index(p_key_size int)
RETURNS void
AS
$BODY$
DROP TABLE IF EXISTS index_test;
CREATE TABLE index_test as select lpad('' || x, p_key_size, '0') AS a FROM generate_series(1,100000) x;
CREATE INDEX index_test_ix_btree ON index_test USING btree (a);
CREATE INDEX index_test_ix_hash ON index_test USING hash (a);
INSERT INTO hash_test_results
(key_size, btree_size, hash_size)
SELECT
p_key_size AS key_size,
(SELECT pg_relation_size(c.oid) FROM pg_class c WHERE c.relname = 'index_test_ix_btree') AS btree_size,
(SELECT pg_relation_size(c.oid) FROM pg_class c WHERE c.relname = 'index_test_ix_hash') AS hash_size;
$BODY$
LANGUAGE SQL;
SELECT pg_temp.test_hash_index(x * 8) FROM generate_series(1, 16) x;
=> SELECT
key_size,
pg_size_pretty(btree_size) AS btree_size,
pg_size_pretty(hash_size) AS hash_size
FROM hash_test_results;
key_size | btree_size | hash_size
----------+------------+-----------
8 | 3104 kB | 4112 kB
16 | 3992 kB | 4112 kB
24 | 4880 kB | 4112 kB
32 | 5792 kB | 4112 kB
40 | 6648 kB | 4112 kB
48 | 7592 kB | 4112 kB
56 | 8464 kB | 4112 kB
64 | 9352 kB | 4112 kB
72 | 10 MB | 4112 kB
80 | 11 MB | 4112 kB
88 | 12 MB | 4112 kB
96 | 13 MB | 4112 kB
104 | 14 MB | 4112 kB
112 | 15 MB | 4112 kB
120 | 15 MB | 4112 kB
128 | 16 MB | 4112 kB
- deleted 10y ago[deleted]
- threepipeproblm 10y agoI'm not a Postgres specialist but, if memory serves, when joining 2 tables the entire hash must be loaded on 1 side (typically the smaller side, of course).
- koolba 10y agoYou're mixing up hash joins with hash indexes.
- threepipeproblm 10y agoI know they're different things, but isn't the main reason to do hash indexes in a relational db to then to a hash join? More to the point: even if you're just talking indexes you can't load/use half a hash table, so wouldn't the point also apply to isolated use of a hash table. I know it's not what was asked for, just a related point.
- koolba 10y ago> I know they're different things, but isn't the main reason to do hash indexes in a relational db to then to a hash join? I think the primary use case is O(1) lookup by key, i.e. similar to how key/value stores work. I'm not aware of the planner being able to reuse an existing hash index to perform a hash join. AFAIK the hash buckets are created on the fly. That does sound like a cool idea though. > More the point, even if you're just talking indexes you can't load/use half a hash table, so wouldn't the point also apply to isolated use of a hash table. What do you mean by half a hash table?
- threepipeproblm 10y agoThanks for this clarification >> What do you mean by half a hash table? What I'm trying to get across is my impression that you don't have to load an entire B-tree index into memory to use it... you can traverse it. Whereas a hash index can't be "streamed" or traversed like that, you have to use the whole thing. I read some papers on hash indexes and hash joins several months ago, and know little about the Postgres specifics... just wanting to wrap my head around it, so please help me understand if I'm off base with this.
- tpetry 10y agoHash indexes are currently (9.6) a little bit larger than btree indexes [1]. There seems to be no space improvement yet committed for postgres 10. But stay tuned, maybe somebody will do it soneday. Hash indexes have not been recommended for years because they have not been crashsafe and therefore are not really that optimized in every term yet (size, query planner, ...). [1] http://blog.andrebarbosa.co/hash-indexes-on-postgres/ http://blog.andrebarbosa.co/hash-indexes-on-postgres/