Tổng quan về đánh giá truy vấn

Thông tin trong danh mục

Hãy cùng chúng tôi xem xét những nội dung được lưu trong danh mục. Ở mức tối thiểu, chúng ta có thông tin về hệ thống, như kích thước của buffer pool và kích thước trang, và những thông tin về các bảng, chỉ mục, và khung nhìn.

• Với mỗi bảng:
  • Thông tin về tên bảng, tên file, cấu trúc file (ví dụ, heap file) của file lưu trữ bảng.
  • Tên chỉ mục của mỗi chỉ mục trên bảng.
  • Các ràng buộc toàn vẹn (ví dụ, ràng buộc khoá chính, khoá ngoại) trên bảng.
• Với mỗi chỉ mục:
  • Tên chỉ mục và cấu trúc của chỉ mục (ví dụ, B-tree).
  • Các thuộc tính khoá tìm kiếm (search key).
• Với mỗi khung nhìn:
  • Thông tin về tên khung nhìn và định nghĩa của nó.

Thêm nữa, các thống kê về các bảng và các chỉ mục được lưu trữ trong các danh mục hệ thống và được cập nhật định kỳ (không phải bất cứ lúc nào khi bảng được thay đổi).

Những thông tin sau được lưu trữ chung:

• Lực lượng: Số lượng các bộ giá trị Ntuples(R) của mỗi bảng R.
• Kích thước: Số lượng các trang Npages(R) của mỗi bảng R.
• Lực lượng chỉ mục: Số lượng các giá trị khoá khác nhau Nkeys(I) của mỗi chỉ mục.
• Kích thước chỉ mục: Số lượng các trang INPages(I) của mỗi chỉ mục .(Với một chỉ mục B+ tree, chúng ta có INpages là số lượng các trang lá.)
• Chiều cao chỉ mục: Số lượng các mức không phải là lá IHeight(I) của mỗi cây chỉ mục.
• Miền chỉ mục: Giá trị khoá nhỏ nhất Ilow(I) và giá trị khoá lớn nhất Ihigh(I) của mỗi chỉ mục.

Chúng ta giả sử rằng kiến trúc cơ sở dữ liệu trình bày ở Chương 1 được sử dụng. Thêm nữa, chúng ta giả sử rằng mỗi file của các bản ghi được thực thi như là một file riêng rẽ của các trang. Tất nhiên những file khác tổ chức như có thể. Ví dụ, một file trang có thể chứa các trang lưu trữ các bản ghi từ các file bản ghi khác nhau.

Danh mục cũng chứa những thông tin về người dùng, như thông tin về tài khoản người dùng và thông tin xác thực người dùng. (Ví dụ, người dùng joe có thể sửa bảng Reservers, nhưng anh ta chỉ có quyền đọc bảng Sailors).

Ba công nghệ phổ biến

Các thuật toán cho các phép toán quan hệ thường có nhiều điểm chung. Có một vài công nghệ được sử dụng để phát triển các thuật toán cho mỗi phép toán.

• Chỉ mục (Indexing): Nếu một lựa chọn hoặc điều kiện kết nối được xác định, sử dụng chỉ mục để kiểm tra xem các bộ giá trị nào thoả mãn điều kiện.
• Lặp (Iteration): Kiểm tra tất cả các bộ giá trị của bảng đầu vào, từng bộ một. Nếu chúng ta chỉ cần một vài trường trong bảng này và ở đây có một chỉ mục của khoá chứa tất cả các trường này, thì thay vì việc kiểm tra các bộ giá trị, chúng ta có thể quét tất cả các cổng vào chỉ mục.
• Phân vùng (Partitioning): Bằng việc phân vùng các bộ giá trị dựa trên khóa sắp xếp, chúng ta có thể phân tích một phép toán nào đó thành một tập các phép toán mà giá phải trả để thực hiện nó là rẻ hơn.

Sắp xếp và Băm là các công nghệ phân vùng được sử dụng phổ biến nhất.

Chúng ta bàn đến vai trò của chỉ mục trong Phần 2.2. Lặp và phân vùng được trình bày trong Phần 3.

Đường dẫn

Đường dẫn truy cập là một cách để truy cập các bộ giá trị từ một bảng nào đó bao gồm (1) một bảng được quét hoặc (2) một chỉ mục cộng thêm với một điều kiện lựa chọn phù hợp. Tất cả các phép toán quan hệ đều chấp nhận đầu vào là một hoặc nhiều bảng, và các phương pháp truy cập đến các bộ giá trị góp Phần đáng kể vào việc định giá các phép toán.

Xem xét một yêu cầu lựa chọn đơn giản là một kết nối với điều kiện attr op value, trong đó op là một phép toán so sánh <, <, =, ^, >, hoặc >. Những lựa chọn như thế này được gọi là liên kết bình thường (conjunctive normal form (CNF)), và mỗi điều kiện được gọi là một liên kết. Một chỉ mục được xem là phù hợp với một điều kiện lựa chọn nếu chỉ mục này có thể được sử dụng để truy cập đến chỉ những bộ giá trị thoả mãn điều kiện.

Một chỉ mục băm (hash index) phù hợp với một CNF selection nếu có một thành Phần có dạng attribute=value ứng với từng khoá tìm kiếm của chỉ mục (index’s search key) trong câu lệnh lọc.

Một chỉ mục dạng cây phù hợp với một CNF selection nếu có một thành Phần có dạng attribute op value ứng với mỗi thuộc tính trong một tiền tố nào đó của khoá tìm kiếm của chỉ mục. {{a} và {a,b} là những tiền tố của khoá {a,b,c}, nhưng {a,c} và {b,c} thì không.)

