Index trong database

Index là gì

Index là một cấu trúc dữ liệu phụ, đã sắp xếp hoặc đã hash theo một hay vài cột, trỏ về vị trí của dòng trong bảng. Không có index, câu WHERE email = 'a@b.vn' buộc database đọc từng dòng (sequential scan). Có index, database đi thẳng tới vài trang dữ liệu chứa dòng đó. MongoDB TDG mô tả: index giống mục lục cuối sách, một danh sách đã sắp xếp trỏ tới nội dung; truy vấn không dùng index gọi là table scan và rất chậm trên collection lớn.¹

Index giống mục lục cuối sách: tra "replication" ra số trang, lật đúng trang. Cái giá là mỗi lần thêm hoặc sửa nội dung, mục lục cũng phải cập nhật, và mục lục chiếm thêm giấy: sách viết mọi insert, update, delete đều chậm hơn với mỗi index thêm vào, vì MongoDB phải cập nhật mọi index.¹

Ba điều cần nhớ:

• Index tăng tốc đọc, làm chậm ghi và tốn thêm dung lượng.¹
• Index không phải lúc nào cũng nhanh hơn: sách nói index hiệu quả nhất khi lấy tập con nhỏ; nếu truy vấn trả về từ 30% collection trở lên thì nên xem table scan có nhanh hơn không (ngưỡng thực tế dao động 2% tới 60%).²
• Index chỉ có ích khi truy vấn khớp với cách index được sắp xếp. Index trên (a, b) không giúp truy vấn chỉ lọc theo b: sách chỉ cho phép dùng tiền tố của index, không dùng tập con bất kỳ.³
• Database tự chọn có dùng index hay không. Bạn kiểm tra bằng EXPLAIN.

Vì sao quan trọng trong phỏng vấn

Khi bạn vẽ bảng posts và nói "lấy 20 bài mới nhất của user", người phỏng vấn muốn biết truy vấn đó chạy bằng index nào. Một câu "thêm index trên (user_id, created_at DESC)" cho thấy bạn hiểu dữ liệu được đọc ra sao. Index cũng là bước scale đọc rẻ nhất, nên đứng trước read replica, cache và sharding trong thứ tự giải pháp (thứ tự ưu tiên của khoá học). Sách MongoDB nhấn mạnh table scan rất chậm trên collection lớn và explain là công cụ chẩn đoán truy vấn chậm quan trọng nhất.¹⁴

Các câu hỏi hay gặp:

• Truy vấn chính của API này dùng index gì?
• Index đó có làm chậm luồng ghi nhiều không?
• Tìm kiếm theo chữ, theo vị trí thì index thế nào?
• Khi đã shard, index phụ nằm ở đâu?

Cách hoạt động: B-tree, hash và LSM

B-tree

B-tree là index chuẩn: Seven Databases viết B-tree là index tiêu chuẩn tốt, lưu giá trị dưới dạng cây cân bằng, rất linh hoạt, và là lựa chọn cho truy vấn khoảng như starts >= '2012-04-01'; MongoDB explain cho thấy con trỏ BtreeCursor khi truy vấn dùng index.⁵⁴ Phần chi tiết dưới đây (B+tree, trang 8–16 KB, hàng trăm con trỏ mỗi trang, 3–4 tầng, lá nối nhau, mặc định của InnoDB) là kiến thức chung chưa có trong sách thư viện.⁶

B-tree hỗ trợ bằng, khoảng, tiền tố (LIKE 'abc%') và sắp xếp. Đây là lựa chọn đúng cho hầu hết trường hợp (nhận xét của khoá học; sách xác nhận B-tree cho khoảng và so sánh, hash chỉ cho bằng).⁵

Hash index

Hash index lưu hash(key) → vị trí. Seven Databases mô tả hash index của Postgres như bảng băm trỏ tới dòng, và nói nó chỉ hợp với so sánh bằng, còn khoảng cần B-tree.⁵ Tra cứu bằng nhau là O(1) và không hỗ trợ khoảng hay sắp xếp (suy ra từ hash). Chuyện hash index trong Postgres hiếm khi đáng dùng là nhận xét của khoá học.⁶ Hash phát huy ở bộ nhớ: Redis, Memcached, và bảng băm trong RAM của các kho key-value; Grokking ch.9 nói key-value store dùng phương pháp như hash table.⁷

LSM-tree

