Kiến thức nền

Liên quan

Kho lưu trữ · 2.997 từ · 13 phút đọc

Trình tối ưu truy vấn: SQL thực sự chạy như thế nào

Bạn viết điều bạn muốn; cơ sở dữ liệu quyết định như thế nào. Tour qua cách một trình tối ưu phân tích, viết lại, ước lượng, và lập kế hoạch một truy vấn SQL — và tại sao cùng truy vấn có thể nhanh thứ Hai và chậm thứ Sáu.

Mục lục
  1. TL;DR
  2. Công việc
  3. Pipeline bốn giai đoạn
  4. Kế hoạch logic vs. vật lý
  5. Tối ưu dựa trên chi phí
  6. Ước lượng cardinality: Thứ bị sai
  7. Chọn index
  8. Thứ tự Join
  9. Tại sao cùng truy vấn có thể nhanh và chậm
  10. Gợi ý truy vấn: Bác bỏ trình tối ưu
  11. Tại sao các trình tối ưu khó
  12. Điều trình tối ưu thực sự mở khóa

#TL;DR

Tính chất ít được đánh giá nhất của mô hình quan hệ là SQL mô tả cái gì bạn muốn, không phải cách lấy nó. Giữa SELECT và kết quả, có một phần mềm — trình tối ưu truy vấn — phân tích truy vấn của bạn, viết lại nó, ước lượng chi phí của hàng chục hay hàng nghìn chiến lược thực thi khả dĩ, và chọn một. Trình tối ưu dựa-trên-chi-phí hiện đại truy nguyên về dự án System R của IBM vào cuối những năm 1970, cụ thể là bài báo của Pat Selinger năm 1979. Bốn mươi bảy năm sau, tối ưu truy vấn vẫn là nguồn lớn nhất duy nhất của những khoảnh khắc “tại sao truy vấn này chậm” trong cơ sở dữ liệu sản xuất — và hiểu cách các trình tối ưu suy nghĩ là khoảng cách kỹ năng chính giữa những người viết SQL và những người gỡ lỗi SQL.

#Công việc

Cho truy vấn:

SELECT c.name, SUM(o.amount)
FROM customers c
JOIN orders o ON o.cust_id = c.id
WHERE c.city = 'London'
GROUP BY c.name
HAVING SUM(o.amount) > 1000;

Cơ sở dữ liệu phải quyết định:

  • Đọc bảng nào trước. Đọc customers, lọc về London, rồi tra cứu orders? Hay đọc orders, rồi join với customers?
  • Cách thực thi JOIN. Nested loop? Hash join? Sort-merge?
  • Dùng index nào. Có index trên customers.city không? Trên orders.cust_id?
  • Cách sắp xếp hay hash cho GROUP BY. Đã sắp xếp theo c.name? Xây bảng hash trong bộ nhớ?
  • Khi nào áp dụng HAVING và các bộ lọc. Lọc càng sớm càng tốt (đẩy predicate xuống)?

Mỗi quyết định này đều độc lập, và các tổ hợp nhân lên nhanh. Một join 10 bảng có 10! = 3,6 triệu thứ tự khả dĩ, mỗi cái với nhiều thuật toán, mỗi cái với các lựa chọn index. Trình tối ưu không thể thử tất cả. Nó phải thông minh về kế hoạch nào đáng xem xét.

#Pipeline bốn giai đoạn

Mọi truy vấn SQL đi qua đại khái bốn giai đoạn giữa việc được gửi và được thực thi.

┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│  Phân tích │►│ Viết lại │►│ Lập kế hoạch│►│ Thực thi │
└──────────┘   └──────────┘   └──────────┘   └──────────┘

Phân tích — biến chuỗi SQL thành cây phân tích. Lỗi cú pháp sống ở đây. Đầu ra: một cây cú pháp trừu tượng, đại khái trung thành với điều người dùng đã gõ.

Viết lại (lập kế hoạch logic) — áp dụng các biến đổi không thay đổi ngữ nghĩa nhưng đơn giản hóa cây. Ví dụ: mở rộng view (thay tham chiếu đến view bằng định nghĩa của nó), gấp hằng (WHERE 1 = 1 được loại bỏ), làm phẳng truy vấn con, đẩy predicate xuống (di chuyển bộ lọc gần các bảng hơn), đơn giản hóa outer join.

