Database Indexing — Nghệ thuật tối ưu query cho hệ thống Production

Posted on: 4/20/2026 11:12:43 AM

Bạn đã bao giờ thấy một query đơn giản chạy mất 30 giây trên production, rồi sau khi thêm đúng một dòng CREATE INDEX thì chỉ còn 5ms? Đó không phải phép màu — đó là sức mạnh của database indexing. Tuy nhiên, index không phải "thêm càng nhiều càng tốt". Hiểu sai về index có thể khiến hệ thống chậm hơn, tốn dung lượng vô ích, và biến mỗi lần INSERT thành cơn ác mộng.

Bài viết này sẽ đi sâu vào cách database index thực sự hoạt động bên trong, các loại index phổ biến trong SQL Server và PostgreSQL, cách đọc Execution Plan, và chiến lược đánh index cho hệ thống production triệu query mỗi ngày.

1. Index hoạt động như thế nào?

Hãy tưởng tượng một cuốn sách dày 1000 trang. Nếu bạn muốn tìm từ "Deadlock", bạn có hai cách: lật từng trang (Table Scan) hoặc mở mục lục ở cuối sách (Index Lookup). Mục lục sách chính là nguyên lý cơ bản của database index.

Trong database, index là một cấu trúc dữ liệu riêng biệt được duy trì song song với bảng gốc. Khi bạn tạo index trên cột Email, database sẽ tạo một "bản sao thu gọn" chứa giá trị Email đã sắp xếp kèm pointer trỏ về row gốc trong bảng.

1.1. Cấu trúc B-Tree — Nền tảng của hầu hết index

B-Tree (Balanced Tree) là cấu trúc dữ liệu phổ biến nhất cho database index. Điểm đặc biệt của B-Tree là chiều cao rất thấp — một B-Tree chứa 1 triệu bản ghi thường chỉ cao 3-4 tầng. Nghĩa là chỉ cần 3-4 lần đọc đĩa (page read) để tìm được bất kỳ bản ghi nào.