Ghi nhớ rằng op có thể là bất kỳ phép so sánh nào.

Những ví dụ sau minh hoạ về đường dẫn truy cập:

Nếu chúng ta có một hash index H trên khoá tìm kiếm là <rname,bid,sid>, chúng ta có thể sử dụng chỉ mục này để truy cập đến chỉ những bộ giá trị trong quan hệ Sailors thoả mãn điều kiện rname='Joe' ∧ bid=5 ∧ sid=3. Chỉ mục này phù hợp với toàn bộ điều kiện rname='Joe' ∧ bid=5 ∧ sid=3. Ngược lại, nếu điều kiện chọn là rname='Joe' ∧ bid=5, hoặc một điều kiện nào đó dựa trên ngày/tháng (date), chỉ mục này sẽ không phù hợp. Tức là, nó không thể được sử dụng để truy vấn đến những bộ giá trị thoả mãn những điều kiện này.

Ngược lại, nếu chỉ mục này là một B+tree, nó sẽ phù hợp với cả rname='Joe'∧ bid=5∧ sid=3 và rname='Joe' ∧ bid=5. Tuy nhiên, nó sẽ không phù hợp với điều kiện bid=5 ∧ sid=3 (vì những bộ giá trị này được sắp xếp chính theo rname).

Nếu chúng ta có một chỉ mục (hash hoặc tree) trên khoá tìm kiếm <bid, sid> và điều kiện lọc là rname='Joe'∧ bid=5 ∧ sid=3, chúng ta có thể sử dụng chỉ mục này để truy cập đến các bộ giá trị thoả mãn điều kiện bid=5 ∧sid=3; Đây là những kết nối chính. Những cụm nhỏ của các bộ giá trị thoả mãn điều kiện kết nối (và nếu chỉ mục là phân cụm) xác định số lượng các trang được truy cập. Sau đó, điều kiện bổ sung về rname được áp dụng lên những bộ giá trị trên để loại đi những bộ giá trị không thoả điều kiện rname= ‘Joe’.

Nếu chúng ta có một chỉ mục nào đó trên khoá tìm kiếm <bid, sid> và chúng ta cũng có một chỉ mục B+tree trên day, điều kiện lọc là day < 8/9/2002 ∧ bid=5 ∧ sid=3 cho chúng ta một lựa chọn. Cả hai chỉ mục đều phù hợp với điều kiện lọc, và chúng ta có thể sử dụng cả hai để truy cập đến các bộ giá trị trong Reserves. Bất cứ chỉ mục nào chúng ta sử dụng, các kết nối trong điều kiện lọc không phù hợp với chỉ mục (ví dụ, bid=5 ∧sid=3 nếu chúng ta sử dụng chỉ mục B+tree trên day) phải được kiểm tra ứng với mỗi bộ giá trị được truy cập.

Phép chọn

Phép chọn là phép toán truy cập các bộ giá trị từ bảng, và cách thực thi của nó đã được bàn đến trong Phần access paths. Để tổng kết, cho một phép chọn có dạng δ _{R.attr op value} (R), nếu ở đây không có chỉ mục nào trên R.attr thì chúng ta phải quét toàn bộ R.

Nếu có một hoặc nhiều chỉ mục trên R phù hợp với phép chọn này, chúng ta có thể sử dụng chỉ mục này để truy cập tới các bộ giá trị thoả mãn, và áp dụng bất kỳ điều kiện chọn còn lại nào để giới hạn tập kết quả. Ví dụ, xem xét một phép chọn có dạng rname < ‘C%’ trên bảng Reserves. Giả sử rằng tên được phân bố đều theo ký tự đầu tiên, để đơn giản, chúng ta ước lượng khoảng 10% bộ giá trị của bảng Reserves sẽ có trong kết quả. Ở đây có tổng số 10,000 bộ giá trị, hoặc 100 trang. Nếu chúng ta có một chỉ mục B+tree trên trường rname của Reserves, chúng ta có thể truy cập tới các bộ giá trị thoả mãn điều kiện với 100 I/Os (cộng thêm một vài I/Os để chuyển từ gốc tới các trang lá phù hợp để bắt đầu việc quét). Tuy nhiên, nếu chỉ mục này là unclustered, chúng ta có thể phải có 10,000 I/Os trong trường hợp xấu nhất, vì mỗi bộ giá trị có thể là nguyên nhân chúng ta phải đọc cả một trang.

Xem Phần 14.1 để có nhiều thông tin hơn về việc thực thi của các phép chọn.

Phép chiếu

Phép chiếu là phép toán lấy ra các cột của bảng. Một yêu cầu phải trả giá đắt của phép toán này là phải đảm bảo rằng không có những bộ giá trị trùng nhau trong kết quả. Ví dụ, nếu chúng ta chỉ muốn lấy ra hai cột sid và bid trong bảng Reserves, chúng ta có thể có những bộ giá trị trùng nhau.

Nếu cho phép có sự trùng lặp (tức là, từ khoá DISTINCT không được chỉ ra trong mệnh đề SELECT), phép chiếu đơn thuần chỉ lấy ra một tập con các trường trong bảng đầu vào. Điều này có thể được thực hiện đơn giản bằng việc lấy ra các trường trong bảng hoặc trong chỉ mục có chứa những trường cần thiết.

