Journal of East China Normal University(Natural Science) ›› 2022, Vol. 2022 ›› Issue (5): 48-60.doi: 10.3969/j.issn.1000-5641.2022.05.005

• Blockchain System and Data Management • Previous Articles     Next Articles

Benchmarking join order selection of query optimizers

Ting CHEN, Zhaokun XIANG, Jinkai XU, Rong ZHANG*()   

  1. School of Data Science and Engineering, East China Normal University, Shanghai 200062, China
  • Received:2022-07-11 Online:2022-09-25 Published:2022-09-26
  • Contact: Rong ZHANG E-mail:rzhang@dase.ecnu.edu.cn

Abstract:

Join order selection, i.e., the determination of the cheapest join order from available alternatives, is one of the most critical tasks in query optimization. The enormous search space of a join order makes it difficult to find an optimal join order in an efficient manner. Although there are many optimization algorithms for join order selection, existing benchmarks are unsuitable for evaluating these join order selection strategies because they cannot configure the depths of the joins or cover all join styles. To effectively evaluate the quality of join order selection algorithms used in an optimizer, a generic evaluation tool for join order selection is implemented in this study. The tool takes the primary key-based deterministic data generation method for portable application scenario migration, a join order sampling algorithm to reduce the investigated join spaces, and a result-guided parameter instantiation algorithm to support a valid query generation. We applied the tool on OceanBase and PostgreSQL, and the experiment results show its effectiveness in evaluating the performance of join order selection in query optimizers in a generic and efficient manner.

Key words: online analytical processing database, query processing, query optimization, join order selection

CLC Number: