| 1 |
src/backend/optimizer/README |
| 2 |
|
| 3 |
Optimizer |
| 4 |
========= |
| 5 |
|
| 6 |
These directories take the Query structure returned by the parser, and |
| 7 |
generate a plan used by the executor. The /plan directory generates the |
| 8 |
actual output plan, the /path code generates all possible ways to join the |
| 9 |
tables, and /prep handles various preprocessing steps for special cases. |
| 10 |
/util is utility stuff. /geqo is the separate "genetic optimization" planner |
| 11 |
--- it does a semi-random search through the join tree space, rather than |
| 12 |
exhaustively considering all possible join trees. (But each join considered |
| 13 |
by /geqo is given to /path to create paths for, so we consider all possible |
| 14 |
implementation paths for each specific join pair even in GEQO mode.) |
| 15 |
|
| 16 |
|
| 17 |
Paths and Join Pairs |
| 18 |
-------------------- |
| 19 |
|
| 20 |
During the planning/optimizing process, we build "Path" trees representing |
| 21 |
the different ways of doing a query. We select the cheapest Path that |
| 22 |
generates the desired relation and turn it into a Plan to pass to the |
| 23 |
executor. (There is pretty nearly a one-to-one correspondence between the |
| 24 |
Path and Plan trees, but Path nodes omit info that won't be needed during |
| 25 |
planning, and include info needed for planning that won't be needed by the |
| 26 |
executor.) |
| 27 |
|
| 28 |
The optimizer builds a RelOptInfo structure for each base relation used in |
| 29 |
the query. Base rels are either primitive tables, or subquery subselects |
| 30 |
that are planned via a separate recursive invocation of the planner. A |
| 31 |
RelOptInfo is also built for each join relation that is considered during |
| 32 |
planning. A join rel is simply a combination of base rels. There is only |
| 33 |
one join RelOptInfo for any given set of baserels --- for example, the join |
| 34 |
{A B C} is represented by the same RelOptInfo no matter whether we build it |
| 35 |
by joining A and B first and then adding C, or joining B and C first and |
| 36 |
then adding A, etc. These different means of building the joinrel are |
| 37 |
represented as Paths. For each RelOptInfo we build a list of Paths that |
| 38 |
represent plausible ways to implement the scan or join of that relation. |
| 39 |
Once we've considered all the plausible Paths for a rel, we select the one |
| 40 |
that is cheapest according to the planner's cost estimates. The final plan |
| 41 |
is derived from the cheapest Path for the RelOptInfo that includes all the |
| 42 |
base rels of the query. |
| 43 |
|
| 44 |
Possible Paths for a primitive table relation include plain old sequential |
| 45 |
scan, plus index scans for any indexes that exist on the table, plus bitmap |
| 46 |
index scans using one or more indexes. Specialized RTE types, such as |
| 47 |
function RTEs, may have only one possible Path. |
| 48 |
|
| 49 |
Joins always occur using two RelOptInfos. One is outer, the other inner. |
| 50 |
Outers drive lookups of values in the inner. In a nested loop, lookups of |
| 51 |
values in the inner occur by scanning the inner path once per outer tuple |
| 52 |
to find each matching inner row. In a mergejoin, inner and outer rows are |
| 53 |
ordered, and are accessed in order, so only one scan is required to perform |
| 54 |
the entire join: both inner and outer paths are scanned in-sync. (There's |
| 55 |
not a lot of difference between inner and outer in a mergejoin...) In a |
| 56 |
hashjoin, the inner is scanned first and all its rows are entered in a |
| 57 |
hashtable, then the outer is scanned and for each row we lookup the join |
| 58 |
key in the hashtable. |
| 59 |
|
| 60 |
A Path for a join relation is actually a tree structure, with the topmost |
| 61 |
Path node representing the last-applied join method. It has left and right |
| 62 |
subpaths that represent the scan or join methods used for the two input |
| 63 |
relations. |
| 64 |
|
| 65 |
|
| 66 |
Join Tree Construction |
| 67 |
---------------------- |
| 68 |
|
| 69 |
The optimizer generates optimal query plans by doing a more-or-less |
| 70 |
exhaustive search through the ways of executing the query. The best Path |
| 71 |
tree is found by a recursive process: |
| 72 |
|
| 73 |
1) Take each base relation in the query, and make a RelOptInfo structure |
| 74 |
for it. Find each potentially useful way of accessing the relation, |
| 75 |
including sequential and index scans, and make Paths representing those |
| 76 |
ways. All the Paths made for a given relation are placed in its |
| 77 |
RelOptInfo.pathlist. (Actually, we discard Paths that are obviously |
| 78 |
inferior alternatives before they ever get into the pathlist --- what |
| 79 |
ends up in the pathlist is the cheapest way of generating each potentially |
| 80 |
useful sort ordering and parameterization of the relation.) Also create a |
| 81 |
RelOptInfo.joininfo list including all the join clauses that involve this |
| 82 |
relation. For example, the WHERE clause "tab1.col1 = tab2.col1" generates |
| 83 |
entries in both tab1 and tab2's joininfo lists. |
| 84 |
|
| 85 |
If we have only a single base relation in the query, we are done. |
| 86 |
Otherwise we have to figure out how to join the base relations into a |
| 87 |
single join relation. |
| 88 |
|
| 89 |
2) Normally, any explicit JOIN clauses are "flattened" so that we just |
| 90 |
have a list of relations to join. However, FULL OUTER JOIN clauses are |
| 91 |
never flattened, and other kinds of JOIN might not be either, if the |
| 92 |
flattening process is stopped by join_collapse_limit or from_collapse_limit |
| 93 |
restrictions. Therefore, we end up with a planning problem that contains |
| 94 |
lists of relations to be joined in any order, where any individual item |
| 95 |
might be a sub-list that has to be joined together before we can consider |
| 96 |
joining it to its siblings. We process these sub-problems recursively, |
| 97 |
bottom up. Note that the join list structure constrains the possible join |
| 98 |
orders, but it doesn't constrain the join implementation method at each |
| 99 |
join (nestloop, merge, hash), nor does it say which rel is considered outer |
| 100 |
or inner at each join. We consider all these possibilities in building |
| 101 |
Paths. We generate a Path for each feasible join method, and select the |
| 102 |
cheapest Path. |
| 103 |
|
| 104 |
For each planning problem, therefore, we will have a list of relations |
| 105 |
that are either base rels or joinrels constructed per sub-join-lists. |
| 106 |
We can join these rels together in any order the planner sees fit. |
| 107 |
The standard (non-GEQO) planner does this as follows: |
| 108 |
|
| 109 |
Consider joining each RelOptInfo to each other RelOptInfo for which there |
| 110 |
is a usable joinclause, and generate a Path for each possible join method |
| 111 |
for each such pair. (If we have a RelOptInfo with no join clauses, we have |
| 112 |
no choice but to generate a clauseless Cartesian-product join; so we |
| 113 |
consider joining that rel to each other available rel. But in the presence |
| 114 |
of join clauses we will only consider joins that use available join |
| 115 |
clauses. Note that join-order restrictions induced by outer joins and |
| 116 |
IN/EXISTS clauses are also checked, to ensure that we find a workable join |
| 117 |
order in cases where those restrictions force a clauseless join to be done.) |
| 118 |
|
| 119 |
If we only had two relations in the list, we are done: we just pick |
| 120 |
the cheapest path for the join RelOptInfo. If we had more than two, we now |
| 121 |
need to consider ways of joining join RelOptInfos to each other to make |
| 122 |
join RelOptInfos that represent more than two list items. |
| 123 |
|
| 124 |
The join tree is constructed using a "dynamic programming" algorithm: |
| 125 |
in the first pass (already described) we consider ways to create join rels |
| 126 |
representing exactly two list items. The second pass considers ways |
| 127 |
to make join rels that represent exactly three list items; the next pass, |
| 128 |
four items, etc. The last pass considers how to make the final join |
| 129 |
relation that includes all list items --- obviously there can be only one |
| 130 |
join rel at this top level, whereas there can be more than one join rel |
| 131 |
at lower levels. At each level we use joins that follow available join |
| 132 |
clauses, if possible, just as described for the first level. |
| 133 |
|
| 134 |
For example: |
| 135 |
|
| 136 |
SELECT * |
| 137 |
FROM tab1, tab2, tab3, tab4 |
| 138 |
WHERE tab1.col = tab2.col AND |
| 139 |
tab2.col = tab3.col AND |
| 140 |
tab3.col = tab4.col |
| 141 |
|
| 142 |
Tables 1, 2, 3, and 4 are joined as: |
| 143 |
{1 2},{2 3},{3 4} |
| 144 |
{1 2 3},{2 3 4} |
| 145 |
{1 2 3 4} |
| 146 |
|
| 147 |
SELECT * |
| 148 |
FROM tab1, tab2, tab3, tab4 |
| 149 |
WHERE tab1.col = tab2.col AND |
| 150 |
tab1.col = tab3.col AND |
| 151 |
tab1.col = tab4.col |
| 152 |
|
| 153 |
Tables 1, 2, 3, and 4 are joined as: |
| 154 |
{1 2},{1 3},{1 4} |
| 155 |
{1 2 3},{1 3 4},{1 2 4} |
| 156 |
{1 2 3 4} |
| 157 |
|
| 158 |
In each of these examples, other join-order possibilities will be excluded |
| 159 |
for lack of join clauses. (In reality, use of EquivalenceClasses would |
| 160 |
allow us to deduce additional join clauses that allow more join orders, |
| 161 |
but here we ignore that to preserve the simplicity of the examples.) |
| 162 |
|
| 163 |
We consider left-handed plans (the outer rel of an upper join is a joinrel, |
| 164 |
but the inner is always a single list item); right-handed plans (outer rel |
| 165 |
is always a single item); and bushy plans (both inner and outer can be |
| 166 |
joins themselves). For example, when building {1 2 3 4} we consider |
| 167 |
joining {1 2 3} to {4} (left-handed), {4} to {1 2 3} (right-handed), and |
| 168 |
{1 2} to {3 4} (bushy), among other choices. Although the jointree |
| 169 |
scanning code produces these potential join combinations one at a time, |
| 170 |
all the ways to produce the same set of joined base rels will share the |
| 171 |
same RelOptInfo, so the paths produced from different join combinations |
| 172 |
that produce equivalent joinrels will compete in add_path(). |
| 173 |
|
| 174 |
The dynamic-programming approach has an important property that's not |
| 175 |
immediately obvious: we will finish constructing all paths for a given |
| 176 |
relation before we construct any paths for relations containing that rel. |
| 177 |
This means that we can reliably identify the "cheapest path" for each rel |
| 178 |
before higher-level relations need to know that. Also, we can safely |
| 179 |
discard a path when we find that another path for the same rel is better, |
| 180 |
without worrying that maybe there is already a reference to that path in |
| 181 |
some higher-level join path. Without this, memory management for paths |
| 182 |
would be much more complicated. |
| 183 |
|
| 184 |
Once we have built the final join rel, we use either the cheapest path |
| 185 |
for it or the cheapest path with the desired ordering (if that's cheaper |
| 186 |
than applying a sort to the cheapest other path). |
| 187 |
|
| 188 |
If the query contains one-sided outer joins (LEFT or RIGHT joins), or |
| 189 |
IN or EXISTS WHERE clauses that were converted to semijoins or antijoins, |
| 190 |
then some of the possible join orders may be illegal. These are excluded |
| 191 |
by having join_is_legal consult a side list of such "special" joins to see |
| 192 |
whether a proposed join is illegal. (The same consultation allows it to |
| 193 |
see which join style should be applied for a valid join, ie, JOIN_INNER, |
| 194 |
JOIN_LEFT, etc.) |
| 195 |
|
| 196 |
|
| 197 |
Valid OUTER JOIN Optimizations |
| 198 |
------------------------------ |
| 199 |
|
| 200 |
The planner's treatment of outer join reordering is based on the following |
| 201 |
identities: |
| 202 |
|
| 203 |
1. (A leftjoin B on (Pab)) innerjoin C on (Pac) |
| 204 |
= (A innerjoin C on (Pac)) leftjoin B on (Pab) |
| 205 |
|
| 206 |
where Pac is a predicate referencing A and C, etc (in this case, clearly |
| 207 |
Pac cannot reference B, or the transformation is nonsensical). |
| 208 |
|
| 209 |
2. (A leftjoin B on (Pab)) leftjoin C on (Pac) |
| 210 |
= (A leftjoin C on (Pac)) leftjoin B on (Pab) |
| 211 |
|
| 212 |
3. (A leftjoin B on (Pab)) leftjoin C on (Pbc) |
| 213 |
= A leftjoin (B leftjoin C on (Pbc)) on (Pab) |
| 214 |
|
| 215 |
Identity 3 only holds if predicate Pbc must fail for all-null B rows |
| 216 |
(that is, Pbc is strict for at least one column of B). If Pbc is not |
| 217 |
strict, the first form might produce some rows with nonnull C columns |
| 218 |
where the second form would make those entries null. |
| 219 |
|
| 220 |
RIGHT JOIN is equivalent to LEFT JOIN after switching the two input |
| 221 |
tables, so the same identities work for right joins. |
| 222 |
|
| 223 |
An example of a case that does *not* work is moving an innerjoin into or |
| 224 |
out of the nullable side of an outer join: |
| 225 |
|
| 226 |
A leftjoin (B join C on (Pbc)) on (Pab) |
| 227 |
!= (A leftjoin B on (Pab)) join C on (Pbc) |
| 228 |
|
| 229 |
SEMI joins work a little bit differently. A semijoin can be reassociated |
| 230 |
into or out of the lefthand side of another semijoin, left join, or |
| 231 |
antijoin, but not into or out of the righthand side. Likewise, an inner |
| 232 |
join, left join, or antijoin can be reassociated into or out of the |
| 233 |
lefthand side of a semijoin, but not into or out of the righthand side. |
| 234 |
|
| 235 |
ANTI joins work approximately like LEFT joins, except that identity 3 |
| 236 |
fails if the join to C is an antijoin (even if Pbc is strict, and in |
| 237 |
both the cases where the other join is a leftjoin and where it is an |
| 238 |
antijoin). So we can't reorder antijoins into or out of the RHS of a |
| 239 |
leftjoin or antijoin, even if the relevant clause is strict. |
| 240 |
|
| 241 |
The current code does not attempt to re-order FULL JOINs at all. |
| 242 |
FULL JOIN ordering is enforced by not collapsing FULL JOIN nodes when |
| 243 |
translating the jointree to "joinlist" representation. Other types of |
| 244 |
JOIN nodes are normally collapsed so that they participate fully in the |
| 245 |
join order search. To avoid generating illegal join orders, the planner |
| 246 |
creates a SpecialJoinInfo node for each non-inner join, and join_is_legal |
| 247 |
checks this list to decide if a proposed join is legal. |
| 248 |
|
| 249 |
What we store in SpecialJoinInfo nodes are the minimum sets of Relids |
| 250 |
required on each side of the join to form the outer join. Note that |
| 251 |
these are minimums; there's no explicit maximum, since joining other |
| 252 |
rels to the OJ's syntactic rels may be legal. Per identities 1 and 2, |
| 253 |
non-FULL joins can be freely associated into the lefthand side of an |
| 254 |
OJ, but in some cases they can't be associated into the righthand side. |
| 255 |
So the restriction enforced by join_is_legal is that a proposed join |
| 256 |
can't join a rel within or partly within an RHS boundary to one outside |
| 257 |
the boundary, unless the proposed join is a LEFT join that can associate |
| 258 |
into the SpecialJoinInfo's RHS using identity 3. |
| 259 |
|
| 260 |
The use of minimum Relid sets has some pitfalls; consider a query like |
| 261 |
A leftjoin (B leftjoin (C innerjoin D) on (Pbcd)) on Pa |
| 262 |
where Pa doesn't mention B/C/D at all. In this case a naive computation |
| 263 |
would give the upper leftjoin's min LHS as {A} and min RHS as {C,D} (since |
| 264 |
we know that the innerjoin can't associate out of the leftjoin's RHS, and |
| 265 |
enforce that by including its relids in the leftjoin's min RHS). And the |
| 266 |
lower leftjoin has min LHS of {B} and min RHS of {C,D}. Given such |
| 267 |
information, join_is_legal would think it's okay to associate the upper |
| 268 |
join into the lower join's RHS, transforming the query to |
| 269 |
B leftjoin (A leftjoin (C innerjoin D) on Pa) on (Pbcd) |
| 270 |
which yields totally wrong answers. We prevent that by forcing the min RHS |
| 271 |
for the upper join to include B. This is perhaps overly restrictive, but |
| 272 |
such cases don't arise often so it's not clear that it's worth developing a |
| 273 |
more complicated system. |
| 274 |
|
| 275 |
|
| 276 |
Pulling Up Subqueries |
| 277 |
--------------------- |
| 278 |
|
| 279 |
As we described above, a subquery appearing in the range table is planned |
| 280 |
independently and treated as a "black box" during planning of the outer |
| 281 |
query. This is necessary when the subquery uses features such as |
| 282 |
aggregates, GROUP, or DISTINCT. But if the subquery is just a simple |
| 283 |
scan or join, treating the subquery as a black box may produce a poor plan |
| 284 |
compared to considering it as part of the entire plan search space. |
| 285 |
Therefore, at the start of the planning process the planner looks for |
| 286 |
simple subqueries and pulls them up into the main query's jointree. |
| 287 |
|
| 288 |
Pulling up a subquery may result in FROM-list joins appearing below the top |
| 289 |
of the join tree. Each FROM-list is planned using the dynamic-programming |
| 290 |
search method described above. |
| 291 |
|
| 292 |
If pulling up a subquery produces a FROM-list as a direct child of another |
| 293 |
FROM-list, then we can merge the two FROM-lists together. Once that's |
| 294 |
done, the subquery is an absolutely integral part of the outer query and |
| 295 |
will not constrain the join tree search space at all. However, that could |
| 296 |
result in unpleasant growth of planning time, since the dynamic-programming |
| 297 |
search has runtime exponential in the number of FROM-items considered. |
| 298 |
Therefore, we don't merge FROM-lists if the result would have too many |
| 299 |
FROM-items in one list. |
| 300 |
|
| 301 |
|
| 302 |
Vars and PlaceHolderVars |
| 303 |
------------------------ |
| 304 |
|
| 305 |
A Var node is simply the parse-tree representation of a table column |
| 306 |
reference. However, in the presence of outer joins, that concept is |
| 307 |
more subtle than it might seem. We need to distinguish the values of |
| 308 |
a Var "above" and "below" any outer join that could force the Var to |
| 309 |
null. As an example, consider |
| 310 |
|
| 311 |
SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE foo(t2.z) |
| 312 |
|
| 313 |
(Assume foo() is not strict, so that we can't reduce the left join to |
| 314 |
a plain join.) A naive implementation might try to push the foo(t2.z) |
| 315 |
call down to the scan of t2, but that is not correct because |
| 316 |
(a) what foo() should actually see for a null-extended join row is NULL, |
| 317 |
and (b) if foo() returns false, we should suppress the t1 row from the |
| 318 |
join altogether, not emit it with a null-extended t2 row. On the other |
| 319 |
hand, it *would* be correct (and desirable) to push that call down to |
| 320 |
the scan level if the query were |
| 321 |
|
| 322 |
SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y AND foo(t2.z)) |
| 323 |
|
| 324 |
This motivates considering "t2.z" within the left join's ON clause |
| 325 |
to be a different value from "t2.z" outside the JOIN clause. The |
| 326 |
former can be identified with t2.z as seen at the relation scan level, |
| 327 |
but the latter can't. |
| 328 |
|
| 329 |
Another example occurs in connection with EquivalenceClasses (discussed |
| 330 |
below). Given |
| 331 |
|
| 332 |
SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE t1.x = 42 |
| 333 |
|
| 334 |
we would like to use the EquivalenceClass mechanisms to derive "t2.y = 42" |
| 335 |
to use as a restriction clause for the scan of t2. (That works, because t2 |
| 336 |
rows having y different from 42 cannot affect the query result.) However, |
| 337 |
it'd be wrong to conclude that t2.y will be equal to t1.x in every joined |
| 338 |
row. Part of the solution to this problem is to deem that "t2.y" in the |
| 339 |
ON clause refers to the relation-scan-level value of t2.y, but not to the |
| 340 |
value that y will have in joined rows, where it might be NULL rather than |
| 341 |
equal to t1.x. |
| 342 |
|
| 343 |
Therefore, Var nodes are decorated with "varnullingrels", which are sets |
| 344 |
of the rangetable indexes of outer joins that potentially null the Var |
| 345 |
at the point where it appears in the query. (Using a set, not an ordered |
| 346 |
list, is fine since it doesn't matter which join forced the value to null; |
| 347 |
and that avoids having to change the representation when we consider |
| 348 |
different outer-join orders.) In the examples above, all occurrences of |
| 349 |
t1.x would have empty varnullingrels, since the left join doesn't null t1. |
| 350 |
The t2 references within the JOIN ON clauses would also have empty |
| 351 |
varnullingrels. But outside the JOIN clauses, any Vars referencing t2 |
| 352 |
would have varnullingrels containing the index of the JOIN's rangetable |
| 353 |
entry (RTE), so that they'd be understood as potentially different from |
| 354 |
the t2 values seen at scan level. Labeling t2.z in the WHERE clause with |
| 355 |
the JOIN's RT index lets us recognize that that occurrence of foo(t2.z) |
| 356 |
cannot be pushed down to the t2 scan level: we cannot evaluate that value |
| 357 |
at the scan level, but only after the join has been done. |
| 358 |
|
| 359 |
For LEFT and RIGHT outer joins, only Vars coming from the nullable side |
| 360 |
of the join are marked with that join's RT index. For FULL joins, Vars |
| 361 |
from both inputs are marked. (Such marking doesn't let us tell which |
| 362 |
side of the full join a Var came from; but that information can be found |
| 363 |
elsewhere at need.) |
| 364 |
|
| 365 |
Notionally, a Var having nonempty varnullingrels can be thought of as |
| 366 |
CASE WHEN any-of-these-outer-joins-produced-a-null-extended-row |
| 367 |
THEN NULL |
| 368 |
ELSE the-scan-level-value-of-the-column |
| 369 |
END |
| 370 |
It's only notional, because no such calculation is ever done explicitly. |
| 371 |
In a finished plan, Vars occurring in scan-level plan nodes represent |
| 372 |
the actual table column values, but upper-level Vars are always |
| 373 |
references to outputs of lower-level plan nodes. When a join node emits |
| 374 |
a null-extended row, it just returns nulls for the relevant output |
| 375 |
columns rather than copying up values from its input. Because we don't |
| 376 |
ever have to do this calculation explicitly, it's not necessary to |
| 377 |
distinguish which side of an outer join got null-extended, which'd |
| 378 |
otherwise be essential information for FULL JOIN cases. |
| 379 |
|
| 380 |
Outer join identity 3 (discussed above) complicates this picture |
| 381 |
a bit. In the form |
| 382 |
A leftjoin (B leftjoin C on (Pbc)) on (Pab) |
| 383 |
all of the Vars in clauses Pbc and Pab will have empty varnullingrels, |
| 384 |
but if we start with |
| 385 |
(A leftjoin B on (Pab)) leftjoin C on (Pbc) |
| 386 |
then the parser will have marked Pbc's B Vars with the A/B join's |
| 387 |
RT index, making this form artificially different from the first. |
| 388 |
For discussion's sake, let's denote this marking with a star: |
| 389 |
(A leftjoin B on (Pab)) leftjoin C on (Pb*c) |
| 390 |
To cope with this, once we have detected that commuting these joins |
| 391 |
is legal, we generate both the Pbc and Pb*c forms of that ON clause, |
| 392 |
by either removing or adding the first join's RT index in the B Vars |
| 393 |
that the parser created. While generating paths for a plan step that |
| 394 |
joins B and C, we include as a relevant join qual only the form that |
| 395 |
is appropriate depending on whether A has already been joined to B. |
| 396 |
|
| 397 |
It's also worth noting that identity 3 makes "the left join's RT index" |
| 398 |
itself a bit of a fuzzy concept, since the syntactic scope of each join |
| 399 |
RTE will depend on which form was produced by the parser. We resolve |
| 400 |
this by considering that a left join's identity is determined by its |
| 401 |
minimum set of right-hand-side input relations. In both forms allowed |
| 402 |
by identity 3, we can identify the first join as having minimum RHS B |
| 403 |
and the second join as having minimum RHS C. |
| 404 |
|
| 405 |
Another thing to notice is that C Vars appearing outside the nested |
| 406 |
JOIN clauses will be marked as nulled by both left joins if the |
| 407 |
original parser input was in the first form of identity 3, but if the |
| 408 |
parser input was in the second form, such Vars will only be marked as |
| 409 |
nulled by the second join. This is not really a semantic problem: |
| 410 |
such Vars will be marked the same way throughout the upper part of the |
| 411 |
query, so they will all look equal() which is correct; and they will not |
| 412 |
look equal() to any C Var appearing in the JOIN ON clause or below these |
| 413 |
joins. However, when building Vars representing the outputs of join |
| 414 |
relations, we need to ensure that their varnullingrels are set to |
| 415 |
values consistent with the syntactic join order, so that they will |
| 416 |
appear equal() to pre-existing Vars in the upper part of the query. |
| 417 |
|
| 418 |
Outer joins also complicate handling of subquery pull-up. Consider |
| 419 |
|
| 420 |
SELECT ..., ss.x FROM tab1 |
| 421 |
LEFT JOIN (SELECT *, 42 AS x FROM tab2) ss ON ... |
| 422 |
|
| 423 |
We want to be able to pull up the subquery as discussed previously, |
| 424 |
but we can't just replace the "ss.x" Var in the top-level SELECT list |
| 425 |
with the constant 42. That'd result in always emitting 42, rather |
| 426 |
than emitting NULL in null-extended join rows. |
| 427 |
|
| 428 |
To solve this, we introduce the concept of PlaceHolderVars. |
| 429 |
A PlaceHolderVar is somewhat like a Var, in that its value originates |
| 430 |
at a relation scan level and can then be forced to null by higher-level |
| 431 |
outer joins; hence PlaceHolderVars carry a set of nulling rel IDs just |
| 432 |
like Vars. Unlike a Var, whose original value comes from a table, |
| 433 |
a PlaceHolderVar's original value is defined by a query-determined |
| 434 |
expression ("42" in this example); so we represent the PlaceHolderVar |
| 435 |
as a node with that expression as child. We insert a PlaceHolderVar |
| 436 |
whenever subquery pullup needs to replace a subquery-referencing Var |
| 437 |
that has nonempty varnullingrels with an expression that is not simply a |
| 438 |
Var. (When the replacement expression is a pulled-up Var, we can just |
| 439 |
add the replaced Var's varnullingrels to its set. Also, if the replaced |
| 440 |
Var has empty varnullingrels, we don't need a PlaceHolderVar: there is |
| 441 |
nothing that'd force the value to null, so the pulled-up expression is |
| 442 |
fine to use as-is.) In a finished plan, a PlaceHolderVar becomes just |
| 443 |
the contained expression at whatever plan level it's supposed to be |
| 444 |
evaluated at, and then upper-level occurrences are replaced by Var |
| 445 |
references to that output column of the lower plan level. That causes |
| 446 |
the value to go to null when appropriate at an outer join, in the same |
| 447 |
way as for normal Vars. Thus, PlaceHolderVars are never seen outside |
| 448 |
the planner. |
| 449 |
|
| 450 |
PlaceHolderVars (PHVs) are more complicated than Vars in another way: |
| 451 |
their original value might need to be calculated at a join, not a |
| 452 |
base-level relation scan. This can happen when a pulled-up subquery |
| 453 |
contains a join. Because of this, a PHV can create a join order |
| 454 |
constraint that wouldn't otherwise exist, to ensure that it can |
| 455 |
be calculated before it is used. A PHV's expression can also contain |
| 456 |
LATERAL references, adding complications that are discussed below. |
| 457 |
|
| 458 |
|
| 459 |
Relation Identification and Qual Clause Placement |
| 460 |
------------------------------------------------- |
| 461 |
|
| 462 |
A qual clause obtained from WHERE or JOIN/ON can be enforced at the lowest |
| 463 |
scan or join level that includes all relations used in the clause. For |
| 464 |
this purpose we consider that outer joins listed in varnullingrels or |
| 465 |
phnullingrels are used in the clause, since we can't compute the qual's |
| 466 |
result correctly until we know whether such Vars have gone to null. |
| 467 |
|
| 468 |
The one exception to this general rule is that a non-degenerate outer |
| 469 |
JOIN/ON qual (one that references the non-nullable side of the join) |
| 470 |
cannot be enforced below that join, even if it doesn't reference the |
| 471 |
nullable side. Pushing it down into the non-nullable side would result |
| 472 |
in rows disappearing from the join's result, rather than appearing as |
| 473 |
null-extended rows. To handle that, when we identify such a qual we |
| 474 |
artificially add the join's minimum input relid set to the set of |
| 475 |
relations it is considered to use, forcing it to be evaluated exactly at |
| 476 |
that join level. The same happens for outer-join quals that mention no |
| 477 |
relations at all. |
| 478 |
|
| 479 |
When attaching a qual clause to a join plan node that is performing an |
| 480 |
outer join, the qual clause is considered a "join clause" (that is, it is |
| 481 |
applied before the join performs null-extension) if it does not reference |
| 482 |
that outer join in any varnullingrels or phnullingrels set, or a "filter |
| 483 |
clause" (applied after null-extension) if it does reference that outer |
| 484 |
join. A qual clause that originally appeared in that outer join's JOIN/ON |
| 485 |
will fall into the first category, since the parser would not have marked |
| 486 |
any of its Vars as referencing the outer join. A qual clause that |
| 487 |
originally came from some upper ON clause or WHERE clause will be seen as |
| 488 |
referencing the outer join if it references any of the nullable side's |
| 489 |
Vars, since those Vars will be so marked by the parser. But, if such a |
| 490 |
qual does not reference any nullable-side Vars, it's okay to push it down |
| 491 |
into the non-nullable side, so it won't get attached to the join node in |
| 492 |
the first place. |
| 493 |
|
| 494 |
These things lead us to identify join relations within the planner |
| 495 |
by the sets of base relation RT indexes plus outer join RT indexes |
| 496 |
that they include. In that way, the sets of relations used by qual |
| 497 |
clauses can be directly compared to join relations' relid sets to |
| 498 |
see where to place the clauses. These identifying sets are unique |
| 499 |
because, for any given collection of base relations, there is only |
| 500 |
one valid set of outer joins to have performed along the way to |
| 501 |
joining that set of base relations (although the order of applying |
| 502 |
them could vary, as discussed above). |
| 503 |
|
| 504 |
SEMI joins do not have RT indexes, because they are artifacts made by |
| 505 |
the planner rather than the parser. (We could create rangetable |
| 506 |
entries for them, but there seems no need at present.) This does not |
| 507 |
cause a problem for qual placement, because the nullable side of a |
| 508 |
semijoin is not referenceable from above the join, so there is never a |
| 509 |
need to cite it in varnullingrels or phnullingrels. It does not cause a |
| 510 |
problem for join relation identification either, since whether a semijoin |
| 511 |
has been completed is again implicit in the set of base relations |
| 512 |
included in the join. |
| 513 |
|
| 514 |
As usual, outer join identity 3 complicates matters. If we start with |
| 515 |
(A leftjoin B on (Pab)) leftjoin C on (Pbc) |
| 516 |
then the parser will have marked any C Vars appearing above these joins |
| 517 |
with the RT index of the B/C join. If we now transform to |
| 518 |
A leftjoin (B leftjoin C on (Pbc)) on (Pab) |
| 519 |
then it would appear that a clause using only such Vars could be pushed |
| 520 |
down and applied as a filter clause (not a join clause) at the lower |
| 521 |
B/C join. But *this might not give the right answer* since the clause |
| 522 |
might see a non-null value for the C Var that will be replaced by null |
| 523 |
once the A/B join is performed. We handle this by saying that the |
| 524 |
pushed-down join hasn't completely performed the work of the B/C join |
| 525 |
and hence is not entitled to include that outer join relid in its |
| 526 |
relid set. When we form the A/B join, both outer joins' relids will |
| 527 |
be added to its relid set, and then the upper clause will be applied |
| 528 |
at the correct join level. (Note there is no problem when identity 3 |
| 529 |
is applied in the other direction: if we started with the second form |
| 530 |
then upper C Vars are marked with both outer join relids, so they |
| 531 |
cannot drop below whichever join is applied second.) Similarly, |
| 532 |
Vars representing the output of a pushed-down join do not acquire |
| 533 |
nullingrel bits for that join until after the upper join is performed. |
| 534 |
|
| 535 |
There is one additional complication for qual clause placement, which |
| 536 |
occurs when we have made multiple versions of an outer-join clause as |
| 537 |
described previously (that is, we have both "Pbc" and "Pb*c" forms of |
| 538 |
the same clause seen in outer join identity 3). When forming an outer |
| 539 |
join we only want to apply one of the redundant versions of the clause. |
| 540 |
If we are forming the B/C join without having yet computed the A/B |
| 541 |
join, it's easy to reject the "Pb*c" form since its required relid |
| 542 |
set includes the A/B join relid which is not in the input. However, |
| 543 |
if we form B/C after A/B, then both forms of the clause are applicable |
| 544 |
so far as that test can tell. We have to look more closely to notice |
| 545 |
that the "Pbc" clause form refers to relation B which is no longer |
| 546 |
directly accessible. While such a check could be performed using the |
| 547 |
per-relation RelOptInfo.nulling_relids data, it would be annoyingly |
| 548 |
expensive to do over and over as we consider different join paths. |
| 549 |
To make this simple and reliable, we compute an "incompatible_relids" |
| 550 |
set for each variant version (clone) of a redundant clause. A clone |
| 551 |
clause should not be applied if any of the outer-join relids listed in |
| 552 |
incompatible_relids has already been computed below the current join. |
| 553 |
|
| 554 |
|
| 555 |
Optimizer Functions |
| 556 |
------------------- |
| 557 |
|
| 558 |
The primary entry point is planner(). |
| 559 |
|
| 560 |
planner() |
| 561 |
set up for recursive handling of subqueries |
| 562 |
-subquery_planner() |
| 563 |
pull up sublinks and subqueries from rangetable, if possible |
| 564 |
canonicalize qual |
| 565 |
Attempt to simplify WHERE clause to the most useful form; this includes |
| 566 |
flattening nested AND/ORs and detecting clauses that are duplicated in |
| 567 |
different branches of an OR. |
| 568 |
simplify constant expressions |
| 569 |
process sublinks |
| 570 |
convert Vars of outer query levels into Params |
| 571 |
--grouping_planner() |
| 572 |
preprocess target list for non-SELECT queries |
| 573 |
handle UNION/INTERSECT/EXCEPT, GROUP BY, HAVING, aggregates, |
| 574 |
ORDER BY, DISTINCT, LIMIT |
| 575 |
---query_planner() |
| 576 |
make list of base relations used in query |
| 577 |
split up the qual into restrictions (a=1) and joins (b=c) |
| 578 |
find qual clauses that enable merge and hash joins |
| 579 |
----make_one_rel() |
| 580 |
set_base_rel_pathlists() |
| 581 |
find seqscan and all index paths for each base relation |
| 582 |
find selectivity of columns used in joins |
| 583 |
make_rel_from_joinlist() |
| 584 |
hand off join subproblems to a plugin, GEQO, or standard_join_search() |
| 585 |
------standard_join_search() |
| 586 |
call join_search_one_level() for each level of join tree needed |
| 587 |
join_search_one_level(): |
| 588 |
For each joinrel of the prior level, do make_rels_by_clause_joins() |
| 589 |
if it has join clauses, or make_rels_by_clauseless_joins() if not. |
| 590 |
Also generate "bushy plan" joins between joinrels of lower levels. |
| 591 |
Back at standard_join_search(), generate gather paths if needed for |
| 592 |
each newly constructed joinrel, then apply set_cheapest() to extract |
| 593 |
the cheapest path for it. |
| 594 |
Loop back if this wasn't the top join level. |
| 595 |
Back at grouping_planner: |
| 596 |
do grouping (GROUP BY) and aggregation |
| 597 |
do window functions |
| 598 |
make unique (DISTINCT) |
| 599 |
do sorting (ORDER BY) |
| 600 |
do limit (LIMIT/OFFSET) |
| 601 |
Back at planner(): |
| 602 |
convert finished Path tree into a Plan tree |
| 603 |
do final cleanup after planning |
| 604 |
|
| 605 |
|
| 606 |
Optimizer Data Structures |
| 607 |
------------------------- |
| 608 |
|
| 609 |
PlannerGlobal - global information for a single planner invocation |
| 610 |
|
| 611 |
PlannerInfo - information for planning a particular Query (we make |
| 612 |
a separate PlannerInfo node for each sub-Query) |
| 613 |
|
| 614 |
RelOptInfo - a relation or joined relations |
| 615 |
|
| 616 |
RestrictInfo - WHERE clauses, like "x = 3" or "y = z" |
| 617 |
(note the same structure is used for restriction and |
| 618 |
join clauses) |
| 619 |
|
| 620 |
Path - every way to generate a RelOptInfo(sequential,index,joins) |
| 621 |
A plain Path node can represent several simple plans, per its pathtype: |
| 622 |
T_SeqScan - sequential scan |
| 623 |
T_SampleScan - tablesample scan |
| 624 |
T_FunctionScan - function-in-FROM scan |
| 625 |
T_TableFuncScan - table function scan |
| 626 |
T_ValuesScan - VALUES scan |
| 627 |
T_CteScan - CTE (WITH) scan |
| 628 |
T_NamedTuplestoreScan - ENR scan |
| 629 |
T_WorkTableScan - scan worktable of a recursive CTE |
| 630 |
T_Result - childless Result plan node (used for FROM-less SELECT) |
| 631 |
IndexPath - index scan |
| 632 |
BitmapHeapPath - top of a bitmapped index scan |
| 633 |
TidPath - scan by CTID |
| 634 |
TidRangePath - scan a contiguous range of CTIDs |
| 635 |
SubqueryScanPath - scan a subquery-in-FROM |
| 636 |
ForeignPath - scan a foreign table, foreign join or foreign upper-relation |
| 637 |
CustomPath - for custom scan providers |
| 638 |
AppendPath - append multiple subpaths together |
| 639 |
MergeAppendPath - merge multiple subpaths, preserving their common sort order |
| 640 |
GroupResultPath - childless Result plan node (used for degenerate grouping) |
| 641 |
MaterialPath - a Material plan node |
| 642 |
MemoizePath - a Memoize plan node for caching tuples from sub-paths |
| 643 |
UniquePath - remove duplicate rows (either by hashing or sorting) |
| 644 |
GatherPath - collect the results of parallel workers |
| 645 |
GatherMergePath - collect parallel results, preserving their common sort order |
| 646 |
ProjectionPath - a Result plan node with child (used for projection) |
| 647 |
ProjectSetPath - a ProjectSet plan node applied to some sub-path |
| 648 |
SortPath - a Sort plan node applied to some sub-path |
| 649 |
IncrementalSortPath - an IncrementalSort plan node applied to some sub-path |
| 650 |
GroupPath - a Group plan node applied to some sub-path |
| 651 |
UpperUniquePath - a Unique plan node applied to some sub-path |
| 652 |
AggPath - an Agg plan node applied to some sub-path |
| 653 |
GroupingSetsPath - an Agg plan node used to implement GROUPING SETS |
| 654 |
MinMaxAggPath - a Result plan node with subplans performing MIN/MAX |
| 655 |
WindowAggPath - a WindowAgg plan node applied to some sub-path |
| 656 |
SetOpPath - a SetOp plan node applied to two sub-paths |
| 657 |
RecursiveUnionPath - a RecursiveUnion plan node applied to two sub-paths |
| 658 |
LockRowsPath - a LockRows plan node applied to some sub-path |
| 659 |
ModifyTablePath - a ModifyTable plan node applied to some sub-path(s) |
| 660 |
LimitPath - a Limit plan node applied to some sub-path |
| 661 |
NestPath - nested-loop joins |
| 662 |
MergePath - merge joins |
| 663 |
HashPath - hash joins |
| 664 |
|
| 665 |
EquivalenceClass - a data structure representing a set of values known equal |
| 666 |
|
| 667 |
PathKey - a data structure representing the sort ordering of a path |
| 668 |
|
| 669 |
The optimizer spends a good deal of its time worrying about the ordering |
| 670 |
of the tuples returned by a path. The reason this is useful is that by |
| 671 |
knowing the sort ordering of a path, we may be able to use that path as |
| 672 |
the left or right input of a mergejoin and avoid an explicit sort step. |
| 673 |
Nestloops and hash joins don't really care what the order of their inputs |
| 674 |
is, but mergejoin needs suitably ordered inputs. Therefore, all paths |
| 675 |
generated during the optimization process are marked with their sort order |
| 676 |
(to the extent that it is known) for possible use by a higher-level merge. |
| 677 |
|
| 678 |
It is also possible to avoid an explicit sort step to implement a user's |
| 679 |
ORDER BY clause if the final path has the right ordering already, so the |
| 680 |
sort ordering is of interest even at the top level. grouping_planner() will |
| 681 |
look for the cheapest path with a sort order matching the desired order, |
| 682 |
then compare its cost to the cost of using the cheapest-overall path and |
| 683 |
doing an explicit sort on that. |
| 684 |
|
| 685 |
When we are generating paths for a particular RelOptInfo, we discard a path |
| 686 |
if it is more expensive than another known path that has the same or better |
| 687 |
sort order. We will never discard a path that is the only known way to |
| 688 |
achieve a given sort order (without an explicit sort, that is). In this |
| 689 |
way, the next level up will have the maximum freedom to build mergejoins |
| 690 |
without sorting, since it can pick from any of the paths retained for its |
| 691 |
inputs. |
| 692 |
|
| 693 |
|
| 694 |
EquivalenceClasses |
| 695 |
------------------ |
| 696 |
|
| 697 |
During the deconstruct_jointree() scan of the query's qual clauses, we |
| 698 |
look for mergejoinable equality clauses A = B. When we find one, we |
| 699 |
create an EquivalenceClass containing the expressions A and B to record |
| 700 |
that they are equal. If we later find another equivalence clause B = C, |
| 701 |
we add C to the existing EquivalenceClass for {A B}; this may require |
| 702 |
merging two existing EquivalenceClasses. At the end of the scan, we have |
| 703 |
sets of values that are known all transitively equal to each other. We can |
| 704 |
therefore use a comparison of any pair of the values as a restriction or |
| 705 |
join clause (when these values are available at the scan or join, of |
| 706 |
course); furthermore, we need test only one such comparison, not all of |
| 707 |
them. Therefore, equivalence clauses are removed from the standard qual |
| 708 |
distribution process. Instead, when preparing a restriction or join clause |
| 709 |
list, we examine each EquivalenceClass to see if it can contribute a |
| 710 |
clause, and if so we select an appropriate pair of values to compare. For |
| 711 |
example, if we are trying to join A's relation to C's, we can generate the |
| 712 |
clause A = C, even though this appeared nowhere explicitly in the original |
| 713 |
query. This may allow us to explore join paths that otherwise would have |
| 714 |
been rejected as requiring Cartesian-product joins. |
| 715 |
|
| 716 |
Sometimes an EquivalenceClass may contain a pseudo-constant expression |
| 717 |
(i.e., one not containing Vars or Aggs of the current query level, nor |
| 718 |
volatile functions). In this case we do not follow the policy of |
| 719 |
dynamically generating join clauses: instead, we dynamically generate |
| 720 |
restriction clauses "var = const" wherever one of the variable members of |
| 721 |
the class can first be computed. For example, if we have A = B and B = 42, |
| 722 |
we effectively generate the restriction clauses A = 42 and B = 42, and then |
| 723 |
we need not bother with explicitly testing the join clause A = B when the |
| 724 |
relations are joined. In effect, all the class members can be tested at |
| 725 |
relation-scan level and there's never a need for join tests. |
| 726 |
|
| 727 |
The precise technical interpretation of an EquivalenceClass is that it |
| 728 |
asserts that at any plan node where more than one of its member values |
| 729 |
can be computed, output rows in which the values are not all equal may |
| 730 |
be discarded without affecting the query result. (We require all levels |
| 731 |
of the plan to enforce EquivalenceClasses, hence a join need not recheck |
| 732 |
equality of values that were computable by one of its children.) |
| 733 |
|
| 734 |
Outer joins complicate this picture quite a bit, however. While we could |
| 735 |
theoretically use mergejoinable equality clauses that appear in outer-join |
| 736 |
conditions as sources of EquivalenceClasses, there's a serious difficulty: |
| 737 |
the resulting deductions are not valid everywhere. For example, given |
| 738 |
|
| 739 |
SELECT * FROM a LEFT JOIN b ON (a.x = b.y AND a.x = 42); |
| 740 |
|
| 741 |
we can safely derive b.y = 42 and use that in the scan of B, because B |
| 742 |
rows not having b.y = 42 will not contribute to the join result. However, |
| 743 |
we cannot apply a.x = 42 at the scan of A, or we will remove rows that |
| 744 |
should appear in the join result. We could apply a.x = 42 as an outer join |
| 745 |
condition (and then it would be unnecessary to also check a.x = b.y). |
| 746 |
This is not yet implemented, however. |
| 747 |
|
| 748 |
A related issue is that constants appearing below an outer join are |
| 749 |
less constant than they appear. Ordinarily, if we find "A = 1" and |
| 750 |
"B = 1", it's okay to put A and B into the same EquivalenceClass. |
| 751 |
But consider |
| 752 |
|
| 753 |
SELECT * FROM a |
| 754 |
LEFT JOIN (SELECT * FROM b WHERE b.z = 1) b ON (a.x = b.y) |
| 755 |
WHERE a.x = 1; |
| 756 |
|
| 757 |
It would be a serious error to conclude that a.x = b.z, so we cannot |
| 758 |
form a single EquivalenceClass {a.x b.z 1}. |
| 759 |
|
| 760 |
This leads to considering EquivalenceClasses as applying within "join |
| 761 |
domains", which are sets of relations that are inner-joined to each other. |
| 762 |
(We can treat semijoins as if they were inner joins for this purpose.) |
| 763 |
There is a top-level join domain, and then each outer join in the query |
| 764 |
creates a new join domain comprising its nullable side. Full joins create |
| 765 |
two join domains, one for each side. EquivalenceClasses generated from |
| 766 |
WHERE are associated with the top-level join domain. EquivalenceClasses |
| 767 |
generated from the ON clause of an outer join are associated with the |
| 768 |
domain created by that outer join. EquivalenceClasses generated from the |
| 769 |
ON clause of an inner or semi join are associated with the syntactically |
| 770 |
most closely nested join domain. |
| 771 |
|
| 772 |
Having defined these domains, we can fix the not-so-constant-constants |
| 773 |
problem by considering that constants only match EquivalenceClass members |
| 774 |
when they come from clauses within the same join domain. In the above |
| 775 |
example, this means we keep {a.x 1} and {b.z 1} as separate |
| 776 |
EquivalenceClasses and don't erroneously merge them. We don't have to |
| 777 |
worry about this for Vars (or expressions containing Vars), because |
| 778 |
references to the "same" column from different join domains will have |
| 779 |
different varnullingrels and thus won't be equal() anyway. |
| 780 |
|
| 781 |
In the future, the join-domain concept may allow us to treat mergejoinable |
| 782 |
outer-join conditions as sources of EquivalenceClasses. The idea would be |
| 783 |
that conditions derived from such classes could only be enforced at scans |
| 784 |
or joins that are within the appropriate join domain. This is not |
| 785 |
implemented yet, however, as the details are trickier than they appear. |
| 786 |
|
| 787 |
Another instructive example is: |
| 788 |
|
| 789 |
SELECT * |
| 790 |
FROM a LEFT JOIN |
| 791 |
(SELECT * FROM b JOIN c ON b.y = c.z WHERE b.y = 10) ss |
| 792 |
ON a.x = ss.y |
| 793 |
ORDER BY ss.y; |
| 794 |
|
| 795 |
We can form the EquivalenceClass {b.y c.z 10} and thereby apply c.z = 10 |
| 796 |
while scanning C, as well as b.y = 10 while scanning B, so that no clause |
| 797 |
needs to be checked at the inner join. The left-join clause "a.x = ss.y" |
| 798 |
(really "a.x = b.y") is not considered an equivalence clause, so we do |
| 799 |
not insert a.x into that same EquivalenceClass; if we did, we'd falsely |
| 800 |
conclude a.x = 10. In the future though we might be able to do that, |
| 801 |
if we can keep from applying a.x = 10 at the scan of A, which in principle |
| 802 |
we could do by noting that the EquivalenceClass only applies within the |
| 803 |
{B,C} join domain. |
| 804 |
|
| 805 |
Also notice that ss.y in the ORDER BY is really b.y* (that is, the |
| 806 |
possibly-nulled form of b.y), so we will not confuse it with the b.y member |
| 807 |
of the lower EquivalenceClass. Thus, we won't mistakenly conclude that |
| 808 |
that ss.y is equal to a constant, which if true would lead us to think that |
| 809 |
sorting for the ORDER BY is unnecessary (see discussion of PathKeys below). |
| 810 |
Instead, there will be a separate EquivalenceClass containing only b.y*, |
| 811 |
which will form the basis for the PathKey describing the required sort |
| 812 |
order. |
| 813 |
|
| 814 |
Also consider this variant: |
| 815 |
|
| 816 |
SELECT * |
| 817 |
FROM a LEFT JOIN |
| 818 |
(SELECT * FROM b JOIN c ON b.y = c.z WHERE b.y = 10) ss |
| 819 |
ON a.x = ss.y |
| 820 |
WHERE a.x = 42; |
| 821 |
|
| 822 |
We still form the EquivalenceClass {b.y c.z 10}, and additionally |
| 823 |
we have an EquivalenceClass {a.x 42} belonging to a different join domain. |
| 824 |
We cannot use "a.x = b.y" to merge these classes. However, we can compare |
| 825 |
that outer join clause to the existing EquivalenceClasses and form the |
| 826 |
derived clause "b.y = 42", which we can treat as a valid equivalence |
| 827 |
within the lower join domain (since no row of that domain not having |
| 828 |
b.y = 42 can contribute to the outer-join result). That makes the lower |
| 829 |
EquivalenceClass {42 b.y c.z 10}, resulting in the contradiction 10 = 42, |
| 830 |
which lets the planner deduce that the B/C join need not be computed at |
| 831 |
all: the result of that whole join domain can be forced to empty. |
| 832 |
(This gets implemented as a gating Result filter, since more usually the |
| 833 |
potential contradiction involves Param values rather than just Consts, and |
| 834 |
thus it has to be checked at runtime. We can use the join domain to |
| 835 |
determine the join level at which to place the gating condition.) |
| 836 |
|
| 837 |
There is an additional complication when re-ordering outer joins according |
| 838 |
to identity 3. Recall that the two choices we consider for such joins are |
| 839 |
|
| 840 |
A leftjoin (B leftjoin C on (Pbc)) on (Pab) |
| 841 |
(A leftjoin B on (Pab)) leftjoin C on (Pb*c) |
| 842 |
|
| 843 |
where the star denotes varnullingrels markers on B's Vars. When Pbc |
| 844 |
is (or includes) a mergejoinable clause, we have something like |
| 845 |
|
| 846 |
A leftjoin (B leftjoin C on (b.b = c.c)) on (Pab) |
| 847 |
(A leftjoin B on (Pab)) leftjoin C on (b.b* = c.c) |
| 848 |
|
| 849 |
We could generate an EquivalenceClause linking b.b and c.c, but if we |
| 850 |
then also try to link b.b* and c.c, we end with a nonsensical conclusion |
| 851 |
that b.b and b.b* are equal (at least in some parts of the plan tree). |
| 852 |
In any case, the conclusions we could derive from such a thing would be |
| 853 |
largely duplicative. Conditions involving b.b* can't be computed below |
| 854 |
this join nest, while any conditions that can be computed would be |
| 855 |
duplicative of what we'd get from the b.b/c.c combination. Therefore, |
| 856 |
we choose to generate an EquivalenceClause linking b.b and c.c, but |
| 857 |
"b.b* = c.c" is handled as just an ordinary clause. |
| 858 |
|
| 859 |
To aid in determining the sort ordering(s) that can work with a mergejoin, |
| 860 |
we mark each mergejoinable clause with the EquivalenceClasses of its left |
| 861 |
and right inputs. For an equivalence clause, these are of course the same |
| 862 |
EquivalenceClass. For a non-equivalence mergejoinable clause (such as an |
| 863 |
outer-join qualification), we generate two separate EquivalenceClasses for |
| 864 |
the left and right inputs. This may result in creating single-item |
| 865 |
equivalence "classes", though of course these are still subject to merging |
| 866 |
if other equivalence clauses are later found to bear on the same |
| 867 |
expressions. |
| 868 |
|
| 869 |
Another way that we may form a single-item EquivalenceClass is in creation |
| 870 |
of a PathKey to represent a desired sort order (see below). This happens |
| 871 |
if an ORDER BY or GROUP BY key is not mentioned in any equivalence |
| 872 |
clause. We need to reason about sort orders in such queries, and our |
| 873 |
representation of sort ordering is a PathKey which depends on an |
| 874 |
EquivalenceClass, so we have to make an EquivalenceClass. This is a bit |
| 875 |
different from the above cases because such an EquivalenceClass might |
| 876 |
contain an aggregate function or volatile expression. (A clause containing |
| 877 |
a volatile function will never be considered mergejoinable, even if its top |
| 878 |
operator is mergejoinable, so there is no way for a volatile expression to |
| 879 |
get into EquivalenceClasses otherwise. Aggregates are disallowed in WHERE |
| 880 |
altogether, so will never be found in a mergejoinable clause.) This is just |
| 881 |
a convenience to maintain a uniform PathKey representation: such an |
| 882 |
EquivalenceClass will never be merged with any other. Note in particular |
| 883 |
that a single-item EquivalenceClass {a.x} is *not* meant to imply an |
| 884 |
assertion that a.x = a.x; the practical effect of this is that a.x could |
| 885 |
be NULL. |
| 886 |
|
| 887 |
An EquivalenceClass also contains a list of btree opfamily OIDs, which |
| 888 |
determines what the equalities it represents actually "mean". All the |
| 889 |
equivalence clauses that contribute to an EquivalenceClass must have |
| 890 |
equality operators that belong to the same set of opfamilies. (Note: most |
| 891 |
of the time, a particular equality operator belongs to only one family, but |
| 892 |
it's possible that it belongs to more than one. We keep track of all the |
| 893 |
families to ensure that we can make use of an index belonging to any one of |
| 894 |
the families for mergejoin purposes.) |
| 895 |
|
| 896 |
For the same sort of reason, an EquivalenceClass is also associated |
| 897 |
with a particular collation, if its datatype(s) care about collation. |
| 898 |
|
| 899 |
An EquivalenceClass can contain "em_is_child" members, which are copies |
| 900 |
of members that contain appendrel parent relation Vars, transposed to |
| 901 |
contain the equivalent child-relation variables or expressions. These |
| 902 |
members are *not* full-fledged members of the EquivalenceClass and do not |
| 903 |
affect the class's overall properties at all. They are kept only to |
| 904 |
simplify matching of child-relation expressions to EquivalenceClasses. |
| 905 |
Most operations on EquivalenceClasses needn't look at child members. |
| 906 |
|
| 907 |
|
| 908 |
PathKeys |
| 909 |
-------- |
| 910 |
|
| 911 |
The PathKeys data structure represents what is known about the sort order |
| 912 |
of the tuples generated by a particular Path. A path's pathkeys field is a |
| 913 |
list of PathKey nodes, where the n'th item represents the n'th sort key of |
| 914 |
the result. Each PathKey contains these fields: |
| 915 |
|
| 916 |
* a reference to an EquivalenceClass |
| 917 |
* a btree opfamily OID (must match one of those in the EC) |
| 918 |
* a sort direction (ascending or descending) |
| 919 |
* a nulls-first-or-last flag |
| 920 |
|
| 921 |
The EquivalenceClass represents the value being sorted on. Since the |
| 922 |
various members of an EquivalenceClass are known equal according to the |
| 923 |
opfamily, we can consider a path sorted by any one of them to be sorted by |
| 924 |
any other too; this is what justifies referencing the whole |
| 925 |
EquivalenceClass rather than just one member of it. |
| 926 |
|
| 927 |
In single/base relation RelOptInfo's, the Paths represent various ways |
| 928 |
of scanning the relation and the resulting ordering of the tuples. |
| 929 |
Sequential scan Paths have NIL pathkeys, indicating no known ordering. |
| 930 |
Index scans have Path.pathkeys that represent the chosen index's ordering, |
| 931 |
if any. A single-key index would create a single-PathKey list, while a |
| 932 |
multi-column index generates a list with one element per key index column. |
| 933 |
Non-key columns specified in the INCLUDE clause of covering indexes don't |
| 934 |
have corresponding PathKeys in the list, because they have no influence on |
| 935 |
index ordering. (Actually, since an index can be scanned either forward or |
| 936 |
backward, there are two possible sort orders and two possible PathKey lists |
| 937 |
it can generate.) |
| 938 |
|
| 939 |
Note that a bitmap scan has NIL pathkeys since we can say nothing about |
| 940 |
the overall order of its result. Also, an indexscan on an unordered type |
| 941 |
of index generates NIL pathkeys. However, we can always create a pathkey |
| 942 |
by doing an explicit sort. The pathkeys for a Sort plan's output just |
| 943 |
represent the sort key fields and the ordering operators used. |
| 944 |
|
| 945 |
Things get more interesting when we consider joins. Suppose we do a |
| 946 |
mergejoin between A and B using the mergeclause A.X = B.Y. The output |
| 947 |
of the mergejoin is sorted by X --- but it is also sorted by Y. Again, |
| 948 |
this can be represented by a PathKey referencing an EquivalenceClass |
| 949 |
containing both X and Y. |
| 950 |
|
| 951 |
With a little further thought, it becomes apparent that nestloop joins |
| 952 |
can also produce sorted output. For example, if we do a nestloop join |
| 953 |
between outer relation A and inner relation B, then any pathkeys relevant |
| 954 |
to A are still valid for the join result: we have not altered the order of |
| 955 |
the tuples from A. Even more interesting, if there was an equivalence clause |
| 956 |
A.X=B.Y, and A.X was a pathkey for the outer relation A, then we can assert |
| 957 |
that B.Y is a pathkey for the join result; X was ordered before and still |
| 958 |
is, and the joined values of Y are equal to the joined values of X, so Y |
| 959 |
must now be ordered too. This is true even though we used neither an |
| 960 |
explicit sort nor a mergejoin on Y. (Note: hash joins cannot be counted |
| 961 |
on to preserve the order of their outer relation, because the executor |
| 962 |
might decide to "batch" the join, so we always set pathkeys to NIL for |
| 963 |
a hashjoin path.) |
| 964 |
|
| 965 |
An outer join doesn't preserve the ordering of its nullable input |
| 966 |
relation(s), because it might insert nulls at random points in the |
| 967 |
ordering. We don't need to think about this explicitly in the PathKey |
| 968 |
representation, because a PathKey representing a post-join variable |
| 969 |
will contain varnullingrel bits, making it not equal to a PathKey |
| 970 |
representing the pre-join value. |
| 971 |
|
| 972 |
In general, we can justify using EquivalenceClasses as the basis for |
| 973 |
pathkeys because, whenever we scan a relation containing multiple |
| 974 |
EquivalenceClass members or join two relations each containing |
| 975 |
EquivalenceClass members, we apply restriction or join clauses derived from |
| 976 |
the EquivalenceClass. This guarantees that any two values listed in the |
| 977 |
EquivalenceClass are in fact equal in all tuples emitted by the scan or |
| 978 |
join, and therefore that if the tuples are sorted by one of the values, |
| 979 |
they can be considered sorted by any other as well. It does not matter |
| 980 |
whether the test clause is used as a mergeclause, or merely enforced |
| 981 |
after-the-fact as a qpqual filter. |
| 982 |
|
| 983 |
Note that there is no particular difficulty in labeling a path's sort |
| 984 |
order with a PathKey referencing an EquivalenceClass that contains |
| 985 |
variables not yet joined into the path's output. We can simply ignore |
| 986 |
such entries as not being relevant (yet). This makes it possible to |
| 987 |
use the same EquivalenceClasses throughout the join planning process. |
| 988 |
In fact, by being careful not to generate multiple identical PathKey |
| 989 |
objects, we can reduce comparison of EquivalenceClasses and PathKeys |
| 990 |
to simple pointer comparison, which is a huge savings because add_path |
| 991 |
has to make a large number of PathKey comparisons in deciding whether |
| 992 |
competing Paths are equivalently sorted. |
| 993 |
|
| 994 |
Pathkeys are also useful to represent an ordering that we wish to achieve, |
| 995 |
since they are easily compared to the pathkeys of a potential candidate |
| 996 |
path. So, SortGroupClause lists are turned into pathkeys lists for use |
| 997 |
inside the optimizer. |
| 998 |
|
| 999 |
An additional refinement we can make is to insist that canonical pathkey |
| 1000 |
lists (sort orderings) do not mention the same EquivalenceClass more than |
| 1001 |
once. For example, in all these cases the second sort column is redundant, |
| 1002 |
because it cannot distinguish values that are the same according to the |
| 1003 |
first sort column: |
| 1004 |
SELECT ... ORDER BY x, x |
| 1005 |
SELECT ... ORDER BY x, x DESC |
| 1006 |
SELECT ... WHERE x = y ORDER BY x, y |
| 1007 |
Although a user probably wouldn't write "ORDER BY x,x" directly, such |
| 1008 |
redundancies are more probable once equivalence classes have been |
| 1009 |
considered. Also, the system may generate redundant pathkey lists when |
| 1010 |
computing the sort ordering needed for a mergejoin. By eliminating the |
| 1011 |
redundancy, we save time and improve planning, since the planner will more |
| 1012 |
easily recognize equivalent orderings as being equivalent. |
| 1013 |
|
| 1014 |
Another interesting property is that if the underlying EquivalenceClass |
| 1015 |
contains a constant, then the pathkey is completely redundant and need not |
| 1016 |
be sorted by at all! Every interesting row must contain the same value, |
| 1017 |
so there's no need to sort. This might seem pointless because users |
| 1018 |
are unlikely to write "... WHERE x = 42 ORDER BY x", but it allows us to |
| 1019 |
recognize when particular index columns are irrelevant to the sort order: |
| 1020 |
if we have "... WHERE x = 42 ORDER BY y", scanning an index on (x,y) |
| 1021 |
produces correctly ordered data without a sort step. We used to have very |
| 1022 |
ugly ad-hoc code to recognize that in limited contexts, but discarding |
| 1023 |
constant ECs from pathkeys makes it happen cleanly and automatically. |
| 1024 |
|
| 1025 |
|
| 1026 |
Order of processing for EquivalenceClasses and PathKeys |
| 1027 |
------------------------------------------------------- |
| 1028 |
|
| 1029 |
As alluded to above, there is a specific sequence of phases in the |
| 1030 |
processing of EquivalenceClasses and PathKeys during planning. During the |
| 1031 |
initial scanning of the query's quals (deconstruct_jointree followed by |
| 1032 |
reconsider_outer_join_clauses), we construct EquivalenceClasses based on |
| 1033 |
mergejoinable clauses found in the quals. At the end of this process, |
| 1034 |
we know all we can know about equivalence of different variables, so |
| 1035 |
subsequently there will be no further merging of EquivalenceClasses. |
| 1036 |
At that point it is possible to consider the EquivalenceClasses as |
| 1037 |
"canonical" and build canonical PathKeys that reference them. At this |
| 1038 |
time we construct PathKeys for the query's ORDER BY and related clauses. |
| 1039 |
(Any ordering expressions that do not appear elsewhere will result in |
| 1040 |
the creation of new EquivalenceClasses, but this cannot result in merging |
| 1041 |
existing classes, so canonical-ness is not lost.) |
| 1042 |
|
| 1043 |
Because all the EquivalenceClasses are known before we begin path |
| 1044 |
generation, we can use them as a guide to which indexes are of interest: |
| 1045 |
if an index's column is not mentioned in any EquivalenceClass then that |
| 1046 |
index's sort order cannot possibly be helpful for the query. This allows |
| 1047 |
short-circuiting of much of the processing of create_index_paths() for |
| 1048 |
irrelevant indexes. |
| 1049 |
|
| 1050 |
There are some cases where planner.c constructs additional |
| 1051 |
EquivalenceClasses and PathKeys after query_planner has completed. |
| 1052 |
In these cases, the extra ECs/PKs are needed to represent sort orders |
| 1053 |
that were not considered during query_planner. Such situations should be |
| 1054 |
minimized since it is impossible for query_planner to return a plan |
| 1055 |
producing such a sort order, meaning an explicit sort will always be needed. |
| 1056 |
Currently this happens only for queries involving multiple window functions |
| 1057 |
with different orderings, for which extra sorts are needed anyway. |
| 1058 |
|
| 1059 |
|
| 1060 |
Parameterized Paths |
| 1061 |
------------------- |
| 1062 |
|
| 1063 |
The naive way to join two relations using a clause like WHERE A.X = B.Y |
| 1064 |
is to generate a nestloop plan like this: |
| 1065 |
|
| 1066 |
NestLoop |
| 1067 |
Filter: A.X = B.Y |
| 1068 |
-> Seq Scan on A |
| 1069 |
-> Seq Scan on B |
| 1070 |
|
| 1071 |
We can make this better by using a merge or hash join, but it still |
| 1072 |
requires scanning all of both input relations. If A is very small and B is |
| 1073 |
very large, but there is an index on B.Y, it can be enormously better to do |
| 1074 |
something like this: |
| 1075 |
|
| 1076 |
NestLoop |
| 1077 |
-> Seq Scan on A |
| 1078 |
-> Index Scan using B_Y_IDX on B |
| 1079 |
Index Condition: B.Y = A.X |
| 1080 |
|
| 1081 |
Here, we are expecting that for each row scanned from A, the nestloop |
| 1082 |
plan node will pass down the current value of A.X into the scan of B. |
| 1083 |
That allows the indexscan to treat A.X as a constant for any one |
| 1084 |
invocation, and thereby use it as an index key. This is the only plan type |
| 1085 |
that can avoid fetching all of B, and for small numbers of rows coming from |
| 1086 |
A, that will dominate every other consideration. (As A gets larger, this |
| 1087 |
gets less attractive, and eventually a merge or hash join will win instead. |
| 1088 |
So we have to cost out all the alternatives to decide what to do.) |
| 1089 |
|
| 1090 |
It can be useful for the parameter value to be passed down through |
| 1091 |
intermediate layers of joins, for example: |
| 1092 |
|
| 1093 |
NestLoop |
| 1094 |
-> Seq Scan on A |
| 1095 |
Hash Join |
| 1096 |
Join Condition: B.Y = C.W |
| 1097 |
-> Seq Scan on B |
| 1098 |
-> Index Scan using C_Z_IDX on C |
| 1099 |
Index Condition: C.Z = A.X |
| 1100 |
|
| 1101 |
If all joins are plain inner joins then this is usually unnecessary, |
| 1102 |
because it's possible to reorder the joins so that a parameter is used |
| 1103 |
immediately below the nestloop node that provides it. But in the |
| 1104 |
presence of outer joins, such join reordering may not be possible. |
| 1105 |
|
| 1106 |
Also, the bottom-level scan might require parameters from more than one |
| 1107 |
other relation. In principle we could join the other relations first |
| 1108 |
so that all the parameters are supplied from a single nestloop level. |
| 1109 |
But if those other relations have no join clause in common (which is |
| 1110 |
common in star-schema queries for instance), the planner won't consider |
| 1111 |
joining them directly to each other. In such a case we need to be able |
| 1112 |
to create a plan like |
| 1113 |
|
| 1114 |
NestLoop |
| 1115 |
-> Seq Scan on SmallTable1 A |
| 1116 |
NestLoop |
| 1117 |
-> Seq Scan on SmallTable2 B |
| 1118 |
-> Index Scan using XYIndex on LargeTable C |
| 1119 |
Index Condition: C.X = A.AID and C.Y = B.BID |
| 1120 |
|
| 1121 |
so we should be willing to pass down A.AID through a join even though |
| 1122 |
there is no join order constraint forcing the plan to look like this. |
| 1123 |
|
| 1124 |
Before version 9.2, Postgres used ad-hoc methods for planning and |
| 1125 |
executing nestloop queries of this kind, and those methods could not |
| 1126 |
handle passing parameters down through multiple join levels. |
| 1127 |
|
| 1128 |
To plan such queries, we now use a notion of a "parameterized path", |
| 1129 |
which is a path that makes use of a join clause to a relation that's not |
| 1130 |
scanned by the path. In the example two above, we would construct a |
| 1131 |
path representing the possibility of doing this: |
| 1132 |
|
| 1133 |
-> Index Scan using C_Z_IDX on C |
| 1134 |
Index Condition: C.Z = A.X |
| 1135 |
|
| 1136 |
This path will be marked as being parameterized by relation A. (Note that |
| 1137 |
this is only one of the possible access paths for C; we'd still have a |
| 1138 |
plain unparameterized seqscan, and perhaps other possibilities.) The |
| 1139 |
parameterization marker does not prevent joining the path to B, so one of |
| 1140 |
the paths generated for the joinrel {B C} will represent |
| 1141 |
|
| 1142 |
Hash Join |
| 1143 |
Join Condition: B.Y = C.W |
| 1144 |
-> Seq Scan on B |
| 1145 |
-> Index Scan using C_Z_IDX on C |
| 1146 |
Index Condition: C.Z = A.X |
| 1147 |
|
| 1148 |
This path is still marked as being parameterized by A. When we attempt to |
| 1149 |
join {B C} to A to form the complete join tree, such a path can only be |
| 1150 |
used as the inner side of a nestloop join: it will be ignored for other |
| 1151 |
possible join types. So we will form a join path representing the query |
| 1152 |
plan shown above, and it will compete in the usual way with paths built |
| 1153 |
from non-parameterized scans. |
| 1154 |
|
| 1155 |
While all ordinary paths for a particular relation generate the same set |
| 1156 |
of rows (since they must all apply the same set of restriction clauses), |
| 1157 |
parameterized paths typically generate fewer rows than less-parameterized |
| 1158 |
paths, since they have additional clauses to work with. This means we |
| 1159 |
must consider the number of rows generated as an additional figure of |
| 1160 |
merit. A path that costs more than another, but generates fewer rows, |
| 1161 |
must be kept since the smaller number of rows might save work at some |
| 1162 |
intermediate join level. (It would not save anything if joined |
| 1163 |
immediately to the source of the parameters.) |
| 1164 |
|
| 1165 |
To keep cost estimation rules relatively simple, we make an implementation |
| 1166 |
restriction that all paths for a given relation of the same parameterization |
| 1167 |
(i.e., the same set of outer relations supplying parameters) must have the |
| 1168 |
same rowcount estimate. This is justified by insisting that each such path |
| 1169 |
apply *all* join clauses that are available with the named outer relations. |
| 1170 |
Different paths might, for instance, choose different join clauses to use |
| 1171 |
as index clauses; but they must then apply any other join clauses available |
| 1172 |
from the same outer relations as filter conditions, so that the set of rows |
| 1173 |
returned is held constant. This restriction doesn't degrade the quality of |
| 1174 |
the finished plan: it amounts to saying that we should always push down |
| 1175 |
movable join clauses to the lowest possible evaluation level, which is a |
| 1176 |
good thing anyway. The restriction is useful in particular to support |
| 1177 |
pre-filtering of join paths in add_path_precheck. Without this rule we |
| 1178 |
could never reject a parameterized path in advance of computing its rowcount |
| 1179 |
estimate, which would greatly reduce the value of the pre-filter mechanism. |
| 1180 |
|
| 1181 |
To limit planning time, we have to avoid generating an unreasonably large |
| 1182 |
number of parameterized paths. We do this by only generating parameterized |
| 1183 |
relation scan paths for index scans, and then only for indexes for which |
| 1184 |
suitable join clauses are available. There are also heuristics in join |
| 1185 |
planning that try to limit the number of parameterized paths considered. |
| 1186 |
|
| 1187 |
In particular, there's been a deliberate policy decision to favor hash |
| 1188 |
joins over merge joins for parameterized join steps (those occurring below |
| 1189 |
a nestloop that provides parameters to the lower join's inputs). While we |
| 1190 |
do not ignore merge joins entirely, joinpath.c does not fully explore the |
| 1191 |
space of potential merge joins with parameterized inputs. Also, add_path |
| 1192 |
treats parameterized paths as having no pathkeys, so that they compete |
| 1193 |
only on cost and rowcount; they don't get preference for producing a |
| 1194 |
special sort order. This creates additional bias against merge joins, |
| 1195 |
since we might discard a path that could have been useful for performing |
| 1196 |
a merge without an explicit sort step. Since a parameterized path must |
| 1197 |
ultimately be used on the inside of a nestloop, where its sort order is |
| 1198 |
uninteresting, these choices do not affect any requirement for the final |
| 1199 |
output order of a query --- they only make it harder to use a merge join |
| 1200 |
at a lower level. The savings in planning work justifies that. |
| 1201 |
|
| 1202 |
Similarly, parameterized paths do not normally get preference in add_path |
| 1203 |
for having cheap startup cost; that's seldom of much value when on the |
| 1204 |
inside of a nestloop, so it seems not worth keeping extra paths solely for |
| 1205 |
that. An exception occurs for parameterized paths for the RHS relation of |
| 1206 |
a SEMI or ANTI join: in those cases, we can stop the inner scan after the |
| 1207 |
first match, so it's primarily startup not total cost that we care about. |
| 1208 |
|
| 1209 |
|
| 1210 |
LATERAL subqueries |
| 1211 |
------------------ |
| 1212 |
|
| 1213 |
As of 9.3 we support SQL-standard LATERAL references from subqueries in |
| 1214 |
FROM (and also functions in FROM). The planner implements these by |
| 1215 |
generating parameterized paths for any RTE that contains lateral |
| 1216 |
references. In such cases, *all* paths for that relation will be |
| 1217 |
parameterized by at least the set of relations used in its lateral |
| 1218 |
references. (And in turn, join relations including such a subquery might |
| 1219 |
not have any unparameterized paths.) All the other comments made above for |
| 1220 |
parameterized paths still apply, though; in particular, each such path is |
| 1221 |
still expected to enforce any join clauses that can be pushed down to it, |
| 1222 |
so that all paths of the same parameterization have the same rowcount. |
| 1223 |
|
| 1224 |
We also allow LATERAL subqueries to be flattened (pulled up into the parent |
| 1225 |
query) by the optimizer, but only when this does not introduce lateral |
| 1226 |
references into JOIN/ON quals that would refer to relations outside the |
| 1227 |
lowest outer join at/above that qual. The semantics of such a qual would |
| 1228 |
be unclear. Note that even with this restriction, pullup of a LATERAL |
| 1229 |
subquery can result in creating PlaceHolderVars that contain lateral |
| 1230 |
references to relations outside their syntactic scope. We still evaluate |
| 1231 |
such PHVs at their syntactic location or lower, but the presence of such a |
| 1232 |
PHV in the quals or targetlist of a plan node requires that node to appear |
| 1233 |
on the inside of a nestloop join relative to the rel(s) supplying the |
| 1234 |
lateral reference. (Perhaps now that that stuff works, we could relax the |
| 1235 |
pullup restriction?) |
| 1236 |
|
| 1237 |
|
| 1238 |
Security-level constraints on qual clauses |
| 1239 |
------------------------------------------ |
| 1240 |
|
| 1241 |
To support row-level security and security-barrier views efficiently, |
| 1242 |
we mark qual clauses (RestrictInfo nodes) with a "security_level" field. |
| 1243 |
The basic concept is that a qual with a lower security_level must be |
| 1244 |
evaluated before one with a higher security_level. This ensures that |
| 1245 |
"leaky" quals that might expose sensitive data are not evaluated until |
| 1246 |
after the security barrier quals that are supposed to filter out |
| 1247 |
security-sensitive rows. However, many qual conditions are "leakproof", |
| 1248 |
that is we trust the functions they use to not expose data. To avoid |
| 1249 |
unnecessarily inefficient plans, a leakproof qual is not delayed by |
| 1250 |
security-level considerations, even if it has a higher syntactic |
| 1251 |
security_level than another qual. |
| 1252 |
|
| 1253 |
In a query that contains no use of RLS or security-barrier views, all |
| 1254 |
quals will have security_level zero, so that none of these restrictions |
| 1255 |
kick in; we don't even need to check leakproofness of qual conditions. |
| 1256 |
|
| 1257 |
If there are security-barrier quals, they get security_level zero (and |
| 1258 |
possibly higher, if there are multiple layers of barriers). Regular quals |
| 1259 |
coming from the query text get a security_level one more than the highest |
| 1260 |
level used for barrier quals. |
| 1261 |
|
| 1262 |
When new qual clauses are generated by EquivalenceClass processing, |
| 1263 |
they must be assigned a security_level. This is trickier than it seems. |
| 1264 |
One's first instinct is that it would be safe to use the largest level |
| 1265 |
found among the source quals for the EquivalenceClass, but that isn't |
| 1266 |
safe at all, because it allows unwanted delays of security-barrier quals. |
| 1267 |
Consider a barrier qual "t.x = t.y" plus a query qual "t.x = constant", |
| 1268 |
and suppose there is another query qual "leaky_function(t.z)" that |
| 1269 |
we mustn't evaluate before the barrier qual has been checked. |
| 1270 |
We will have an EC {t.x, t.y, constant} which will lead us to replace |
| 1271 |
the EC quals with "t.x = constant AND t.y = constant". (We do not want |
| 1272 |
to give up that behavior, either, since the latter condition could allow |
| 1273 |
use of an index on t.y, which we would never discover from the original |
| 1274 |
quals.) If these generated quals are assigned the same security_level as |
| 1275 |
the query quals, then it's possible for the leaky_function qual to be |
| 1276 |
evaluated first, allowing leaky_function to see data from rows that |
| 1277 |
possibly don't pass the barrier condition. |
| 1278 |
|
| 1279 |
Instead, our handling of security levels with ECs works like this: |
| 1280 |
* Quals are not accepted as source clauses for ECs in the first place |
| 1281 |
unless they are leakproof or have security_level zero. |
| 1282 |
* EC-derived quals are assigned the minimum (not maximum) security_level |
| 1283 |
found among the EC's source clauses. |
| 1284 |
* If the maximum security_level found among the EC's source clauses is |
| 1285 |
above zero, then the equality operators selected for derived quals must |
| 1286 |
be leakproof. When no such operator can be found, the EC is treated as |
| 1287 |
"broken" and we fall back to emitting its source clauses without any |
| 1288 |
additional derived quals. |
| 1289 |
|
| 1290 |
These rules together ensure that an untrusted qual clause (one with |
| 1291 |
security_level above zero) cannot cause an EC to generate a leaky derived |
| 1292 |
clause. This makes it safe to use the minimum not maximum security_level |
| 1293 |
for derived clauses. The rules could result in poor plans due to not |
| 1294 |
being able to generate derived clauses at all, but the risk of that is |
| 1295 |
small in practice because most btree equality operators are leakproof. |
| 1296 |
Also, by making exceptions for level-zero quals, we ensure that there is |
| 1297 |
no plan degradation when no barrier quals are present. |
| 1298 |
|
| 1299 |
Once we have security levels assigned to all clauses, enforcement |
| 1300 |
of barrier-qual ordering restrictions boils down to two rules: |
| 1301 |
|
| 1302 |
* Table scan plan nodes must not select quals for early execution |
| 1303 |
(for example, use them as index qualifiers in an indexscan) unless |
| 1304 |
they are leakproof or have security_level no higher than any other |
| 1305 |
qual that is due to be executed at the same plan node. (Use the |
| 1306 |
utility function restriction_is_securely_promotable() to check |
| 1307 |
whether it's okay to select a qual for early execution.) |
| 1308 |
|
| 1309 |
* Normal execution of a list of quals must execute them in an order |
| 1310 |
that satisfies the same security rule, ie higher security_levels must |
| 1311 |
be evaluated later unless leakproof. (This is handled in a single place |
| 1312 |
by order_qual_clauses() in createplan.c.) |
| 1313 |
|
| 1314 |
order_qual_clauses() uses a heuristic to decide exactly what to do with |
| 1315 |
leakproof clauses. Normally it sorts clauses by security_level then cost, |
| 1316 |
being careful that the sort is stable so that we don't reorder clauses |
| 1317 |
without a clear reason. But this could result in a very expensive qual |
| 1318 |
being done before a cheaper one that is of higher security_level. |
| 1319 |
If the cheaper qual is leaky we have no choice, but if it is leakproof |
| 1320 |
we could put it first. We choose to sort leakproof quals as if they |
| 1321 |
have security_level zero, but only when their cost is less than 10X |
| 1322 |
cpu_operator_cost; that restriction alleviates the opposite problem of |
| 1323 |
doing expensive quals first just because they're leakproof. |
| 1324 |
|
| 1325 |
Additional rules will be needed to support safe handling of join quals |
| 1326 |
when there is a mix of security levels among join quals; for example, it |
| 1327 |
will be necessary to prevent leaky higher-security-level quals from being |
| 1328 |
evaluated at a lower join level than other quals of lower security level. |
| 1329 |
Currently there is no need to consider that since security-prioritized |
| 1330 |
quals can only be single-table restriction quals coming from RLS policies |
| 1331 |
or security-barrier views, and security-barrier view subqueries are never |
| 1332 |
flattened into the parent query. Hence enforcement of security-prioritized |
| 1333 |
quals only happens at the table scan level. With extra rules for safe |
| 1334 |
handling of security levels among join quals, it should be possible to let |
| 1335 |
security-barrier views be flattened into the parent query, allowing more |
| 1336 |
flexibility of planning while still preserving required ordering of qual |
| 1337 |
evaluation. But that will come later. |
| 1338 |
|
| 1339 |
|
| 1340 |
Post scan/join planning |
| 1341 |
----------------------- |
| 1342 |
|
| 1343 |
So far we have discussed only scan/join planning, that is, implementation |
| 1344 |
of the FROM and WHERE clauses of a SQL query. But the planner must also |
| 1345 |
determine how to deal with GROUP BY, aggregation, and other higher-level |
| 1346 |
features of queries; and in many cases there are multiple ways to do these |
| 1347 |
steps and thus opportunities for optimization choices. These steps, like |
| 1348 |
scan/join planning, are handled by constructing Paths representing the |
| 1349 |
different ways to do a step, then choosing the cheapest Path. |
| 1350 |
|
| 1351 |
Since all Paths require a RelOptInfo as "parent", we create RelOptInfos |
| 1352 |
representing the outputs of these upper-level processing steps. These |
| 1353 |
RelOptInfos are mostly dummy, but their pathlist lists hold all the Paths |
| 1354 |
considered useful for each step. Currently, we may create these types of |
| 1355 |
additional RelOptInfos during upper-level planning: |
| 1356 |
|
| 1357 |
UPPERREL_SETOP result of UNION/INTERSECT/EXCEPT, if any |
| 1358 |
UPPERREL_PARTIAL_GROUP_AGG result of partial grouping/aggregation, if any |
| 1359 |
UPPERREL_GROUP_AGG result of grouping/aggregation, if any |
| 1360 |
UPPERREL_WINDOW result of window functions, if any |
| 1361 |
UPPERREL_PARTIAL_DISTINCT result of partial "SELECT DISTINCT", if any |
| 1362 |
UPPERREL_DISTINCT result of "SELECT DISTINCT", if any |
| 1363 |
UPPERREL_ORDERED result of ORDER BY, if any |
| 1364 |
UPPERREL_FINAL result of any remaining top-level actions |
| 1365 |
|
| 1366 |
UPPERREL_FINAL is used to represent any final processing steps, currently |
| 1367 |
LockRows (SELECT FOR UPDATE), LIMIT/OFFSET, and ModifyTable. There is no |
| 1368 |
flexibility about the order in which these steps are done, and thus no need |
| 1369 |
to subdivide this stage more finely. |
| 1370 |
|
| 1371 |
These "upper relations" are identified by the UPPERREL enum values shown |
| 1372 |
above, plus a relids set, which allows there to be more than one upperrel |
| 1373 |
of the same kind. We use NULL for the relids if there's no need for more |
| 1374 |
than one upperrel of the same kind. Currently, in fact, the relids set |
| 1375 |
is vestigial because it's always NULL, but that's expected to change in |
| 1376 |
the future. For example, in planning set operations, we might need the |
| 1377 |
relids to denote which subset of the leaf SELECTs has been combined in a |
| 1378 |
particular group of Paths that are competing with each other. |
| 1379 |
|
| 1380 |
The result of subquery_planner() is always returned as a set of Paths |
| 1381 |
stored in the UPPERREL_FINAL rel with NULL relids. The other types of |
| 1382 |
upperrels are created only if needed for the particular query. |
| 1383 |
|
| 1384 |
|
| 1385 |
Parallel Query and Partial Paths |
| 1386 |
-------------------------------- |
| 1387 |
|
| 1388 |
Parallel query involves dividing up the work that needs to be performed |
| 1389 |
either by an entire query or some portion of the query in such a way that |
| 1390 |
some of that work can be done by one or more worker processes, which are |
| 1391 |
called parallel workers. Parallel workers are a subtype of dynamic |
| 1392 |
background workers; see src/backend/access/transam/README.parallel for a |
| 1393 |
fuller description. The academic literature on parallel query suggests |
| 1394 |
that parallel execution strategies can be divided into essentially two |
| 1395 |
categories: pipelined parallelism, where the execution of the query is |
| 1396 |
divided into multiple stages and each stage is handled by a separate |
| 1397 |
process; and partitioning parallelism, where the data is split between |
| 1398 |
multiple processes and each process handles a subset of it. The |
| 1399 |
literature, however, suggests that gains from pipeline parallelism are |
| 1400 |
often very limited due to the difficulty of avoiding pipeline stalls. |
| 1401 |
Consequently, we do not currently attempt to generate query plans that |
| 1402 |
use this technique. |
| 1403 |
|
| 1404 |
Instead, we focus on partitioning parallelism, which does not require |
| 1405 |
that the underlying table be partitioned. It only requires that (1) |
| 1406 |
there is some method of dividing the data from at least one of the base |
| 1407 |
tables involved in the relation across multiple processes, (2) allowing |
| 1408 |
each process to handle its own portion of the data, and then (3) |
| 1409 |
collecting the results. Requirements (2) and (3) are satisfied by the |
| 1410 |
executor node Gather (or GatherMerge), which launches any number of worker |
| 1411 |
processes and executes its single child plan in all of them, and perhaps |
| 1412 |
in the leader also, if the children aren't generating enough data to keep |
| 1413 |
the leader busy. Requirement (1) is handled by the table scan node: when |
| 1414 |
invoked with parallel_aware = true, this node will, in effect, partition |
| 1415 |
the table on a block by block basis, returning a subset of the tuples from |
| 1416 |
the relation in each worker where that scan node is executed. |
| 1417 |
|
| 1418 |
Just as we do for non-parallel access methods, we build Paths to |
| 1419 |
represent access strategies that can be used in a parallel plan. These |
| 1420 |
are, in essence, the same strategies that are available in the |
| 1421 |
non-parallel plan, but there is an important difference: a path that |
| 1422 |
will run beneath a Gather node returns only a subset of the query |
| 1423 |
results in each worker, not all of them. To form a path that can |
| 1424 |
actually be executed, the (rather large) cost of the Gather node must be |
| 1425 |
accounted for. For this reason among others, paths intended to run |
| 1426 |
beneath a Gather node - which we call "partial" paths since they return |
| 1427 |
only a subset of the results in each worker - must be kept separate from |
| 1428 |
ordinary paths (see RelOptInfo's partial_pathlist and the function |
| 1429 |
add_partial_path). |
| 1430 |
|
| 1431 |
One of the keys to making parallel query effective is to run as much of |
| 1432 |
the query in parallel as possible. Therefore, we expect it to generally |
| 1433 |
be desirable to postpone the Gather stage until as near to the top of the |
| 1434 |
plan as possible. Expanding the range of cases in which more work can be |
| 1435 |
pushed below the Gather (and costing them accurately) is likely to keep us |
| 1436 |
busy for a long time to come. |
| 1437 |
|
| 1438 |
Partitionwise joins |
| 1439 |
------------------- |
| 1440 |
|
| 1441 |
A join between two similarly partitioned tables can be broken down into joins |
| 1442 |
between their matching partitions if there exists an equi-join condition |
| 1443 |
between the partition keys of the joining tables. The equi-join between |
| 1444 |
partition keys implies that all join partners for a given row in one |
| 1445 |
partitioned table must be in the corresponding partition of the other |
| 1446 |
partitioned table. Because of this the join between partitioned tables to be |
| 1447 |
broken into joins between the matching partitions. The resultant join is |
| 1448 |
partitioned in the same way as the joining relations, thus allowing an N-way |
| 1449 |
join between similarly partitioned tables having equi-join condition between |
| 1450 |
their partition keys to be broken down into N-way joins between their matching |
| 1451 |
partitions. This technique of breaking down a join between partitioned tables |
| 1452 |
into joins between their partitions is called partitionwise join. We will use |
| 1453 |
term "partitioned relation" for either a partitioned table or a join between |
| 1454 |
compatibly partitioned tables. |
| 1455 |
|
| 1456 |
Even if the joining relations don't have exactly the same partition bounds, |
| 1457 |
partitionwise join can still be applied by using an advanced |
| 1458 |
partition-matching algorithm. For both the joining relations, the algorithm |
| 1459 |
checks whether every partition of one joining relation only matches one |
| 1460 |
partition of the other joining relation at most. In such a case the join |
| 1461 |
between the joining relations can be broken down into joins between the |
| 1462 |
matching partitions. The join relation can then be considered partitioned. |
| 1463 |
The algorithm produces the pairs of the matching partitions, plus the |
| 1464 |
partition bounds for the join relation, to allow partitionwise join for |
| 1465 |
computing the join. The algorithm is implemented in partition_bounds_merge(). |
| 1466 |
For an N-way join relation considered partitioned this way, not every pair of |
| 1467 |
joining relations can use partitionwise join. For example: |
| 1468 |
|
| 1469 |
(A leftjoin B on (Pab)) innerjoin C on (Pac) |
| 1470 |
|
| 1471 |
where A, B, and C are partitioned tables, and A has an extra partition |
| 1472 |
compared to B and C. When considering partitionwise join for the join {A B}, |
| 1473 |
the extra partition of A doesn't have a matching partition on the nullable |
| 1474 |
side, which is the case that the current implementation of partitionwise join |
| 1475 |
can't handle. So {A B} is not considered partitioned, and the pair of {A B} |
| 1476 |
and C considered for the 3-way join can't use partitionwise join. On the |
| 1477 |
other hand, the pair of {A C} and B can use partitionwise join because {A C} |
| 1478 |
is considered partitioned by eliminating the extra partition (see identity 1 |
| 1479 |
on outer join reordering). Whether an N-way join can use partitionwise join |
| 1480 |
is determined based on the first pair of joining relations that are both |
| 1481 |
partitioned and can use partitionwise join. |
| 1482 |
|
| 1483 |
The partitioning properties of a partitioned relation are stored in its |
| 1484 |
RelOptInfo. The information about data types of partition keys are stored in |
| 1485 |
PartitionSchemeData structure. The planner maintains a list of canonical |
| 1486 |
partition schemes (distinct PartitionSchemeData objects) so that RelOptInfo of |
| 1487 |
any two partitioned relations with same partitioning scheme point to the same |
| 1488 |
PartitionSchemeData object. This reduces memory consumed by |
| 1489 |
PartitionSchemeData objects and makes it easy to compare the partition schemes |
| 1490 |
of joining relations. |
| 1491 |
|
| 1492 |
Partitionwise aggregates/grouping |
| 1493 |
--------------------------------- |
| 1494 |
|
| 1495 |
If the GROUP BY clause contains all of the partition keys, all the rows |
| 1496 |
that belong to a given group must come from a single partition; therefore, |
| 1497 |
aggregation can be done completely separately for each partition. Otherwise, |
| 1498 |
partial aggregates can be computed for each partition, and then finalized |
| 1499 |
after appending the results from the individual partitions. This technique of |
| 1500 |
breaking down aggregation or grouping over a partitioned relation into |
| 1501 |
aggregation or grouping over its partitions is called partitionwise |
| 1502 |
aggregation. Especially when the partition keys match the GROUP BY clause, |
| 1503 |
this can be significantly faster than the regular method. |