LSM (log-structured merge tree) dùng trong Cassandra, ScyllaDB, RocksDB, LevelDB và nhiều time-series database. Ghi đi vào memtable trong RAM và commit log tuần tự. Khi memtable đầy, nó được ghi ra đĩa thành file SSTable đã sắp xếp, không sửa tại chỗ. Compaction chạy nền để gộp các SSTable. Thư viện không có sách mô tả LSM, memtable, SSTable hay compaction.⁸

• Ghi rất nhanh vì chỉ ghi tuần tự.
• Đọc có thể phải xem nhiều SSTable. Bloom filter giúp bỏ qua file chắc chắn không chứa key; Seven Databases mô tả Bloom filter (trong HBase) là cấu trúc dùng không gian cố định, trả lời nhanh một key có tồn tại không, và đổi lại đôi khi cho kết quả dương tính giả.⁹
• Compaction tốn I/O nền và cần đĩa trống khoảng 30–50% (ước lượng, cần load test).

Bảng so sánh là tóm tắt của khoá học; chỉ phần B-tree và hash có đối chiếu trong sách.⁵⁸

Các loại index cần biết

Composite index và thứ tự cột

Index trên nhiều cột sắp xếp theo cột đầu, rồi cột thứ hai trong từng giá trị cột đầu, giống danh bạ sắp theo họ rồi tên. Sách MongoDB minh họa đúng như vậy: với index {age: 1, username: -1} các tuổi xếp từ nhỏ tới lớn và trong mỗi tuổi các username xếp từ Z tới A.¹⁰ Hệ quả:

• Index (user_id, created_at) dùng được cho WHERE user_id = ?, cho WHERE user_id = ? AND created_at > ?, và cho WHERE user_id = ? ORDER BY created_at DESC LIMIT 20.
• Nó không dùng hiệu quả cho WHERE created_at > ? đơn lẻ, vì chỉ tiền tố của index được tận dụng.³

Quy tắc chọn thứ tự: cột lọc bằng nhau đặt trước, cột dùng để sắp xếp tiếp theo, cột lọc theo khoảng đặt cuối. Một khi gặp điều kiện khoảng, các cột phía sau không còn dùng để thu hẹp tìm kiếm được nữa. Phần "bằng trước, sort, khoảng sau" là kinh nghiệm của khoá học.¹¹ Sách cũng khuyên đặt cột có cardinality cao trước cột cardinality thấp trong compound index.¹²

-- Truy vấn: 20 đơn mới nhất của một user theo trạng thái
SELECT id, total, created_at
FROM orders
WHERE user_id = $1 AND status = 'paid'
ORDER BY created_at DESC
LIMIT 20;

CREATE INDEX orders_user_status_created_idx
  ON orders (user_id, status, created_at DESC);

Covering index

Nếu index chứa mọi cột truy vấn cần, database trả kết quả từ index mà không quay lại bảng. MongoDB TDG ch.5 gọi là covered query: dùng projection loại _id nếu _id không nằm trong index, có thể phải index cả trường không dùng để lọc, và phải cân với chi phí ghi; index trên trường mảng không bao giờ cover được truy vấn.¹³ Postgres gọi là index-only scan, thêm cột chỉ để trả về bằng INCLUDE (cú pháp Postgres, chưa có trong sách).¹⁴

CREATE INDEX orders_user_created_cover_idx
  ON orders (user_id, created_at DESC) INCLUDE (total, status);

Partial index

Chỉ index những dòng thỏa điều kiện. Index nhỏ hơn, ghi rẻ hơn, và hợp với truy vấn luôn có cùng điều kiện. Sách MongoDB có sparse index là index không cần chứa mọi document (khác khái niệm sparse của CSDL quan hệ); partial index của Postgres là cú pháp chưa có trong sách.¹⁵¹⁴

-- Chỉ các job còn chờ, thường là phần nhỏ của bảng
CREATE INDEX jobs_pending_run_at_idx
  ON jobs (run_at) WHERE status = 'pending';

-- Unique chỉ trên dòng chưa xóa mềm
CREATE UNIQUE INDEX users_email_active_uq
  ON users (lower(email)) WHERE deleted_at IS NULL;

Full-text và GIN

B-tree không giúp LIKE '%keyword%' hay tìm theo từ. Postgres có GIN (generalized inverted index): Seven Databases giới thiệu GIN là index API giống GiST, tạo index trên lexeme của tsvector, và nói inverted index là cấu trúc phổ biến cho full-text search như trong Lucene hay Sphinx; không có index thì full-text search chậm.¹⁶ Sách cũng dùng GiST với pg_trgm cho tìm gần đúng theo trigram, chịu lỗi chính tả.¹⁷ Việc dùng GIN cho jsonb và mảng là chưa có trong sách.¹⁴

