Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Database & ORMSenior26 phút đọc

Các loại index ngoài B-tree: hash, GIN, GiST, bitmap và LSM-tree

Ôn 19 thẻ
Trong bài này

Cụm bài Index chuyên sâu: 1. Index bên trong · 2. Các loại index ngoài B-tree

B-tree giỏi “bằng”, “trong khoảng” và “sắp xếp”, nhưng backend còn cần chứa tag, JSON có key, văn bản khớp từ khoá, khoảng chồng nhau, điểm gần nhất, hay tải ghi cực lớn. Đọc xong, bạn chọn được hash, GIN, GiST, bitmap hay LSM-tree theo hình dạng truy vấn và biết cái giá khi ghi của từng loại (số đo trên PostgreSQL 16 và MySQL 8.4 chạy Docker trên laptop: nhớ tỉ lệ hơn con số). Nên đọc trước Index bên trong và lab index PostgreSQL, bài đó đã đo hash index và BRIN.

1. Hash index: phần còn thiếu

Ý chính: hash chỉ trả lời “bằng giá trị này”. Hàm băm cố ý phá thứ tự, nên không có range, sort, UNIQUE hay nhiều cột.

  • Hai khoá kề nhau rơi vào hai bucket bất kỳ, nên không thể “đi tiếp sang khoá kế bên”. Lab trước: trên PostgreSQL hash chỉ nhỉnh hơn B-tree với =.
  • Hai khoá khác nhau có thể trùng bucket (collision), nên index chỉ trả ứng viên và DB phải so lại giá trị thật.
  • MySQL: InnoDB có adaptive hash index (AHI), bảng băm InnoDB tự dựng trong RAM cho các trang B-tree hay bị tra bằng. Từ 8.4 nó mặc định tắt.
Hash phía MySQL: engine MEMORY và adaptive hash index

Engine MEMORY dùng hash mặc định (mất dữ liệu khi restart). Slide nói “clustered index InnoDB không thể là hash” là đúng với cấu trúc trên đĩa, nhưng AHI vẫn là một lớp hash phía trên.

2. GIN: inverted index cho “chứa phần tử”

Ý chính: GIN tách mỗi giá trị thành phần tử và lưu, với mỗi phần tử, danh sách dòng chứa nó. Nó trả lời “chứa X” cho mảng, jsonb và full-text, nhưng chỉ với toán tử thuộc operator class của nó.

2.1. Cấu trúc

Ý chính: GIN là một B-tree trên các phần tử, mỗi lá trỏ tới một posting list (danh sách id dòng chứa phần tử đó).

B-tree trên cột tags text[] coi cả mảng là một giá trị. GIN (Generalized Inverted Index) lật ngược quan hệ, giống mục lục cuối sách, và cũng là lõi của Elasticsearch.

flowchart LR
  R1["id 1: {kafka, java}"] --> K2["kafka → [1, 3]"]
  R1 --> K1["java → [1]"]
  R2["id 2: {redis}"] --> K3["redis → [2, 3]"]
  R3["id 3: {kafka, redis}"] --> K2
  R3 --> K3
  • Posting list được nén; dài quá thì thành posting tree.
  • tags @> ARRAY['kafka','redis'] tra hai phần tử rồi lấy giao hai danh sách.
  • GIN trả một tập dòng không theo thứ tự, nên gần như luôn đi kèm Bitmap Heap Scan.

2.2. Mảng tag

Ý chính: GIN trên mảng nhỏ và nhanh với @>, &&, nhưng = ANY thì không dùng được nó.

Bảng 300.000 bài, mỗi bài 1–4 tag trong 50 tag, phân bố lệch (tag0 có trong 92.065 bài, tag49 trong 7.386 bài). GIN trên tags chỉ 1,6 MB cho bảng 64 MB.