Nếu chúng ta muốn loại những bộ giá trị trùng nhau, chúng ta phải sử dụng đến sự chia tách. Giả sử chúng ta muốn lấy {sid, bid} trong Reserves. Chúng ta có thể chia tách như sau (1) quét Reserves để lấy cặp {sid, bid} và (2) sắp xếp các cặp này sử dụng {sid, bid} như là khoá sắp xếp. Sau đó, chúng ta có thể quét những cặp được sắp xếp và dễ dàng loại bỏ những cặp trùng lặp vì những cặp này nằm sát cạnh nhau.

Sắp xếp một lượng lớn dữ liệu trên đĩa là một phép toán rất quan trọng trong các hệ cơ sở dữ liệu, và được trình bày trong Chương 13.

Phép chiếu có thể được tối ưu bằng việc kết hợp việc quét bảng Reserves với việc quét trong bước đầu tiên của sắp xếp. Tương tự, việc quét các cặp đã sắp xếp có thể được kết hợp với bước cuối cùng của việc sắp xếp. Với cách thực hiện tối ưu như vậy, phép chiếu có sự loại bỏ trùng lặp yêu cầu (1) bước đầu tiên là toàn bộ bảng được quét và chỉ cặp {sid, bid} được viết ra, và (2) bước cuối cùng sau khi tất cả các cặp được quét, chỉ duy nhất một bản sao của mỗi cặp được viết ra. Thêm nữa, có thể có một bước trung gian trong đó tất cả các cặp được đọc ra và viết lên đĩa.

Sự hiệu quả của các chỉ mục thích hợp có thể dẫn tới những kế hoạch ít tốn kém hơn khi có yêu cầu sắp xếp đồng thời loại các giá trị trùng lặp. Nếu chúng ta có một chỉ mục trong đó khoá tìm kiếm chứa tất cả các trường có trong phép chiếu, chúng ta có thể sắp xếp dữ liệu ngay trong chỉ mục. Nếu tất cả các thuộc tính có trong phép chiếu xuất hiện trong một tiền tố nào đó của khoá tìm kiếm của mỗi chỉ mục phân cụm, chúng ta có thể làm điều này nhanh hơn; chúng ta đơn giản có thể truy cập toàn bộ dữ liệu sử dụng những chỉ mục này, và sự trùng lặp dễ dang bị loại bỏ vì chúng đứng gần nhau. Những kế hoạch này là những ví dụ bổ sung của các chiến lược đánh giá chỉ-chỉ-số, Phần này sẽ được trình bày trong Phần 8.5.2.

Xem Phần 14.3 để có nhiều thông tin hơn về việc thực thi của các phép chiếu.

Liên kết

Liên kết là phép toán đắt và rất phổ biến. Vì thế, chúng được nghiên cứu một cách rộng rãi, và các hệ thống tiêu biểu hỗ trợ một số thuật toán để thực thi phép toán này.

Xem xét một phép liên kết của Reserves với Sailors, với điều kiện nối là Reserves.sid = Sailors.sid. Một trong số các bảng này, giả sử là Sailors, có một chỉ mục trên cột sid. Chúng ta có thể quét từng bộ giá trị của Reserves, sử dụng chỉ mục này để khảo sát Sailor lấy ra những bộ giá trị phù hợp. Cách tiếp cận này được gọi là liên kết lặp lồng nhau chỉ mục.

Giả sử rằng chúng ta có một hash-based index sử dụng Alternative (2) trên thuộc tính sid của quan hệ Sailors và trung bình nó cần khoảng 1.2 I/Os để truy cập tới trang thích hợp của chỉ mục này. Vì sid là một khoá của Sailors, chúng ta có nhiều nhất một bộ giá trị thỏa mãn điều kiện. Thực tế, sid trong Reserves là một khoá ngoại tham chiếu tới Sailors, và vì thế chúng ta có chính xác một bộ giá trị của Sailor ứng với mỗi bộ giá trị của Reserves. Hãy cùng chúng tôi xem xét giá phải trả của việc quét Reserves và sử dụng chỉ mục này để truy cập tới bộ giá trị của Sailors ứng với mỗi bộ giá trị trong Reserves. Giá phải trả cho việc quét Reserves là 1000. Có 100*1000 bộ giá trị trong Reserves. Ứng với mỗi bộ giá trị này, việc truy cập trang chỉ mục chứa rid phù hợp với bộ giá trị của Sailors phải trả là 1.2 I/Os (trung bình); thêm nữa, chúng ta phải truy cập tới trang lưu Sailors chứa bộ giá trị thoả mãn. Vì thế chúng ta có 100,000*(1+1.2) I/Os để truy cập tới các bộ giá trị Sailors thoả mãn. Tổng cộng là 221,000 I/Os.

Nếu chúng ta không có chỉ mục phù hợp với điều kiện nối trên cả hai bảng, chúng ta không thể sử dụng lặp lồng nhau chỉ mục. Trong trường hợp này, chúng ta có thể sắp xếp cả hai bảng dựa trên cột liên kết, và sau đó quét chúng để tìm ra những bộ giá trị thoả mãn. Cách làm này gọi là liên kết sắp-xếp-trộn. Giả sử rằng chúng ta có thể sắp xếp Reserves trên hai pha, và Sailors cũng trên hai pha, hãy cùng chúng tôi xem xét giá phải trả của liên kết sắp-xếp-trộn. Xem xét liên kết này trên hai bảng Reserves và Sailors. Vì chúng ta đọc và ghi Reserves trên mỗi pha, giá sắp xếp là 2*2*1000=4000 I/Os. Thêm nữa, pha thứ hai của thuật toán liên kết sắp-xếp-trộn yêu cầu một việc quét bổ sung trên cả hai bảng. Vì thế, tổng chi phí phải trả là 4000 + 2000 + 1000 + 500 = 7500 I/Os.

