Improving join performance for skewed databases

The largest queries in data warehouses and decision support systems use hybrid hash join to relate information in multiple tables. Hybrid hash join functions independently of the data distributions of the join relations. Real-world data sets are not uniformly distributed and often contain significant skew. Although partition skew has been studied for hash joins, no prior work has examined how exploiting data skew can improve performance. In this paper, we present histo join, a join algorithm that uses histograms to identify data skew and improve join performance. Experimental results show that for skewed data sets histo join performs significantly fewer I/O operations and is faster by 20 to 60% than hybrid hash join.