Truy vấn Không index Có GIN
tags @> ARRAY['tag49'] Parallel Seq Scan 20,8 ms 3,6 ms
tags @> ARRAY['tag49','tag48'] (156 dòng) Seq Scan 0,43 ms
tags && ARRAY['tag49','tag48'] (một trong hai) Seq Scan 5,0 ms
'tag49' = ANY(tags) Seq Scan 18 ms vẫn Seq Scan 18 ms

2.3. jsonb: hai operator class

Ý chính: GIN trên jsonb phục vụ “chứa” (@>) cho mọi key. Lọc attrs->>'k' = 'v' thì không dùng GIN nào, cần expression index.

  • attrs @> '{"author_id": 42}' (GIN): 0,07 ms. attrs->>'author_id' = '42': Seq Scan 33 ms.
  • Sửa bằng expression index B-tree trên đúng biểu thức ((attrs->>'author_id')::int): 0,08 ms.
Bảng jsonb_ops và jsonb_path_ops, và chi tiết số đo

Với attrs jsonb dạng {"lang": "vi", "author_id": 42, "featured": false}:

Operator class Index gì Toán tử Kích thước
jsonb_ops (mặc định) Từng key và từng value @>, ?, `? , ?&, @?, @@`
jsonb_path_ops Hash của cả đường dẫn tới value @>, @?, @@ 2,7 MB
  • attrs ? 'promo' (có key không) chỉ dùng được jsonb_ops.
  • attrs->>'author_id' = '42' không dùng GIN nào vì ->> cộng = trên text không thuộc operator class.
  • Expression index đầy đủ: CREATE INDEX ON post (((attrs->>'author_id')::int)), rồi viết WHERE (attrs->>'author_id')::int = 42.

Ý chính: full-text tách văn bản thành lexeme (từ đã chuẩn hoá) trong tsvector rồi index bằng GIN. ILIKE '%kafka%production%' 180 ms, full-text 22 ms.

ALTER TABLE post ADD COLUMN tsv tsvector
  GENERATED ALWAYS AS (to_tsvector('simple', title)) STORED;
CREATE INDEX post_tsv_gin ON post USING gin (tsv);

SELECT id, title, ts_rank(tsv, q) AS rank
FROM post, websearch_to_tsquery('simple', 'kafka production') q
WHERE tsv @@ q
ORDER BY rank DESC LIMIT 10;
  • 5.981 bài khớp; riêng Bitmap Index Scan 1,9 ms, phần còn lại của 22 ms là xếp hạng và sort.
  • websearch_to_tsquery hiểu cú pháp kiểu Google ("cụm từ", -loại trừ, or), an toàn hơn to_tsquery với chuỗi người dùng gõ.
  • Tiếng Việt: không có cấu hình ngôn ngữ riêng, dùng 'simple' cộng unaccent. Cần tách từ, đồng nghĩa, gợi ý thì chuyển sang Elasticsearch/OpenSearch.
Tiếng Việt với unaccent, FULLTEXT của MySQL và bẫy token duy nhất

PostgreSQL và tiếng Việt. 'simple' không stem; unaccent cho tìm không dấu ('Tối ưu Kafka' thành 'toi' 'uu' 'kafka'). unaccent() không IMMUTABLE, đưa thẳng vào generated column sẽ lỗi generation expression is not immutable; phải bọc trong một hàm IMMUTABLE gọi unaccent với dictionary chỉ định rõ.

MySQL có FULLTEXT trên InnoDB (MATCH ... AGAINST). Lab trên 100.000 tiêu đề tiếng Việt:

  • +kafka +production ra 2.078 dòng, đúng bằng LIKE.
  • +toi không dấu vẫn khớp “tối” nhờ collation utf8mb4_0900_ai_ci.
  • +ưu ra 0 dòng: parser mặc định bỏ token ngắn hơn innodb_ft_min_token_size = 3 ký tự, mà nhiều âm tiết tiếng Việt chỉ có hai ký tự.
  • Parser ngram (cụm 2 ký tự, sinh ra cho tiếng Trung, Nhật, Hàn) tìm được “ưu” nhưng index lớn hơn và dễ khớp nhầm.
  • Lần nạp đầu dính bẫy client mysql mặc định latin1: chuỗi UTF-8 bị mã hoá hai lần và MATCH trả 0 dòng cho mọi từ có dấu. Luôn đặt --default-character-set=utf8mb4 hoặc SET NAMES utf8mb4.

