Hash indexes are faster than btree indexes?

Re:Hash indexes are faster than btree indexes? by koolba on Monday March 20, 2017 @08:49AM (#13913634)

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

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by tpetry on Monday March 20, 2017 @10:11AM (#13914346)

Hash 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/

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by threepipeproblm on Monday March 20, 2017 @09:23AM (#13913933)

I'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).

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by koolba on Monday March 20, 2017 @09:30AM (#13914000)

You're mixing up hash joins with hash indexes.

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by threepipeproblm on Monday March 20, 2017 @09:38AM (#13914059)

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?

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.

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by koolba on Monday March 20, 2017 @09:41AM (#13914087)

> 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?

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by threepipeproblm on Monday March 20, 2017 @09:47AM (#13914144)

Thanks 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.

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by threepipeproblm on Monday March 20, 2017 @10:00AM (#13914270)

>> That means you don't load it into memory at all, you just jump to Bucket[Hash(KEY)] and then check there for KEY (it may or may not be there due to false positives and the bucket being full).

Right, of course. You're making me realize this really is my confusion between hash indexes and hash joins. The issue I'm thinking of is all about dynamically constructed hash joins. Sorry, you called it right from the start but it took me a minute to see... thanks for helping talk through it.

[ Parent | on HN ]

Re:Hash indexes are faster than btree indexes? by koolba on Monday March 20, 2017 @09:52AM (#13914188)

A hash index allows you to determine which bucket an arbitrary key is mapped to without having to look anything else up.

That means you don't load it into memory at all, you just jump to Bucket[Hash(KEY)] and then check there for KEY (it may or may not be there due to false positives and the bucket being full).

[ Parent | on HN ]