On Producing High and Early Result Throughput in Multijoin Query Plans

• Published in: IEEE transactions on knowledge and data engineering 2011-12, Vol.23 (12), p.1888-1902
• Main Authors: Levandoski, J. K., Khalefa, M. E., Mokbel, M. F.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Applied sciences; Computer science; control theory; systems; Database management; Database systems; Disks; Exact sciences and technology; Flushing; Information systems. Data bases; Memory organisation. Data processing; Operators; Optimization; Query processing; Radicals; Runtime; Software; Spatial databases; State of the art; Studies; Switches; systems
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2010.182

This paper introduces an efficient framework for producing high and early result throughput in multijoin query plans. While most previous research focuses on optimizing for cases involving a single join operator, this work takes a radical step by addressing query plans with multiple join operators. The proposed framework consists of two main methods, a flush algorithm and operator state manager. The framework assumes a symmetric hash join, a common method for producing early results, when processing incoming data. In this way, our methods can be applied to a group of previous join operators (optimized for single-join queries) when taking part in multijoin query plans. Specifically, our framework can be applied by 1) employing a new flushing policy to write in-memory data to disk, once memory allotment is exhausted, in a way that helps increase the probability of producing early result throughput in multijoin queries, and 2) employing a state manager that adaptively switches operators in the plan between joining in-memory data and disk-resident data in order to positively affect the early result throughput. Extensive experimental results show that the proposed methods outperform the state-of-the-art join operators optimized for both single and multijoin query plans.