ALTER TABLE posts ADD COLUMN tsv tsvector
  GENERATED ALWAYS AS (to_tsvector('simple', coalesce(title,'') || ' ' || body)) STORED;
CREATE INDEX posts_tsv_idx ON posts USING gin (tsv);

SELECT id FROM posts WHERE tsv @@ plainto_tsquery('simple', 'consistent hashing');

Postgres không có cấu hình ngôn ngữ tiếng Việt sẵn, nên dùng simple kèm unaccent (nhận xét của khoá học, chưa có trong sách).¹⁴ Khi cần xếp hạng tốt, gợi ý, chịu lỗi chính tả, hoặc dữ liệu lớn, chuyển sang Elasticsearch. MongoDB TDG ch.6 mô tả full-text index của MongoDB, hỗ trợ stemming và stop words nhiều ngôn ngữ, và cảnh báo nó nặng hơn các index thường: tạo chậm, ghi chậm hơn vì mọi chuỗi phải tách và lưu ở nhiều chỗ.¹⁸

Geo index

Tìm "quán ăn trong bán kính 2 km" cần index hai chiều. MongoDB dùng index 2dsphere cho bản đồ bề mặt Trái đất, nhận điểm, đường, đa giác theo GeoJSON, và 2d cho bản đồ phẳng (TDG ch.6).¹⁹ PostGIS dùng GiST trên cột geography và Redis GEO dùng geohash trong sorted set là ví dụ ngoài thư viện.¹⁴ Chi tiết so sánh geohash, quadtree và H3 nằm ở bài Tìm kiếm gần.

CREATE INDEX places_geo_idx ON places USING gist (location);
SELECT id FROM places
WHERE ST_DWithin(location, ST_MakePoint(106.70, 10.77)::geography, 2000);

MongoDB: compound index và hướng sắp xếp

MongoDB TDG ch.5 nhấn mạnh một điểm hay bị bỏ qua: với compound index, hướng của từng cột quan trọng khi sort theo nhiều cột; muốn chọn hướng, cứ khớp hướng của câu sort.¹⁰

db.users.createIndex({ age: 1, username: -1 });

// Dùng được index: cùng hướng, hoặc đảo ngược toàn bộ
db.users.find().sort({ age: 1, username: -1 });
db.users.find().sort({ age: -1, username: 1 });

// Không dùng index để sort: chỉ đảo một cột
db.users.find().sort({ age: 1, username: 1 });

Với index một cột, hướng không quan trọng vì MongoDB đọc ngược index được. Index {age: 1, username: 1} cũng phục vụ luôn truy vấn chỉ trên age, nên không cần tạo thêm index {age: 1}.¹⁰³ Kiểm tra bằng explain(): bản sách ghi trường indexOnly là true khi truy vấn được cover, và BtreeCursor khi dùng index, BasicCursor khi quét cả collection; explain("executionStats") và totalDocsExamined: 0 là cách ghi của bản MongoDB mới hơn, chưa có sách.⁴¹³

Bảng tổng hợp

Bảng sau là tóm tắt của khoá học, các mục tương ứng đã trích ở trên.^5101619

Đọc EXPLAIN ANALYZE trong Postgres

EXPLAIN cho kế hoạch dự kiến. Seven Databases dùng EXPLAIN để xem kế hoạch thực thi (ví dụ Seq Scan kèm Filter) và để kiểm tra index có được dùng không.²⁰ EXPLAIN ANALYZE chạy thật và ghi thời gian thật (chi tiết ANALYZE, BUFFERS, các dòng plan bên dưới là kiến thức Postgres chưa có trong sách).¹⁴ Ví dụ bảng orders có 5 triệu dòng, chưa có index phù hợp (kết quả rút gọn, số minh họa):

EXPLAIN ANALYZE
SELECT id, total FROM orders
WHERE user_id = 42 AND created_at > now() - interval '30 days'
ORDER BY created_at DESC LIMIT 20;

Limit  (actual time=412.3..412.4 rows=20 loops=1)
  ->  Sort  (actual time=412.3..412.3 rows=20 loops=1)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 26kB
        ->  Seq Scan on orders  (actual time=0.9..411.8 rows=287 loops=1)
              Filter: ((user_id = 42) AND (created_at > (now() - '30 days'::interval)))
              Rows Removed by Filter: 4999713
Execution Time: 412.5 ms

