Challenges in Join Optimization

Summary

✍🏼 About The Author: Seaven He, StarRocks Committer, Engineer at Celerdata Joins are the hardest part of OLAP. Many systems can’t run them efficiently at scale, so teams denormalize into wide tables instead, 10× their storage, dealing with complex stream processing pipelines, and painfully slow and expensive schema evolution that triggers large backfills. StarRocks takes the opposite approach: keep data normalized and make joins fast enough to run on the fly. The challenge is the plan. In a distributed system, the join search space is huge, and a good plan can be orders of magnitude faster. This deep dive explains how StarRocks’ cost-based optimizer makes that possible, in four parts: join fundamentals and optimization challenges, logical join optimizations, join reordering, and distributed join planning. Finally, we examine real-world case studies from NAVER, Demandbase, and Shopee to illustrate how efficient join execution delivers tangible business value. Join Fundamentals and Optimization Challenges 1.1 Join Types The diagram above illustrates several common join types: Cross Join: Produces a Cartesian product between the left and right tables. Full / Left / Right Outer Join: For rows that do not find a match, outer joins return results with NULL values filled in according to the join semantics—on both tables (full), the left table (left), or the right table (right). Anti Join: Returns rows that do not have a matching counterpart in the join relationship. Anti-joins typically appear in query plans for NOT IN or NOT EXISTS subqueries. Semi Join: The opposite of an anti-join, it returns only rows that do have a match in the join relationship, without producing duplicate result rows from the matching side. Inner Join: Returns the intersection of the left and right tables. Based on the join condition, it may generate one-to-many result rows. 1.2 Challenges in Join Optimization Join performance optimization generally falls into two areas: improving the efficiency of ...