2.5. Cái giá khi ghi: pending list

Ý chính: một dòng có 7 phần tử thì GIN phải chèn vào 7 posting list. fastupdate (mặc định bật) gom dòng mới vào một pending list để ghi rẻ, đổi lại có những cú nhảy p99.

Pending list là danh sách chưa sắp xếp, được gộp vào cấu trúc chính khi vượt gin_pending_list_limit (mặc định 4 MB), khi autovacuum chạy, hoặc khi gọi gin_clean_pending_list(). Chèn 300.000 dòng vào bảng có hai GIN (tags, attrs):

Cấu hình Thời gian
Không index 0,29 s
fastupdate = on 1,07 s
fastupdate = off 4,5 s

3. GiST và SP-GiST: khoảng, toạ độ và “gần nhất”

Ý chính: GiST là cây các “hộp bao”; nó trả lời “chồng lên nhau” và “gần nhất”. Ứng dụng backend quan trọng nhất là exclusion constraint chống đặt phòng trùng.

3.1. Ý tưởng R-tree

Ý chính: mỗi node trong lưu một hộp bao (bounding box) chứa mọi thứ bên dưới; tìm “cái gì chồng lên vùng này” chỉ đi xuống nhánh có hộp giao với vùng đó.

  • GiST (Generalized Search Tree) dựng cây cân bằng cho mọi kiểu có “hộp bao” và phép “chồng lấn”. Với tstzrange, “hộp” là đoạn thời gian nhỏ nhất chứa các đoạn con.
  • Khác B-tree, các hộp có thể chồng nhau: một truy vấn có thể đi nhiều nhánh, và kết quả từ index cần kiểm tra lại.
  • SP-GiST (space-partitioned) chia không gian thành vùng không chồng nhau (quadtree, k-d tree), thường nhỏ hơn với điểm phân bố đều: 8,9 MB so với 13 MB của GiST trên 200.000 điểm.

3.2. Exclusion constraint: chống đặt phòng trùng

Ý chính: exclusion constraint tổng quát hoá UNIQUE thành “không có hai dòng mà mọi toán tử liệt kê đều đúng”. Database tự chặn, kể cả khi hai transaction chạy song song.

UNIQUE không diễn đạt được “chồng thời gian”, còn kiểm tra bằng code (SELECT rồi INSERT) có race condition giữa hai transaction (xem transaction và isolation level).

CREATE EXTENSION IF NOT EXISTS btree_gist;  -- cho phép dùng = trên bigint trong GiST

CREATE TABLE room_booking (
  id      bigserial PRIMARY KEY,
  room_id bigint    NOT NULL,
  during  tstzrange NOT NULL,
  EXCLUDE USING gist (room_id WITH =, during WITH &&)
);

INSERT INTO room_booking (room_id, during) VALUES
  (1, tstzrange('2026-12-01 14:00+07', '2026-12-03 12:00+07', '[)')),
  (1, tstzrange('2026-12-03 12:00+07', '2026-12-05 12:00+07', '[)')), -- nối tiếp: OK
  (2, tstzrange('2026-12-01 14:00+07', '2026-12-03 12:00+07', '[)')); -- phòng khác: OK

INSERT INTO room_booking (room_id, during)
VALUES (1, tstzrange('2026-12-02 14:00+07', '2026-12-04 12:00+07', '[)'));
-- ERROR: conflicting key value violates exclusion constraint (SQLSTATE 23P01)
  • Biên [) (gồm đầu, không gồm cuối): khách trả phòng 12:00 và khách nhận phòng 12:00 không bị coi là chồng lấn.
  • Index GiST của ràng buộc cũng được planner dùng cho truy vấn thường như “phòng nào bận ngày 1/3”.