Quan sát thấy rằng chi phí của liên kết sắp-xếp-trộn, cái mà không yêu cầu có sẵn một chỉ mục, thấp hơn giá thành của liên kết lặp lồng nhau chỉ mục. Thêm nữa, kết quả của liên kết sắp-xếp-trộn được sắp xếp trên (các) cột liên kết. Các thuật toán liên kết khác không dựa trên chỉ mục có sẵn và rẻ hơn lặp lồng nhau chỉ mục được biết đến là (lặp lồng nhau trên khối và nối băm; xem thêm trong Chương 14). Dựa vào đây, bạn Trả lời vì sao lại đề cập đến lặp lồng nhau chỉ mục ở đây?

Lặp lồng nhau chỉ mục có một tính chất rất tốt đó là tăng trưởng. Chi phí của liên kết trong ví dụ tăng trưởng theo số lượng bộ giá trị của Reserves mà chúng ta xử lý. Vì thế, nếu một số điều kiện lựa chọn trong truy vấn cho phép chúng ta chỉ cần quan tâm đến một tập con các bộ giá trị trong Reserves, chúng ta có thể tránh được việc phải thực hiện liên kết toàn bộ thực thể. Ví dụ, giả sử rằng chúng ta chỉ muốn thực liên kết cho các bộ giá trị có boat là 101, và ở đó sẽ chỉ có một vài giá trị của Reserves thỏa mãn. Với mỗi bộ giá trị này, chhúng ta tìm kiếm trong Sailors. Nếu chúng ta sử dụng liên kết sắp-xếp-trộn thì chúng ta phải quét toàn bộ bảng Sailors ít nhất một lần, và giá thành của riêng bước này đã lớn hơn toàn bộ giá thành của liên kết lặp lồng nhau chỉ mục.

Quan sát thấy rằng việc lựa chọn liên kết lặp lồng nhau chỉ mục dựa trên việc xem xét bản thân truy vấn, bao gồm các điều kiện chọn, không chỉ đơn thuần là bản thân phép toán liên kết. Điều này dẫn chúng ta đến chủ đề tiếp theo là tối ưu hoá truy vấn, mục đích của nó chính là tìm ra được kế hoạch tốt cho toàn bộ truy vấn.

Xem Phần 14.4 để có thêm thông tin.

Những phép toán khác

Một truy vấn SQL có thể chứa mệnh đề group-by và các hàm nhóm. Các kết quả truy vấn khác nhau có thể được kết hợp bằng phép hợp, phép giao, phép trừ.

Các phép toán tập hợp như phép hợp và phép giao phải trả giá đắt cho việc loại bỏ những giá trị trùng nhau, giống như phép chiếu. Cách tiếp cận sử dụng để thực thi phép chiếu có thể dễ dàng tương thích với các phép toán này. Xem Phần 14.5 để có thêm thông tin.

Group-by được thực hiện thông qua việc sắp xếp, các bảng đầu vào có một chỉ mục dạng cây với một khóa tìm kiếm phù hợp với các thuộc tính được nhóm. Trong trường hợp này, chúng ta có thể truy cập tới các bộ giá trị sử dụng một chỉ mục theo thứ tự phù hợp mà không cần sử dụng bước sắp xếp. Các phép toán nhóm được thực thi sử dụng các biến đếm phụ lưu trong bộ nhớ chính như là các bộ giá trị được truy cập. Xem chi tiết trong Phần 14.6.

Giới thiệu về tối ưu hoá truy vấn

Tối ưu hoá truy vấn là một trong những công việc quan trọng nhất của một RDBMS (Relational DBMS). Một trong những ưu điểm của các ngôn ngữ truy vấn quan hệ là nó có nhiều cách khác nhau để thực hiện một truy vấn, vì thế hệ thống phải đánh giá được truy vấn. Một truy vấn có thể được viết bằng nhiều cách khác nhau, và giá phải trả cho từng cách là khác nhau. Chúng ta không thể hy vọng luôn tìm được kế hoạch tốt nhất cho một truy vấn nào đó, nhưng chúng ta hy vọng tìm ra một kế hoạch đủ tốt.

Nhiều thông tin hơn về tối ưu hoá truy vấn và các lớp (layer) thực thi trong kiến trúc DBMS được chỉ ra trong Hình 2. Các truy vấn được biên dịch, sau đó được gửi tới bộ tối ưu hoá truy vấn, nơi có trách nhiệm chỉ ra một cách thực thi có hiệu quả. Bộ tối ưu hoá đưa ra các kế hoạch khác nhau và lựa chọn một kế hoạch có giá ít tốn kém nhất.

Các kế hoạch được xem xét bởi một bộ tối ưu hoá truy vấn quan hệ có thể được hiểu bằng việc nhận thức rằng một truy vấn về bản chất giống như một biểu thức đại số σ - π - , và các phép toán còn lại được thực hiện trên kết quả của biểu thức σ - π - .

Biên dịch, Tối ưu và Thực hiện truy vấn

Bộ tối ưu thương mại hóa: Các bộ tối ưu hiện tại của các RDBMS chứa các gói Phần mềm cực kỳ phức tạp, nhiều chi tiết tỉ mỉ, và họ nói rằng phải mất 40 tới 50 năm công (man-years) để nỗ lực phát triển.

