3.2 Boolean retrieval: giao hai danh sách

Trước khi có ranking, search chỉ là phép toán tập hợp. Hiểu bước này thì hiểu vì sao inverted index nhanh, và vì sao chỉ boolean là không đủ.

Dùng lại ba tài liệu ở 1.6:

term	postings (đã sắp theo doc id)
mật	d1, d2
khẩu	d1, d2
quên	d2
đổi	d1
xác	d3

Ba phép toán

Truy vấn	Phép	Kết quả
`mật AND quên`	giao	`{d1,d2} ∩ {d2}` = `{d2}`
`mật OR xác`	hợp	`{d1,d2} ∪ {d3}` = `{d1,d2,d3}`
`mật AND NOT quên`	trừ	`{d1,d2} \ {d2}` = `{d1}`

Thuật toán giao: hai con trỏ

Vì postings đã sắp tăng dần, giao hai danh sách chỉ cần một lượt đi:

i, j = 0, 0
while i < len(A) and j < len(B):
    if   A[i] == B[j]: emit A[i]; i += 1; j += 1
    elif A[i] <  B[j]: i += 1
    else:              j += 1

Chi phí O(|A| + |B|), không phải O(|A|·|B|). Đây là toàn bộ lý do postings phải được giữ sắp thứ tự — mọi tối ưu về sau đều dựa vào tính chất này.

Hai mẹo luôn có giá trị:

Xử lý term hiếm trước. Với a AND b AND c, giao theo thứ tự df tăng dần. Danh sách trung gian nhỏ nhất có thể ở mọi bước.
Skip pointer. Chèn con trỏ nhảy mỗi √n phần tử trong postings dài. Khi A[i] còn xa B[j], nhảy qua cả khối thay vì bước từng doc id. Lucene làm việc này ở mức khối 128 doc id.

Vì sao boolean một mình không đủ

Vấn đề	Biểu hiện
Không có thứ tự	5.000 tài liệu khớp `mật AND khẩu` — trả về theo doc id? Vô nghĩa
Vách đá AND/OR	`AND` quá ít kết quả, `OR` quá nhiều. Không có nút xoay ở giữa
Không có “gần đúng”	thiếu một từ là mất hoàn toàn tài liệu, dù 9/10 từ khớp

Cách chữa là ranking: thay vì hỏi “có khớp không”, hỏi “khớp bao nhiêu”. Đó là 3.4 TF-IDF và BM25.

Nhưng boolean không hề mất đi — trong mọi hệ thống thật nó thành filter: WHERE tenant_id = ? AND status = 'published' chạy trước hoặc song song với phần ranking. Bẫy khi kết hợp filter với vector search nằm ở Tầng 5.

Phần 3 — Nền tảng kỹ thuật