Thử hai session song song và bẫy kiểu bigint với btree_gist

Thử đồng thời. Session A chèn phòng 7 ngày 10–12 và giữ transaction 2 giây; session B chèn phòng 7 ngày 11–13 bị chặn chờ khoảng 1,5 giây, A commit thì B nhận lỗi 23P01. Ràng buộc đúng cả khi chạy song song, không cần khoá ở tầng ứng dụng.

3.3. Tìm gần nhất (KNN)

Ý chính: GiST và SP-GiST sắp theo khoảng cách ngay trong index với <->, duyệt “hộp gần nhất trước” và dừng khi đủ kết quả.

CREATE INDEX homestay_loc_gist ON homestay USING gist (loc);  -- loc kiểu point
SELECT id, name FROM homestay ORDER BY loc <-> point(105.85, 21.03) LIMIT 5;
  • 200.000 điểm: SP-GiST 0,03 ms, GiST 0,08 ms; không index thì Parallel Seq Scan cộng top-N sort 30 ms.
  • point là toạ độ phẳng; khoảng cách thật theo kinh vĩ độ cần PostGIS kiểu geography, vẫn dùng GiST bên dưới.
  • MySQL có SPATIAL INDEX (R-tree) cho kiểu hình học nhưng không có KNN qua index như <->.

4. Bitmap index và bitmap scan: hai thứ khác nhau

Ý chính: bitmap index lưu sẵn (Oracle, kho dữ liệu) khác hẳn bitmap scan lúc chạy của PostgreSQL. Bài toán “đếm đơn PROCESSING” trong slide, trên PostgreSQL, giải bằng partial index.

  • Bitmap index lưu sẵn (Oracle, kho dữ liệu dạng cột): mỗi giá trị của cột một chuỗi bit, bit thứ i bằng 1 nếu dòng i có giá trị đó, nén rất tốt. status = 'PROCESSING' AND region = 'HN' là AND hai chuỗi bit; đếm là đếm bit 1.
  • Bitmap scan lúc chạy (PostgreSQL): không có bitmap index trên đĩa. Executor dùng B-tree/GIN/GiST dựng bitmap trong bộ nhớ (Bitmap Index Scan), có thể AND/OR nhiều bitmap (BitmapAnd, BitmapOr), rồi đọc heap theo thứ tự vật lý.
  • MySQL không có cả hai; gần nhất là index merge (Using union(idx_author, idx_lang) cho author_id = 42 OR lang = 'ja' trong lab).

Vì sao kho dữ liệu dạng cột (ClickHouse) hợp với báo cáo quét nhiều dòng nhưng ít cột có ở bài chọn database.

Trên bảng orders 1 triệu dòng, partial index (id) WHERE status = 'PROCESSING' chỉ 128 KB mà vẫn cho Index Only Scan dưới 1 ms; giá trị phổ biến (90% bảng) thì không index nào giúp.

Số đo đếm đơn trên bảng orders 1 triệu dòng

5.105 đơn PROCESSING, đếm count(*):

Cách Kích thước Thời gian
Không index – Parallel Seq Scan 43 ms
B-tree (status) 6,9 MB Index Only Scan 0,37 ms
Partial index (id) WHERE status = 'PROCESSING' 128 KB Index Only Scan 0,69 ms

Đơn chuyển sang COMPLETED tự rời partial index. Còn WHERE status = 'COMPLETED' (90% bảng) thì không index nào giúp: vẫn Seq Scan 90 ms, đúng như slide nói đừng index cột ít giá trị cho giá trị phổ biến.

5. LSM-tree: khi ghi là chính