Việc tối ưu hoá giống như một biểu thức đại số quan hệ bao gồm hai bước cơ bản:

• Liệt kê các kế hoạch cho biểu thức này. Điển Hình , bộ tối ưu xem xét một tập con nào đó của tất cả các kế hoạch có thể vì số lượng các kế hoạch có thể là rất lớn.
• Định giá cho mỗi kế hoạch đã liệt kê và lựa chọn một kế hoạch có giá thấp nhất.

Các kế hoạch đánh giá truy vấn

Một kế hoạch đánh giá truy vấn (hay gọi đơn giản là kế hoạch) được biểu diễn dưới dạng Hình cây các phép đại số quan hệ, cùng với chú thích bổ sung ở mỗi nút chỉ ra các phương thức truy cập đối với mỗi bảng và phương thức thực hiện sử dụng với mỗi phép toán quan hệ.

Xem xét truy vấn SQL sau:

SELECT S.sname
    FROM Reserves R, Sailors S
    WHERE R.sid = S.sid AND R.bid = 100 AND S.rating > 5
    

Truy vấn này có thể được biểu diễn trong đại số quan hệ như sau:

π sname(σ bid=100 ∧ rating>5(Reserves sid=sid Sailors))

Biểu thức này được chỉ ra dưới dạng Hình cây trong Hình 3. Biểu thức đại số này được sử dụng là một thành Phần để đánh giá truy vấn- đầu tiên chúng ta thực hiện kết nối tự nhiên giữa Reserves và Sailors, sau đó thực hiện phép chọn và cuối cùng là thực hiện phép chiếu lấy ra trường sname.

Truy vấn được biểu diễn bằng đại số quan hệ dưới dạng Hình cây

Kế hoạch đánh giá cho một truy vấn ví dụ

Để có được một kế hoạch đánh giá đầy đủ, chúng ta phải quyết định việc thực hiện trên mỗi phép toán đại số quan hệ liên quan. Ví dụ, chúng ta có thể sử dụng liên kết lặp lồng nhau đơn giản trong đó Reserves là bảng phía ngoài và áp dụng phép chọn và phép chiếu tới mỗi bộ giá trị trong kết quả của phép nối này; kết quả của phép nối trước khi thực hiện chọn và chiếu không bao giờ được lưu trữ lại toàn bộ. Kế hoạch đánh giá truy vấn này được chỉ ra trong Hình 4.

Trong Hình vẽ kế hoạch đánh giá truy vấn, chúng ta thống nhất rằng bảng phía ngoài là một nút con phía trái của phép toán liên kết. Chúng ta sẽ sử dụng thống nhất nguyên tắc này từ đây trở về sau.

Truy vấn đa-toán-tử: Truyền liên tục

Khi một truy vấn sử dụng nhiều toán tử, kết quả của toán tử này được truyền liên tục (pipeline) tới toán tử khác mà không tạo ra một bảng phụ để lưu trữ kết quả tạm thời. Kế hoạch trong Hình 4 cho thấy đầu ra của phép nối giữa Sailors và Reserves được đưa vào phép chọn và phép chiếu theo sau.

Thực hiện liên hoàn như vậy làm tiết kiệm giá thành của việc viết ra kết quả trung gian và đọc trở lại nó, giá thành tiết kiệm được này thực tế rất đáng kể. Nếu đầu ra của một phép toán được lưu trữ trong bảng phụ phục vụ quá trình xử lý phép toán tiếp theo, chúng ta nói rằng các bộ giá trị này được hiện thực hoá.

Giá thành của thực hiện theo kiểu truyền liên tục thấp hơn so với kiểu hiện thực hoá và được thực hiện bất cứ khi nào nếu thuật toán của toán tử này cho phép.

Có rất nhiều cơ hội dành cho kiểu thực hiện truyền liên tục đối với những kế hoạch truy vấn điển Hình , thậm chí những kế hoạch đơn giản chỉ bao gồm các phép chọn. Xem xét một truy vấn chọn trong đó chỉ một Phần của điều kiện chọn phù hợp với một chỉ mục nào đó. Chúng ta giả sử truy vấn có hai điều kiện chọn: Điều kiện đầu tiên là điều kiện chính, và thứ hai là điều kiện còn lại. Chúng ta có thể đánh giá truy vấn này bằng việc áp dụng điều kiện chính và viết kết quả này lên một bảng tạm, sau đó áp dụng điều kiện còn lại lên bảng tạm này. Ngược lại, sử dụng việc truyền liên tục sẽ áp dụng điều kiện thứ hai lên mỗi bộ giá trị của tập kết qủa của điều kiện thứ nhất và thêm những bộ giá trị thoả mãn vào kết quả cuối cùng. Khi bảng đầu vào chịu tác động của toán tử một toán hạng (ví dụ, phép chọn hoặc phép chiếu) và thực hiện truyền liên tục lên nó, chúng ta gọi phép toán này được thực hiện theo kiểu on-the-fly.

Sau đây là một ví dụ thường gặp, xem xét một kết nối có dạng (A B) C, Hình 5 chỉ ra dạng cây của kết nối này.

Cây truy vấn minh hoạ việc thực hiện truyền liên tục

