Indeks PostgreSQL: Hash vs B-tree

Apakah Anda selalu tahu kapan harus menggunakan indeks hash di atas indeks b-tree? Seberapa signifikan manfaat dari pilihan tersebut? Saya tidak.

Jadi saya melakukan sedikit riset untuk mengetahui aturan praktis. Dan dalam artikel ini, saya akan membagikan hasilnya.

UPD : Artikel telah diperbarui.

Sayangnya, di versi postingan pertama, saya membuat kesalahan kecil di benchmark yang sulit ditangkap. Anda dapat membaca lebih lanjut tentang itu di artikel ini .

Spoiler: indeks hash bahkan lebih manis sekarang.

Saya melewatkan bagian tentang b-tree dan indeks hash karena ada banyak sumber yang dapat Anda baca. Namun, saya berhenti sejenak pada deskripsi hash dari dokumentasi resmi PostgreSQL .

Indeks hash menyimpan kode hash 32-bit yang berasal dari nilai kolom yang diindeks. Karenanya, indeks semacam itu hanya dapat menangani perbandingan kesetaraan sederhana . Perencana kueri akan mempertimbangkan untuk menggunakan indeks hash setiap kali kolom yang diindeks terlibat dalam perbandingan menggunakan operator yang sama.

Meskipun indeks b-tree, yang dapat menyimpan banyak nilai tanpa mengurangi kinerja yang diharapkan, indeks hash memiliki batas 2 ³²-1 kode hash unik (nilai yang berbeda mungkin memiliki kode hash yang sama). Oleh karena itu, meningkatkan jumlah duplikat (dalam hal kode hash) berdampak negatif terhadap kinerja indeks.

Nilai memiliki kardinalitas tinggi. Idealnya, kode hash mereka juga memiliki kardinalitas tinggi.

Salah satu alasan mengapa indeks b-tree sangat standar adalah fleksibilitasnya karena mendukung semua operator pembanding. Indeks hash, di sisi lain, hanya mendukung operator kesetaraan .

Nilai hanya ditanyakan dengan operator kesetaraan.

Sekarang, mari ikuti tolok ukur dan bandingkan konsumsi dan kinerja memori.

Sebelum kita melihat hasilnya, saya ingin membagikan prosedur PL/pgSQL yang saya gunakan untuk meneliti metrik.

Prosedur random_stringdi bawah menghasilkan string acak dengan panjang tertentu.

-- returns a randomized string of given length
CREATE OR REPLACE FUNCTION random_string(length integer)
RETURNS text AS
$$
DECLARE
    chars text[] := '{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}';
    result text := '';
    i integer := 0;
BEGIN
    FOR i IN 1..length LOOP
        result := result || chars[ceil(61 * random()) + 1];
    END LOOP;
    RETURN result;
END
$$ LANGUAGE plpgsql;

-- executes a given query for every string in strings
-- returns an average time for a single execution in milliseconds
CREATE OR REPLACE FUNCTION benchmark(query text, strings varchar[])
RETURNS numeric AS
$$
DECLARE
    _start_ts timestamptz;
    _end_ts   timestamptz;
    string    varchar;
BEGIN
    _start_ts := clock_timestamp();
    FOREACH string IN ARRAY strings LOOP
        EXECUTE format(query) using string;
    END LOOP;
    _end_ts := clock_timestamp();

    RETURN 1000 * (extract(epoch FROM _end_ts - _start_ts)) /
           array_length(strings, 1);
END
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION test(length integer, count numeric)
RETURNS TABLE (
    sample_length integer,
    unique_ratio decimal, -- in percentage
    hash_index_size bigint, -- in kilobytes
    btree_index_size bigint, -- in kilobytes
    column_size bigint, -- in kilobytes
    hash_select_query decimal, -- in milliseconds
    btree_select_query decimal, -- in milliseconds
    hash_insert_query decimal, -- in milliseconds
    btree_insert_query decimal -- in milliseconds
) AS
$$
DECLARE
    strings varchar[];