Ý chính: B-tree sửa trang tại chỗ, nên tải ghi lớn bị giới hạn bởi ghi ngẫu nhiên. LSM-tree (Log-Structured Merge tree) không bao giờ sửa tại chỗ: ghi nối tiếp, rồi gộp file ở nền.

flowchart TB
  W["Ghi (put/delete)"] --> WAL["WAL trên đĩa"]
  W --> M["Memtable trong RAM"]
  M -->|"đầy: flush"| L0["L0: SSTable bất biến"]
  L0 -->|"compaction"| L1["L1"]
  L1 -->|"compaction"| L2["L2: lớn gấp ~10 lần L1"]
  R["Đọc key"] --> M
  R --> BF["Bloom filter từng SSTable"]
  BF --> L0
  BF --> L1
  BF --> L2
  • Ghi: vào memtable (cây sắp xếp trong RAM) và ghi nối tiếp vào WAL. Memtable đầy thì xả thành SSTable, file bất biến sắp theo key. Xoá là ghi một tombstone (dấu “đã xoá”).
  • Đọc: xem memtable rồi các SSTable từ mới đến cũ; bloom filter mỗi file trả lời “chắc chắn không có key này” để bỏ qua file.
  • Compaction: tiến trình nền gộp SSTable, bỏ bản cũ và tombstone. Size-tiered gộp file cùng cỡ (ghi rẻ, tốn chỗ, đọc xem nhiều file; mặc định cũ của Cassandra). Leveled giữ mỗi tầng lớn gấp ~10 lần tầng trước, key không chồng nhau trong tầng (đọc và dung lượng tốt hơn, ghi lại nhiều hơn; mặc định của RocksDB).

Phần này không có lab; các con số amplification là khoảng thường gặp trong tài liệu RocksDB, cần đo lại với tải thật.

6. Chọn loại index theo hình dạng truy vấn

Ý chính: nhìn toán tử trong WHERE/ORDER BY rồi chọn loại index phục vụ toán tử đó.

Slide của khoá học phân loại index theo cấu trúc dữ liệu (B+tree, hash, inverted, LSM-tree, R-tree, bitmap); bảng dưới xếp lại theo câu hỏi bạn cần trả lời.

Hình dạng truy vấn Ví dụ PostgreSQL MySQL
Bằng, khoảng, sắp xếp created_at >= ? ORDER BY created_at B-tree B-tree
Phần tử trong mảng tags @> '{kafka}' GIN Bảng N–N, hoặc multi-valued index trên JSON (8.0.17+)
Chứa trong JSON attrs @> '{"featured": true}' GIN jsonb_path_ops Multi-valued index / generated column
Từ khoá trong văn bản “kafka production” GIN trên tsvector FULLTEXT
Chuỗi con bất kỳ LIKE '%abc%' GIN pg_trgm Search engine
Khoảng chồng lấn, chống trùng during && ? GiST + exclusion constraint Khoá + kiểm tra
Gần nhất ORDER BY loc <-> ? GiST / SP-GiST / PostGIS SPATIAL lọc theo vùng
Giá trị hiếm trong cột ít giá trị status = 'PROCESSING' Partial index Index thường

Ví dụ thực tế của dòng LIKE '%abc%' là ô tìm sản phẩm trong bài phân trang và lọc động: lower(name) like '%tuf%' quét cả bảng cho tới khi có GIN pg_trgm.

7. Case study: tìm bài theo tag, từ khoá và thời gian

Ý chính: ba index đơn (GIN tags, GIN tsv, B-tree created_at) đủ nhanh ở 300.000 dòng và phục vụ nhiều màn hình. Chuyển sang Elasticsearch khi cần ranking tiếng Việt tốt hoặc tìm kiếm ăn phần lớn CPU database.

Đề bài. Trang quản trị blog: chọn một tag, gõ từ khoá, chọn “30 ngày gần đây”, hiện 20 bài mới nhất. Bảng post 300.000 dòng, tăng khoảng 2.000 bài/ngày. Có thêm trang “bài mới nhất của một tag” không có từ khoá.