Cả hai liên kết có thể được thực hiện bằng việc sử dụng một số phiên bản của các phép lặp lồng nhau liên kết. Việc thực hiện được bắt đầu từ nút gốc, và nút liên kết giữa A và B sẽ đưa ra các bộ giá trị kết quả của phép nối này khi nút cha yêu cầu. Khi nút gốc có một trang nào đó chứa các bộ giá trị từ phía nút con bên trái của nó (bảng phía ngoài), nó sẽ thực hiện nối với quan hệ phía trong và lấy ra những bộ giá trị phù hợp (sử dụng chỉ mục hoặc quét); trang hiện tại chứa các bộ giá trị của nút con bên trái sau đó sẽ bị loại bỏ. Việc này được thực hiện lặp đi lặp lại với các trang tiếp theo. Thực hiện theo kiểu truyền liên tục có hiệu quả lớn, nó không viết kết quả của phép nối trung gian ra file tạm bởi vì kết quả được đưa ra, xử lý và loại bỏ cùng đồng thời.

Giao diện lập trình con chạy

Kế hoạch đánh giá truy vấn được biểu diễn bằng một cây các phép toán quan hệ, các phép toán này được thực hiện theo thứ tự. Mối phép toán có một hoặc nhiều đầu vào và một đầu ra, đó là những nút trong cây.

Để đơn giản cho việc phối hợp thực hiện một kế hoạch, các phép toán quan hệ được biểu diễn trong các nút của cây thường hỗ trợ một giao diện lập trình con chạy thống nhất, ẩn đi những thực hiện chi tiết bên trong mỗi phép toán. Giao diện lập trình con chạy bao gồm các hàm open, get_next, và close. Hàm open khởi động trạng thái của con chạy bằng việc định vị các bộ đệm cho các đầu vào và đầu ra của nó. Phần mã chương trình của chức năng get_next được gọi là hàm get_next trên mỗi nút đầu vào để xử lý các bộ giá trị đầu vào. Các bộ giá trị kết quả của quá trình xử lý được đặt trong bộ đệm đầu ra của mỗi phép toán, và trạng thái của mỗi iterator được cập nhật để biết có bao nhiêu đầu vào đã được xử lý. Khi tất cả các bộ giá trị đầu ra đã được xử lý thông qua việc gọi lặp đi lặp lại get_next, hàm close được gọi để đóng con chạy.

Giao diện lập trình con chạy hỗ trợ việc xử lý truyền liên tục một cách tự nhiên; việc truyền liên tục hay hiện thực hoá các bộ giá trị đầu vào được gói trong đoạn mã chương trình đặc trưng của phép toán để xử lý các bộ giá trị đầu vào. Nếu thuật toán này thực thi mỗi phép toán cho phép các bộ giá trị đầu vào được xử lý hoàn toàn sau khi chúng được nhận, những bộ giá trị đầu vào không phải là hiện thực hoá và việc đánh giá chúng là truyền liên tục. Nếu thuật toán này kiểm tra cùng các giá trị đầu vào một vài lần, chúng là hiện thực hoá.

Giống như những chi tiết của việc thực thi các phép toán, quyết định này được ẩn đi bởi các giao diện lập trình con chạy của mỗi phép toán. Giao diện lập trình con chạy cũng được sử dụng để đóng gói các phương thức truy cập như các chỉ mục B+trees và hash-based. Nhìn bề ngoài, các phương thức truy cập có thể được nhìn thấy như là các phép toán xử lý một chuỗi các bộ giá trị đầu vào. Trong trường hợp này, hàm open có thể được sử dụng để gán những điều kiện lựa chọn đường dẫn truy cập.

Các phép chọn được đẩy xuống

Phép nối là phép toán quan hệ có giá thành đắt, và một ý kiến hay ở đây là giảm càng nhiều càng tốt kích thước của các bảng tham gia kết nối. Một cách tiếp cận sớm với các phép chọn là: nếu có một phép chọn nào đó xuất hiện sau một phép nối thì tốt nhất là cố “đẩy” phép chọn lên đằng trước phép nối. Ví dụ, phép chọn với bid=100 chỉ bao gồm các thuộc tính của Reserves và có thể áp dụng trên Reserves trước khi thực hiện nối. Tương tự, phép chọn với rating>5 chỉ gồm các thuộc tính của Sailors và có thể áp dụng trên Sailor trước phép nối. Hãy cùng chúng tôi giả sử rằng, các phép chọn được thực thi đơn giản sử dụng việc quét file, kết quả của mỗi phép chọn được viết lên một bảng tạm trên đĩa, và vì thế các bảng tạm này được nối sử dụng một phép kết nối sắp-xếp-trộn. Kết quả của kế hoạch đánh giá truy vấn được chỉ ra trong Hình 6.

Hãy cùng chúng tôi giả sử rằng ở đây có năm trang đệm đang sẵn sàng và chúng ta cần ước lượng giá thành của kế hoạch này. (Trên thực tế, có nhiều trang đệm có thể đang sẵn sàng. Chúng ta chọn số lượng nhỏ này đơn giản chỉ để minh hoạ ví dụ này). Giá thành của việc áp dụng điều kiện chọn bid=100 cho Reserves là chi phí của việc quét Reserves (1000 trang) cộng với chi phí để viết kết quả lên một bảng tạm, gọi là T1.

Phương án 2: Kế hoạch đánh giá truy vấn