BEGIN
    CREATE TABLE IF NOT EXISTS hash_table(example varchar);
    CREATE TABLE IF NOT EXISTS btree_table(example varchar);

    INSERT INTO hash_table (SELECT random_string(length) FROM generate_series(1, count));
    INSERT INTO btree_table (SELECT example FROM hash_table);

    ANALYSE hash_table; -- this is critical for hash index
    ANALYSE btree_table;

    CREATE INDEX IF NOT EXISTS hash_index ON hash_table USING hash(example);
    CREATE INDEX IF NOT EXISTS btree_index ON btree_table USING btree(example);

    ANALYSE hash_table;
    ANALYSE btree_table;

    strings := array_agg(random_string(length)) FROM generate_series(1, 100);

    RETURN QUERY
    SELECT (SELECT length(example) FROM hash_table LIMIT 1),
        round(count(DISTINCT example)::decimal / count(*) * 100, 2) AS unique_ratio,
       pg_relation_size('hash_index') / 1024 AS hash_index_size,
       pg_relation_size('btree_index') / 1024 AS btree_index_size,
       pg_table_size('hash_table') / 1024 AS column_size,
       benchmark('SELECT example FROM hash_table WHERE example = $1', strings) AS hash_select_query,
       benchmark('SELECT example FROM btree_table WHERE example = $1', strings) AS btree_select_query,
       benchmark('INSERT INTO hash_table VALUES($1)', strings) AS hash_insert_query,
       benchmark('INSERT INTO btree_table VALUES($1)', strings) AS btree_insert_query
    FROM hash_table;

    DROP TABLE IF EXISTS hash_table;
    DROP TABLE IF EXISTS btree_table;
END
$$ LANGUAGE plpgsql;

SELECT (test(length, 1000)).*
FROM (VALUES (3), (5), (7), (10), (25), (100), (255), (355), (512), (755), (835), (1024)) s(length);

Hasilnya dikumpulkan menggunakan PostgreSQL 15.1.

Mari selami perbandingan konsumsi memori. Di bawah ini, saya akan memposting serangkaian grafik untuk baris 1.000, 10.000, 100.000, dan 1.000.000.

Mari soroti beberapa hal yang kita lihat di grafik:

• Indeks hash adalah agnostik data, artinya ukurannya hanya bergantung pada jumlah data yang diindeks;
• Semakin banyak baris yang Anda miliki, semakin sedikit panjang string yang Anda perlukan untuk memanfaatkan indeks hash;
• Dalam kebanyakan kasus, indeks hash mengkonsumsi lebih sedikit memori daripada bidang yang disimpan, sedangkan ketika b-tree membutuhkan lebih dari bidang yang disimpan;
• Panjang awal di mana kami melihat manfaatnya bisa antara 15–30; namun, untuk menyederhanakan aturan praktis, kami akan mengatakan setidaknya 25 .

Sekarang mari beralih ke perbandingan kinerja.

Berdasarkan grafik untuk perbandingan kinerja, kita dapat mengatakan:

• dalam semua kasus, kinerjanya lebih baik dengan indeks hash ;
• pilih kueri memiliki peningkatan 20–60% , meningkat seiring dengan jumlah baris;
• masukkan kueri memiliki peningkatan 10–80% , meningkat seiring dengan jumlah baris;
• kedua indeks bekerja dengan cepat, dan beberapa dapat mengabaikan kenaikan 0,01 milidetik.

• menghemat sekitar 1,5GB pada disk ( 50 kali lebih kecil dari indeks b-tree);
• memberi Anda sekitar 60–80% peningkatan kinerja ( 0,02–0,04 md per kueri).

Mari kita simpulkan aturan praktisnya :

• Nilai memiliki kardinalitas tinggi . Idealnya, kode hash mereka juga memiliki kardinalitas tinggi;
• Nilai ditanyakan hanya dengan operator kesetaraan ;
• Panjang nilai minimal harus 25 karakter.