Volcano - An Extensible and Parallel Query Evaluation System

Volcano—Một Hệ thống Đánh giá Truy vấn Mở rộng được và Song song

Goetz Graefe

Tóm tắt—Để khảo sát sự tương tác giữa khả năng mở rộng và tính song song trong xử lý truy vấn cơ sở dữ liệu, chúng tôi đã phát triển một hệ thống thực thi truy vấn luồng dữ liệu mới có tên Volcano. Nỗ lực Volcano cung cấp một môi trường phong phú cho nghiên cứu và giáo dục về thiết kế hệ thống cơ sở dữ liệu, các heuristic cho tối ưu hóa truy vấn, thực thi truy vấn song song và phân bổ tài nguyên.

Volcano sử dụng một giao diện tiêu chuẩn giữa các toán tử đại số, cho phép dễ dàng bổ sung các toán tử mới và các triển khai toán tử. Các phép toán trên từng mục riêng lẻ, ví dụ như các vị từ, được nhập vào các toán tử xử lý truy vấn bằng cách sử dụng các hàm hỗ trợ. Ngữ nghĩa của các hàm hỗ trợ không được quy định; mọi kiểu dữ liệu bao gồm các đối tượng phức tạp và mọi phép toán đều có thể được hiện thực hóa. Do đó, Volcano có khả năng mở rộng với các toán tử, thuật toán, kiểu dữ liệu và các phương pháp đặc thù theo kiểu mới.

Volcano bao gồm hai toán tử meta mới. Toán tử meta choose-plan hỗ trợ các kế hoạch đánh giá truy vấn động, cho phép trì hoãn một số quyết định tối ưu hóa được chọn cho đến thời gian chạy, ví dụ như đối với các truy vấn nhúng có các biến tự do. Toán tử meta exchange hỗ trợ tính song song nội toán tử trên các tập dữ liệu được phân vùng và cả tính song song liên toán tử theo chiều dọc và chiều ngang, chuyển đổi giữa luồng dữ liệu hướng theo nhu cầu bên trong các tiến trình và luồng dữ liệu hướng theo dữ liệu giữa các tiến trình.

Tất cả các toán tử, ngoại trừ toán tử exchange, đã được thiết kế và triển khai trong một môi trường đơn tiến trình, và được song song hóa bằng cách sử dụng toán tử exchange. Ngay cả các toán tử chưa được thiết kế cũng có thể được song song hóa bằng toán tử mới này nếu chúng sử dụng và cung cấp giao diện interator. Vì vậy, các vấn đề về thao tác dữ liệu và tính song song đã trở nên trực giao, khiến Volcano trở thành công cụ thực thi truy vấn đầu tiên được triển khai kết hợp hiệu quả khả năng mở rộng và tính song song.

Abstract—To investigate the interactions of extensibility and parallelism in database query processing, we have developed a new dataflow query execution system called Volcano. The Volcano effort provides a rich environment for research and education in database systems design, heuristics for query optimization, parallel query execution, and resource allocation.

Volcano uses a standard interface between algebra operators, allowing easy addition of new operators and operator implementations. Operations on individual items, e.g., predicates, are imported into the query processing operators using support functions. The semantics of support functions is not prescribed; any data type including complex objects and any operation can be realized. Thus, Volcano is extensible with new operators, algorithms, data types, and type-specific methods.

Volcano includes two novel meta-operators. The choose-plan meta-operator supports dynamic query evaluation plans that allow delaying selected optimization decisions until run-time, e.g., for embedded queries with free variables. The exchange meta-operator supports intra-operator parallelism on partitioned datasets and both vertical and horizontal inter-operator parallelism, translating between demand-driven dataflow within processes and data-driven dataflow between processes.

All operators, with the exception of the exchange operator, have been designed and implemented in a single-process environment, and parallelized using the exchange operator. Even operators not yet designed can be parallelized using this new operator if they use and provide the interator interface. Thus, the issues of data manipulation and parallelism have become orthogonal, making Volcano the first implemented query execution engine that effectively combines extensibility and parallelism.

Index Terms—Dynamic query evaluation plans, extensible database systems, iterators, operator model of parallelization, query execution.

This section is missing here.

I INTRODUCTION

This section is missing here.

II RELATED WORK

This section is missing here.

III VOLCANO SYSTEM DESIGN

This section is missing here.

IV EXTENSIBILITY

This section is missing here.

V DYNAMIC QUERY EVALUATION PLANS

This section is missing here.

VI MULTIPROCESSOR QUERY EVALUATION

This section is missing here.

VII SUMMARY AND CONCLUSIONS

This section is missing here.

Acknowledgments