(Ghi nhớ rằng giá của việc viết kết quả tạm thời lên bảng phụ không thể được bỏ qua- chúng ta chỉ có thể bỏ qua giá của viết ra kết quả cuối cùng của truy vấn vì nó là Phần chung của mọi kế hoạch). Để ước lượng kích thước của t1, chúng ta yêu cầu bổ sung thêm thông tin, nếu chúng ta giả sử rằng số lượng người phục vụ (thuỷ thủ) trên một tàu nào đó là 1, chỉ có một bộ giá trị xuất hiện trong kết quả. Thêm nữa, nếu chúng ta biết rằng có 100 tàu, chúng ta có thể giả sử rằng số lượng người phục vụ dàn ra trên tất cả các tàu và ước lượng số trang của T1 là 10. Cụ thể, giả sử rằng số lượng các trang trong T1 thực sự là 10.

Chi phí của việc thực hiện truy vấn rating>5 trên Sailors là chi phí của việc quét bảng Sailors (500 trang) cộng với chi phí của việc viết kết quả ra một bảng tạm, giả sử T2. Nếu chúng ta giả sử rằng ratings được phân bố trong khoảng từ 1 đến 10, chúng ta có thể ước lượng được kích thước của T2 là 250 trang.

Để làm một kết nối sắp-xếp-trộn giữa T1 và T2, hãy cùng chúng tôi giả sử rằng hai bảng này đã được sắp xếp và sau đó đã được trộn. Vì năm trang bộ đệm đã ở chế độ sẵn sàng, chúng ta có thể sắp xếp T1 (có 10 trang) trong hai pha. Hai pha này thực hiện 5 trang mỗi lần và kết quả xuất ra pha thứ nhất và sau đó thực hiện trộn trong pha thứ hai. Trong mỗi pha, chúng ta đọc và viết 10 trangs; ví thế, giá của sắp xếp T1 là 2*2*10=40 trang I/Os. Chúng ta cần bốn pha để sắp xếp T2 nơi có 250 trang. Giá là 2*4*250=2000 trang I/Os. Để trộn các phiên bản đã được sắp của T1 và T2, chúng ta cần quét những bảng này, và giá của bước này là 10+250=260. Phép chiếu cuối cùng được thực hiện theo kiểu on-the-fly, và như đã nói ở trên chúng ta bỏ qua giá của việc viết ra kết quả cuối cùng.

Tổng chi phí của kế hoạch chỉ ra trong Hình 6 là tổng chi phí của các phép chọn (1000+10+500+250=1760) và chi phí của phép nối là (40+2000+260 = 2300), do đó có 4060 trang I/Os.

Phép nối sắp-xếp-trộn là một trong số một vài các phương pháp nối. Chúng ta có thể giảm giá của kế hoạch này bằng việc chọn một phương pháp nối khác. Như một lựa chọn, giả sử rằng chúng ta sử dụng kết nối lặp lồng nhau trên khối thay vì kết nối sắp-xếp-trộn. Sử dụng T1 như là bảng phía ngoài, với mỗi khối của T1 là ba-trang, chúng ta quét toàn bộ T2; do đó chúng ta quét T2 bốn lần. Vì thế, giá của phép nối là giá của việc quét T1 (10) cộng với giá của việc quét T2 (4*250=1000). Giá của kế hoạch này bây giờ là 1760+1010=2770 trang I/Os.

Một cải tiến tiếp theo là đẩy phép chiếu xuống, giống như chúng ta đã đẩy các phép chọn xuống dưới phép nối. Quan sát thấy rằng chỉ có thuộc tính sid trong T1 và thuộc tính sid và sname trong T2 được yêu cầu. Vì chúng ta quét Reserves và Sailors để thực hiện các phép chọn, nên chúng ta có thể loại đi những cột không mong muốn. Phép chiếu on-the-fly này giảm đi kích thước của bảng tạm T1 và T2. Việc giảm kích thước của T1 là đáng kể vì chỉ có một trường kiểu integer cần giữ lại. Thực tế là bây giờ T1 đủ trong ba trang đệm, và chúng ta có thể thực hiện một kết nối lặp lồng nhau trên khối cùng với việc quét bảng T2. Chi phí của bước kết nối giảm xuống dưới 250 trang I/Os, và tổng chi phí của kế hoạch này giảm xuống khoảng 2000 I/Os.

Sử dụng chỉ mục

Một kế hoạch đánh giá truy vấn sử dụng các chỉ mục

Nếu các chỉ mục đã được thiết lập và đang sẵn sàng trên các bảng Reserves và Sailors, thì các kế hoạch đánh giá truy vấn sẽ tốt hơn nữa. Ví dụ, giả sử rằng chúng ta có chỉ mục băm tĩnh phân cụm trên trường bid của Reserves và chỉ mục băm khác trên trường sid của Sailors. Chúng ta có thể sử dụng kế hoạch đánh giá truy vấn trong Hình 7.

Phép chọn bid=100 được thực hiện trên Reserves bằng việc sử dụng một chỉ mục băm trên bid để truy cập chỉ những bộ giá trị phù hợp. Như ví dụ trước, nếu chúng ta biết rằng có 100 tàu và người phục vụ được dải ra trên tất cả các tàu, chúng ta có thể ước lượng được số lượng các bộ giá trị được chọn là 100,000/100=1000. Vì chỉ mục trên bid là phân cụm, nên có 1000 bộ giá trị xuất hiện liên tiếp trong cùng một bộ đệm; vì thế giá sẽ là 10 trang I/Os.

Với mỗi bộ giá trị được chọn, chúng ta truy cập đến các bộ giá trị thoả mãn của Sailors sử dụng một chỉ mục băm trên trường sid; các bộ giá trị trong Reserves được lựa chọn không được hiện thực hoá và kết nối này được thực hiện theo kiểu truyền liên tục. Với mỗi bộ giá trị trong kết qủa của phép kết nối, chúng ta thực hiện việc lọc với rating>5 và phép chiếu lấy ra sname theo kiểu on-the-fly. Có một vài điểm quan trọng cần ghi nhớ ở đây:

1. Vì kết quả của phép chọn trên Reserves là không hiện thực hoá, nên việc tối ưu hoá phép chiếu đối với các trường cần ở bước sau là không cần thiết (và không được sử dụng trong kế hoạch chỉ ra trong Hình 7).

2. Trường nối sid là khoá của Sailors. Vì thế, có nhiều nhất một bộ giá trị trong Sailors tương ứng với một bộ giá trị nào đó của Reserves. Chi phí của việc truy cập bộ giá trị tương ứng này phụ thuộc vào việc thư mục chỉ mục băm trên cột sid của Sailors có đặt vừa vào bộ nhớ và trên các trang tràn (nếu có). Tuy nhiên, chi phí ở đây không phụ thuộc vào việc chỉ mục chỉ mục này có phải là phân cụm không bởi vì có nhiều nhất một bộ giá trị của Sailors và những yêu cầu đối với các bộ giá trị của Sailors được thực hiện theo trật tự ngẫu nhiên của sid (bởi vì các bộ giá trị của Reserves được truy cập theo bid và vì thế được xem xét theo trật tự ngẫu nhiên của sid). Với mỗi chỉ mục băm, 1.2 trang I/Os (trung bình) là một ước lượng tốt về chi phí cho một truy cập dữ liệu. Giả sử rằng chỉ mục băm trên sid của Sailors được sử dụng trong Alternative(1) cho các cổng vào dữ liệu, 1.2 I/Os là giá để truy cập một bộ giá trị của Sailors phù hợp (và nếu một trong hai Alternative khác được sử dụng, thì giá sẽ là 2.2 I/Os).

3. Chúng ta đã lựa chọn không đẩy phép chọn rating>b lên trên phép nối, có một lý do quan trọng cho quyết định này. Nếu chúng ta thực hiện phép chọn trước phép nối, phép chọn này sẽ bao gồm cả việc quét Sailors, giả sử rằng không có chỉ mục nào đang sẵn sàng trên trường rating của Sailors. Thêm nữa, dù có hay không có một chỉ mục như vậy đang sẵn sàng, thì kết quả của phép chọn này cũng không có chỉ mục trên trường sid (trừ khi chúng ta xây dựng một chỉ mục độc lập như vậy để phục vụ cho những kết nối đằng sau). Việc đẩy các phép chọn lên trước các phép nối là một ý tưởng rất tốt, nhưng điều này không phải lúc nào cũng đúng. Điển Hình như trong ví dụ này, việc có các chỉ mục hữu ích đang tồn tại là lý do phép chọn không nên được đẩy lên. (Trong những trường hợp khác, các phép chọn nên được đẩy lên trên phép nối).

Giả sử chúng ta cần ước lượng chi phí của kế hoạch chỉ ra trong Hình 7. Việc chọn các bộ giá trị của Reserves có giá là 10 I/Os, như chúng tôi đã trình bày phía trên. Có 1000 bộ giá trị như vậy, và với mỗi bộ, chi phí của việc tìm bộ giá trị tương ứng trong Sailors trung bình là 1.2 I/Os. Chi phí của bước này (phép nối) vì thế là 1200 I/Os. Tất cả các phép chọn còn lại và các phép chiếu được thực hiện theo kiểu on-the-fly. Tổng chi phí của kế hoạch này là 1210 I/Os.

Như đã lưu ý ở phía trên, kế hoạch này không tận dụng được chỉ mục phân cụm của Sailors. Nó có thể được tinh chỉnh thêm nếu chỉ mục trên trường sid của Sailors là phân cụm. Giả sử chúng ta hiện thực hoá các kết quả của phép chọn với bid=100 trên Reserves và sắp xếp các kết quả này trên bảng tạm. Bảng này sẽ chứa 10 trang. Việc chọn các bộ giá trị có giá là 10 trang I/Os (như trước), việc viết kết quả ra bảng tạm có chi phí là 10 I/Os nữa, và với 5 trang đệm, việc sắp xếp trên bảng tạm này sẽ mất 2*2*10=40 I/Os. (Chi phí này sẽ giảm nếu chúng ta đẩy phép chiếu lấy sid lên trên). Cột sid của các bộ giá trị trong Reserves chỉ yêu cầu 3 trang và có thể được sắp xếp trong bộ nhớ với năm trang đệm). Bây giờ, các bộ giá trị Reserves được chọn có thể được truy cập theo thứ tự của sid.

Nếu một thuỷ thủ nào đó phục vụ trên một tàu nhiều lần, tất cả các bộ giá trị của Reserves tương ứng được truy cập một cách liên tiếp và tất cả chúng có thể được tìm thấy trong một buffer pool. Kế hoạch cải tiến này cũng chứng minh một điều rằng, việc thực hiện theo kiểu truyền liên tục không phải lúc nào cũng là một chiến lược tốt nhất.

Việc kết hợp việc đẩy các phép chọn lên và sử dụng các chỉ mục trong kế hoạch này rất hiệu quả. Nếu các bộ giá trị được chọn trong bảng phía ngoài nối với một bộ giá trị duy nhất bên trong, thì phép nối này trở nên rất tầm thường, và những ích lợi của việc thực hiện kế hoạch ngờ nghệch trong Hình 6 thậm chí lại gây ấn