Lập kế hoạch (lập kế hoạch vật lý, còn gọi là tối ưu) — quyết định chiến lược thực thi thực tế. Đây là nơi thứ tự join, thuật toán join, chọn index, và chiến lược tổng hợp được chọn. Đầu ra là một kế hoạch thực thi — một cây các toán tử vật lý.

Thực thi — chạy kế hoạch. Đọc các trang, áp dụng bộ lọc, thực hiện join, stream kết quả. Đến khi thực thi bắt đầu, tất cả các quyết định thú vị đã được đưa ra.

#Kế hoạch logic vs. vật lý

Đáng xem kế hoạch thực sự trông như thế nào. Đầu ra EXPLAIN của Postgres cho truy vấn trên có thể tạo ra:

 GroupAggregate  (cost=0.71..24.86 rows=10 width=40)
   Group Key: c.name
   Filter: (sum(o.amount) > 1000)
   ->  Nested Loop  (cost=0.71..24.76 rows=25 width=14)
         ->  Index Scan using customers_city_idx on customers c
               (cost=0.29..8.30 rows=5 width=10)
               Index Cond: (city = 'London')
         ->  Index Scan using orders_cust_id_idx on orders o
               (cost=0.43..3.27 rows=5 width=8)
               Index Cond: (cust_id = c.id)

Đọc từ dưới lên:

  1. Sử dụng customers_city_idx để tìm các hàng có city = ‘London’. Ước tính 5 hàng.
  2. Với mỗi hàng, sử dụng orders_cust_id_idx để tìm các đơn hàng khớp. Ước tính 5 mỗi khách hàng.
  3. Đưa các cặp đã join vào một GroupAggregate, tổng hợp các số tiền theo tên.
  4. Áp dụng bộ lọc HAVING.

Trình tối ưu chọn một nested loop join vì nó mong đợi bên ngoài (khách hàng London) nhỏ. Với nhiều khách hàng hơn, nó có thể đã chọn một hash join thay vì.

Các số cost=0.71..24.86 là ước lượng chi phí của trình tối ưu trong đơn vị nội bộ. rows=10 là đoán của nó về bao nhiêu hàng bước này sẽ tạo ra. Cả hai đều là ước lượng, và chúng là đầu vào quan trọng cho chọn kế hoạch.

#Tối ưu dựa trên chi phí

Các trình tối ưu hiện đại là dựa trên chi phí. Chúng ước lượng mỗi kế hoạch ứng viên sẽ đắt đến đâu, rồi chọn cái rẻ nhất. Lựa chọn thay thế — tối ưu dựa trên quy tắc — áp dụng các quy tắc cố định bất kể đặc điểm dữ liệu, và nó phần lớn đã chết vào những năm 1990 vì nó tạo ra các kế hoạch tồi tệ cho khối lượng công việc không tầm thường.

Ước lượng chi phí phụ thuộc vào hai thứ:

Thống kê về dữ liệu. Mọi cơ sở dữ liệu hiện đại duy trì thống kê mỗi-cột: tổng số hàng, số giá trị khác biệt, phân phối giá trị (thường dưới dạng histogram), tỷ lệ null, độ rộng hàng trung bình. Postgres thu thập chúng qua ANALYZE. Các cơ sở dữ liệu khác có các cơ chế tương tự.

Mô hình chi phí chuyển các phép toán kế hoạch thành các đơn vị chi phí. Một quét tuần tự của N hàng có chi phí tỷ lệ với số trang đọc. Một nested loop của N × M hàng có chi phí tỷ lệ với N × M. Một tra cứu index có chi phí đại khái tỷ lệ với log M. Mỗi cái được điều chỉnh với các hằng số như seq_page_cost (chi phí đọc một trang tuần tự) và cpu_tuple_cost (chi phí xử lý một bộ trong bộ nhớ).

Kết hợp thống kê và mô hình chi phí cho chi phí ước lượng cho bất kỳ kế hoạch ứng viên nào. Trình tối ưu khám phá không gian kế hoạch — được thông báo bởi một tập các heuristic về kế hoạch nào thậm chí đáng xem xét — và chọn cái rẻ nhất.

#Ước lượng cardinality: Thứ bị sai

Đầu vào chính cho ước lượng chi phí là cardinality — bao nhiêu hàng một phép toán nhất định sẽ tạo ra.

Cho một predicate đơn giản như WHERE city = 'London', trình tối ưu nhìn vào histogram của cột city. Nếu ‘London’ chiếm 5% mẫu histogram, và bảng có 10.000 hàng, ước lượng là 500 hàng.