graph TD
    Root["Root Node
Pointer: 30 | 60"]
    I1["Internal
10 | 20"]
    I2["Internal
40 | 50"]
    I3["Internal
70 | 80 | 90"]
    L1["Leaf
1,3,5,8,10"]
    L2["Leaf
12,15,18,20"]
    L3["Leaf
22,25,28,30"]
    L4["Leaf
32,35,38,40"]
    L5["Leaf
42,45,48,50"]
    L6["Leaf
55,58,60"]

    Root --> I1
    Root --> I2
    Root --> I3
    I1 --> L1
    I1 --> L2
    I1 --> L3
    I2 --> L4
    I2 --> L5
    I2 --> L6

    style Root fill:#e94560,stroke:#fff,color:#fff
    style I1 fill:#2c3e50,stroke:#fff,color:#fff
    style I2 fill:#2c3e50,stroke:#fff,color:#fff
    style I3 fill:#2c3e50,stroke:#fff,color:#fff
    style L1 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style L2 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style L3 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style L4 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style L5 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style L6 fill:#f8f9fa,stroke:#e94560,color:#2c3e50

Mỗi node trong B-Tree chứa nhiều key và pointer. Khi tìm kiếm giá trị 45:

1. Root node: 45 nằm giữa 30 và 60 → đi vào nhánh giữa
2. Internal node: 45 nằm giữa 40 và 50 → đi vào leaf tương ứng
3. Leaf node: Tìm thấy 45, trả về pointer đến row trong bảng

2. Clustered vs Non-Clustered Index

Đây là khái niệm quan trọng nhất cần nắm, đặc biệt trong SQL Server. Hai loại index này hoạt động hoàn toàn khác nhau về mặt vật lý.

graph LR
    subgraph CI["Clustered Index"]
        direction TB
        CR["Root: 50"]
        CL1["Leaf: Row 1-50
(chứa toàn bộ data)"]
        CL2["Leaf: Row 51-100
(chứa toàn bộ data)"]
        CR --> CL1
        CR --> CL2
    end

    subgraph NCI["Non-Clustered Index"]
        direction TB
        NR["Root: 'M'"]
        NL1["Leaf: Email A-M
+ Clustered Key"]
        NL2["Leaf: Email N-Z
+ Clustered Key"]
        NR --> NL1
        NR --> NL2
    end

    NL1 -.->|Key Lookup| CL1
    NL2 -.->|Key Lookup| CL2

    style CR fill:#e94560,stroke:#fff,color:#fff
    style NR fill:#2c3e50,stroke:#fff,color:#fff
    style CL1 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style CL2 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style NL1 fill:#f8f9fa,stroke:#2c3e50,color:#2c3e50
    style NL2 fill:#f8f9fa,stroke:#2c3e50,color:#2c3e50

Trong PostgreSQL, khái niệm hơi khác: tất cả table đều là heap (không sắp xếp vật lý), và mọi index đều là "non-clustered" theo nghĩa SQL Server. Tuy nhiên, PostgreSQL có lệnh CLUSTER để sắp xếp lại data một lần theo index — nhưng không tự duy trì thứ tự sau đó.

-- SQL Server: Clustered Index tự động với Primary Key
CREATE TABLE Users (
    Id INT IDENTITY(1,1) PRIMARY KEY, -- Clustered Index tự động
    Email NVARCHAR(255),
    FullName NVARCHAR(500),
    CreatedDate DATETIME2
);

-- Non-Clustered Index trên Email
CREATE NONCLUSTERED INDEX IX_Users_Email
ON Users (Email);

-- PostgreSQL: Tương đương
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(255),
    full_name VARCHAR(500),
    created_date TIMESTAMPTZ
);

CREATE INDEX idx_users_email ON users (email);

3. Composite Index và quy tắc Leftmost Prefix

Composite index (index trên nhiều cột) là vũ khí mạnh nhất trong toolkit của bạn, nhưng cũng là nơi dễ mắc sai lầm nhất. Quy tắc vàng: thứ tự cột trong composite index quyết định query nào được hưởng lợi.

-- Tạo composite index
CREATE INDEX IX_Orders_Status_Date_Customer
ON Orders (Status, OrderDate, CustomerId);

Với index trên (Status, OrderDate, CustomerId), các query sau sẽ sử dụng được index:

3.1. Chiến lược sắp xếp cột trong Composite Index

Thứ tự ưu tiên khi thiết kế composite index:

1. Equality first: Cột dùng = đứng trước cột dùng >, <, BETWEEN
2. Range sau: Cột dùng range filter đứng sau equality
3. Sort cuối: Cột dùng trong ORDER BY đứng cuối cùng

-- Query pattern:
SELECT * FROM Orders
WHERE Status = 'shipped'        -- equality
  AND OrderDate >= '2026-01-01' -- range
ORDER BY CustomerId;            -- sort

-- Index tối ưu: equality → range → sort
CREATE INDEX IX_Orders_Optimal
ON Orders (Status, OrderDate, CustomerId);

4. Covering Index — Tránh Key Lookup

Đây là kỹ thuật tối ưu mạnh mẽ nhất mà nhiều developer bỏ qua. Khi query cần trả về cột không nằm trong index key, database phải thực hiện thêm bước Key Lookup (quay về bảng gốc lấy data). Mỗi Key Lookup là một random I/O — với query trả về 10.000 rows, nghĩa là 10.000 random reads bổ sung.

Covering Index giải quyết vấn đề này bằng cách INCLUDE thêm cột cần thiết vào leaf node của index — không ảnh hưởng thứ tự sắp xếp, nhưng loại bỏ hoàn toàn Key Lookup.

-- SQL Server: INCLUDE clause
CREATE NONCLUSTERED INDEX IX_Orders_Status_Covering
ON Orders (Status, OrderDate)
INCLUDE (CustomerId, TotalAmount, ShippingAddress);

-- Giờ query này được cover hoàn toàn:
SELECT CustomerId, TotalAmount, ShippingAddress
FROM Orders
WHERE Status = 'shipped' AND OrderDate >= '2026-01-01';
-- → Index Seek, KHÔNG Key Lookup

-- PostgreSQL: Tương đương (từ v11+)
CREATE INDEX idx_orders_status_covering
ON orders (status, order_date)
INCLUDE (customer_id, total_amount, shipping_address);

graph LR
    subgraph Without["Không có Covering Index"]
        Q1["Query"] --> IS1["Index Seek
tìm key"]
        IS1 --> KL["Key Lookup
10,000 random I/O"]
        KL --> R1["Result"]
    end

    subgraph With["Có Covering Index"]
        Q2["Query"] --> IS2["Index Seek
tìm key + INCLUDE data"]
        IS2 --> R2["Result"]
    end

    style Q1 fill:#f8f9fa,stroke:#e94560,color:#2c3e50
    style Q2 fill:#f8f9fa,stroke:#4CAF50,color:#2c3e50
    style KL fill:#e94560,stroke:#fff,color:#fff
    style IS1 fill:#2c3e50,stroke:#fff,color:#fff
    style IS2 fill:#4CAF50,stroke:#fff,color:#fff
    style R1 fill:#f8f9fa,stroke:#e0e0e0,color:#2c3e50
    style R2 fill:#f8f9fa,stroke:#e0e0e0,color:#2c3e50

5. Filtered Index — Index có điều kiện

Filtered Index (SQL Server) hay Partial Index (PostgreSQL) cho phép bạn chỉ index một subset của data. Đặc biệt hữu ích khi bạn thường xuyên query trên một phần nhỏ dữ liệu.

-- SQL Server: Filtered Index
-- Chỉ index orders chưa xử lý (5% tổng data)
CREATE NONCLUSTERED INDEX IX_Orders_Pending
ON Orders (OrderDate, CustomerId)
WHERE Status = 'pending';

-- Query sử dụng filtered index:
SELECT * FROM Orders
WHERE Status = 'pending' AND OrderDate > '2026-04-01';

-- PostgreSQL: Partial Index
CREATE INDEX idx_orders_pending
ON orders (order_date, customer_id)
WHERE status = 'pending';

6. Index đặc biệt trong PostgreSQL

PostgreSQL cung cấp nhiều loại index ngoài B-Tree, mỗi loại tối ưu cho use case khác nhau.

-- GIN Index cho JSONB (PostgreSQL)
CREATE INDEX idx_products_attrs ON products
USING GIN (attributes jsonb_path_ops);

-- Query JSONB hiệu quả:
SELECT * FROM products
WHERE attributes @> '{"color": "red", "size": "L"}';

-- BRIN Index cho time-series data
-- Cực kỳ nhỏ (~0.1% kích thước B-Tree) nhưng hiệu quả
-- khi data insert theo thứ tự thời gian
CREATE INDEX idx_logs_created ON logs
USING BRIN (created_at) WITH (pages_per_range = 32);

-- Full-text Search với GIN
CREATE INDEX idx_articles_fts ON articles
USING GIN (to_tsvector('english', title || ' ' || body));

7. Đọc hiểu Execution Plan

Execution Plan là "bản đồ" cho thấy database thực thi query như thế nào. Đọc được plan là kỹ năng bắt buộc để tối ưu index.

-- SQL Server: Xem Estimated Plan
SET SHOWPLAN_XML ON;
GO
SELECT * FROM Orders WHERE Status = 'pending';
GO
SET SHOWPLAN_XML OFF;

-- Hoặc Actual Plan (chạy query thật)
SET STATISTICS XML ON;
SELECT * FROM Orders WHERE Status = 'pending';
SET STATISTICS XML OFF;

-- PostgreSQL: EXPLAIN ANALYZE
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT * FROM orders WHERE status = 'pending';

7.1. Các operator quan trọng trong Execution Plan

graph TD
    TS["Table Scan / Seq Scan
Đọc toàn bộ bảng
❌ Chậm nhất"]
    IS["Index Scan
Đọc toàn bộ index
⚠️ Tốt hơn Table Scan"]
    IK["Index Seek / Index Only Scan
Nhảy đến vị trí chính xác
✅ Nhanh nhất"]
    KL["Key Lookup / Heap Fetch
Quay về bảng lấy cột thiếu
⚠️ Chi phí bổ sung"]

    TS -.->|"Thêm Index"| IS
    IS -.->|"WHERE selective"| IK
    IK -.->|"Cần cột ngoài index"| KL
    KL -.->|"INCLUDE cột"| IK

    style TS fill:#e94560,stroke:#fff,color:#fff
    style IS fill:#ff9800,stroke:#fff,color:#fff
    style IK fill:#4CAF50,stroke:#fff,color:#fff
    style KL fill:#ff9800,stroke:#fff,color:#fff

-- PostgreSQL EXPLAIN output mẫu:
EXPLAIN (ANALYZE) SELECT email, full_name FROM users WHERE status = 'active';

-- KẾT QUẢ KHI KHÔNG CÓ INDEX:
Seq Scan on users  (cost=0.00..25432.00 rows=50000 width=64)
                   (actual time=0.021..245.123 rows=48532 loops=1)
  Filter: (status = 'active')
  Rows Removed by Filter: 951468
Planning Time: 0.085 ms
Execution Time: 267.456 ms      ← CHẬM

-- KẾT QUẢ SAU KHI TẠO COVERING INDEX:
-- CREATE INDEX idx_users_status ON users (status) INCLUDE (email, full_name);
Index Only Scan using idx_users_status on users
                   (cost=0.42..1523.45 rows=50000 width=64)
                   (actual time=0.031..8.234 rows=48532 loops=1)
  Index Cond: (status = 'active')
  Heap Fetches: 0               ← Không cần quay về bảng!
Planning Time: 0.112 ms
Execution Time: 12.567 ms       ← NHANH 21x

8. Index Anti-patterns — Những sai lầm phải tránh

8.1. Dùng hàm trên cột indexed

-- ❌ SAI: Index trên Email không được sử dụng
SELECT * FROM Users WHERE UPPER(Email) = 'ADMIN@EXAMPLE.COM';
SELECT * FROM Users WHERE YEAR(CreatedDate) = 2026;

-- ✅ ĐÚNG: Giữ cột indexed nguyên vẹn
SELECT * FROM Users WHERE Email = 'admin@example.com'; -- collation CI
SELECT * FROM Users
WHERE CreatedDate >= '2026-01-01' AND CreatedDate < '2027-01-01';

-- ✅ PostgreSQL: Expression Index nếu cần
CREATE INDEX idx_users_email_upper ON users (UPPER(email));

8.2. Over-indexing — Nhiều index quá

Mỗi index là một bản copy dữ liệu phải được cập nhật khi INSERT/UPDATE/DELETE. Bảng có 10 index nghĩa là mỗi INSERT phải ghi 11 lần (1 bảng + 10 index).

8.3. Index trên cột low-cardinality

-- ❌ Ít hiệu quả: Cột Gender chỉ có 2-3 giá trị
CREATE INDEX IX_Users_Gender ON Users (Gender);
-- Index trả về 50% rows → Optimizer chọn Table Scan thay vì Index

-- ✅ Tốt hơn: Composite index hoặc Filtered Index
CREATE INDEX IX_Users_Gender_Date ON Users (Gender, CreatedDate);
-- Hoặc nếu query phổ biến chỉ lọc 1 giá trị:
CREATE INDEX IX_Users_Active ON Users (CreatedDate) WHERE IsActive = 1;

8.4. Implicit conversion giết index

-- ❌ Cột UserId là VARCHAR nhưng truyền INT → implicit conversion
-- Database phải convert TỪNG ROW → Table Scan
SELECT * FROM Users WHERE UserId = 12345;

-- ✅ Truyền đúng kiểu
SELECT * FROM Users WHERE UserId = '12345';

8.5. LIKE với wildcard đầu

-- ❌ Index không dùng được: wildcard ở đầu
SELECT * FROM Products WHERE Name LIKE '%phone%';

-- ✅ Index dùng được: wildcard chỉ ở cuối
SELECT * FROM Products WHERE Name LIKE 'phone%';

-- ✅ Giải pháp cho full-text: dùng Full-Text Index
-- SQL Server:
CREATE FULLTEXT INDEX ON Products (Name) KEY INDEX PK_Products;
SELECT * FROM Products WHERE CONTAINS(Name, 'phone');

-- PostgreSQL:
CREATE INDEX idx_products_fts ON products USING GIN (to_tsvector('simple', name));
SELECT * FROM products WHERE to_tsvector('simple', name) @@ to_tsquery('phone');

9. Chiến lược Index cho Production

9.1. Quy trình 4 bước

-- SQL Server: Top queries by CPU
SELECT TOP 20
    qs.total_worker_time / qs.execution_count AS avg_cpu,
    qs.execution_count,
    SUBSTRING(qt.text, 1, 200) AS query_text
FROM sys.dm_exec_query_stats qs
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) qt
ORDER BY avg_cpu DESC;

-- PostgreSQL: Top queries (cần enable pg_stat_statements)
SELECT query, calls, mean_exec_time, total_exec_time
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 20;

9.2. Phát hiện index thừa và thiếu

-- SQL Server: Index không bao giờ được dùng
SELECT
    OBJECT_NAME(i.object_id) AS table_name,
    i.name AS index_name,
    s.user_seeks, s.user_scans, s.user_lookups, s.user_updates
FROM sys.indexes i
LEFT JOIN sys.dm_db_index_usage_stats s
    ON i.object_id = s.object_id AND i.index_id = s.index_id
WHERE OBJECTPROPERTY(i.object_id, 'IsUserTable') = 1
    AND (s.user_seeks + s.user_scans + s.user_lookups) = 0
    AND s.user_updates > 0
ORDER BY s.user_updates DESC;

-- SQL Server: Missing index suggestions
SELECT
    d.statement AS table_name,
    d.equality_columns,
    d.inequality_columns,
    d.included_columns,
    s.avg_user_impact,
    s.user_seeks
FROM sys.dm_db_missing_index_details d
JOIN sys.dm_db_missing_index_groups g ON d.index_handle = g.index_handle
JOIN sys.dm_db_missing_index_group_stats s ON g.index_group_handle = s.group_handle
ORDER BY s.avg_user_impact * s.user_seeks DESC;

-- PostgreSQL: Index không được dùng
SELECT
    schemaname, tablename, indexname,
    idx_scan AS times_used,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

9.3. Bảo trì Index định kỳ

Index bị fragmentation theo thời gian khi data INSERT/UPDATE/DELETE. Index fragmented nghĩa là leaf pages không liên tục trên disk, gây tăng I/O.

-- SQL Server: Kiểm tra fragmentation
SELECT
    OBJECT_NAME(ips.object_id) AS table_name,
    i.name AS index_name,
    ips.avg_fragmentation_in_percent,
    ips.page_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'LIMITED') ips
JOIN sys.indexes i ON ips.object_id = i.object_id AND ips.index_id = i.index_id
WHERE ips.avg_fragmentation_in_percent > 10
ORDER BY ips.avg_fragmentation_in_percent DESC;

-- Fragmentation 10-30%: REORGANIZE (online, nhẹ)
ALTER INDEX IX_Orders_Status ON Orders REORGANIZE;

-- Fragmentation > 30%: REBUILD (tốn hơn nhưng triệt để)
ALTER INDEX IX_Orders_Status ON Orders REBUILD WITH (ONLINE = ON);

-- PostgreSQL: REINDEX (tương đương REBUILD)
REINDEX INDEX CONCURRENTLY idx_orders_status;

-- PostgreSQL: VACUUM + ANALYZE (bảo trì routine)
VACUUM ANALYZE orders;

10. Một số pattern index thường gặp

10.1. Pagination hiệu quả

-- ❌ OFFSET lớn = chậm (phải đọc rồi bỏ N rows đầu)
SELECT * FROM Products ORDER BY CreatedDate DESC
OFFSET 100000 ROWS FETCH NEXT 20 ROWS ONLY;

-- ✅ Keyset Pagination (cursor-based) + Index
-- Index: CREATE INDEX IX_Products_Date ON Products (CreatedDate DESC, Id DESC);
SELECT TOP 20 * FROM Products
WHERE (CreatedDate, Id) < (@lastDate, @lastId)
ORDER BY CreatedDate DESC, Id DESC;

-- PostgreSQL tương đương:
SELECT * FROM products
WHERE (created_date, id) < ($1, $2)
ORDER BY created_date DESC, id DESC
LIMIT 20;

10.2. Soft Delete pattern

-- Hầu hết query chỉ cần active records
-- Filtered Index rất hiệu quả ở đây:
CREATE INDEX IX_Users_Active
ON Users (Email, CreatedDate)
WHERE IsDeleted = 0;

-- 95% queries chỉ truy cập data chưa xóa
-- Index chỉ chiếm 5% kích thước so với full index

10.3. Multi-tenant SaaS

-- TenantId luôn là cột đầu trong composite index
CREATE INDEX IX_Orders_Tenant
ON Orders (TenantId, Status, OrderDate)
INCLUDE (TotalAmount);

-- Mỗi tenant chỉ scan subset nhỏ của bảng
SELECT Status, COUNT(*), SUM(TotalAmount)
FROM Orders
WHERE TenantId = @tenantId AND OrderDate >= '2026-01-01'
GROUP BY Status;

11. Tổng kết

Database Indexing không chỉ là CREATE INDEX rồi xong. Đó là quá trình liên tục: phân tích workload → thiết kế index → đo lường → tinh chỉnh. Những điểm cần nhớ:

Index là trade-off giữa read performance và write cost + storage. Không có index hoàn hảo cho mọi trường hợp — chỉ có index phù hợp với workload cụ thể của bạn. Hãy bắt đầu từ slow query log, đọc Execution Plan, và áp dụng nguyên tắc ESR. Kết quả sẽ thấy ngay.

Tài liệu tham khảo

• Use The Index, Luke — A Guide to Database Performance
• Microsoft SQL Server Index Architecture and Design Guide
• PostgreSQL Documentation — Indexes
• Hussein Nasser — Database Indexing Explained
• pganalyze — Efficient Search in PostgreSQL