Qd-tree: Learning Data Layouts for Big Data Analytics
This addresses performance bottlenecks in query processing for large-scale corporate data analytics, offering a novel optimization over incremental improvements in data layout techniques.
The paper tackles the problem of assigning records to data blocks in big data analytics to minimize the number of blocks accessed by queries, proposing a qd-tree framework that achieves over an order of magnitude speedup compared to current schemes and comes within 2X of a lower bound based on selectivity.
Corporations today collect data at an unprecedented and accelerating scale, making the need to run queries on large datasets increasingly important. Technologies such as columnar block-based data organization and compression have become standard practice in most commercial database systems. However, the problem of best assigning records to data blocks on storage is still open. For example, today's systems usually partition data by arrival time into row groups, or range/hash partition the data based on selected fields. For a given workload, however, such techniques are unable to optimize for the important metric of the number of blocks accessed by a query. This metric directly relates to the I/O cost, and therefore performance, of most analytical queries. Further, they are unable to exploit additional available storage to drive this metric down further. In this paper, we propose a new framework called a query-data routing tree, or qd-tree, to address this problem, and propose two algorithms for their construction based on greedy and deep reinforcement learning techniques. Experiments over benchmark and real workloads show that a qd-tree can provide physical speedups of more than an order of magnitude compared to current blocking schemes, and can reach within 2X of the lower bound for data skipping based on selectivity, while providing complete semantic descriptions of created blocks.