Cho một JOIN, trình tối ưu ước lượng mỗi bên sẽ tạo ra bao nhiêu hàng, rồi bao nhiêu sẽ khớp. Cho hai bảng với 1.000 và 10.000 hàng join trên một khóa ngoại, trình tối ưu có thể ước lượng join tạo ra 10.000 hàng (nếu khóa ngoại được điền đầy đủ).

Ước lượng cardinality là thứ bị sai nhiều nhất trong các trình tối ưu thực. Các thất bại của nó tạo ra các kế hoạch cổ điển “tốt cho dữ liệu nhỏ, thảm họa cho dữ liệu lớn”:

  • Các cột tương quan. Trình tối ưu giả định các cột độc lập. Nếu city = 'London' và country = 'UK' tương quan mạnh, ước lượng của “hàng khớp cả hai” thường quá thấp.
  • Dữ liệu lệch. Một histogram với 100 bucket không thể nắm bắt sự thật rằng 60% hàng có giá trị 'pending' cho cột trạng thái, đặc biệt nếu ranh giới bucket không căn chỉnh.
  • Chồng predicate. Nhiều bộ lọc thường được giả định kết hợp nhân. Nếu mỗi bộ lọc giữ 10% hàng, bốn bộ lọc được ước lượng giữ 0,01% — thường quá hung hăng.
  • Thống kê cũ. Nếu ANALYZE chưa được chạy gần đây, phân phối trình tối ưu đang sử dụng không khớp với dữ liệu hiện tại.

Khi ước lượng cardinality sai, trình tối ưu chọn một kế hoạch được tối ưu cho kích thước dữ liệu sai. Kế hoạch sau đó được mong đợi xử lý 100 hàng nhưng thực sự xử lý 10 triệu, với một nested loop tuyệt vời cho 100 và thảm họa cho 10 triệu. Đây là vấn đề hiệu năng phổ biến nhất duy nhất trong cơ sở dữ liệu sản xuất.

EXPLAIN ANALYZE tồn tại cụ thể để chẩn đoán điều này — nó hiển thị số hàng ước lượng vs. thực tế ở mỗi bước.

->  Nested Loop  (cost=... rows=100 width=...)
              (actual rows=10432892 loops=1)

Một sai lệch 5-bậc-độ-lớn giữa ước lượng và thực tế có nghĩa là kế hoạch sai và lý do là ước lượng cardinality. Sửa thường là thống kê tốt hơn, một lần viết lại truy vấn để giúp trình tối ưu, hoặc một gợi ý rõ ràng.

#Chọn index

Trình tối ưu xem xét mọi index trên một cột liên quan và ước lượng chi phí của mỗi đường truy cập tiềm năng:

  • Quét tuần tự. Đọc mọi hàng của bảng. Chi phí tỷ lệ với kích thước bảng.
  • Quét index. Duyệt một index (B-tree hay hash), đọc các hàng khớp. Chi phí tỷ lệ với kích thước kết quả, không phải kích thước bảng — nhưng với I/O ngẫu nhiên thêm mỗi hàng.
  • Quét chỉ-index. Nếu mọi cột cần thiết ở trong index, bỏ qua bảng hoàn toàn. Nhanh hơn nhiều.
  • Quét index bitmap. Xây dựng một bitmap các ID hàng khớp, rồi đọc các hàng đó theo thứ tự vật lý. Tốt cho các tập kết quả kích thước trung bình.

Lựa chọn phụ thuộc vào bao nhiêu hàng bộ lọc được mong đợi trả về. Cho 1% của một bảng lớn, quét index nhanh hơn nhiều. Cho 50% của một bảng, quét tuần tự thực sự tốt hơn — I/O ngẫu nhiên của quét index vượt quá sự tiết kiệm.

Đây là lý do thêm một index không luôn làm truy vấn nhanh hơn. Nếu trình tối ưu đã chọn quét tuần tự vì bộ lọc không chọn lọc, thêm một index bị bỏ qua. Nếu trình tối ưu chọn index mới nhưng bộ lọc ít chọn lọc hơn nó nhìn (ước lượng cardinality sai), hiệu năng có thể tệ hơn.

#Thứ tự Join

