SELECT với biến truy vấn không sử dụng INDEXes

Question

Tôi đã chơi xung quanh (không quan tâm) bằng cách truy xuất một cây nút trong danh sách kề đơn giản với truy vấn đệ quy bằng cách sử dụng các biến cục bộ.

Giải pháp tôi có cho đến nay rất thú vị nhưng tôi tự hỏi (và đây là câu hỏi duy nhất của tôi) tại sao MySQL từ chối sử dụng bất kỳ INDEX nào để tối ưu hóa truy vấn này. Không nên MySQL có thể tra cứu (các) đứa trẻ gần nhất bằng cách sử dụng một số INDEX?

Tôi rất tò mò vì sao MySQL lại không. Ngay cả khi tôi sử dụng FORCE INDEX kế hoạch thực hiện không thay đổi.

Đây là truy vấn cho đến nay, với 5 là ID của nút cha:

SELECT 
    @last_id := id AS id, 
    parent_id, 
    name, 
    @depth := IF(parent_id = 5, 1, @depth + 1) AS depth 
FROM 
    tree FORCE INDEX (index_parent_id, PRIMARY, index_both), 
    (SELECT @last_id := 5, @depth := -1) vars 
WHERE id = 5 OR parent_id = @last_id OR parent_id = 5 

Try live example at SQLfiddle

Lưu ý rằng lý do không thể là tập dữ liệu nhỏ, bởi vì hành vi không thay đổi khi tôi chỉ định FORCE INDEX (id) hoặc FORCE INDEX (parent_id) hoặc FORCE INDEX (id, parent_id) ...

Các tài liệu nói:

Bạn cũng có thể sử dụng FORCE INDEX, hoạt động như USE INDEX (index_list) nhưng bổ sung quét bảng được giả định là rất tốn kém. Nói cách khác, quét bảng chỉ được sử dụng nếu không có cách nào để sử dụng một trong các chỉ mục đã cho để tìm các hàng trong bảng.

Phải có điều gì đó khiến truy vấn không thể sử dụng INDEX, nhưng tôi không hiểu nó là gì.

---

Disclaimer: Tôi biết có những cách khác để lưu trữ và lấy dữ liệu thứ bậc trong SQL. Tôi biết về mô hình bộ lồng nhau. Tôi không tìm kiếm một triển khai thay thế. Tôi không tìm kiếm các bộ lồng nhau.

Tôi cũng biết truy vấn tự nó là hạt và tạo ra kết quả sai.

Tôi chỉ muốn hiểu (chi tiết) tại sao MySQL không sử dụng INDEX trong trường hợp này.

Answer 1

Lý do nằm trong việc sử dụng các HOẶC điều kiện trong mệnh đề ĐÂU.

Để minh họa, hãy thử chạy các truy vấn một lần nữa, lần này chỉ với điều kiện id = 5, và nhận được (GIẢI THÍCH đầu ra):

+----+-------------+------------+--------+--------------------+---------+---------+-------+------+----------------+ 
| id | select_type | table  | type | possible_keys  | key  | key_len | ref | rows | Extra   | 
+----+-------------+------------+--------+--------------------+---------+---------+-------+------+----------------+ 
| 1 | PRIMARY  | <derived2> | system | NULL    | NULL | NULL | NULL | 1 |    | 
| 1 | PRIMARY  | tree  | const | PRIMARY,index_both | PRIMARY | 4  | const | 1 |    | 
| 2 | DERIVED  | NULL  | NULL | NULL    | NULL | NULL | NULL | NULL | No tables used | 
+----+-------------+------------+--------+--------------------+---------+---------+-------+------+----------------+ 

Và một lần nữa, lần này chỉ với điều kiện parent_id = @last_id OR parent_id = 5, và nhận được:

+----+-------------+------------+--------+-----------------+------+---------+------+------+----------------+ 
| id | select_type | table  | type | possible_keys | key | key_len | ref | rows | Extra   | 
+----+-------------+------------+--------+-----------------+------+---------+------+------+----------------+ 
| 1 | PRIMARY  | <derived2> | system | NULL   | NULL | NULL | NULL | 1 |    | 
| 1 | PRIMARY  | tree  | ALL | index_parent_id | NULL | NULL | NULL | 10 | Using where | 
| 2 | DERIVED  | NULL  | NULL | NULL   | NULL | NULL | NULL | NULL | No tables used | 
+----+-------------+------------+--------+-----------------+------+---------+------+------+----------------+ 

MySQL không quá tốt với việc xử lý nhiều chỉ mục trong cùng một truy vấn. Mọi thứ tốt hơn một chút với điều kiện AND; một người có nhiều khả năng thấy tối ưu hóa index_merge hơn là tối ưu hóa index union.

Mọi thứ đang cải thiện như phiên bản trước, nhưng tôi đã thử nghiệm bạn truy vấn trên phiên bản 5.5, phiên bản sản xuất mới nhất hiện tại và kết quả như bạn mô tả.

Để giải thích lý do tại sao điều này là khó khăn, hãy xem xét: hai chỉ mục khác nhau sẽ trả lời cho hai điều kiện khác nhau của truy vấn. Một sẽ trả lời cho id = 5, một cho parent_id = @last_id OR parent_id = 5 (BTW không có vấn đề với HOẶC bên trong, vì cả hai thuật ngữ được xử lý từ trong cùng một chỉ mục).

Không có chỉ mục duy nhất có thể trả lời cho cả hai và do đó, lệnh FORCE INDEX bị bỏ qua. Hãy xem, FORCE INDEX nói rằng MySQL phải sử dụng một chỉ số qua quét bảng. Nó không ngụ ý rằng nó phải sử dụng nhiều hơn một chỉ mục trên một lần quét bảng.

Vì vậy, MySQL tuân thủ các quy tắc của tài liệu tại đây. Nhưng tại sao điều này lại phức tạp đến vậy? Bởi vì để trả lời bằng cách sử dụng cả hai chỉ mục, MySQL phải thu thập kết quả từ cả hai, lưu trữ của một người sang một bên trong một số bộ đệm tạm thời trong khi quản lý thứ hai. Sau đó, phải đi qua bộ đệm đó để lọc ra các hàng giống hệt nhau (có thể một số hàng phù hợp với tất cả các điều kiện). Và sau đó quét bộ đệm đó để trả lại kết quả.

Nhưng hãy chờ, bộ đệm đó tự nó không được lập chỉ mục. Lọc trùng lặp không phải là một nhiệm vụ rõ ràng. Vì vậy, MySQL thích làm việc trên bảng gốc và thực hiện quét ở đó, và tránh tất cả những mớ hỗn độn đó.

Tất nhiên điều này có thể giải quyết được. Các kỹ sư tại Oracle vẫn có thể cải thiện điều này (gần đây họ đã làm việc chăm chỉ để cải thiện các kế hoạch thực hiện truy vấn), nhưng tôi không biết đây có phải là nhiệm vụ TODO hay không, hoặc nếu nó có ưu tiên cao.