Vì sao phải tối ưu hóa truy xuất khối đĩa

Một người đàn ông trở về nhà sau khi đi vòng quanh thế giới trong mười một năm. Ngày hôm sau, khi anh ấy nói với vợ rằng anh ấy đang đi đến cửa hàng ở góc phố, cô ấy hỏi anh ấy, "Anh đi đường ngắn hay đường dài?"

Các truy vấn có thể được thực hiện theo nhiều cách khác nhau. Tất cả các đường dẫn đều dẫn đến cùng một kết quả truy vấn. Trình tối ưu hóa truy vấn đánh giá các khả năng và chọn kế hoạch hiệu quả. Hiệu quả được đo bằng độ trễ và thông lượng, tùy thuộc vào khối lượng công việc. Chi phí sử dụng Bộ nhớ, CPU, đĩa được thêm vào chi phí của gói trong trình tối ưu hóa dựa trên chi phí.

Bây giờ, hầu hết các cơ sở dữ liệu NoSQL đều có hỗ trợ ngôn ngữ truy vấn giống SQL . Vì vậy, một trình tối ưu hóa tốt là bắt buộc. Khi bạn không có một trình tối ưu hóa tốt, các nhà phát triển phải sống với những hạn chế về tính năng và DBA phải sống chung với các vấn đề về hiệu suất.

Trình tối ưu hóa Cơ sở dữ liệu

Trình tối ưu hóa truy vấn chọn một chỉ mục tối ưu và các đường dẫn truy cập để thực hiện truy vấn. Ở mức rất cao, trình tối ưu hóa SQL quyết định những điều sau trước khi tạo cây thực thi:

1. Truy vấn được viết lại dựa trên heuristics, chi phí hoặc cả hai.
2. Lựa chọn chỉ mục.
   • Chọn [các] chỉ mục tối ưu cho mỗi bảng [không gian khóa trong Couchbase N1QL, bộ sưu tập trong trường hợp MongoDB]
   • Tùy thuộc vào chỉ mục được chọn, hãy chọn các vị từ để đẩy xuống, xem truy vấn có được bao phủ hay không, quyết định chiến lược sắp xếp và phân trang.
3. Tham gia sắp xếp lại
4. Tham gia loại

Hãy xem xét trường hợp hạn chế MongoDB. "Một bộ sưu tập có thể có nhiều nhất một chỉ mục văn bản." //docs.mongodb.com/manual/core/index-text/#restrictions Nó ghi lại một số hạn chế khác cùng với điều này. Đối với bài viết này, giải thích một hạn chế này là đủ.

Tại sao bạn nên quan tâm đến hạn chế này?

1. MongoDB và các cơ sở dữ liệu NoSQL khác khuyến khích bạn không chuẩn hóa [tổng hợp] lược đồ của mình để bạn tạo một tài liệu lớn đại diện cho một đối tượng: khách hàng, đối tác, v.v. để phần lớn các hoạt động của bạn diễn ra trên một tài liệu [JSON]. Vì vậy, một tài liệu khách hàng duy nhất có thể chứa thông tin khách hàng, đơn đặt hàng của khách hàng, thông tin giao hàng của khách hàng và thông tin thanh toán của khách hàng. Có một chỉ mục tìm kiếm duy nhất có nghĩa là bạn cần tạo một chỉ mục RẤT LỚN duy nhất kết hợp tất cả các trường bạn muốn tìm kiếm. Đây là vấn đề: khi bạn tìm kiếm địa chỉ khách hàng, bạn không muốn thấy địa chỉ giao hàng. Khi bạn tìm kiếm ID đơn đặt hàng giao hàng, bạn sẽ không muốn thấy ID đơn đặt hàng bị trả lại.
2. Bạn có thể tạo nhiều chỉ mục trên vô hướng trong MongoDB. Tại sao hạn chế về chỉ mục văn bản?

Tại sao chỉ mục văn bản MongoDB bị giới hạn ở một chỉ mục cho mỗi bộ sưu tập?

• Nó có phải là số của các chỉ mục văn bản không? Các chỉ mục tìm kiếm thường được xây dựng với cấu trúc dữ liệu cây ngược , nhưng MongoDB đã chọn xây dựng nó với chỉ mục B-Tree. Đây không phải là vấn đề.
• Nó có phải là kích thước của các chỉ mục văn bản không? Chỉ mục văn bản tạo ra một loạt các mã thông báo trên văn bản và lập chỉ mục chúng. Vì vậy, nó là một chỉ mục mảng. Kích thước của nó có thể tăng theo cấp số nhân khi bạn sử dụng chỉ mục mảng. Kích thước của chỉ mục tăng tuyến tính với số lượng chỉ mục từ chứ không phải số lượng tài liệu. Chúng có thể gây ra vấn đề.
• Nó có vấn đề với trình tối ưu hóa không? Khi bạn có nhiều chỉ mục, trình tối ưu hóa sẽ phải chọn chỉ mục phù hợp cho truy vấn. Nếu bạn giới hạn ở một chỉ mục văn bản, lựa chọn rất dễ dàng. Đây là dấu hiệu của một vấn đề lớn hơn trong trình tối ưu hóa MongoDB; nó đưa ra các quyết định đặc biệt dẫn đến các hạn chế như thế này.

Ngôn ngữ truy vấn của MongoDB rất đơn giản ngay cả khi nó đang cố gắng bắt chước các hoạt động SQL . Hãy xem cách trình tối ưu hóa của MongoDB xử lý những điều này.

1. Viết lại truy vấn: Không được hỗ trợ . Các truy vấn của MongoDB rất đơn giản trong các phương thức find [], save [], remove [] và update []. Quy trình tổng hợp mang tính thủ tục và dài dòng. Mặc dù về mặt lý thuyết có thể viết lại, nhưng không có gì trong tài liệu hoặc kế hoạch để chỉ ra bất kỳ truy vấn nào được viết lại.
2. Lựa chọn chỉ mục: Được hỗ trợ . Trình tối ưu hóa của MongoDB cố gắng chọn một chỉ mục phù hợp cho từng phần của truy vấn và chỉ mục có thể / nên được sử dụng. Thêm về điều này bên dưới.
3. Tham gia sắp xếp lại: Không được hỗ trợ . Tra cứu $ của MongoDB là một phần của khung tổng hợp phức tạp, nơi truy vấn được viết giống như đường ống Unix, một cách tiếp cận thủ tục.
4. Lựa chọn kiểu tham gia: Không được hỗ trợ vì chỉ có một kiểu tham gia trong MongoDB. MongoDB có hỗ trợ kết nối bên ngoài bên trái bị hạn chế thông qua toán tử $ lookup - các mảng không được hỗ trợ trong điều kiện tham gia. Nếu bạn sử dụng $ lookup, trình tối ưu hóa sẽ tự động sử dụng thuật toán kết hợp mặc định. Không có đề cập đến loại kết hợp được thực hiện.