Cùng hiện tượng với ví dụ của MongoDB TDG: quét 1 triệu document mất 721 ms, có index còn vài ms.¹ Dấu hiệu cần sửa: Seq Scan trên bảng lớn, Rows Removed by Filter gấp hàng nghìn lần số dòng trả về, và một bước Sort riêng. Thêm index:

CREATE INDEX CONCURRENTLY orders_user_created_idx
  ON orders (user_id, created_at DESC) INCLUDE (total);

Limit  (actual time=0.04..0.09 rows=20 loops=1)
  ->  Index Only Scan using orders_user_created_idx on orders  (actual time=0.04..0.08 rows=20 loops=1)
        Index Cond: ((user_id = 42) AND (created_at > (now() - '30 days'::interval)))
        Heap Fetches: 0
Execution Time: 0.11 ms

Không còn Sort vì index đã đúng thứ tự, Heap Fetches: 0 nghĩa là không đọc bảng. Vài điều khi đọc plan:

• So rows= ước lượng (trong EXPLAIN thường) với rows= thật. Lệch hàng chục lần là dấu hiệu thống kê cũ, chạy ANALYZE.
• loops= lớn trong Nested Loop nghĩa là bước bên trong chạy lặp nhiều lần, nhân thời gian lên.
• Thêm BUFFERS (EXPLAIN (ANALYZE, BUFFERS)) để thấy bao nhiêu trang đọc từ cache, bao nhiêu từ đĩa.
• Trên production, dùng CREATE INDEX CONCURRENTLY để không khóa ghi trong lúc tạo index.

Con số: chi phí ghi và kích thước

Mỗi index là một cấu trúc phải cập nhật khi ghi: MongoDB TDG viết mọi lần dữ liệu đổi, MongoDB phải cập nhật tất cả index, nên giới hạn 64 index mỗi collection và khuyên không nên có quá vài index.¹ Một INSERT vào bảng có 5 index là 6 lần ghi cấu trúc (số học từ nguyên tắc đó), cộng WAL tương ứng. Các con số dưới đây là ước lượng của khoá học để tính nhẩm, không có trong sách, cần đo lại trên dữ liệu thật.²¹

Quy tắc thực hành:

• Index của các truy vấn nóng nên vừa RAM (sách MongoDB cũng nhắc giữ working set nhỏ và cảnh báo full-text index lớn hơn RAM).¹³¹⁸ Ngưỡng "Postgres 4 vCPU · 16 GB dưới khoảng 10 GB" là ước lượng của khoá học.²¹
• Bảng ghi nhiều (log, event, vị trí): giữ ít index, 1–3 cái. Bảng đọc nhiều (sản phẩm, người dùng): nhiều index hơn cũng được. Hướng "ít index khi ghi nhiều" theo sách; con số 1–3 là của khoá học.¹
• Postgres có HOT update: nếu cột được sửa không nằm trong index nào và trang còn chỗ, index không phải cập nhật. Đừng index cột thay đổi liên tục như last_seen_at nếu không thật sự cần.¹⁴

Index khi đã shard

Grokking ch.9 phân biệt hai cách đặt index phụ khi dữ liệu đã chia partition:²²

• Index cục bộ (theo document): mỗi partition có index riêng cho dữ liệu của nó. Ghi rẻ, nhưng truy vấn theo cột phụ phải hỏi mọi partition rồi gộp (scatter-gather).
• Index toàn cục (theo term): index phụ được chia theo giá trị của cột phụ. Đọc chỉ hỏi một partition của index, nhưng mỗi lần ghi có thể chạm nhiều partition và thường cập nhật bất đồng bộ. Microservices Patterns mô tả secondary index của DynamoDB là cách truy cập thay thế, được tự động cập nhật khi bảng đổi và có thể chứa thuộc tính không phải khóa;²³ chuyện GSI chỉ eventually consistent chưa có trong sách.²⁴

Sai lầm hay gặp

• Sai thứ tự cột trong composite index. Đặt cột khoảng trước cột bằng làm index gần như vô dụng cho phần sau.³¹¹
• Bọc cột trong hàm. WHERE lower(email) = ? không dùng index trên email. Tạo expression index ON users (lower(email)). Seven Databases có đúng ví dụ này: CREATE INDEX movies_title_pattern ON movies (lower(title) text_pattern_ops).²⁵
• Index cột có ít giá trị khác nhau. Index riêng trên status với 3 giá trị hiếm khi được dùng. Sách MongoDB nói index trên trường cardinality thấp (như giới tính) chỉ loại được khoảng một nửa kết quả. Gộp vào composite hoặc dùng partial index.¹²
• OFFSET lớn để phân trang. OFFSET 100000 vẫn phải đi qua 100.000 dòng trong index. Dùng cursor: WHERE created_at < $last ORDER BY created_at DESC LIMIT 20.¹⁴
• Tạo index trên production không CONCURRENTLY. Khóa ghi của cả bảng trong nhiều phút. MongoDB TDG cũng cảnh báo tạo index (đặc biệt full-text) trên collection bận có thể làm quá tải, nên làm lúc ít tải.¹⁸¹⁴
• Thêm index cho mọi thứ. Mỗi index làm chậm ghi, tốn RAM, tốn dung lượng backup. Xem pg_stat_user_indexes để xóa index không ai dùng.¹

