Phân tích cấu trúc của SQL engine

(dolthub.com)

2 điểm bởi GN⁺ 2025-04-29 | Chưa có bình luận nào. | Chia sẻ qua WhatsApp

SQL engine là tầng logic của cơ sở dữ liệu, hoạt động giữa client và storage
Giải thích chi tiết về các giai đoạn chính của SQL engine: parsing, binding, simplification kế hoạch, khám phá join và đánh giá chi phí, thực thi, spooling kết quả
- Parsing chuyển truy vấn SQL thành cây cú pháp trừu tượng (AST) có cấu trúc
- Binding ánh xạ các trường trong AST với các symbol trong catalog cơ sở dữ liệu hiện tại
- Plan simplification chuẩn hóa cú pháp SQL phức tạp thành dạng đơn giản hơn để tăng tốc độ thực thi
- Plan exploration khám phá nhiều biến thể của join, aggregate và window function để tìm kế hoạch thực thi tối ưu
- Execution và result spooling chuyển kế hoạch cuối cùng thành dạng có thể thực thi và trả kết quả cho client

Tổng quan về SQL engine

SQL engine là lớp trung gian logic giữa yêu cầu từ client và kho lưu trữ dữ liệu
Các bước chính
- Parsing: chuyển truy vấn thành AST (cây cú pháp trừu tượng)
- Binding: liên kết các identifier trong AST với các symbol trong catalog cơ sở dữ liệu
- Plan Simplification: đơn giản hóa nhiều cú pháp SQL khác nhau thành dạng plan chuẩn hóa
- Join Exploration & Costing: khám phá nhiều thứ tự join và đánh giá chi phí
- Execution: thực thi truy vấn bằng plan thực thi tối ưu
- Spooling Results: trả kết quả về cho client

Parsing là quá trình token hóa truy vấn đầu vào và chuyển nó thành AST
Parser đệ quy phải dễ hiểu và dễ debug, nhưng dùng nhiều bộ nhớ stack
Parser đệ quy trái (dựa trên Yacc) hiệu quả hơn về bộ nhớ nhưng cần logic phức tạp hơn
Dolt sử dụng parser đệ quy trái để hỗ trợ phân tích cú pháp nhanh
Khi parsing thành công, cấu trúc AST sẽ khớp với các quy tắc Yacc

Binding là quá trình liên kết các trường trong AST với symbol của bảng và cột thực tế trong cơ sở dữ liệu
Các khái niệm chính
- Định nghĩa bảng: đóng vai trò là nguồn dữ liệu
- Định nghĩa cột: tham chiếu đến một cột cụ thể từ nguồn bảng
- Bí danh (Alias): dùng giá trị scalar vừa như source vừa như sink
- Scalar subquery: chia sẻ scope cha và thực hiện name binding
Kết quả của binding là tạo ra các node kế hoạch thực thi ở dạng sql.Node

Đây là quá trình chuyển nhiều biểu diễn SQL khác nhau sang dạng chuẩn hóa để hỗ trợ tối ưu thực thi
Các tối ưu tiêu biểu
- Filter Pushdown: loại bỏ các hàng không cần thiết
- Column Pruning: loại bỏ các cột không cần thiết
Ngoài ra còn tối ưu kế hoạch join thông qua các biến đổi như subquery decorrelation

Type coercion là quá trình tự động chuyển đổi kiểu của biểu thức theo ngữ cảnh
Kiểu dữ liệu có thể thay đổi tùy theo ngữ cảnh như WHERE, INSERT, v.v.
Dolt đang xử lý việc chuyển đổi kiểu dần dần ở giai đoạn binding

Khám phá join là quá trình tạo ra và xem xét nhiều thứ tự join khác nhau
Hai chiến lược khám phá
- Backtracking top-down: chỉ khám phá các thứ tự join hợp lệ
- Dynamic programming (DP) bottom-up: thử mọi tổ hợp để tìm thứ tự join tối ưu
Sử dụng cấu trúc Memo để quản lý trạng thái trung gian hiệu quả

Khi join từ 5 bảng trở lên, chi phí có thể tăng mạnh
Có thể giảm chi phí khám phá bằng cách tận dụng quan hệ 1:1 như join dựa trên primary key (PK)
Tối ưu bằng cách ưu tiên xem xét LOOKUP_JOIN

Tóm tắt 3 giai đoạn IR đã đi qua
- AST: sắp xếp token
- Scope binding: kiểm tra tham chiếu cột
- Memo: biểu diễn cho việc khám phá join và đánh giá chi phí

Đánh giá chi phí join là quá trình ước tính chi phí thực thi cho mọi kế hoạch khả dĩ
Các yếu tố chi phí
- Kích thước bảng đầu vào
- Kích thước bảng kết quả
- Loại toán tử join (LOOKUP_JOIN, HASH_JOIN, v.v.)
Dolt đánh giá chi phí dựa trên thống kê bảng chính xác (histogram)

Hệ thống cố gắng ưu tiên áp dụng chiến lược join theo các hint do người dùng cung cấp
Các hint mâu thuẫn hoặc không phù hợp sẽ bị bỏ qua

Chuyển plan tối ưu thành cấu trúc iterator (Volcano Iterator) có thể thực thi thực tế
Đặc điểm
- Iterator không materialize: trả hàng ngay lập tức
- Iterator materialize: thu thập toàn bộ hàng rồi mới trả về
Tham chiếu cột được ánh xạ theo offset chỉ mục trước khi thực thi

Kết quả thực thi được chuyển sang định dạng giao thức MySQL rồi gửi đến client
Trong một số trường hợp, hệ thống còn tối ưu bằng cách đọc kết quả trực tiếp từ lớp lưu trữ key-value (KV)
Cải thiện tốc độ xử lý và hiệu quả bộ nhớ thông qua batch và tái sử dụng buffer

Về cơ bản, Dolt đang sử dụng row-based execution trên server cục bộ
Hệ thống hỗ trợ xây dựng kế hoạch thực thi tối ưu bằng 3 giai đoạn biểu diễn trung gian (IR) như AST, binding dựa trên scope, và khám phá join thông qua cấu trúc Memo
Xác định chiến lược join tối ưu thông qua Join Search và Join Costing
Trong tương lai, Dolt có kế hoạch cải thiện hiệu năng thông qua hợp nhất IR và tối ưu tái sử dụng bộ nhớ