Câu SQL, ba phương án, số đo phương án 1 và bẫy ORDER BY … LIMIT
SELECT id, title, created_at FROM post
WHERE tags @> ARRAY['tag12']
  AND tsv @@ websearch_to_tsquery('simple', 'kafka production')
  AND created_at >= now() - interval '30 days'
ORDER BY created_at DESC
LIMIT 20;
Phương án Được Mất
(1) Ba index riêng, planner tự chọn Nhỏ, mỗi index phục vụ nhiều màn hình Phụ thuộc lựa chọn của planner
(2) Một GIN nhiều cột với btree_gin Một index nhận cả ba điều kiện GIN không trả theo thứ tự nên vẫn sort; ghi đắt hơn
(3) Elasticsearch đồng bộ qua CDC Ranking và tiếng Việt tốt nhất Thêm một hệ thống, dữ liệu trễ vài giây

Đo phương án 1. Planner không dùng BitmapAnd. Nó bắt đầu từ điều kiện nó tin là chọn lọc nhất (tsv, 5.981 dòng), lọc tags và created_at trên từng dòng heap, ra 34 dòng, sort: 4,9 ms khi dữ liệu trong cache, 176 ms khi cache lạnh (đọc 4.444 trang từ đĩa). Với trang chỉ có tag, plan đổi hẳn: Index Scan Backward trên B-tree created_at, lọc tag từng dòng, dừng khi đủ 20 bài: 0,13 ms với tag49, 0,02 ms với tag0.

Chọn. Phương án 1 (ba index riêng, 4,9 ms khi cache nóng) thay vì (2) một GIN nhiều cột với btree_gin hay (3) Elasticsearch qua CDC. Plan ORDER BY ... LIMIT có thể chậm đột ngột với tag hiếm, nên theo dõi max latency.

Bài tập

Bài 1: Chống đặt phòng trùng ở tầng database

Đề (diễn đạt lại). Hai khách bấm đặt cùng phòng cùng lúc thỉnh thoảng đều thành công. Chặn ở tầng database và trả HTTP 409 cho người đến sau.

Lời giải Bài 1: exclusion constraint và bắt lỗi 23P01 trong Spring Boot

Exclusion constraint như mục 3.2, biên [). Ở Spring Boot, lỗi 23P01 đi qua Hibernate thành DataIntegrityViolationException; bắt và đổi thành 409:

@Transactional
public Booking book(long roomId, OffsetDateTime checkIn, OffsetDateTime checkOut) {
    try {
        return repo.saveAndFlush(new Booking(roomId, checkIn, checkOut)); // flush để lỗi nổ ở đây
    } catch (DataIntegrityViolationException e) {
        if (e.getMostSpecificCause() instanceof SQLException sql
                && "23P01".equals(sql.getSQLState())) {      // exclusion_violation
            throw new RoomAlreadyBookedException(roomId);    // @ResponseStatus(CONFLICT)
        }
        throw e;
    }
}

Nếu không muốn map tstzrange trong JPA, lưu check_in, check_out rồi đặt constraint trên biểu thức EXCLUDE USING gist (room_id WITH =, tstzrange(check_in, check_out, '[)') WITH &&). Phần SQL đã chạy trên PG16, kể cả thử hai session song song; đoạn Java chưa chạy.

Bài 2: Vì sao ba câu này không dùng index?

Đề. Có GIN trên tags, GIN jsonb_path_ops trên attrs, exclusion constraint GiST (room_id WITH =, during WITH &&) với room_id bigint. Giải thích và sửa:

