Indeksy PostgreSQL: Hash vs B-drzewo

Czy zawsze wiesz, kiedy użyć indeksu skrótu zamiast indeksu b-drzewa? Jak znacząca byłaby korzyść z wyboru? Ja nie.

Zrobiłem więc małe rozeznanie, aby znaleźć praktyczną zasadę. W tym artykule podzielę się wynikami.

UPD : Artykuł został zaktualizowany.

Niestety w pierwszej wersji postu popełniłem mały błąd w benchmarku, który ciężko było wyłapać. Możesz przeczytać więcej na ten temat w tym artykule .

Spoiler: indeks hash jest teraz jeszcze słodszy.

Pomijam część o indeksach b-tree i hash , ponieważ istnieje wiele zasobów, które możesz przeczytać. Zatrzymuję się jednak na chwilę przy opisie skrótu z oficjalnej dokumentacji PostgreSQL .

Indeksy skrótu przechowują 32-bitowy kod skrótu pochodzący z wartości indeksowanej kolumny. Dlatego takie indeksy mogą obsługiwać tylko proste porównania równości . Planista zapytań rozważy użycie indeksu skrótu, ilekroć indeksowana kolumna zostanie uwzględniona w porównaniu przy użyciu operatora równości.

Pomimo indeksu b-drzewa, który może przechowywać wiele wartości bez zmniejszania oczekiwanej wydajności, indeks hash ma limit 2 ³²-1 unikalnych kodów skrótu (różne wartości mogą mieć te same kody skrótu). Dlatego zwiększanie liczby duplikatów (pod względem kodów skrótu) negatywnie wpływa na wydajność indeksu.

Wartości mają dużą liczność. Idealnie, ich kody skrótu mają również wysoką liczność.

Jednym z powodów, dla których indeks b-drzewa jest tak standardowy, jest jego elastyczność, ponieważ obsługuje wszystkie operatory porównania. Z drugiej strony indeks Hash obsługuje tylko operatory równości .

Zapytania o wartości są wykonywane tylko za pomocą operatorów równości.

Przejdźmy teraz do testów porównawczych i porównajmy zużycie pamięci i wydajność.

Zanim przyjrzymy się wynikom, chciałbym podzielić się procedurami PL/pgSQL , których użyłem do zbadania metryk.

Poniższa random_stringprocedura generuje losowe ciągi znaków o określonej długości.

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

Wyniki są zbierane przy użyciu PostgreSQL 15.1.

Przejdźmy do porównania zużycia pamięci. Poniżej zamieszczę serię wykresów dla 1000, 10 000, 100 000 i 1 000 000 wierszy.

Podkreślmy kilka rzeczy, które widzimy na wykresach:

• Indeksy skrótu są niezależne od danych, co oznacza, że ​​ich rozmiar zależy tylko od liczby zindeksowanych danych;
• Im więcej masz wierszy, tym mniej długości łańcucha potrzebujesz, aby skorzystać z indeksu skrótu;
• W większości przypadków indeks skrótu zużywa znacznie mniej pamięci niż przechowywane pole, podczas gdy b-drzewo wymaga więcej niż przechowywane pole;
• Długość początkowa, przy której widzimy korzyści, może wynosić od 15 do 30; jednak, aby uprościć praktyczną zasadę, powiedzielibyśmy co najmniej 25 .

Przejdźmy teraz do porównania wydajności.

Na podstawie wykresów do porównania wydajności możemy powiedzieć:

• we wszystkich przypadkach wydajność jest lepsza w przypadku indeksu skrótu ;
• wybrane zapytania mają wzrost o 20–60% , rosnący wraz z liczbą wierszy;
• zapytania wstawiania mają wzrost o 10–80% , zwiększając się wraz z liczbą wierszy;
• oba indeksy działają szybko, a niektóre mogą pominąć wzrost o 0,01 milisekundy.

• zaoszczędzić około 1,5 GB na dysku ( 50 razy mniej niż indeks b-drzewa);
• daje wzrost wydajności o około 60–80% ( 0,02–0,04 ms na zapytanie).

Podsumujmy ogólną zasadę :

• Wartości mają dużą kardynalność . Idealnie byłoby, gdyby ich kody skrótu miały również wysoką liczność;
• Wartości są odpytywane tylko za pomocą operatorów równości ;
• Długości wartości powinny mieć co najmniej 25 znaków.