Chỉ mục PostgreSQL: Hash vs B-tree

Dec 20 2022

Bạn có luôn biết khi nào nên sử dụng chỉ mục băm trên chỉ mục b-tree không? Lợi ích sẽ đáng kể như thế nào từ sự lựa chọn? Tôi không. Vì vậy, tôi đã thực hiện một nghiên cứu nhỏ để tìm ra một quy tắc chung.

Bạn có luôn biết khi nào nên sử dụng chỉ mục băm trên chỉ mục b-tree không? Lợi ích sẽ đáng kể như thế nào từ sự lựa chọn? Tôi không.

Vì vậy, tôi đã thực hiện một nghiên cứu nhỏ để tìm ra một quy tắc chung. Và trong bài viết này, tôi sẽ chia sẻ kết quả.

CẬP NHẬT : Bài viết đã được cập nhật.

Thật không may, trong phiên bản đầu tiên của bài đăng, tôi đã mắc một lỗi nhỏ trong điểm chuẩn rất khó nắm bắt. Bạn có thể đọc thêm về nó trong bài viết này .

Spoiler: chỉ số băm bây giờ thậm chí còn ngọt ngào hơn.

Tôi bỏ qua phần về b-tree và chỉ mục băm vì có rất nhiều tài nguyên bạn có thể đọc. Tuy nhiên, tôi dừng lại một giây ở phần mô tả hàm băm từ tài liệu chính thức của PostgreSQL .

Các chỉ mục băm lưu trữ mã băm 32 bit được lấy từ giá trị của cột được lập chỉ mục. Do đó, các chỉ mục như vậy chỉ có thể xử lý các phép so sánh đẳng thức đơn giản . Công cụ lập kế hoạch truy vấn sẽ cân nhắc sử dụng chỉ mục băm bất cứ khi nào một cột được lập chỉ mục liên quan đến so sánh bằng cách sử dụng toán tử bằng.

Mặc dù chỉ mục b-tree có thể lưu trữ nhiều giá trị mà không làm giảm hiệu suất dự kiến, nhưng chỉ mục băm có giới hạn 2 ³²-1 mã băm duy nhất (các giá trị khác nhau có thể có cùng mã băm). Do đó, việc tăng số lượng bản sao (về mã băm) ảnh hưởng tiêu cực đến hiệu suất của chỉ mục.

Giá trị có cardinality cao. Lý tưởng nhất là mã băm của họ cũng có số lượng thẻ cao.

Một trong những lý do tại sao chỉ mục b-tree rất chuẩn là tính linh hoạt của nó vì nó hỗ trợ tất cả các toán tử so sánh. Mặt khác, chỉ mục băm chỉ hỗ trợ các toán tử đẳng thức .

Các giá trị chỉ được truy vấn với các toán tử đẳng thức.

Bây giờ, hãy theo dõi điểm chuẩn và so sánh hiệu suất và mức tiêu thụ bộ nhớ.

Trước khi chúng ta xem xét kết quả, tôi muốn chia sẻ các quy trình PL/pgSQL mà tôi đã sử dụng để nghiên cứu các số liệu.

Quy random_stringtrình dưới đây tạo các chuỗi ngẫu nhiên có độ dài nhất định.

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

Các kết quả được thu thập bằng PostgreSQL 15.1.

Hãy đi sâu vào so sánh mức tiêu thụ bộ nhớ. Dưới đây, tôi sẽ đăng một loạt biểu đồ cho các hàng 1.000, 10.000, 100.000 và 1.000.000.