SELECT id FROM post WHERE 'tag49' = ANY(tags);
SELECT id FROM post WHERE attrs->>'author_id' = '42';
SELECT 1 FROM room_booking WHERE room_id = 500 AND during && tstzrange('2027-03-01','2027-03-02');
Lời giải Bài 2 (đã chạy)
  1. = ANY không thuộc operator class GIN mảng; viết tags @> ARRAY['tag49'] (18 ms xuống 3,6 ms).
  2. ->> cộng = trên text không phải toán tử GIN; viết attrs @> '{"author_id": 42}' (0,07 ms) hoặc tạo expression index rồi viết đúng biểu thức (0,08 ms).
  3. 500 là int4 mà btree_gist không có int8 = int4; viết 500::bigint (6,4 ms xuống 0,65 ms).

Bài học: index được chọn theo toán tử và kiểu, không theo tên cột; đọc Index Cond và Filter trong plan.

Ghi nhớ

  • Giải thích được vì sao hash không phục vụ range/sort, và vì sao GIN trả dòng không theo thứ tự.
  • Biết vì sao = ANY, ->> = và literal int4 trên cột bigint làm index bị bỏ qua, và sửa từng câu.
  • Viết được exclusion constraint chống đặt phòng trùng và nói được vì sao nó đúng khi chạy song song.
  • Phân biệt được bitmap index lưu sẵn với bitmap scan, và biết dùng partial index cho giá trị hiếm.
  • So sánh được B-tree và LSM-tree qua ba loại amplification, và biết dấu hiệu compaction tụt hậu.

Câu hỏi phỏng vấn

Junior

Vì sao hash index không phục vụ được range hay ORDER BY?

Vì hàm băm cố ý phá thứ tự: index không biết khoá nào đứng cạnh khoá nào.

Các khoá gần nhau rơi vào bucket bất kỳ, nên không thể đi từ khoá này sang khoá kế tiếp. Hash chỉ trả lời “bằng giá trị này”, và vì có collision nên DB vẫn phải so lại giá trị thật.

Inverted index là gì?

Cấu trúc lưu, với mỗi phần tử (từ, tag, key JSON), danh sách các dòng chứa nó, giống mục lục cuối sách.

“Chứa X” là tra X; “chứa X và Y” là giao hai danh sách. GIN của PostgreSQL và Elasticsearch đều theo ý tưởng này.

Mid

jsonb_ops và jsonb_path_ops khác nhau thế nào?

jsonb_ops index từng key và value, hỗ trợ thêm ?; jsonb_path_ops index hash cả đường dẫn, nhỏ và nhanh hơn cho @> nhưng không hỗ trợ ?.

Toán tử kiểm tra key của jsonb_ops là ?, ?|, ?&. Cả hai không phục vụ attrs->>'k' = 'v'; trường hợp đó cần expression index.

Full-text search trong PostgreSQL hoạt động thế nào?

Văn bản thành tsvector, câu tìm thành tsquery, @@ kiểm tra khớp, GIN trên tsvector để tìm nhanh.

tsvector là lexeme chuẩn hoá kèm vị trí theo một cấu hình ngôn ngữ; ts_rank để xếp hạng. Thường lưu tsvector trong generated column. Tiếng Việt dùng cấu hình simple cộng unaccent.

Exclusion constraint giải quyết gì mà UNIQUE không giải quyết được?

UNIQUE chỉ cấm hai dòng bằng nhau; exclusion constraint cấm hai dòng mà mọi toán tử liệt kê đều đúng, ví dụ cùng phòng và chồng thời gian.

room_id WITH =, during WITH && cấm hai booking cùng phòng chồng thời gian. Nó dùng index GiST và đúng cả khi transaction chạy song song: transaction sau chờ rồi nhận lỗi 23P01.

GIN fastupdate ảnh hưởng gì tới độ trễ?

Bật thì ghi rẻ hơn nhiều nhưng có đột biến p99; tắt thì độ trễ ghi đều nhưng cao hơn.

Khi bật, dòng mới vào pending list chưa sắp xếp; đọc phải quét thêm list, và câu ghi nào làm list vượt gin_pending_list_limit phải gộp cả list.

Senior

Bitmap index và bitmap heap scan của PostgreSQL khác nhau thế nào?

