Nghịch thử Postgres Gin index

Gần đây, mình đang tìm hiểu và sử dụng thêm 1 loại index mới mà các RDBMS hỗ trợ: Gin Index (tương tự MySQL có Fulltext). Vậy thì chính xác nó dùng cho mục đích gì ?

Recap Invert Index

GIN (Generalized Inverted Index), như cái tên gợi mở của nó, là một Inverted Index. Nghe tới đây chắc hẳn bạn đọc sẽ thấy nó giống với cách đánh index của ElasticSearch, đây cũng là cách đánh index tối ưu nhất cho use-case searching.

Mục đích của một inverted index, đó là từ 1 elem bất kỳ loại dữ liệu(là một phần tử trong array, một keyword trong 1 documents,…) truy ngược lại nó thuộc về document nào.

Ví dụ 3 đoạn văn bản sau:

This is first document

this is second document

this is third document

Inverted index:

Term DocID
This 1
this 2,3
is 1,2,3
first 1
second 2
third 3
document 1,2,3

Ngược lại, ta cũng có forward index:

DocID Terms
1 This,is,first,document
2 this,is,second,document
3 this,is,third,document

Tất nhiên trong DB, biểu diễn của inverted index còn phức tạp hơn nhiều(tf-id,…) Có thể thấy rằng, với Inverted index, việc tìm kiếm 1 keyword trong 1 docs rất dễ dàng.

Vấn đề

Ok, Use-case fulltext search thì khá phổ biến, hãy thử 1 use-case khác: Post & tags

Funtional Requirement:

  • Một post sẽ có rất nhiều tags, assume nhiều nhất 1000 tags
  • Từ tags, tìm kiếm posts

Không dùng GIN

Không có GIN, ta có thể thiết kế normalized database như thông thường:

posts

Column Type Note
id serial, primary key
title varchar(255)
content text
author_id integer foreign key(user)

tags

Column Type Note
id serial, primary key
name varchar(255)
description text

posts_tags

Column Type Note
post_id integer pkey: (post_id, tag_id)
tag_id integer

Dùng GIN:

posts

Column Type Note
id serial, primary key
title varchar(255)
content text
author_id integer foreign key(user)
tags varchar(255)[]

Như có thể thấy table này đã được denormalized ở cột tags

Tạo GIN index:

CREATE INDEX idx_posts_tags on posts USING GIN (tags);

Query posts có tag postgres:

EXPLAIN ANALYZE SELECT * FROM `posts` 
WHERE "tags" @> ARRAY['postgres'::varchar] ORDER BY ID LIMIT 10;

Kết quả

Limit  (cost=12.03..12.04 rows=1 width=64) (actual time=0.022..0.025 rows=1 loops=1)
  ->  Sort  (cost=12.03..12.04 rows=1 width=64) (actual time=0.021..0.022 rows=1 loops=1)
        Sort Key: id
        Sort Method: quicksort  Memory: 25kB
        ->  Bitmap Heap Scan on posts3  (cost=8.01..12.02 rows=1 width=64) (actual time=0.015..0.017 rows=1 loops=1)
              Recheck Cond: (tags @> '{postgres}'::character varying[])
              Heap Blocks: exact=1
              ->  Bitmap Index Scan on posts3_user_ids_idx  (cost=0.00..8.01 rows=1 width=0) (actual time=0.009..0.010 rows=1 loops=1)
                    Index Cond: (tags @> '{postgres}'::character varying[])
Planning Time: 0.112 ms
Execution Time: 0.049 ms

Như có thể thấy, database được denormalized và đơn giản hơn rất nhiều so với many-to-many relations. Lợi ích có thể thấy được đó là việc migrations, scale ngang sẽ dễ dàng hơn nếu có scale về data

Hạn chế

  • Khi mình test với lượng data lớn lên tới vài triệu rows, việc dùng GIN index và ORDER BY đang có vấn đề - pagination do đó cũng sẽ không work được, Postgres stats đang collect không đủ data, postgres planner do đó đang không sử dụng Gin index (thay vào đó dùng một index khác) làm cho câu query rất chậm, trong tương lai postgres sẽ tích hợp Gin sorted index, fix performance của Order BY khi dùng với GIN. Hiện tại, chỉ có thể có vài cách cheating để force postgres dùng GIN index thay vì một index khác
  • Tất cả ví dụ bên dưới mình đều đã chạy VACUUM FULL và ANALYZE trước khi thực hiện query Ví dụ:
EXPLAIN ANALYZE 
  SELECT * FROM `posts` 
  WHERE 
    "tags" @> ARRAY['postgres'::varchar] ORDER BY id LIMIT 10;

Result:

Limit  (cost=0.43..212.05 rows=10 width=578) (actual time=26417.740..26417.741 rows=0 loops=1)
  ->  Index Scan using posts_pkey on posts  (cost=0.43..219748.75 rows=10384 width=578) (actual time=26417.736..26417.737 rows=0 loops=1)
        Filter: (tags @> '{postgres}'::character varying[])
        Rows Removed by Filter: 2100000
Planning Time: 0.953 ms
Execution Time: 26417.917 ms

Khá là lạ khi mà Postgres Execution planner chọn pkey để thực hiện việc filter

Tuy nhiên, nếu thử order trên một column khác, không có index(như content):

Limit  (cost=32865.58..32865.59 rows=1 width=578) (actual time=0.203..0.204 rows=0 loops=1)
  ->  Sort  (cost=32865.58..32891.54 rows=10384 width=578) (actual time=0.201..0.202 rows=0 loops=1)
        Sort Key: author_id
        Sort Method: quicksort  Memory: 25kB
        ->  Bitmap Heap Scan on posts  (cost=116.47..32813.66 rows=10384 width=578) (actual time=0.192..0.193 rows=0 loops=1)
              Recheck Cond: (tags && '{151818c6-d8ee-40d2-9985-6f6ba8046f51}'::character varying[])
              ->  Bitmap Index Scan on idx_posts_user_ids  (cost=0.00..113.88 rows=10384 width=0) (actual time=0.031..0.031 rows=0 loops=1)
                    Index Cond: (tags && '{151818c6-d8ee-40d2-9985-6f6ba8046f51}'::character varying[])
Planning Time: 0.382 ms
Execution Time: 0.416 ms

Kết luận

  • GIN index là một inverted index hỗ trợ cho RDBMS. Với nó, nhu cầu design denormalized database sẽ có thể được thực hiện dễ dàng
  • Hạn chế cần cân nhắc đó là nó còn khá là immature. Postgres Query Planner còn khá “dummy”, nên có lẽ vẫn còn cần thời gian để cộng đồng postgres cải thiện, lời khuyên là đừng nên dùng nó vào trong Production nếu bạn không biết bạn đang làm gì và well-tested

References

Table of content

Tags

Share article with

comments powered by Disqus