Về cơ bản, trình tối ưu hóa truy vấn của MongoDB chỉ thực hiện lựa chọn chỉ mục trước khi tạo kế hoạch thực thi, nhưng nó dường như chọn các chỉ mục theo kiểu kỳ quặc - không theo quy tắc không theo thống kê.

1. Chọn một chỉ mục ngẫu nhiên trên một hoặc nhiều chỉ mục đủ điều kiện.
2. Sử dụng kế hoạch đó nếu một truy vấn tiếp theo phù hợp với các vị từ truy vấn, ngay cả khi các hằng số, vùng chọn và hệ số khác nhau.
3. Sau đó, trong thời gian chạy, nếu quá trình quét chỉ mục trả về hơn 100 khóa [!], Hãy chạy từng kế hoạch thay thế để xem kế hoạch nào trả về khóa trước. Tại một số thời điểm, nó hủy bỏ quá trình thực hiện song song và chọn một trong số chúng. Nó cũng thay thế kế hoạch trong bộ nhớ cache kế hoạch của nó.

Collection t1, with 3000 documenbts. Create the following indexes: Appendix 1 for the definition: MongoDB Enterprise > db.t1.createIndex[{x:1}] MongoDB Enterprise > db.t1.createIndex[{y:1}] MongoDB Enterprise > db.t1.createIndex[{x:1, y:1}] MongoDB Enterprise > db.t1.createIndex[{y:1, x:1}]

Đây là một tập hợp duy nhất với 4 chỉ mục trên [x], [y], [x, y] và [y, x]. Bây giờ, hãy xem cái này:

MongoDB Enterprise > db.t1.find[{x:{$gt:0}, y:99}].explain[] { "queryPlanner" : { "plannerVersion" : 1, "namespace" : "test.t1", "indexFilterSet" : false, "parsedQuery" : { "$and" : [ { "y" : { "$eq" : 99 } }, { "x" : { "$gt" : 0 } } ] }, "winningPlan" : { "stage" : "FETCH", "filter" : { "x" : { "$gt" : 0 } }, "inputStage" : { "stage" : "IXSCAN", "keyPattern" : { "y" : 1 }, "indexName" : "y_1", "isMultiKey" : false, "multiKeyPaths" : { "y" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "y" : [ "[99.0, 99.0]" ] } } },

Ngay cả trên cấu trúc tài liệu đơn giản này, MongoDB chọn chỉ mục trên [y] mặc dù ở đó truy vấn có các bộ lọc trên x và y: [{x: {$ gt: 0}, y: 99}] .

Để quản lý tất cả những điều không chắc chắn này và các vấn đề về hiệu suất mà nó sẽ dẫn đến, MongoDB cung cấp một số API để quản lý bộ nhớ cache của kế hoạch truy vấn : xóa mục nhập bộ nhớ cache cụ thể và xóa toàn bộ bộ nhớ cache của gói. Thay vì phát triển ứng dụng, các nhà phát triển MongoDB và DBA cần quản lý bộ nhớ cache của kế hoạch. Các nhà phát triển và DBA không cần quản lý bộ nhớ cache của kế hoạch trong các cơ sở dữ liệu doanh nghiệp khác.

Quay lại câu hỏi ban đầu: Tại sao bạn không thể tạo nhiều chỉ mục văn bản trên MongoDB?

Việc tạo nhiều chỉ mục sẽ không thành vấn đề nếu họ chỉ đơn giản là cho phép. Các vấn đề thực sự là khi bạn đưa ra một vị văn bản trong truy vấn của bạn, MongoDB ưu không thể chọn chỉ số đúng. Nó không thể xác thực các chỉ mục văn bản này so với vị ngữ văn bản. Trình tối ưu hóa MongoDB không tuân theo logic tự nhiên hoặc khuôn khổ logic. Do đó hạn chế.

Và, nó thậm chí có thể làm tổn thương bạn!

@philipp_hauer

Couchbase N1QL đã thêm chỉ mục văn bản vào N1QL cho bản phát hành sắp tới. Xem thông tin chi tiết tại đây . Người dùng có thể tạo bất kỳ số lượng chỉ mục văn bản nào và trình tối ưu hóa sẽ chọn một chỉ mục đủ tiêu chuẩn [có thể phân loại] và sử dụng nó. Nó cũng hỗ trợ tìm kiếm trong quá trình nối, quét chỉ mục đăng, v.v. bởi vì trình tối ưu hóa hiểu vị từ tìm kiếm và các lớp thành logic quyết định của nó. Không có API mới hoặc kế hoạch mới để quản lý. Đó là sức mạnh của việc có Couchbase!

Tài nguyên

Trong chương này, chúng tôi trình bày tổng quan về cách thức thực hiện các truy vấn trong một hệ quản trị cơ sở dữ liệu quan hệ. Chúng ta bắt đầu bằng việc bàn về cách quản lý dữ liệu bao gồm các bảng và các chỉ mục trong Phần 1. Dữ liệu về cấu trúc, còn gọi là metadata, được lưu trữ trong các bảng đặc biệt gọi là các danh mục hệ thống, được sử dụng để tìm ra cách tốt nhất thực hiện một truy vấn.

Các truy vấn SQL được biên dịch sang đại số quan hệ và các bước tiến hành thực hiện truy vấn được biểu diễn bằng các phép toán của đại số quan hệ dưới dạng Hình cây, các phép toán được biểu diễn trong các nút. Vì thế, việc thực thi các phép toán quan hệ được tối ưu một cách cẩn thận để cho truy vấn được thực hiện tốt nhất có thể. Chúng tôi giới thiệu việc đánh giá các phép toán trong Phần 2 và trình bày các thuật toán đánh giá cho hàng loạt các phép toán trong Phần 3.

Nhìn chung, các truy vấn thường có một vài các phép toán, và có nhiều cách để kết hợp các phép toán này. Quá trình tìm ra cách tốt nhất để thực hiện truy vấn được gọi là tối ưu hoá truy vấn. Chúng tôi giới thiệu về tối ưu hoá truy vấn trong Phần 4. Công việc cơ sở để tối ưu hoá truy vấn là xem xét một số kế hoạch thực hiện truy vấn đó, minh hoạ trong ví dụ của Phần 5. Phần 6 xem xét các bước tiến hành thực hiện một truy vấn nếu thực hiện thủ công.

Công việc này được trình bày một cách đầy đủ, chi tiết để người đọc hiểu được cách thức các hệ thống cơ sở dữ liệu thực hiện các truy vấn. Chương này cung cấp kiến thức nền tảng của việc thực hiện truy vấn. Thực thi các phép toán quan hệ và tối ưu hoá truy vấn được trình bày thêm trong Chương 13, 14 và 15; những chương này trình bày sâu hơn về cách thức các hệ thống cơ sở dữ liệu thực hiện điều này như thế nào.

Chúng ta giả sử rằng mỗi một bộ giá trị của quan hệ Reserver có dung lượng là 40 bytes, vì thế mỗi trang có thể quản lý 100 bộ giá trị của quan hệ này, và giả sử chúng ta có 1000 trang chứa các bộ giá trị. Tương tự, chúng ta giả sử rằng mỗi bộ giá trị của quan hệ Sailors có dung lượng là 50 bytes, vì thế mỗi trang có thể quản lý 80 bộ giá trị Sailors, và chúng ta có 500 trang chứa các bộ giá trị này.

Chúng ta có thể lưu trữ một bảng sử dụng một trong số một vài cấu trúc file khác nhau, và chúng ta có thể tạo ra một hoặc nhiều chỉ mục- mỗi một chỉ mục được lưu trong một file- trên mỗi bảng. Ngược lại, trong một DBMS quan hệ, mỗi file chứa các bộ giá trị trong một bảng hoặc các cổng vào chỉ mục. Tập hợp các file này tương ứng với các bảng của người dùng và các chỉ mục biểu diễn dữ liệu trong cơ sở dữ liệu.

DBMS quan hệ duy trì thông tin về tất cả các bảng và các chỉ mục có trong nó. Những thông tin định nghĩa các bảng và các chỉ mục được lưu trong một tập các bảng đặc biệt gọi là các bảng danh mục. Một ví dụ về bảng danh mục được minh hoạ trong Hình 1. Các bảng danh mục còn được gọi là từ điển dữ liệu, danh mục hệ thống, hay đơn giản gọi là 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].

Một đặc điểm của DBMS quan hệ là bản thân danh mục hệ thống là một tập hợp các bảng. Ví dụ, chúng ta có thể lưu trữ thông tin về các thuộc tính của các bảng trong một bảng danh mục gọi là Attribute_Cat:

Atttribute_Cat[attr_name: string, rel_name: string, type: string, position: integer]

Giả sử rằng cơ sở dữ liệu chứa hai bảng đã được giới thiệu ở đầu chương:

Sailors[sid: integer, sname: string, rating: integer, age: real] Reserves[sid: integer, bid: integer, day: dates, rname: string]

Hình 1 chỉ ra các bộ giá trị của bảng Attribute_Cat biểu diễn các thuộc tính của hai bảng này. Ghi nhớ rằng ngoài những bộ giá trị biểu diễn các thuộc tính của Sailors và Reserves còn có những bộ giá trị khác biểu diễn các thuộc tính của chính quan hệ này. Những bộ giá trị này chỉ ra một đặc điểm quan trọng: danh mục các bảng biểu diễn tất cả các bảng trong cơ sở dữ liệu và cả chính bản thân nó. Khi thông tin về một bảng được yêu cầu, nó sẽ được lấy ra từ danh mục hệ thống.

Cách tổ chức danh mục hệ thống là một tập hợp các bảng tỏ ra rất hiệu quả. Ví dụ, các bảng danh mục có thể được truy cập giống như một bảng bất kỳ, sử dụng ngôn ngữ truy vấn của DBMS! Thêm nữa, tất cả các công nghệ thực thi và quản lý các bảng đều có thể áp dụng cho các bảng danh mục. Những lựa chọn cho các bảng danh mục và lược đồ của nó không phải là duy nhất và được làm bởi những người thực thi DBMS. Các hệ thống thực thay đổi theo thiết kế lược đồ của nó, nhưng danh mục luôn được thực thi như một tập các bảng và cơ bản là nó chỉ ra cấu trúc của các dữ liệu được lưu trữ trong cơ sở dữ liệu.

Minh hoạ dữ liệu của quan hệ Attribute_Cat

Một số các thuật toán có thể được thực thi trên các phép toán quan hệ. Có một số nhân tố giúp cho các thuật toán được thực hiện tốt nhất, bao gồm kích thước của các bảng, các chỉ mục đang tồn tại và thứ tự sắp xếp các bản ghi trong bảng, kích thước của buffer pool và những luật được áp lên buffer.

Trong Phần này chúng ta trình bày một số công nghệ phổ biến được sử dụng trong việc phát triển các thuật toán đánh giá các phép toán quan hệ, và giới thiệu khái niệm về đường truy cập, những cách khác nhau mà các dòng của bảng có thể được truy cập.

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 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 . 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à , 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 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 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.

Lựa chọn một đường dẫn truy cập là số lượng những trang truy cập [các trang chỉ mục cộng với các trang dữ liệu] nếu chúng ta sử dụng đường dẫn truy cập này để truy cập đến những bộ giá trị mong muốn. Nếu bảng chứa một chỉ mục nào đó phù hợp với yêu cầu lọc dữ liệu, có ít nhất hai đường dẫn truy cập: chỉ mục và việc quét file dữ liệu. Đôi khi, tất nhiên, chúng ta có thể quét chính bản thân chỉ mục [hơn là quét file dữ liệu hoặc sử dụng chỉ mục để duyệt file dữ liệu], cung cấp cho chúng ta đường dẫn truy cập thứ ba.

Đường dẫn truy cập được lựa chọn nhiều nhất là đường dẫn truy cập tới ít trang nhất vì nó tối thiểu hoá được chi phí phải trả cho truy cập dữ liệu. Việc lựa chọn các đường dẫn truy cập phụ thuộc vào những kết nối chính trong điều kiện lựa chọn [bao gồm cả những ảnh hưởng của các chỉ mục liên quan]. Mỗi kết nối làm việc như một bộ lọc trên bảng. Tỷ lệ của các bộ giá trị trong bảng thoả mãn một kết nối nào đó được gọi là nhân tố giảm. Khi ở đó có một vài kết nối chính, tỷ lệ của các bộ giá trị thoả mãn tất cả các kết nối chính này có thể xấp xỉ bằng tích của các nhân tố giảm.

Giả sử chúng ta có một chỉ mục băm H trên quan hệ Sailors với khoá tìm kiếm chính là < rname,bid,sid >, và chúng ta có đ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 cả ba điều kiện nối. Danh mục chứa số lượng những giá trị khoá phân biệt trong chỉ mục băm này Nkeys[H], cũng như là số lượng các trang trong bảng sailor Npages. Tỷ lệ của trang thoả mãn các kết nối chính là Npages [ Sailors ] ⋅ 1 NKeys H size 12{ ital "Npages" \[ ital "Sailors" \] cdot { {1} over { ital "NKeys" left [H right ]} } } {} .

Nếu chỉ mục này có khoá tìm kiếm < bid, sid >, kết nối chính là bid=5 ∧ sid=3. Nếu chúng ta biết số lượng những giá trị phân biệt trong cột bid, chúng ta có thể ước lượng được nhân tố giảm cho kết nối đầu tiên. Thông tin này có giá trị trong danh mục nếu có một chỉ mục nào đó với bid là khoá tìm kiếm; nếu không, bộ tối ưu hoá sẽ sử dụng giá trị mặc định là 1/10. Sự tăng lên của các nhân tố giảm với bid=5 và sid=3 cung cấp cho chúng ta tỷ lệ các bộ giá trị được truy cập; nếu chỉ mục được phân cụm, đây cũng là tỷ lệ của các trang truy cập. Nếu chỉ mục này không phân cụm, mỗi bộ dữ liệu được truy cập có thể ở trên các trang khác nhau [xem lại Phần 8.4].

Chúng ta ước lượng được nhân tố giảm với một điều kiện miền như day > 8/9/2002 bằng việc giả sử rằng những giá trị trong cột này được phân bố đều nhau. Nếu có B+tree T với khoá day, nhân tố giảm là High T − value High T − Low T size 12{ { { ital "High" left [T right ] - ital "value"} over { ital "High" left [T right ] - ital "Low" left [T right ]} } } {}

Trong Phần này chúng tôi sẽ trình bày về các thuật toán đánh giá cho các phép toán quan hệ chính. Những ý tưởng quan trọng được giới thiệu ở đây, và những nghiên cứu sâu hơn sẽ được trình bày trong Chương 14. Trong chương 6, chúng ta chỉ xem xét chi phí I/Os và định giá chi phí này thông qua các trang I/Os. Trong chương này, chúng ta sử dụng những ví dụ chi tiết để minh hoạ cách định giá của mỗi thuật toán.

Mặc dù chúng tôi không trình bày công thức định giá một cách chính xác trong chương này, nhưng người đọc nên áp dụng những ý tưởng đã nêu để tính toán cho những ví dụ khác.

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 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 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.

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.

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.

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.

Xem xét ví dụ truy vấn trong Phần 4. Giả sử chúng ta xem xét giá thành của kế hoạch trong Hình 4. Chúng ta bỏ qua giá thành của việc viết ra kết quả cuối cùng vì điều này là Phần chung của tất cả các thuật toán, và nó không ảnh hưởng tới giá thành của các Phần liên quan khác. Giá của phép kết nối là 1000+1000*500= 501,000 trang I/Os. Các phép chọn và phép chiếu được thực hiện là on-the-fly và không có I/Os bổ sung. Vì thế, tổng giá thành của kế hoạch này sẽ là 501,000 trang I/Os. Kế hoạch này được thừa nhận là ngờ nghệch; tuy nhiên, nó sẽ là ngờ nghệch hơn nữa nếu phép nối được đối xử như phép nhân-chéo đi theo một phép chọn nào đó.

Bây giờ, chúng ta xem xét một số kế hoạch khác cho việc đánh giá truy vấn này. Mỗi kế hoạch sẽ có những cải tiến so với kế hoạch ban đầu và giới thiệu một vài ý tưởng tối ưu hoá ở Phần còn lại của chương này.

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.

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 tượng. Ví dụ theo sau minh hoạ tình trạng này:

SELECT S.sname FROM Reserves R, Sailors S WHERE R.sid = S.sid AND R.bid = 100 AND S.rating > 5 AND R.day = '8/9/2002'

Kế hoạch đánh giá truy vấn của ví dụ thứ hai

Kết quả của kế hoạch thực hiện truy vấn này được chỉ ra trong Hình 8 sai khác không đáng kể so với kế hoạch trong Hình 7. Phép chọn day='8/9/2002' được thực hiện on-the-fly trên kết quả của phép chọn với bid=100.

Giả sử rằng bid và day là khoá của Reserves. [Ghi nhớ rằng giả định này khác với lược đồ đã trình phía trên trong chương này]. Hãy cùng chúng tôi ước lượng chi phí của kế hoạch trong Hình 8. Phép chọn bid=100 có giá là 10 trang I/Os như đã nói ở trên, và điều kiện bổ sung day ='8/9/2002' được áp dụng theo kiểu on-the-fly sẽ loại đi tất cả trừ [nhiều nhất] một bộ giá trụi của Reserves. Có nhiều nhất một bộ giá trị của Sailors tương ứng, và nó được truy cập bởi 1.2 I/Os [trung bình]. ­Phép chọn trên rating và sau đó là phép chiếu lấy sname được áp dụng theo kiểu on-the-fly không mất thêm giá thành. Vì thế, giá tổng cộng của kế hoạch này trong Hình 8 mất khoảng 11 I/Os. Ngược lại, nếu chúng ta thay đổi kế hoạch ngờ nghệch trình bày trong Hình 6 để thực hiện phép chọn trên day và phép chọn bid=100 thì giá còn lại là 501,000 I/Os.

Tối ưu hoá truy vấn sử dụng đại số quan hệ có thể tạo ra rất nhiều biểu thức tương đương ứng với một truy vấn. Với mỗi biểu thức như vậy, tất cả các công nghệ thực thi có thể được áp dụng cho các phép toán quan hệ có liên quan trong biểu thức này, vì thế có thể phát sinh thêm những kế hoạch mới. Bộ tối ưu hoá sẽ ước lượng giá thành phải trả cho từng phương án và chọn một phương án có giá thấp nhất.

Hai biểu thức đại số trên cùng một tập các bảng đầu vào được gọi là tương đương nếu chúng sinh ra cùng một kết quả trên tất cả các minh hoạ dữ liệu của các bảng đầu vào. Sự tương đương của các biểu thức đại số quan hệ đóng vai trò trung tâm trong việc xác định các kế hoạch thay thế.

Xem xét một truy vấn cơ bản chứa một mệnh đề SELECT, một mệnh đề FROM, và một mệnh đề WHERE. Truy vấn này có thể dễ dàng biểu diễn bằng một biểu thức đại số; các trường đề cập trong mệnh đề SELECT được chiếu từ kết quả của phép nhân-chéo các bảng trong mệnh đề FROM sau khi đã áp dụng các phép chọn trong mệnh đề WHERE. Sử dụng sự tương đương có thể giúp chúng ta chuyển biểu thức ban đầu thành một vài biểu thức tương đương với nó. Cụ thể:

• Các phép chọn và nhân-chéo có thể được kết hợp trong các phép nối.
• Các phép nối có thể được sắp xếp lại thứ tự.
• Các phép chiếu và phép chọn làm giảm kích thước của đầu vào có thể được đẩy lên trên các phép nối.

Truy vấn được trình bày trong Phần 5 minh hoạ những điểm trên, việc đẩy phép chọn trong truy vấn này lên trên phép nối đã tạo ra một kế hoạch đánh giá tốt hơn rất nhiều. Chúng tôi trình bày về sự tương đương của các biểu thức đại số quan hệ trong Phần 15.3.

Xem xét một truy vấn có dạng A

B

C

D; đây là phép nối tự nhiên trên bốn bảng. Ba cây đại số quan hệ trong Hình 9 là tương đương nhau. Theo quy ước, cây con bên trái của nút kết nối là bảng phía ngoài và cây con bên phải là bảng phía trong. Bằng việc thêm vào những chi tiết như các phương thức kết nối tại mỗi nút thì có thể dễ hiểu để thực hiện một vài kế hoạch đánh giá truy vấn trên những cây này.

Ba cây kết nối

Hai cây đầu trong Hình 9 là những ví dụ về cây tuyến tính. Trong một cây tuyến tính, có ít nhất một con của phép nối là bảng cơ sở. Cây đầu tiên là ví dụ về cây sâu-trái [left-deep]- con phải của mỗi nút là bảng cơ sở. Cây thứ ba là ví dụ về cây không tuyến tính hay còn gọi là cây rậm rạp [bushy tree].

Các bộ tối ưu hoá thông thường sử dụng cách tiếp cận lập trình động [xem Phần 15.4.2] để tìm kiếm các kế hoạch sâu-trái một cách hiệu quả. Vì thế loại cây thứ hai và thứ ba không bao giờ được xem xét. Ta thấy cây đầu tiên biểu diễn một kế hoạch trong đó A và B được nối trước, sau đó kết quả của phép nối này được nối với C, sau đó kết quả này được tiếp tục nối với D. Có 23­­5 những kế hoạch sâu-trái được tạo ra chỉ do thay đổi thứ tự các bảng được kết nối. Nếu một kế hoạch nào đó trong số những kế hoạch này có phép chọn và phép chiếu có điều kiện thì những điều kiện này được áp dụng sớm nhất có thể sẽ cung cấp một lựa chọn về thứ tự kết nối các bảng.

Tất nhiên, quyết định này loại trừ rất nhiều kế hoạch mà chi phí của nó có thể ít hơn chi phí của kế hoạch tốt nhất sử dụng một cây sâu-trái; chúng ta phải chịu một thực tế rằng bộ tối ưu hoá sẽ không bao giờ tìm được những kế hoạch như vậy. Có hai lý do của quyết định này để tập trung vào các kế hoạch sâu-trái, hoặc những kế hoạch dựa trên các cây sâu-trái:

1. Khi số lượng các kết nối tăng lên, số lượng các kế hoạch tăng lên nhanh chóng.
2. Các cây sâu-trái cho phép chúng ta đưa ra tất cả các kế hoạch theo kiểu truyền liên tục đầy đủ [fully pipelined]; tức là các kế hoạch trong đó tất cả các kết nối được đánh giá sử dụng truyền liên tục. [Các bảng bên trong luôn phải được hiện thực hoá bởi vì chúng ta phải kiểm tra toàn bộ bảng bên trong ứng với mỗi giá trị của bảng bên ngoài. Vì thế, một kế hoạch trong đó một bảng bên trong là kết quả của phép nối bắt buộc chúng ta phải hiện thực hoá kết quả của phép nối đó.]

Giá của một kế hoạch là tổng giá của các phép toán bên trong nó. Giá của các phép toán quan hệ riêng lẻ trong một kế hoạch được ước lượng sử dụng thông tin lấy từ danh mục hệ thống, các thuộc tính [ví dụ, kích cỡ, thứ tự sắp xếp] của các bảng đầu vào. Chúng ta minh hoạ cách ước lượng chi phí của các kế hoạch toán-tử-duy-nhất [single-operatorr] trong Phần 2 và3, và cách ước lượng giá của các kế hoạch đa-toán-tử [multi-operator] trong Phần 5.

Nếu chúng ta tập trung vào giá của I/O, giá của một kế hoạch nào đó có thể được chia làm ba Phần : [1] đọc các bảng đầu vào [có thể nhiều lần trong trường hợp nối và các thuật toán sắp xếp], [2] viết lên các bảng tạm, và có thể [3] sắp xếp kết quả cuối cùng [nếu truy vấn cần loại bỏ các giá trị trùng lặp hoặc đầu ra cần được sắp xếp]. Phần thứ ba là chung cho tất cả các kế hoạch [trừ khi kết quả là đầu vào của một thủ tục nào đó], và trong trường hợp kế hoạch được thực hiện theo kiểu truyền liên tục hoàn toàn [fully-pipelined], không yêu cầu bảng tạm nào phải ghi ra.

Vì thế, giá của một kế hoạch truyền liên tục hoàn toàn bị chi phối bởi Phần [1]. Giá này phụ thuộc Phần lớn vào các đường dẫn truy cập được sử dụng để đọc các bảng đầu vào; tất nhiên, các đường dẫn truy cập được sử dụng lặp đi lặp lại để truy cập các bộ giá trị thoả mãn trong một thuật toán kết nối là đặc biệt quan trọng.

Với những kế hoạch không phải theo kiểu truyền liên tục hoàn toàn, giá của các bảng tạm phải hiện thực hoá là rất đáng kể. Giá của việc hiện thực hoá các kết quả tạm phụ thuộc vào kích thước của nó, và kích thước này cũng ảnh hưởng đến các phép toán trong đó các bảng tạm là dữ liệu đầu vào. Số lượng các bộ giá trị trong kết quả của một phép chọn được ước lượng bằng tích của kích thước đầu vào nhân với hệ số giảm do các điều kiện chọn. Số lượng các bộ giá trị trong kết quả của một phép chiếu giống với đầu vào trong trường hợp sự trùng lặp không được loại bỏ, còn nếu sự trùng lặp bị loại bỏ thì số lượng các bộ giá trị trong kết quả sẽ ít hơn đầu vào vì nó chứa ít trường hơn.

Kích thước kết quả của một phép nối có thể được ước lượng bằng việc nhân kích thước kết quả lớn nhất, là tích của các kích thước của các bảng đầu vào, với hệ số giảm của điều kiện kết nối. Hệ số giảm của điều kiện nối columnl = column2 có thể được xấp xỉ bằng công thức 1 MAX NKeys I1 , NKeys I2 size 12{ { {1} over { ital "MAX" left [ ital "NKeys" left [I1 right ], ital "NKeys" left [I2 right ] right ]} } } {} nếu có các chỉ mục I1 và I2 tương ứng trên column1 và column2. Công thức này áp dụng trong trường hợp mỗi giá trị khoá trong chỉ mục nhỏ hơn, giả sử I1 có một giá trị tương ứng trong chỉ mục khác.

Trả lời những câu hỏi sau, kết quả có thể được tìm thấy ở các mục liệt kê bên cạnh.

• Metadata là gì? Dữ liệu nào của metadata được lưu trữ trong danh mục hệ thống. Trình bày những thông tin lưu trong mỗi quan hệ, mỗi chỉ mục [Phần 1].
• Danh mục bản thân nó được lưu như một tập các quan hệ. Giải thích vì sao? [Phần 1]
• Ba công nghệ nào được sử dụng chung trong các thuật toán đánh giá các phép toán quan hệ? [Phần 2]
• Đường dẫn truy cập là gì? Khi nào một chỉ mục so sánh được [math] với một điều kiện tìm kiếm? [Phần 2.2]
• Các cách tiếp cận chính để đánh giá các phép chọn là gì? Cụ thể, trình bày về việc sử dụng các chỉ mục. [Phần 3.1]
• Các cách tiếp cận chính để đánh giá các phép chiếu là gì? Điều gì làm các phép chiếu trở nên tốn kém? [Phần 3.2]
• Các cách tiếp cận chính để đánh giá các phép nối là gì? Vì sao các phép nối phải là các phép toán đắt? [Phần 3.3]
• Mục đích của tối ưu hoá truy vấn là gì? Nó có tìm ra kế hoạch tốt nhất không? [Phần 4]
• DBMS biểu diễn một kế hoạch đánh giá truy vấn quan hệ như thế nào? [Phần 4.1]
• Đánh giá truyền liên tục là gì? Lợi ích của nó là gì? [Phần 4.2]
• Trình bày về giao diện lập trình con chạy của các phép toán và các phương thức truy cập. Mục đích của nó là gì? [Phần 4.3]
• Vì sao chúng ta bàn về sự khác nhau về chi phí giữa các kế hoạch khác nhau cho một truy vấn. Cung cấp ví dụ minh hoạ ảnh hưởng của việc đẩy các phép chọn lên, các lựa chọn về phương thức kết nối, và lợi ích của các chỉ mục thích hợp. [Phần 5]
• Vai trò của sự tương đương trong đại số quan hệ đối với tối ưu hoá truy vấn? [Phần 6]
• Các cách biểu diễn kế hoạch khác nhau được bộ tối hoá truy vấn quan hệ điển Hình xem xét là gì? Giải thích về các cách biểu diễn này. [Phần 6.1]
• Giá của các kế hoạch được ước lượng như thế nào? Vai trò của danh mục hệ thống là gì? Sự lựa chọn đường dẫn truy cập là gì, và nó ảnh hưởng đến chi phí của một kế hoạch như thế nào? Vì sao việc ước lượng được kích thước của kết quả truy vấn lại quan trọng? [Phần 6.2]

Trả lời tóm tắt những câu hỏi sau:

1. Trình bày ba công nghệ phổ biến được sử dụng khi phát triển các thuật toán cho các phép toán quan hệ. Giải thích vì sao ba công nghệ này có thể được sử dụng để thiết kế thuật toán cho phép chọn, phép chiếu, và phép nối.
2. Đường dẫn truy cập là gì? Khi nào một chỉ mục so sánh được với một đường dẫn truy cập? Liên kết chính là gì, và vì sao nó quan trọng?
3. Thông tin nào đượca lưu trong các danh mục hệ thống?
4. Lợi ích của việc làm cho các danh mục hệ thống là các quan hệ là gì?
5. Mục đích của tối ưu hoá truy vấn là gì? Vì sao việc tối ưu hoá lại quan trọng?
6. Trình bày về truyền liên tục [pipelining] và những lợi ích của nó?
7. Cung cấp một truy vấn ví dụ mà kế hoạch thực hiện của nó không thể sử dụng được cách truyền liên tục.
8. Trình bày về giao diện lập trình con chạy và giải thích những ưu điểm của nó.
9. Các thống kê trong cơ sở dữ liệu đóng vao trò gì trong tối ưu hóa truy vấn?
10. Những quyết định thiết kế quan trọng được làm trong bộ tối ưu hoá System R là gì?
11. Vì sao bộ tối ưu hoá truy vấn chỉ đề cập đến các cây liên kết sâu-trái? Cung cấp một ví dụ của một truy vấn và một kế hoạch không được giải quyết do giới hạn này.

Câu Trả lời với từng câu hỏi như sau:

1. Ba công nghệ phổ biến được sử dụng là chỉ mục hóa, con chạy, và sự phân vùng:

• Chỉ mục hóa: Nếu một phép chọn hoặc điều kiện nối được xác định, nó sử dụng một chỉ mục nào đó để kiểm tra chỉ những bộ giá trị thỏa mãn điều kiện này.
• Con chạy: Kiểm tra tất cả các bộ giá trị trong một bảng đầu vào nào đó, bộ giá trị này sau bộ giá trị kia. Nếu chúng ta chỉ cần một vài trường của mỗi bộ giá trị và ở đây có một chỉ mục chứa tất cả các trường này, thì thay vì kiểm tra các bộ giá trị dữ liệu, chúng ta chỉ cần quét tất cả các cổng vào dữ liệu chỉ mục.
• Sự phân vùng: Bằng việc phân chia các bộ giá trị trên một khóa sắp xếp nào đó, chúng ta có thể phân tích một thao tác nào đó thành một tập các thao tác trên các vùng khác nhau với chi phí thấp hơn. Sắp xếp hoặc băm là hai công nghệ phân vùng được sử dụng phổ biến.

Chúng có thể được sử dụng để thiết kế các thuật toán cho phép chọn, phép chiếu và các phép nối, như sau:

• Phép chọn: Với một phép chọn nào đó có nhiều hơn một bộ giá trị thỏa mãn [thông thường, nhỏ hơn 5%], sử dụng chỉ mục như B+trees sẽ rất hữu ích. Các truy vấn này thường là các truy vấn miền. Nó cho phép chúng ta không chỉ tìm được bộ giá trị thỏa mãn đầu tiên nhanh nhất, mà còn có thể tìm được những bộ giá trị khác sớm hơn [đặc biệt trong trường hợp chỉ mục này được phân cụm]. Với một điều kiện chọn nào đó cùng với một truy vấn bằng mà chỉ có rất ít [thường là 1] bộ giá trị phù hợp, việc phân vùng sử dụng chỉ mục băm thường là thích hợp. Nó cho phép chúng ta tìm ra một bộ giá trị chính xác mà chúng ta đang tìm kiếm chỉ với chi phí rất thấp [chỉ một hoặc hai I/Os].
• Phép chiếu: Phép chiếu yêu cầu chúng ta loại bỏ một số trường hiện tại của đầu vào, điều này có thể dẫn đến sự trùng lặp trong tập kết quả. Nếu chúng ta không cần loại bỏ sự trùng lặp này, thì công nghệ con chạy có thể quản lý hiệu quả vấn đề này. Ngược lại, nếu chúng ta cần loại bỏ sự trùng lặp, việc phân vùng dữ liệu và áp dụng khóa sắp xếp sẽ tốt hơn.

Trong trường hợp có nhiều chỉ mục thích hợp đang sẵn sàng, thì chúng ta có thể có được những kế hoạch rẻ hơn cho việc sắp xếp các bộ giá trị trong quá trình loại bỏ sự trùng lặp vì tất cả dữ liệu có thể được sắp xếp trên chỉ mục này [trong trường hợp này chúng ta chỉ đơn giản so sánh các cổng vào dữ liệu cạnh nhau để kiểm tra sự trùng lặp].

• Phép nối: Đây là phép thao tác có chi phí đắt đỏ nhất, có thể kết hợp sử dụng cả ba công nghệ. Phép nối thường có nhiều phép chọn và các Phần tử được chiếu ra, vì thế việc có các chỉ mục thích hợp và các phân vùng dữ liệu như trên là rất quan trọng. Bất cứ khi nào có thể, các phép chọn độc lập và các phép chiếu được áp dụng cho hai quan hệ nên được thực thi trước khi thực hiện phép nối để giảm kích thước của bảng trung gian.

Ví dụ, xem xét phép nối hai quan hệ có 100,000 bộ giá trị ở mỗi quan hệ và chỉ có 5% các bộ giá trị thỏa mãn trong mỗi bảng. Việc thực hiện phép nối trước khi áp dụng các điều kiện chọn sẽ dẫn đến kích thước bảng trung gian rất lớn và sau đó lại phải tìm kiếm các phép chọn phù hợp. Cách làm khác là, chúng ta áp dụng các phép chọn trước. Sau đó chúng ta có thể thực hiện một phép nối của 5000 bộ giá trị thỏa mãn nhận được sau khi áp dụng phép chọn trên mỗi bảng, thì việc tìm kiếm và quản lý các bộ giá trị này sẽ nhanh hơn đáng kể.

2. Đường truy cập là một đường để truy cập các bộ giá trị trong một bảng nào đó, nó yêu cầu một thao tác quét file hoặc một chỉ mục nào đó cộng với một điều kiện chọn phù hợp. Một chỉ mục phù hợp với một điều kiện chọn nếu chỉ mục này có thể được sử dụng để truy cập chỉ các bộ giá trị thỏa mãn điều kiện này. Một chỉ mục có thể phù hợp với một số các phép liên kết trong một điều kiện chọn nào đó, có thể nó không phù hợp với toàn bộ điều kiện và chúng ta coi phép liên kết mà chỉ mục này phù hợp là các liên kết chính trong phép chiếu này. Các liên kết chính rất quan trọng vì chúng cho phép chúng ta nhanh chóng bỏ qua các thông tin mà chúng ta không cần đến và chỉ tập trung vào việc tìm kiếm/ sắp xếp những dữ liệu liên quan nhiều nhất đến những điều kiện chọn này.

3. Thông tin về các quan hệ, chỉ mục, và các khung nhìn được lưu trữ trong các danh mục hệ thống. Nó bao gồm các tên file, kích thước file, và cấu trúc file, tên thuộc tính và kiểu dữ liệu, danh sách các khóa, và các ràng buộc.

Các thông tin thống kê được lưu trữ phổ biến nhất bao gồm:

1. Lực lượng – Số lượng các bộ giá trị trong mỗi quan hệ.
2. Kích thước – số lượng các trang trong mỗi quan hệ.
3. Lực lượng chỉ mục - số lượng các giá trị khóa phân biệt cho từng chỉ mục.
4. Kích thước chỉ mục - số lượng các trang của từng chỉ mục [hoặc số lượng các trang trái]
5. Chiều cao chỉ mục - số lượng các mức không-lá của từng chỉ mục cây.
6. Miền chỉ mục - giá trị khóa hiện tại nhỏ nhất và lớn nhất của từng chỉ mục.

4. Có một số ưu điểm của việc lưu trữ các danh mục hệ thống như là các quan hệ. Các danh mục hệ thống có tất cả các ưu điểm của các quan hệ về mặt thực thi và quản lý: lưu trữ thông tin hiệu quả và các khả năng truy vấn phong phú. Lựa chọn cái gì được lưu trữ trong các danh mục hệ thống là công việc của người xây dựng DBMS.

5. Mục đích của tối ưu hóa truy vấn là tránh các kế hoạch tồi nhất và tìm ra được một kế hoạch đủ tốt. Mục đích của nó không phải là tìm ra được một kế hoạch tốt nhất. Sự khác nhau trong chi phí của kế hoạch tốt và kế hoạch tồi là rất lớn: kế hoạch truy vấn tốt có thể đánh giá truy vấn theo thời gian tính bằng giây, trong khi đó kế hoạch tồi có thể phải mất nhiều ngày!

6. Truyền liên tục [Pipelining] cho phép chúng ta tránh được việc tạo và đọc các quan hệ tạm; giảm được các chi phí I/Os.

7. Các truy vấn rậm rạp [bushy] không thể tận dụng được các ưu điểm của việc truyền liên tục vì những giới hạn của bộ đệm và tài nguyên của CPU. Xem xét một kế hoạch trong đó chúng ta phải thực hiện một phép chọn trên hai quan hệ, sau đó là phép nối. Chúng ta không thể luôn sử dụng được việc truyền liên tục trong chiến lược này, vì kết quả của phép chọn đầu tiên có thể không đặt vừa bộ nhớ, và chúng ta phải đợi phép chọn thứ hai hoàn thành trước khi chúng ta có thể bắt đầu thực hiện phép nối.

8. Giao diện con chạy cho một thao tác nào đó bao gồm các hàm open, get next, và close; nó ẩn đi những chi tiết về cách thức thực thi, và cho phép chúng ta xem tất cả các nút trong một kế hoạch truy vấn.

9. Bộ tối ưu hóa truy vấn sử dụng các thống kê để tăng khả năng chọn được một kế hoạch thực thi truy vấn tốt nhất. Các thống kê này được sử dụng để tính toán các nhân tố giảm trong đó các nhân tố này bị ảnh hưởng bởi các chỉ mục và các đầu vào khác nhau.

10. Một số các quyết định thiết kế quan trọng trong bộ tối ưu hóa System R là:

1. Sử dụng các thống kê về một minh họa cơ sở dữ liệu nào đó để tính toán chi phí của một kế hoạch đánh giá truy vấn nào đó.
2. Một quyết định để xem xét chỉ những kế hoạch có các phép nối nhị phân, trong đó quan hệ phía trong là quan hệ cơ sở. Điều này giúp làm giảm số lượng các kế hoạch khác nhau phải xem xét.
3. Một quyết định để tập trung cho việc tối ưu hóa trên lớp các truy vấn SQL không có sự lồng nhau và đối xử với các truy vấn lồng nhau theo một cách đặc biệt.
4. Một quyết định để thực hiện loại bỏ các giá trị trùng lặp của các phép chiếu [loại bỏ là bước cuối cùng trong đánh giá truy vấn khi truy vấn này có mệnh đề DISTINCT].
5. Mô Hình chi phí bao gồm cả chi phí của CPU và chi phí I/O.

11. Có hai lý do chính để quyết định chỉ tập trung vào các kế hoạch sâu-trái là:

1. Khi số lượng các phép nối tăng lên, số lượng các kế hoạch khác nhau cũng tăng lên rất nhanh chóng và việc tỉa không gian của các kế hoạch khác nhau trở nên cần thiết.
2. Cây sâu-trái cho phép chúng ta đưa ra tất cả các kế hoạch chỉ có truyền liên tục; tức là, các kế hoạch trong đó tất cả các phép nối được đánh giá sử dụng việc truyền liên tục.

Xem xét phép nối A

B

C

D. Kế hoạch [A

B]

[C

D] sẽ không bao giờ được xem xét vì nó là một cây rậm rạp.

Xem xét quan hệ R[a, b, c, d] chứa 5,000,000 bản ghi, trong đó mỗi trang dữ liệu của quan hệ này lưu được 10 bản ghi. R được tổ chức như một file đã sắp xếp bởi các chỉ mục phụ. Giả sử rằng R.a là một khoá dự tuyển của R, với các giá trị nằm trong dải từ 0 đến 4,999,999 và R được sắp xếp theo thứ tự của R.a. Với mỗi truy vấn đại số quan hệ theo sau, cách tiếp cận nào trong ba cách sau là rẻ nhất:

• Truy cập file được sắp của R một cách trực tiếp.
• Sử dụng một chỉ mục B+ tree [clustered] trên thuộc tính R.a.
• Sử dụng một chỉ mục băm tuyến tính trên thuộc tính R.a.
• σa50,000 ∧ a.
• σSailors.sid.
• σSailors.sid.
  1. σ Sailors.sid2l[Sailors]
  2. σ Sailors.sid=50,000[Sailors]
  3. σ Sailors.age=2l[Sailors]
• Một chỉ mục băm trên khoá tìm kiếm < Sailors.sid, Sailors.age >.
  1. σSailors.sid=50,000∧Sailors.age=21[Sailors]
  2. σSailors.sid=50,000 ∧ Sailors.age>21[Sailors]

Xem xét lại lược đồ quan hệ với quan hệ Sailors sau:

Sailors[sid: integer, sname: string, rating: integer, age: real]

Giả sử rằng mỗi bộ giá trị của Sailors có chiều dài là 50 bytes, do đó mỗi trang có thể nắm giữ 80 bộ giá trị Sailors, và do đó chúng ta có 500 trang cho những bộ giá trị này. Với mỗi điều kiện chọn sau, ước lượng số lượng các trang đã truy cập.

1. Giả sử rằng chúng ta có một chỉ mục B+ tree là T trên khoá tìm kiếm , và giả sử rằng IHeight[T]=4, INPages[T] = 50, Low[T] = 1, và High[T]=100,000.

[a] σ Sailors.sid, và giả sử rằng IHeight[T]=2, INPages[T]=50, Low[T]=1, và High[T]=100,000.

[a] σ Sailors.sid