Cho một truy vấn join N bảng, trình tối ưu phải chọn một thứ tự. Về mặt lý thuyết, tất cả N! thứ tự là ứng viên. Trong thực tế, trình tối ưu sử dụng quy hoạch động để chỉ xem xét các kế hoạch nghiêng trái hoặc rậm rạp đến một ngưỡng (thường 8-12 bảng), và chuyển sang heuristic cho các join lớn hơn.

Quy hoạch động (kiểu Selinger). Xây dựng các join lớn hơn từ các join nhỏ hơn. Cho 2 bảng, thử cả hai thứ tự và tất cả thuật toán, chọn cái tốt nhất. Cho 3 bảng, lấy mỗi kế hoạch con 2 bảng và thêm bảng thứ ba theo mọi cách khả dĩ. Cho N bảng, lặp lại. Điều này tạo ra khoảng O(2^N) kế hoạch ứng viên, quản lý được đến 8-12 bảng.

Tham lam / heuristic cho các join lớn. Vượt ngưỡng DP, các trình tối ưu quay lại heuristic: “join cái nhỏ nhất trước,” “ưu tiên các join có bộ lọc chọn lọc,” “tránh tích Descartes.” Chúng tạo ra các kế hoạch nhanh chóng nhưng không được đảm bảo tối ưu. Postgres có geqo (tối ưu truy vấn di truyền) cho các join 12+ bảng, chạy một thuật toán di truyền trên các kế hoạch ứng viên.

Bài báo Selinger từ 1979 (“Access Path Selection in a Relational Database Management System”) giới thiệu cách tiếp cận DP và vẫn đại khái là cách các trình tối ưu hiện đại hoạt động. Hầu hết các cải tiến hiện đại là trong các ước lượng chi phí tốt hơn và các heuristic thông minh hơn cho các join lớn, không phải trong thuật toán cơ bản.

#Tại sao cùng truy vấn có thể nhanh và chậm

Một câu hỏi các nhà phát triển hỏi với chút tiếc nuối: “Tại sao truy vấn này mất 50 ms hôm qua và 5 phút hôm nay?”

Một số lý do:

  • Thay đổi kế hoạch do thống kê đã cập nhật. Một ANALYZE chạy, thay đổi phân phối dữ liệu trình tối ưu nhìn. Trình tối ưu chọn một kế hoạch khác. Kế hoạch mới tệ hơn cho dữ liệu hiện tại.
  • Tham số “đánh hơi”. Cơ sở dữ liệu đã cache một kế hoạch được tối ưu cho một giá trị tham số cụ thể. Một lần gọi mới với giá trị tham số khác sử dụng kế hoạch đã cache, sai cho giá trị mới.
  • Tăng trưởng dữ liệu vượt một ngưỡng. Một quét tuần tự ổn trên một bảng 1.000 hàng. Ở 100.000 hàng, nó chậm. Trình tối ưu có thể chưa nhận ra vì thống kê của nó chưa bắt kịp.
  • Phình index hoặc thống kê cũ. Trình tối ưu ước lượng một index sẽ nhanh; index thực tế đã phình to do cập nhật và hoạt động tệ hơn nhiều so với ước lượng.
  • Các truy vấn khác cạnh tranh tài nguyên. Cùng kế hoạch nhanh trên một hệ thống nhàn rỗi chậm khi cơ sở dữ liệu bận.
  • Một index mới được thêm hoặc bỏ. Các đường truy cập đã thay đổi.

Chẩn đoán “tại sao cái này chậm” thường có nghĩa là chạy EXPLAIN ANALYZE và tìm hai điều: sai lệch lớn giữa số hàng ước lượng và thực tế (vấn đề cardinality), và các bước đắt không mong đợi (đường truy cập sai).

#Gợi ý truy vấn: Bác bỏ trình tối ưu

Một số cơ sở dữ liệu cho bạn đưa gợi ý cho trình tối ưu — các chỉ thị buộc các đường truy cập cụ thể hoặc thuật toán join. Ví dụ:

  • Oracle: SELECT /*+ USE_NL(o, c) */ ...
  • SQL Server: SELECT ... FROM o INNER LOOP JOIN c ...
  • MySQL: SELECT ... FROM t1 FORCE INDEX (idx1) ...
  • Postgres: không hỗ trợ gợi ý một cách bản địa, mặc dù extension pg_hint_plan thêm chúng.

