Banner Banner

Exploiting Access Pattern Characteristics for Join Reordering

Nils Schubert
Philipp M Grulich
Steffen Zeuch
Volker Markl

June 18, 2023

With increasing main memory sizes, data processing has significantly shifted from secondary storage to main memory. However, choosing a good join order is still very important for efficient query execution in modern DBMS. This choice bases mainly on cardinality estimates for intermediate join results. However, the memory access pattern, e.g., sequential or random, on the intermediate state is an often neglected performance factor.

In this paper, we examine this impact on join query performance by evaluating the execution time, and cache misses for n-ary foreign-key joins. Based on this analysis, we propose a novel join reordering algorithm that detects the memory access pattern (using machine learning on hardware performance counters) and adapts the join order accordingly at runtime. By considering the access pattern, our evaluation shows that our adaptive reorder algorithm converges quickly to a good join order and reaches improvements of up to a factor of 5.7 ×.