Reducing the costs of I/O intensive operations during query processing.

摘要

I/O intensive plan operations (operations that incur intensive disk I/O's) often dominate the cost of query processing because of the relatively low transfer speed between memory and disk. In this thesis, we introduce two techniques for reducing the costs of I/O intensive operations during query processing: I/O avoidance and I/O refinement.; I/O avoidance infers ordering and grouping properties that intermediate query results hold so as to determine where query plans include redundant sorting or grouping operations. We defined rules that can be used to infer ordering and grouping properties, and designed algorithms that exploit these rules to infer properties that allow for the automatic elimination of redundant sorting and grouping operations from query plans.; I/O refinement involves permuting block request sequences (sequences of read and write system calls) for I/O intensive operations, in a manner that exploits the management policies of underlying, autonomous buffer management schemes. We propose four techniques for refining block request sequences: block-level I/O grouping, file-level I/O grouping, I/O ordering, and block recycling. We incorporate these techniques into well-known external sort and hash join operations, resulting in two alternative sort and hash join operations: multi-level merge sort (MMS) and sort-hash join (SHJ), and then show empirical results establishing when and to what degree these operations improve the performance of query processing.; In short, I/O avoidance (which removes redundant I/O intensive operations from a query plan), and I/O refinement (which reduces the costs of the I/O intensive operations that remain) together can be used to significantly reduce the overall cost of query processing.