Figure 3.4: Complexity of Join of n Relations

           To get an idea of the size of the search space involved in join queries,¹³ figure 3.4 lists number of groups, the number of (logical) expressions and the number of (logical) query trees in the final (logical) memo for a join of n relations. The second row in the table (join of 3 relations) corresponds to the logical memo structure of figure 3.3, which has 7 groups, 15 logical expressions and includes 12 query trees.

---

13. The numbers shown in figure 3.4 are for bushy joins where Cartesian products are allowed -- that is they are for the complete (largest possible) join order search space. This is the logical search space in that only the logical join operator is considered.

3. Fundamental Concepts:	<Models> <Log> <Query Trees> <Groups> <Memo> <Phys> <Item> <Rules> <Opt Stages> <Find Best> <Complexity>   3.1: EQJOIN     3.2a: Query Tree     3.2b: Equiv.     3.3a: Init Memo     3.3b: Memo     3.3c: Key     3.4: Complexity     3.5: Phys Memo     3.6: Plan     3.7: Pred.     3.8: Op Types     3.9: Rule

		Page 15