Bitmap index lưu trên đĩa (Oracle, kho dữ liệu); bitmap heap scan là bitmap PostgreSQL dựng trong bộ nhớ lúc chạy từ index thường.

Bitmap index mỗi giá trị một chuỗi bit, rất tốt cho cột ít giá trị nhưng khoá theo đoạn bitmap nên tệ với OLTP ghi đồng thời. PostgreSQL dựng bitmap từ B-tree/GIN/GiST, có thể AND/OR nhiều bitmap, rồi đọc heap theo thứ tự vật lý. “Đếm đơn PROCESSING” trên PG giải bằng partial index.

Khi nào chọn storage engine LSM-tree thay vì B-tree?

Khi tải ghi lớn và chiếm đa số (event, log, time-series, counter), truy cập theo key, cần nén tốt.

Phải chấp nhận read amplification (bloom filter chỉ giúp point lookup), write amplification do compaction, dung lượng tạm thời lớn và rủi ro compaction tụt hậu. OLTP nhiều đọc, range scan và truy vấn ad-hoc thì B-tree hợp hơn.

Size-tiered và leveled compaction khác nhau thế nào?

Size-tiered ghi rẻ nhưng đọc và dung lượng tệ hơn; leveled đọc và dung lượng tốt hơn nhưng ghi lại nhiều hơn.

Size-tiered gộp các SSTable cùng cỡ: một key nằm ở nhiều file và cần nhiều chỗ trống khi gộp. Leveled giữ tầng sau lớn gấp ~10 lần tầng trước, file trong một tầng không chồng key, nên mỗi byte bị ghi lại nhiều lần hơn.

Bạn thiết kế index cho màn hình tìm bài theo tag, từ khoá, thời gian, mới nhất trước thế nào?

Bắt đầu bằng index đơn phục vụ nhiều màn hình (GIN tags, GIN tsvector, B-tree created_at), đo plan trên dữ liệu thật và theo dõi max latency.

Planner thường bắt đầu từ điều kiện chọn lọc nhất rồi lọc phần còn lại, hoặc đi ngược B-tree thời gian khi có LIMIT. Plan ORDER BY ... LIMIT tệ với bộ lọc hiếm, nên nhìn max chứ không chỉ trung bình. Khi cần ranking và tiếng Việt tốt hơn thì chuyển sang Elasticsearch đồng bộ bằng CDC.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
inverted index /ɪnˈvɜːtɪd ˈɪndeks/ index đảo, từ phần tử tới danh sách dòng “GIN is an inverted index, so it answers containment queries, not range queries.”
posting list /ˈpəʊstɪŋ lɪst/ danh sách dòng chứa một phần tử “Each tag maps to a compressed posting list of row IDs.”
operator class /ˈɒpəreɪtə klɑːs/ tập toán tử một index hỗ trợ “The index wasn’t used because = ANY isn’t in the operator class.”
exclusion constraint /ɪkˈskluːʒn kənˈstreɪnt/ ràng buộc cấm các dòng xung đột “An exclusion constraint guarantees no overlapping bookings, even under concurrency.”
pending list /ˈpendɪŋ lɪst/ danh sách chờ gộp của GIN “A full pending list makes one unlucky insert pay for the cleanup.”
compaction /kəmˈpækʃn/ gộp file nền trong LSM “If compaction falls behind, read latency creeps up.”
write amplification /raɪt ˌæmplɪfɪˈkeɪʃn/ số lần ghi thực tế trên mỗi lần ghi logic “Leveled compaction trades write amplification for faster reads.”
bloom filter /bluːm ˈfɪltə/ cấu trúc xác suất kiểm tra “chắc chắn không có” “Bloom filters let us skip SSTables that can’t contain the key.”
partial index /ˈpɑːʃl ˈɪndeks/ index chỉ trên một phần dòng “A partial index on the PROCESSING rows is fifty times smaller.”

Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.