X-HYBRIDJOIN for Near-real-time Data Warehousing

Abstract. In order to make timely and effective decisions, businesses need the latest information from data warehouse repositories. To keep these repositories up-to-date with respect to end user updates, near-real-time data integration is required. An important phase in near-real-time data integration is data transformation where the stream of up-dates is joined with disk-based master data. The stream-based algorithm Mesh Join (MESHJOIN) has been proposed to amortize disk access. MESHJOIN makes no assumptions about the data distribution. In real world applications, however, skewed distributions can be found, e.g, cer-tain products are sold more frequently than the remainder of the prod-ucts. The question arises, how much does MESHJOIN loose in terms of performance by not adapting to data skew. In this paper we per-form a rigorous experimental study analyzing the possible performance improvements while considering typical data distributions. For this pur-pose we design an algorithm Extended Hybrid Join (X-HYBRIDJOIN) that is complementary to MESHJOIN in that it can adapt to data skew and stores parts of the master data in memory permanently, reducing the disk access overhead significantly. We compare the performance of X-HYBRIDJOIN against the performance of MESHJOIN. We take sev-eral precautions to make sure the comparison is adequate and focuses on the utilization of data skew. The experiments show that considering data skew offers substantial room for performance gains that cannot be used by non-adaptive approaches such as MESHJOIN