Khi nào nhắc tới trong phỏng vấn

Bảng dưới là cách khoá học áp index vào từng bài; nguyên tắc nền ở các mục trên.¹¹⁰

Đọc tiếp: Mô hình dữ liệu để chọn bảng và khóa, PostgreSQL cho phần vận hành, Scale đọc cho bước sau khi index không còn đủ.

Nguồn trích dẫn

1. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Introduction to Indexing" (tr. 81–84). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰

2. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "When Not to Index" (tr. 102–103). ↩

3. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Using Compound Indexes", "Implicit indexes" (tr. 91). ↩ ↩² ↩³ ↩⁴

4. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Using explain() and hint()" (tr. 98–101). ↩ ↩² ↩³

5. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · §2.2 Day 1, phần về hash index và B-tree. ↩ ↩² ↩³ ↩⁴ ↩⁵

6. Chưa có nguồn trong thư viện: cấu trúc B+tree, kích thước trang và độ sâu cây, mặc định index của MySQL InnoDB, và nhận xét về hash index của Postgres không có trong các sách của thư viện; giữ lại ở mức khái niệm. ↩ ↩²

7. Grokking Modern System Design · ch.9 Databases · bài "Types of Databases", mục "Key-value database". ↩

8. Chưa có nguồn trong thư viện: thư viện không có sách mô tả LSM-tree, memtable, SSTable, compaction; phần này chỉ nêu khái niệm cơ bản. ↩ ↩²

9. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.4 HBase · §4.3 Day 2, mục "Compression and Bloom Filters" và "How Do Bloom Filters Work?". ↩

10. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Using Compound Indexes", "Choosing key directions" (tr. 89–91). ↩ ↩² ↩³ ↩⁴ ↩⁵

11. Chưa có nguồn trong thư viện: quy tắc "bằng, sort, khoảng" để xếp cột composite index là kinh nghiệm thực hành. ↩ ↩²

12. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Index Cardinality" (tr. 98). ↩ ↩²

13. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Using covered indexes" (tr. 90–91). ↩ ↩² ↩³

14. Chưa có nguồn trong thư viện: cú pháp và hành vi riêng của Postgres (INCLUDE, partial index, BRIN, HOT update, CONCURRENTLY, EXPLAIN ANALYZE, PostGIS, unaccent, GIN cho jsonb) hoặc Redis GEO không có trong các sách của thư viện; giữ lại vì cần cho ví dụ. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

15. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Types of Indexes", "Unique Indexes" và "Sparse Indexes" (tr. 104–106). ↩

16. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · §2.4 Day 3: Full-Text and Multidimensions, mục "Indexing Lexemes". ↩ ↩²

17. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · §2.4 Day 3, mục về trigram (pg_trgm) và GiST. ↩

18. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.6 Special Index and Collection Types · mục "Full-Text Indexes" (tr. 115–119). ↩ ↩² ↩³

19. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.6 Special Index and Collection Types · mục "Geospatial Indexing" (tr. 120–121). ↩ ↩²

20. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · §2.3 Day 2, phần về views, rules và EXPLAIN VERBOSE; §2.4 Day 3 về EXPLAIN khi index full-text. ↩

21. Chưa có nguồn trong thư viện: các con số kích thước, độ sâu, chi phí ghi của index là ước lượng của khoá học, cần đo lại. ↩ ↩²

22. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Partitioning and secondary indexes". ↩

23. Microservices Patterns (file .zip, tải về giải nén) · ch.7 · §7.4.2 Data modeling and query design with DynamoDB, mục "Defining an index for the findOrderHistory query" (tr. 245–246). ↩

24. Chưa có nguồn trong thư viện: mô hình nhất quán của DynamoDB GSI không có trong sách. ↩

25. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · §2.4 Day 3, phần tìm chuỗi không phân biệt hoa thường với index lower(title). ↩