SQL Planning: Parser & Optimizer
Kết hợp ngôn ngữ SQL với khả năng mở rộng của key-value store.
Key-Value store là kiểu database có khả năng phân tán cao và khả năng mở rộng theo chiều ngang mà các loại database khác không đạt được.
Mặc khác, SQL database truyền thống lại quen thuộc và dễ dàng tổ chức các bảng, các ràng buộc quan hệ, ..., đồng thời cũng cho phép developer sử dụng transaction thoả mãn tính ACID.
Một số distributed database sẽ kết hợp cả 2 điểm mạnh nói trên: phần cú pháp SQL và hệ thống lưu trữ dưới dạng key-value, có thể kể đến như Cockroach DB, TiDB, …
Mục tiêu của bài viết này là làm rõ một số vấn đề sau:
- Cách thức câu SQL query được chuyển đổi thành cú pháp key-value,
- Quá trình phân tích câu query thành cây cú pháp trừu tượng,
- Quá trình tối ưu hóa câu query trước khi được thực thi,
- Làm thế nào một Distributed database (như TiDB) xử lý quá trình này.
Tổng quan
Đầu tiên, nên nhắc lại một chút về cây phân tích cú pháp (Parse Tree) và cây cú pháp trừu tượng (Abstract Syntax Tree - AST):
- Parse tree là một biểu diễn cụ thể của chuỗi input, giữ lại tất cả thành phần của input (như ngoặc, dấu câu, ...)
- AST là biểu diễn trừu tượng của input, bỏ đi các phần không cần thiết, như ví dụ thì AST có node cha là các toán tử (operator), node con là các toán hạng (operand).
Hai khái niệm trên cũng là 2 bước rất quan trọng trong xây dựng trình biên dịch (Compiler) hay thiết kế ngôn ngữ mới. Các công cụ thông dụng để hỗ trợ trong bước phân tích này có thể kể đến như ANTLR, Lex & Yacc.
Trong bài viết này, ta sử dụng GoYacc, là một thư viện chạy trên Go của Yacc. Đồng thời sử dụng Go như ngôn ngữ hiện thực.
Hình sau cho thấy quá trình một Compiler biên dịch từ chuỗi input thành mã thực thi:
Trong trường hợp của mình, chúng ta mong muốn biến đổi từ chuỗi input thành các cặp key-value tương ứng để cho lớp lưu trữ xử lý. Quá trình này tương đương với việc xây dựng một compiler làm nhiệm vụ biên dịch SQL query -> key-value pairs.
Tuy nhiên do đặc thù của SQL, chúng ta có thể thêm các bước tối ưu hoá (optimize) câu truy vấn để giúp giảm tải cho lớp lưu trữ bên dưới, từ đó tăng hiệu suất thực thi của cả hệ thống.
Flow xử lý mà câu query đi qua như sau:
Từ đó đi đến biểu diễn đầy đủ hơn cho một hệ thống cơ sở dữ liệu phân tán:
Trong đó:
- Protocol Layer chịu trách nhiệm giao tiếp với client, thực hiện một số thao tác xác thực.
- Mỗi câu query sẽ được tạo ra một Session, nắm giữ các thông tin về context,
- Tiếp theo câu query sẽ được Parser và Optimizer lần lượt phân tích và tối ưu hoá thành các plan tương ứng, quá trình này có sự hỗ trợ của thành phần Statistics để ước lượng chi phí (cost) của plan.
- Sau cùng là Executor thực hiện mapping các plan thành các cặp key-value và chuyển cho lớp storage (ví dụ TiKV) xử lý, kết quả trả về được phản hồi cho client.
Bây giờ hãy đi vào chi tiết từng bước.
Bước 1: Parse Statement
Bước này đảm nhiệm các công việc sau:
- Phân tích từ vựng (Lexical Analyzer - Lexer): biến đổi SQL text thành cấu trúc Parse Tree tương ứng (thực ra là list các token).
- Phân tích cú pháp (Syntax Analyzer - Parser): trừu tượng hoá Parse Tree thành Abstract Syntax Tree (AST).
- Phân tích ngữ nghĩa (Semantic Analyzing): phân giải các biến trong AST trở nên cụ thể như thêm table name vào column.
- Phát hiện các lỗi về từ vựng, cú pháp, ngữ nghĩa.
- Cache câu query: thông qua Normalize và DigestHash, các câu SQL được lưu lại trên cache.
Bước này có thể chia làm 3 phase như sau:
Phase 1: Lexical Analyzing
Nhiệm vụ:
- Phân tích câu SQL thành các token dựa trên ký tự phân tách (indent) như white space và các keyword định nghĩa trước.
- Xác định các kí tự có valid hay không.
Phase này ta có thể sử dụng các công cụ nhận dạng bằng Regex (Regular Expression) như ANTLR hoặc Lex. Tuy nhiên để tối đa hoá performance, thường các Distributed Database đều tự viết cho mình một công cụ Lexer để sử dụng.
Ví dụ: câu query sau "SELECT * FROM b WHERE a > 0 ORDER BY a;" sẽ được biến đổi thành list các token:
Phase 2: Syntax Analyzing
Nhiệm vụ:
- Tạo cây AST từ các token ở phase 1.
- Xác định các lỗi về cú pháp (về ngoặt, sai thành phần trong câu, …)
Để thực hiện được quá trình phân tích, ta định nghĩa các SQL grammar rule trong một file riêng là 'parser.y' có cấu trúc như sau:
- Phần đầu khai báo một số các biến, thư viện sử dụng,
- Phần giữa định nghĩa các keyword (như ALTER, SELECT, DROP, ...)
- Phần cuối quan trọng nhất để định nghĩa các cú pháp SQL, chính là phần xương sống mà dựa trên đó ta xử lý các câu query sau này.
Các định nghĩa cú pháp nên tuân theo MySQL Reference Manual :: SQL Statement Syntax. Biểu diễn railroad diagram của chúng có thể tham khảo ở pingcap.github.io/sqlgram/:
Khác với ANTLR cung cấp interface visitor để tách riêng phần xử lý logic và phần định nghĩa cú pháp, Yacc (mà ta đang sử dụng) tích hợp luôn cả 2 vào cùng file định nghĩa 'parser.y' duy nhất. Do đó file này đảm nhận luôn nhiệm vụ trả về các node trong cây AST cho từng statement tương ứng, ví dụ:
Nhìn chung có thể chia các node trên AST thành 2 loại:
- Expression node: các node có thể tính toán được giá trị (như các điều kiện trong ON/HAVING/WHERE)
- Statement node: các node có thành phần là các node con khác. Ví dụ
Kết thúc phase này, từ list các token ta thu được một cấu trúc AST tương ứng.
Ví dụ: câu query sau “SELECT * FROM b WHERE a > 0 ORDER BY a;” sẽ được biến đổi thành AST:
Phase 3: Query Planning
Nhiệm vụ:
- Chuyển đổi AST thành Logical Plan Tree.
Chúng ta cần điểm lại một chút về 2 khái niệm:
1. Logical Plan: một biểu diễn dạng đại số quan hệ của câu query. Gồm các Logical Operator.
- Ví dụ: Selection (π), Projection (σ), Join (⋈), …
- Một số logical operator thường dùng:
2. Physical Query Plan: bao gồm các Physical Operator giúp thực thi câu query đó.
- Ví dụ: Index Scan, Hash Join, Stream Aggregate, ...
Quay trở lại với phase 3 này, cấu trúc AST sẽ được chuyển đổi thành Logical Plan tương ứng (SELECT -> Projection, WHERE -> Selection, ...):
Ví dụ 1: câu query “SELECT * FROM b WHERE a > 0 ORDER BY a;” ứng với AST ở phase 2 sẽ được biến đổi thành Logical Plan sau:
Tương ứng với biểu thức đại số quan hệ:
Ví dụ 2: câu query phức tạp hơn để thấy rõ về các toán tử
Sẽ chuyển thành Logical Plan sau:
Ứng với biểu thức đại số quan hệ:
Bước 2: Optimize Statement
Thực hiện tối ưu hoá Logical Plan và Physical Plan.
Bước này gồm 2 phase.
Phase 1: Logical Optimizing
Nhiệm vụ:
- Quá trình Logical Optimization dựa trên các rule để tối ưu hoá query plan, đây được gọi là quá trình Rule-Based Optimization (RBO).
Một số rule để thực hiện tối ưu hoá:
- Column Pruning
- Max/Min Elimination
- Project Elimination
- Outer Join Elimination
- Predicate Push Down
- Aggregate Push Down
- Join Reorder
- …
Tuỳ theo loại node của AST mà áp dụng các rule tương ứng với node đó.
Ví dụ: với câu query và logical plan trong phần trước
Ta lần lượt áp dụng 2 rule:
1. Column Pruner: quá trình table scan chỉ cần trả về data ứng với column cần thiết, Plan tree gọi đệ quy rule này từ root tới leaf, mỗi node chỉ cần giữ lại column mà node cha nó yêu cầu (hình dưới thêm Projection để bỏ bớt các column chỉ giữ lại id, value)
Tương ứng với biểu thức quan hệ:
2. Predicate Pushdown: pushdown các predicate trong WHERE/ON/HAVING xuống sâu nhất có thể. Việc này giúp tối thiểu lượng data phải đọc ở storage (hình dưới push down điều kiện t2.id>5000 trước khi thực hiện Join).
Tương ứng biểu thức:
Phase 2: Physical Optimizing
Nhiệm vụ:
- Trước tiên chuyển đổi Logical Plan thành Physical Plan.
- Quá trình Physical Optimization chọn lấy 1 hiện thực có chi phí ít nhất trong các hiện thực operator của logical plan, đây có thể xem là Cost-Based Optimization (CBO).
Một số Logical Operator và Physical Operator tương ứng:
DataSource:
- IndexReader
- TableReader
- IndexLookUpReader
Aggregation:
- Stream Aggregate
- Hash Aggregate
Join:
- Hash Join
- Index Join
- Sort Merge Join
Sau khi chuyển đổi thành Physical Plan thì tiến hành tính cost của plan:
Trong đó:
- N là chi phí Network.
- M là chi phí Memory.
- C là chi phí CPU.
- a, b, r là các hệ số thay đổi tuỳ theo toán tử (Join khác Aggregate, khác với DataScan,...).
Ví dụ: vẫn là câu query cũ
Trong phase trước trở thành Logical Plan đã tối ưu như sau:
Sẽ được biến đổi thành Physical Plan qua các bước ước lượng chi phí:
- Phương thức findBestTask được gọi đệ quy xuống các node con, tạo ra các toán tử physical và estimate cost. Sau đó xác định và chọn task được thực hiện với chi phí nhỏ nhất.
- Các best task sẽ được store lại để giảm chi phí tính toán cho lần sau cho cùng một loại property. Ở đây có sự tham gia của Statistics như đã nhắc ở phần đầu.
Cuối cùng ta thu được Physical Plan đã tối ưu như sau:
Plan này sẽ được đưa tới Executor và thực hiện mapping với các cặp key-value và gọi tới lớp Storage (ví dụ TiKV) để thực thi.
Trong bài kế tiếp, ta sẽ tìm hiểu nguyên lý cũng như cách thực hiện quá trình mapping này.
Các bạn có thể xem bài viết gốc ở đây http://anhnq.com/posts/sql-planning-parser-optimizer/
Cảm ơn các bạn đã đọc.
Lời kết
Cảm ơn anh AJ Pham đã cùng đóng góp và sửa lỗi, anh Andy Le đã đọc và góp ý rất nhiều cho bài viết.
