PostgreSQL dizinleri: Hash ve B-ağacı

Karma dizini b-ağacı dizini yerine ne zaman kullanacağınızı her zaman biliyor musunuz? Seçimden elde edilecek fayda ne kadar önemli olacaktır? Yapmıyorum.

Bu yüzden pratik bir kural bulmak için küçük bir araştırma yaptım. Ve bu yazıda sonuçları paylaşacağım.

UPD : Makale güncellendi.

Ne yazık ki, ilk gönderi versiyonunda, kıyaslamada yakalanması zor olan küçük bir hata yaptım. Bununla ilgili daha fazla bilgiyi bu makalede okuyabilirsiniz .

Spoiler: hash indeksi şimdi daha da tatlı.

Okuyabileceğiniz birçok kaynak olduğu için b-tree ve hash indeksleri ile ilgili kısmı atlıyorum . Ancak, PostgreSQL'in resmi belgelerindeki karma açıklama üzerinde bir saniye duruyorum .

Hash indeksleri , indekslenmiş sütunun değerinden türetilen 32 bitlik bir hash kodunu saklar. Bu nedenle, bu tür dizinler yalnızca basit eşitlik karşılaştırmalarını işleyebilir . Sorgu planlayıcı, eşittir işleci kullanılarak bir karşılaştırmaya dizinlenmiş bir sütun dahil edildiğinde bir karma dizini kullanmayı düşünecektir.

Beklenen performansı düşürmeden birçok değeri saklayabilen b-tree indeksine rağmen, hash indeksinin 2 ³²-1 benzersiz hash kodu sınırı vardır (farklı değerler aynı hash kodlarına sahip olabilir). Bu nedenle, kopya sayısının artması (karma kodlar açısından) indeks performansını olumsuz etkiler.

Değerler yüksek kardinaliteye sahiptir. İdeal olarak, hash kodları da yüksek kardinaliteye sahiptir.

b-ağacı indeksinin bu kadar standart olmasının nedenlerinden biri, tüm karşılaştırma operatörlerini desteklediği için esnekliğidir. Hash indeksi ise sadece eşitlik operatörlerini destekler .

Değerler yalnızca eşitlik işleçleriyle sorgulanır.

Şimdi kriterleri takip edelim ve bellek tüketimi ile performansı karşılaştıralım.

Sonuçlara bakmadan önce, ölçümleri araştırmak için kullandığım PL/pgSQL prosedürlerini paylaşmak istiyorum .

Aşağıdaki random_stringprosedür, belirli bir uzunlukta rasgele diziler üretir.

-- 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);

Sonuçlar PostgreSQL 15.1 kullanılarak toplanır.

Bellek tüketimi karşılaştırmasına geçelim. Aşağıda 1.000, 10.000, 100.000 ve 1.000.000 satırlık bir dizi grafik yayınlayacağım.

Grafiklerde gördüğümüz birkaç şeyi vurgulayalım:

• Hash dizinleri veriden bağımsızdır, yani boyutları yalnızca dizine alınan verilerin sayısına bağlıdır;
• Ne kadar çok satırınız varsa, hash indeksinden faydalanmak için o kadar az dizi uzunluğuna ihtiyacınız vardır;
• Çoğu durumda, hash indeksi saklanan alandan çok daha az bellek tüketirken, b-ağacı saklanan alandan daha fazlasını gerektirdiğinde;
• Faydasını gördüğümüz başlangıç ​​uzunluğu 15–30 arası olabilir; ancak, pratik kuralı basitleştirmek için en az 25 deriz .

Şimdi performans karşılaştırmasına geçelim.

Performans karşılaştırma çizelgelerine dayanarak şunları söyleyebiliriz:

• her durumda, hash indeksi ile performans daha iyidir;
• seçme sorguları , satır sayısıyla birlikte artan %20-60'lık bir artışa sahiptir;
• ekleme sorguları , satır sayısıyla birlikte artan %10-80'lik bir artışa sahiptir;
• her iki dizin de hızlı çalışır ve bazıları 0,01 milisaniyelik bir kazancı ihmal edebilir.

• diskte yaklaşık 1,5 GB tasarruf edin (b-ağacı dizininden 50 kat daha küçük);
• size yaklaşık %60–80'lik bir performans artışı sağlar ( sorgu başına 0,02–0,04 ms ).

Kuralı tamamlayalım :

• Değerler yüksek kardinaliteye sahiptir . İdeal olarak, hash kodları da yüksek kardinaliteye sahiptir;
• Değerler yalnızca eşitlik işleçleriyle sorgulanır ;
• Değer uzunlukları en az 25 karakter uzunluğunda olmalıdır.