Gợi ý truy vấn là một công cụ thô. Chúng ghi đè phân tích chi phí của trình tối ưu với đánh giá của bạn. Chúng hữu ích khi:

  • Bạn biết trình tối ưu nhất quán sai cho truy vấn cụ thể này.
  • Bạn đã dùng hết các sửa khác (thống kê tốt hơn, thay đổi schema, viết lại truy vấn).
  • Khối lượng công việc ổn định và kế hoạch tối ưu sẽ không thay đổi.

Chúng nguy hiểm vì chúng tồn tại vượt qua các thay đổi mà sẽ tự sửa. Một gợi ý buộc quét index hôm nay sẽ vẫn buộc quét index đó sau khi bạn bỏ index, nâng cấp cơ sở dữ liệu, hoặc thay đổi phân phối dữ liệu. Lựa chọn của Postgres không hỗ trợ gợi ý là tư tưởng — vị trí là nếu trình tối ưu sai, trình tối ưu nên được sửa, không phải bỏ qua.

#Tại sao các trình tối ưu khó

Sau năm mươi năm nghiên cứu, tối ưu truy vấn vẫn là một lĩnh vực hoạt động. Các khó khăn cơ bản:

  • Không gian kế hoạch khổng lồ. Cho một join 20 bảng, có nhiều kế hoạch khả dĩ hơn số nguyên tử trong vũ trụ quan sát được. Bạn chỉ có thể khám phá một phần nhỏ.
  • Ước lượng cardinality chưa giải. Các bộ ước lượng dựa trên histogram, lấy mẫu, machine learning (có nghiên cứu nghiêm túc về việc sử dụng các bộ ước lượng dựa trên ML) tất cả đều thất bại theo cách dự đoán được trên dữ liệu thực tế.
  • Chi phí phụ thuộc vào caching. Một quét tuần tự cache-lạnh rất khác với cache-nóng. Các trình tối ưu có các mô hình không hoàn hảo về nội dung của buffer pool.
  • Trôi khối lượng công việc. Một kế hoạch được tối ưu cho khối lượng công việc từ tháng trước có thể tệ cho khối lượng công việc tháng này. Xử lý truy vấn thích ứng (suy nghĩ lại kế hoạch trong quá trình thực thi) là một lĩnh vực nghiên cứu đang diễn ra.
  • Các hiệu ứng tương tác. Nhiều truy vấn chạy đồng thời cạnh tranh tài nguyên theo các cách mà một trình tối ưu xem xét một truy vấn một lúc không thể mô hình hóa.

Mỗi cái là một chủ đề nghiên cứu sống. Trình tối ưu truy vấn vẫn là một trong những phần mềm khó nhất trong bất kỳ cơ sở dữ liệu nào, và nó chiếm một phần lớn của nỗ lực kỹ thuật hiệu năng trên mọi sản phẩm cơ sở dữ liệu trưởng thành.

#Điều trình tối ưu thực sự mở khóa

Bài Mô hình Quan hệ nói SQL mô tả cái gì cần truy xuất, và engine cơ sở dữ liệu quyết định như thế nào. Tuyên bố đó chỉ có ý nghĩa vì trình tối ưu tồn tại. Không có nó, “ngôn ngữ truy vấn khai báo” chỉ là cú pháp. Với nó, SQL trở thành một trừu tượng thực sự trên truy cập dữ liệu.

Phần thưởng là cùng SQL tiếp tục hoạt động khi cơ sở dữ liệu cải thiện. Truy vấn của bạn có thể chạy nhanh hơn 100 lần sau một nâng cấp cơ sở dữ liệu, vì trình tối ưu trở nên thông minh hơn — mà bạn không thay đổi một dòng. Các index mới có thể được thêm và trình tối ưu sẽ sử dụng chúng. Các phân phối dữ liệu có thể dịch chuyển và trình tối ưu sẽ thích ứng. Truy vấn là hợp đồng ổn định; thực thi là thích ứng.

Đây là lời hứa lặng lẽ, chịu tải mà mô hình quan hệ thực hiện. Bài báo năm 1970 của Codd lập luận cho độc lập dữ liệu — ý tưởng rằng các chương trình không nên biết dữ liệu được lưu trữ như thế nào. Trình tối ưu là thứ thực hiện lời hứa đó trong thực tế. Đó là thành phần làm cho SQL là một ngôn ngữ năng suất để viết, và đó là thành phần làm cho SQL là một ngôn ngữ bực bội để gỡ lỗi. Cả hai điều đều đúng cùng lúc, và đã vậy trong gần năm mươi năm.