ดัชนี PostgreSQL: Hash vs B-tree

คุณรู้เสมอว่าเมื่อใดควรใช้ดัชนีแฮชเหนือดัชนี b-tree ประโยชน์ที่ได้รับจากการเลือกจะมีนัยสำคัญเพียงใด ฉันไม่.

ดังนั้นฉันจึงทำการค้นคว้าเล็กน้อยเพื่อค้นหากฎง่ายๆ และในบทความนี้ฉันจะแบ่งปันผลลัพธ์

UPD : บทความได้รับการอัปเดต

น่าเสียดาย ในเวอร์ชันโพสต์แรก ฉันทำผิดพลาดเล็กน้อยในเกณฑ์มาตรฐานที่ยากจะตรวจจับได้ คุณสามารถอ่านเพิ่มเติมได้ในบทความนี้

สปอยเลอร์: ดัชนีแฮชหวานยิ่งขึ้นในขณะนี้

ฉันข้ามส่วนที่เกี่ยวกับb-treeและ ดัชนี แฮชเนื่องจากมีแหล่งข้อมูลมากมายที่คุณสามารถอ่านได้ อย่างไรก็ตาม ฉันหยุดสักครู่กับคำอธิบายแฮชจาก เอกสาร อย่างเป็นทางการของ 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

เรามาเน้นบางสิ่งที่เราเห็นในแผนภูมิ:

• ดัชนีแฮชเป็นข้อมูลที่ไม่เชื่อเรื่องพระเจ้า หมายความว่าขนาดขึ้นอยู่กับจำนวนข้อมูลที่จัดทำดัชนีเท่านั้น
• ยิ่งคุณมีแถวมากเท่าใด คุณก็ต้องใช้ความยาวสตริงน้อยลงเพื่อรับประโยชน์จากดัชนีแฮช
• ในกรณีส่วนใหญ่ ดัชนีแฮชจะใช้หน่วยความจำน้อยกว่าฟิลด์ที่เก็บไว้ ในขณะที่ b-tree ต้องการมากกว่าฟิลด์ที่เก็บไว้
• ความยาวเริ่มต้นที่เราเห็นประโยชน์อาจอยู่ระหว่าง 15–30; อย่างไรก็ตาม เพื่อลดความซับซ้อนของกฎง่ายๆ เราจะบอกว่า อย่าง น้อย25

ตอนนี้ข้ามไปที่การเปรียบเทียบประสิทธิภาพ

จากแผนภูมิสำหรับการเปรียบเทียบประสิทธิภาพ เราอาจพูดว่า:

• ในทุกกรณี ประสิทธิภาพจะดีกว่าเมื่อ ใช้ ดัชนีแฮช
• ข้อความค้นหาแบบเลือกได้ เพิ่มขึ้น 20–60%เพิ่มขึ้นตามจำนวนแถว
• ข้อความค้นหาแทรกมีการเพิ่มขึ้น 10–80%เพิ่มขึ้นตามจำนวนแถว
• ดัชนีทั้งสองทำงานได้เร็ว และบางดัชนีอาจเพิกเฉยต่อการเพิ่ม 0.01 มิลลิวินาที

• ประหยัดเนื้อที่ดิสก์ ประมาณ 1.5GB ( เล็กกว่าดัชนี b-tree ถึง 50 เท่า );
• ให้การเพิ่มประสิทธิภาพประมาณ60–80% ( 0.02–0.04msต่อการสืบค้น)

เรามาสรุปกฎของหัวแม่มือกัน:

• ค่ามีความสำคัญสูง ตามหลักการแล้ว รหัสแฮชของพวกเขามีจำนวนสมาชิกสูงเช่นกัน
• ค่าจะถูกสอบถามด้วยตัวดำเนินการความเท่าเทียมกัน เท่านั้น
• ความยาวของค่าควรมีความยาวอย่างน้อย 25 อักขระ