Query Optimization (Overview)

Tổng quan

Phần lớn các truy vấn được viết bởi ngôn ngữ bậc cao phi thủ tục như SQL, QBE, OQL. Các truy vấn này phải được chuyển sang các biểu thức đại số quan hệ tương đương (query tree). Các biểu thức này có chứa các toán tử đại số quan hệ, mỗi toán tử có một chi phí (cost) thực thi tương ứng. Với một mệnh đề truy vấn, có thể chuyển đổi tương ứng với nhiều cây truy vấn, việc chọn lựa plan thực thi nào là dựa trên đánh giá chi phí. Các cây truy vấn tương đương được sinh ra nhờ các phép biến đổi tương đương.

Vấn đề ở đây là làm sao để chọn được best plan từ không gian physical plans. Chúng ta sẽ gặp khó khăn vì không gian này có thể rất lớn do:

• Có nhiều phép biến đổi tương đương
• Các phép toán vật lý khác nhau cho cùng một toán tử logic
  • nested loop join, hash join, sort-merge join
  • index-scan, table-scan
• Các mẫu cây khác nhau
• Các chiến thuật xử lý gối đầu (pipelining, …)

Chúng ta có thể sử dụng các chiến lược sau:

• Chọn một plan bất kỳ
• Dựa vào mẹo: Ví dụ sử dụng index nhiều nhất có thể với HQTCSDL MySQL
• Dựa trên chi phí
  • Liệt kê, ước lượng chi phí thi hành, chọn cái tốt nhất
  • Chú ý các vòng lặp trong các plans
• Hybrid

Trên thực tế các chiến lược thường được sử dụng là:

• Hybrid

• Sử dụng mẹo (heuristics, còn gọi là các luật viết lại - rewrite rules)

  • Loại đi những plans “xấu nhất”
  • Tránh bỏ xót những plans tốt

  

• Dựa trên ước lượng chi phí

  • Ước lượng chi phí thi hành đối với mỗi plan, từ đó chọn plan có chi phí tốt nhất

Các chiến lược tối ưu hoá

Tối ưu hóa dựa vào các luật viết lại

Nhờ việc loại bỏ các điều kiện/toán tử dư thừa và sử dụng các luật giúp cải thiện hiệu năng truy vấn, chúng ta giảm bớt được số lượng physical plans. Đồng thời ở giai đoạn tiền xử lý, các truy vấn được chuyển sang dạng dễ dàng xử lý nhất. Kết quả là giảm đáng kể thời gian quá trình thi hành truy vấn (tất nhiên kết quả không bị ảnh hưởng). Ta có các luật viết lại truy vấn:

• Luật chuyển đổi logical plan
• Các biến đổi tương đương trong đại số quan hệ
• Đưa các vị từ xuống dưới
• Thực thi các phép chiếu sớm nhất có thể
• Tránh tối đa nhân chéo cross-join
• Sử dụng cây trái nhất
• Chuyển truy vấn lồng -> Joins
• Sử dụng các ràng buộc, chẳng hạn unique

Ví dụ truy vấn Select B,D From R,S Where R.A = “c” ^ R.C=S.C Khởi tạo Logical Plan:

Áp dụng các luật viết lại:

Các phép biến đổi tương đương áp dụng trong quá trình viết lại truy vấn:

Giai đoạn lực chọn plan thi hành, bộ xử lý truy vấn có nhiệm vụ đưa ra quyết định xem biểu thức đại số tương đương nào sẽ mang lại giải thuật hiệu quả nhất, và với mỗi toán tử đại số, sử dụng giải thuật nào để thực thi. Thường có nhiều cách để thi hành một phép toán logic, cần dựa trên dữ liệu thực lưu trên thiết bị lưu trữ của quan hệ để quyết định lựa chọn cách/giải thuật hiệu quả. Bộ xử lý truy vấn cũng có nhiệm vụ đưa ra quyết định việc chuyển dữ liệu xử lý giữa các toán tử được thực hiện thế nào? (ví dụ, thông qua main memory buffers, disk buffers)

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

Hay còn gọi là tối ưu hoá hệ thống (systematic query optimization). Được thực hiện dựa trên phương pháp ước lượng “chi phi” thi hành của kế hoạch thi hành truy vấn. Thông thường kết hợp cùng với tối ưu hoá sử dụng mẹo (heuristic query optimization), để chọn candidate plans tốt nhất. Chú ý tốc độ ước lượng: đảm bảo đủ nhanh để không ảnh hưởng nhiều đến việc thực thi truy vấn từ người dùng. Phương pháp này sử dụng các chiến thuật sau:

• Sử dụng mẹo để thu hẹp không gian plans
  • Đưa các vị từ xuống thấp nhất trong cây (để được thực thi sớm nhất)
  • Hạn chế các plan đòi hỏi cross join
  • Sử dụng các cây trái nhất
• Đánh giá chi phí cho các plan còn lại
  • Chú trọng việc thi hành các vòng lặp, đặc biệt đối với các phép nối, trong một truy vấn.
• Chọn plan có chi phí thấp nhất Các loại chi phí:
• Chi phí truy cập thiết bị lưu trữ thứ cấp
  • searching, reading, writing data blocks.
• Chi phí lưu trữ
  • Storing intermediate files
• Chi phí cho các phép toán cơ bản
  • Searching for, sorting, merging, records, computing field values,…
• Chi phí truyền thông (đối với distributed database)
  • Chi phí truyền két quả truy vấn từ database site tới query site
• Chi phí sử dụng bộ nhớ
  • Lượng memory buffer cần thiết trong quá trình thực thi truy vấn

Các tham số ảnh hưởng tới chi phí:

• Số lượng bộ (trong mỗi quan hệ)
• Số lượng block (trong mỗi quan hệ)
• Số mức mỗi chỉ mục
• Số lượng block cho mức index đầu tiên
• Số lượng giá trị không trùng lặp (distinct values) trên mỗi thuộc tính