PostgreSQL 인덱스: 해시 대 B-트리

Dec 20 2022

언제 B-트리 인덱스보다 해시 인덱스를 사용해야 하는지 알고 계십니까? 선택의 이점은 얼마나 중요합니까? 나는 아니에요. 그래서 저는 경험 법칙을 찾기 위해 약간의 조사를 했습니다.

언제 B-트리 인덱스보다 해시 인덱스를 사용해야 하는지 알고 계십니까? 선택의 이점은 얼마나 중요합니까? 나는 아니에요.

그래서 저는 경험 법칙을 찾기 위해 약간의 조사를 했습니다. 그리고 이 글에서 그 결과를 공유하겠습니다.

UPD : 기사가 업데이트되었습니다.

아쉽게도 첫 번째 포스트 버전에서는 잡기 힘든 벤치마크에서 작은 실수를 저질렀습니다. 이 문서에서 자세한 내용을 읽을 수 있습니다 .

스포일러: 이제 해시 인덱스가 더욱 달콤해졌습니다.

읽을 수 있는 리소스가 많기 때문에 b-트리 및 해시 인덱스 에 대한 부분은 건너뜁니다 . 그러나 PostgreSQL 공식 문서의 해시 설명에서 잠시 멈춥니 다 .

해시 인덱스 는 인덱싱된 열의 값에서 파생된 32비트 해시 코드를 저장합니다. 따라서 이러한 인덱스는 단순 동등성 비교 만 처리할 수 있습니다 . 쿼리 플래너는 인덱싱된 열이 등호 연산자를 사용하는 비교에 포함될 때마다 해시 인덱스 사용을 고려합니다.

기대 성능 저하 없이 많은 값을 저장할 수 있는 b-tree 인덱스에도 불구하고 해시 인덱스는 고유한 해시 코드가 2³²-1개로 제한됩니다 (다른 값이 동일한 해시 코드를 가질 수 있음). 따라서 중복 수를 늘리면(해시 코드 측면에서) 인덱스 성능에 부정적인 영향을 미칩니다.

값은 카디널리티가 높습니다. 이상적으로는 해시 코드도 높은 카디널리티를 갖습니다.

b-tree 인덱스가 표준이 되는 이유 중 하나는 모든 비교 연산자를 지원하기 때문에 유연성이 있기 때문입니다. 반면 해시 인덱스는 등호 연산자만 지원합니다 .

값은 등호 연산자로만 쿼리됩니다.

이제 벤치마크를 따라 메모리 사용량과 성능을 비교해 보겠습니다.

결과를 살펴보기 전에 메트릭을 조사하는 데 사용한 PL/pgSQL 절차 를 공유하고 싶습니다 .

아래 random_string절차는 주어진 길이의 임의 문자열을 생성합니다.

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

결과는 PostgreSQL 15.1을 사용하여 수집됩니다.

메모리 사용량 비교에 대해 살펴보겠습니다. 아래에서 1.000, 10.000, 100.000 및 1.000.000 행에 대한 일련의 차트를 게시할 것입니다.