@@ -3,25 +3,24 @@ Summary
33
44The optimizer generates optimial query plans by doing several steps:
55
6- 1) Take each relation in a query, and make a RelOptInfo structure for it.
7- Find each way of accessing the relation, called a Path, including
8- sequential and index scans, and add it to the RelOptInfo.path_order
9- list.
6+ 1) Take each relation in a query, and make a RelOptInfo structure for
7+ it. Find each way of accessing the relation, called a Path, including
8+ sequential and index scans, and add it to RelOptInfo.pathlist.
109
11102) Join each RelOptInfo to each other RelOptInfo as specified in the
1211WHERE clause. At this point each RelOptInfo is a single relation, so
13- you are joining every relation to every relationit is joinedto in the
14- WHERE clause.
12+ you are joining every relation to every relationas joined in the WHERE
13+ clause.
1514
1615Joins occur using two RelOptInfos. One is outer, the other inner.
1716Outers drive lookups of values in the inner. In a nested loop, lookups
1817of values in the inner occur by scanning to find each matching inner
19- row. In a mergejoin, inner rows are ordered, and are accessed in order,
20- so only one scan of inner is required to perform the entire join. In a
21- hashjoin, inner rows are hashed for lookups.
18+ row. In a mergejoin, innerand outer rows are ordered, and are accessed
19+ in order, so only one scan of inner is required to perform the entire
20+ join. In a hashjoin, inner rows are hashed for lookups.
2221
2322Each unique join combination becomes a new RelOptInfo. The RelOptInfo
24- is now the joining of two relations. RelOptInfo.path_order are various
23+ is now the joining of two relations. RelOptInfo.pathlist are various
2524paths to create the joined result, having different orderings depending
2625on the join method used.
2726
@@ -30,27 +29,34 @@ a new relation added to each RelOptInfo. This continues until all
3029relations have been joined into one RelOptInfo, and the cheapest Path is
3130chosen.
3231
33- SELECT *
34- FROM tab1, tab2, tab3, tab4
35- WHERE tab1.col = tab2.col AND
36- tab2.col = tab3.col AND
37- tab3.col = tab4.col
38-
39- Tables 1, 2, 3, and 4 are joined as:
40- {1 2},{2 3},{3 4}
41- {1 2 3},{2 3 4}
42- {1 2 3 4}
43-
44- SELECT *
45- FROM tab1, tab2, tab3, tab4
46- WHERE tab1.col = tab2.col AND
47- tab1.col = tab3.col AND
48- tab1.col = tab4.col
49-
50- Tables 1, 2, 3, and 4 are joined as:
51- {1 2},{1 3},{1 4}
52- {1 2 3},{1 3 4},{1,2,4}
53- {1 2 3 4}
32+ SELECT *
33+ FROM tab1, tab2, tab3, tab4
34+ WHERE tab1.col = tab2.col AND
35+ tab2.col = tab3.col AND
36+ tab3.col = tab4.col
37+
38+ Tables 1, 2, 3, and 4 are joined as:
39+ {1 2},{2 3},{3 4}
40+ {1 2 3},{2 3 4}
41+ {1 2 3 4}
42+
43+ SELECT *
44+ FROM tab1, tab2, tab3, tab4
45+ WHERE tab1.col = tab2.col AND
46+ tab1.col = tab3.col AND
47+ tab1.col = tab4.col
48+
49+ Tables 1, 2, 3, and 4 are joined as:
50+ {1 2},{1 3},{1 4}
51+ {1 2 3},{1 3 4},{1,2,4}
52+ {1 2 3 4}
53+
54+ In the default left-handed joins, each RelOptInfo adds one
55+ single-relation RelOptInfo in each join pass, and the added RelOptInfo
56+ is always the inner relation in the join. In right-handed joins, the
57+ added RelOptInfo is the outer relation in the join. In bushy plans,
58+ multi-relation RelOptInfo's can be joined to other multi-relation
59+ RelOptInfo's.
5460
5561Optimizer Functions
5662-------------------
@@ -95,28 +101,28 @@ planner()
95101---subplanner()
96102 make list of relations in target
97103 make list of relations in where clause
98-
99- findwhich relations can do merge sort and hash joins
100- ----find_paths ()
101- find scan and all index paths for each relation not yet joined
102- one relation, return
103- find selectivity of columns used in joins
104- -----find_join_paths ()
104+ split up the qual into restrictions (a=1) and joins (b=c)
105+ findrelation clauses can do merge sort and hash joins
106+ ----make_one_rel ()
107+ set_base_rel_pathlist()
108+ find scan and all index paths for each relation
109+
110+ -----make_one_rel_by_joins ()
105111 jump to geqo if needed
106112 again:
107- find_join_rels ():
113+ make_rels_by_joins ():
108114 for each joinrel:
109- find_clause_joins ()
110- for eachjoin on joinrel :
115+ make_rels_by_clause_joins ()
116+ for eachrel's joininfo list :
111117 if a join from the join clause adds only one relation, do the join
112- orfind_clauseless_joins ()
113- find_all_join_paths ()
114- generatepaths( nested,sortmerge) forjoins found in find_join_rels()
115- prune_joinrels ()
116- remove from the join list therelation we just added to each join
117- prune_rel_paths ()
118- set cheapestand perhaps remove unordered path, recompute table sizes
119- ifwe have not done all the tables, go to again:
118+ ormake_rels_by_clauseless_joins ()
119+ update_rels_pathlist_for_joins ()
120+ generate nested,merge,hash join paths fornew rel's created above
121+ merge_rels_with_same_relids ()
122+ merge RelOptInfo paths that have thesame relids because of joins
123+ rels_set_cheapest ()
124+ set cheapest path
125+ ifall relations in one RelOptInfo, return
120126 do group(GROUP)
121127 do aggregate
122128 put back constants
@@ -129,17 +135,15 @@ planner()
129135Optimizer Structures
130136--------------------
131137
132- RelOptInfo- Every relation
133-
134- RestrictInfo- restriction clauses
135- JoinInfo- join combinations
136-
137- Path- every way to access a relation(sequential, index)
138- IndexPath- index scans
138+ RelOptInfo - a relation or joined relations
139139
140- JoinPath- joins
141- MergePath- merge joins
142- HashPath- hash joins
140+ RestrictInfo - restriction clauses
141+ JoinInfo - join clauses
143142
144- PathOrder- every ordering type (sort, merge of relations)
143+ Path - every way to generate a RelOptInfo(sequential,index,joins)
144+ IndexPath - index scans
145+ NestPath - nested joins
146+ MergePath - merge joins
147+ HashPath - hash joins
145148
149+ PathOrder - every ordering type (sort, merge of relations)