Improving query I/O performance by permuting and refining block request sequences

The I/O performance of query processing can be improved using two complementary approaches: improve the buffer and the file system management policies of the DB buffer manager and the OS file system manager (e.g. page replacement), or improve the sequence of requests that are submitted to a file system manager and that lead to actual I/O's (block request sequences). This paper takes the latter approach. Exploiting common file system practices as found in Linux, we propose four techniques for permuting and refining block request sequences: Block-Level I/O Grouping, File-Level I/O Grouping, I/O Ordering, and Block Recycling. To manifest these techniques, we create two new plan operations, MMS and SHJ, each of which adopts some of the block request refinement techniques above. We implement the new plan operations on top of Postgres running on Linux, and show experimental results that demonstrate up to a factor of 4 performance benefit from the use of these techniques.