Column-Oriented Join Order Optimization in Column Store Systems

Join is one of the most important operations which can largely affect the efficiency of column store based queries. Most work on column-stores is focused on the improving of storage structure and the building of physical auxiliary structures, while the logical plan optimization, especially early join strategy optimization, has seldom been considered. On the basis of this problem, this paper presents a new join strategy optimization method according to the characteristic of column-oriented storage structure and analytical query. We adopt the early optimization strategy in our method and propose a “fact table push-down” rule. In particular, the bushy tree structure will be considered in the multi-fact-table case to receive a “best” join path with small time and space complexity. Then we provide a cost estimation to verify the correctness of the proposed join strategy optimization method. Finally, experimental results on the large-scale data warehouse benchmark data sets SSB also verify the effectiveness of the early optimization strategy and the proposed push-down rule.