Debian Codegraph @

src/backend/executor/README

raw
1 src/backend/executor/README
2
3 The Postgres Executor
4 =====================
5
6 The executor processes a tree of "plan nodes". The plan tree is essentially
7 a demand-pull pipeline of tuple processing operations. Each node, when
8 called, will produce the next tuple in its output sequence, or NULL if no
9 more tuples are available. If the node is not a primitive relation-scanning
10 node, it will have child node(s) that it calls in turn to obtain input
11 tuples.
12
13 Refinements on this basic model include:
14
15 * Choice of scan direction (forwards or backwards). Caution: this is not
16 currently well-supported. It works for primitive scan nodes, but not very
17 well for joins, aggregates, etc.
18
19 * Rescan command to reset a node and make it generate its output sequence
20 over again.
21
22 * Parameters that can alter a node's results. After adjusting a parameter,
23 the rescan command must be applied to that node and all nodes above it.
24 There is a moderately intelligent scheme to avoid rescanning nodes
25 unnecessarily (for example, Sort does not rescan its input if no parameters
26 of the input have changed, since it can just reread its stored sorted data).
27
28 For a SELECT, it is only necessary to deliver the top-level result tuples
29 to the client. For INSERT/UPDATE/DELETE/MERGE, the actual table modification
30 operations happen in a top-level ModifyTable plan node. If the query
31 includes a RETURNING clause, the ModifyTable node delivers the computed
32 RETURNING rows as output, otherwise it returns nothing. Handling INSERT
33 is pretty straightforward: the tuples returned from the plan tree below
34 ModifyTable are inserted into the correct result relation. For UPDATE,
35 the plan tree returns the new values of the updated columns, plus "junk"
36 (hidden) column(s) identifying which table row is to be updated. The
37 ModifyTable node must fetch that row to extract values for the unchanged
38 columns, combine the values into a new row, and apply the update. (For a
39 heap table, the row-identity junk column is a CTID, but other things may
40 be used for other table types.) For DELETE, the plan tree need only deliver
41 junk row-identity column(s), and the ModifyTable node visits each of those
42 rows and marks the row deleted. MERGE is described below.
43
44 XXX a great deal more documentation needs to be written here...
45
46
47 Plan Trees and State Trees
48 --------------------------
49
50 The plan tree delivered by the planner contains a tree of Plan nodes (struct
51 types derived from struct Plan). During executor startup we build a parallel
52 tree of identical structure containing executor state nodes --- generally,
53 every plan node type has a corresponding executor state node type. Each node
54 in the state tree has a pointer to its corresponding node in the plan tree,
55 plus executor state data as needed to implement that node type. This
56 arrangement allows the plan tree to be completely read-only so far as the
57 executor is concerned: all data that is modified during execution is in the
58 state tree. Read-only plan trees make life much simpler for plan caching and
59 reuse.
60
61 A corresponding executor state node may not be created during executor startup
62 if the executor determines that an entire subplan is not required due to
63 execution time partition pruning determining that no matching records will be
64 found there. This currently only occurs for Append and MergeAppend nodes. In
65 this case the non-required subplans are ignored and the executor state's
66 subnode array will become out of sequence to the plan's subplan list.
67
68 Each Plan node may have expression trees associated with it, to represent
69 its target list, qualification conditions, etc. These trees are also
70 read-only to the executor, but the executor state for expression evaluation
71 does not mirror the Plan expression's tree shape, as explained below.
72 Rather, there's just one ExprState node per expression tree, although this
73 may have sub-nodes for some complex expression node types.
74
75 Altogether there are four classes of nodes used in these trees: Plan nodes,
76 their corresponding PlanState nodes, Expr nodes, and ExprState nodes.
77 (Actually, there are also List nodes, which are used as "glue" in all
78 three tree-based representations.)
79
80
81 Expression Trees and ExprState nodes
82 ------------------------------------
83
84 Expression trees, in contrast to Plan trees, are not mirrored into a
85 corresponding tree of state nodes. Instead each separately executable
86 expression tree (e.g. a Plan's qual or targetlist) is represented by one
87 ExprState node. The ExprState node contains the information needed to
88 evaluate the expression in a compact, linear form. That compact form is
89 stored as a flat array in ExprState->steps[] (an array of ExprEvalStep,
90 not ExprEvalStep *).
91
92 The reasons for choosing such a representation include:
93 - commonly the amount of work needed to evaluate one Expr-type node is
94 small enough that the overhead of having to perform a tree-walk
95 during evaluation is significant.
96 - the flat representation can be evaluated non-recursively within a single
97 function, reducing stack depth and function call overhead.
98 - such a representation is usable both for fast interpreted execution,
99 and for compiling into native code.
100
101 The Plan-tree representation of an expression is compiled into an
102 ExprState node by ExecInitExpr(). As much complexity as possible should
103 be handled by ExecInitExpr() (and helpers), instead of execution time
104 where both interpreted and compiled versions would need to deal with the
105 complexity. Besides duplicating effort between execution approaches,
106 runtime initialization checks also have a small but noticeable cost every
107 time the expression is evaluated. Therefore, we allow ExecInitExpr() to
108 precompute information that we do not expect to vary across execution of a
109 single query, for example the set of CHECK constraint expressions to be
110 applied to a domain type. This could not be done at plan time without
111 greatly increasing the number of events that require plan invalidation.
112 (Previously, some information of this kind was rechecked on each
113 expression evaluation, but that seems like unnecessary overhead.)
114
115
116 Expression Initialization
117 -------------------------
118
119 During ExecInitExpr() and similar routines, Expr trees are converted
120 into the flat representation. Each Expr node might be represented by
121 zero, one, or more ExprEvalSteps.
122
123 Each ExprEvalStep's work is determined by its opcode (of enum ExprEvalOp)
124 and it stores the result of its work into the Datum variable and boolean
125 null flag variable pointed to by ExprEvalStep->resvalue/resnull.
126 Complex expressions are performed by chaining together several steps.
127 For example, "a + b" (one OpExpr, with two Var expressions) would be
128 represented as two steps to fetch the Var values, and one step for the
129 evaluation of the function underlying the + operator. The steps for the
130 Vars would have their resvalue/resnull pointing directly to the appropriate
131 args[].value .isnull elements in the FunctionCallInfoBaseData struct that
132 is used by the function evaluation step, thus avoiding extra work to copy
133 the result values around.
134
135 The last entry in a completed ExprState->steps array is always an
136 EEOP_DONE_RETURN or EEOP_DONE_NO_RETURN step; this removes the need to
137 test for end-of-array while iterating. The former is used when the
138 expression returns a value directly, the latter when side-effects of
139 expression initialization are the goal (e.g. for projection or
140 aggregate transition value computation).
141
142 Also, if the expression contains any variable references (to user
143 columns of the ExprContext's INNER, OUTER, or SCAN tuples), the steps
144 array begins with EEOP_*_FETCHSOME steps that ensure that the relevant
145 tuples have been deconstructed to make the required columns directly
146 available (cf. slot_getsomeattrs()). This allows individual Var-fetching
147 steps to be little more than an array lookup.
148
149 Most of ExecInitExpr()'s work is done by the recursive function
150 ExecInitExprRec() and its subroutines. ExecInitExprRec() maps one Expr
151 node into the steps required for execution, recursing as needed for
152 sub-expressions.
153
154 Each ExecInitExprRec() call has to specify where that subexpression's
155 results are to be stored (via the resv/resnull parameters). This allows
156 the above scenario of evaluating a (sub-)expression directly into
157 fcinfo->args[].value/isnull, but also requires some care: target Datum/isnull
158 variables may not be shared with another ExecInitExprRec() unless the
159 results are only needed by steps executing before further usages of those
160 target Datum/isnull variables. Due to the non-recursiveness of the
161 ExprEvalStep representation that's usually easy to guarantee.
162
163 ExecInitExprRec() pushes new operations into the ExprState->steps array
164 using ExprEvalPushStep(). To keep the steps as a consecutively laid out
165 array, ExprEvalPushStep() has to repalloc the entire array when there's
166 not enough space. Because of that it is *not* allowed to point directly
167 into any of the steps during expression initialization. Therefore, the
168 resv/resnull for a subexpression usually point to some storage that is
169 palloc'd separately from the steps array. For instance, the
170 FunctionCallInfoBaseData for a function call step is separately allocated
171 rather than being part of the ExprEvalStep array. The overall result
172 of a complete expression is typically returned into the resvalue/resnull
173 fields of the ExprState node itself.
174
175 Some steps, e.g. boolean expressions, allow skipping evaluation of
176 certain subexpressions. In the flat representation this amounts to
177 jumping to some later step rather than just continuing consecutively
178 with the next step. The target for such a jump is represented by
179 the integer index in the ExprState->steps array of the step to execute
180 next. (Compare the EEO_NEXT and EEO_JUMP macros in execExprInterp.c.)
181
182 Typically, ExecInitExprRec() has to push a jumping step into the steps
183 array, then recursively generate steps for the subexpression that might
184 get skipped over, then go back and fix up the jump target index using
185 the now-known length of the subexpression's steps. This is handled by
186 adjust_jumps lists in execExpr.c.
187
188 The last step in constructing an ExprState is to apply ExecReadyExpr(),
189 which readies it for execution using whichever execution method has been
190 selected.
191
192
193 Expression Evaluation
194 ---------------------
195
196 To allow for different methods of expression evaluation, and for
197 better branch/jump target prediction, expressions are evaluated by
198 calling ExprState->evalfunc (via ExecEvalExpr() and friends).
199
200 ExecReadyExpr() can choose the method of interpretation by setting
201 evalfunc to an appropriate function. The default execution function,
202 ExecInterpExpr, is implemented in execExprInterp.c; see its header
203 comment for details. Special-case evalfuncs are used for certain
204 especially-simple expressions.
205
206 Note that a lot of the more complex expression evaluation steps, which are
207 less performance-critical than the simpler ones, are implemented as
208 separate functions outside the fast-path of expression execution, allowing
209 their implementation to be shared between interpreted and compiled
210 expression evaluation. This means that these helper functions are not
211 allowed to perform expression step dispatch themselves, as the method of
212 dispatch will vary based on the caller. The helpers therefore cannot call
213 for the execution of subexpressions; all subexpression results they need
214 must be computed by earlier steps. And dispatch to the following
215 expression step must be performed after returning from the helper.
216
217
218 Targetlist Evaluation
219 ---------------------
220
221 ExecBuildProjectionInfo builds an ExprState that has the effect of
222 evaluating a targetlist into ExprState->resultslot. A generic targetlist
223 expression is executed by evaluating it as discussed above (storing the
224 result into the ExprState's resvalue/resnull fields) and then using an
225 EEOP_ASSIGN_TMP step to move the result into the appropriate tts_values[]
226 and tts_isnull[] array elements of the result slot. There are special
227 fast-path step types (EEOP_ASSIGN_*_VAR) to handle targetlist entries that
228 are simple Vars using only one step instead of two.
229
230
231 MERGE
232 -----
233
234 MERGE is a multiple-table, multiple-action command: It specifies a target
235 table and a source relation, and can contain multiple WHEN MATCHED and
236 WHEN NOT MATCHED clauses, each of which specifies one UPDATE, INSERT,
237 DELETE, or DO NOTHING actions. The target table is modified by MERGE,
238 and the source relation supplies additional data for the actions. Each action
239 optionally specifies a qualifying expression that is evaluated for each tuple.
240
241 In the planner, transform_MERGE_to_join constructs a join between the target
242 table and the source relation, with row-identifying junk columns from the target
243 table. This join is an outer join if the MERGE command contains any WHEN NOT
244 MATCHED clauses; the ModifyTable node fetches tuples from the plan tree of that
245 join. If the row-identifying columns in the fetched tuple are NULL, then the
246 source relation contains a tuple that is not matched by any tuples in the
247 target table, so the qualifying expression for each WHEN NOT MATCHED clause is
248 evaluated given that tuple as returned by the plan. If the expression returns
249 true, the action indicated by the clause is executed, and no further clauses
250 are evaluated. On the other hand, if the row-identifying columns are not
251 NULL, then the matching tuple from the target table can be fetched; qualifying
252 expression of each WHEN MATCHED clause is evaluated given both the fetched
253 tuple and the tuple returned by the plan.
254
255 If no WHEN NOT MATCHED clauses are present, then the join constructed by
256 the planner is an inner join, and the row-identifying junk columns are
257 always non NULL.
258
259 If WHEN MATCHED ends up processing a row that is concurrently updated or deleted,
260 EvalPlanQual (see below) is used to find the latest version of the row, and
261 that is re-fetched; if it exists, the search for a matching WHEN MATCHED clause
262 to use starts at the top.
263
264 MERGE does not allow its own type of triggers, but instead fires UPDATE, DELETE,
265 and INSERT triggers: row triggers are fired for each row when an action is
266 executed for that row. Statement triggers are fired always, regardless of
267 whether any rows match the corresponding clauses.
268
269
270 Memory Management
271 -----------------
272
273 A "per query" memory context is created during CreateExecutorState();
274 all storage allocated during an executor invocation is allocated in that
275 context or a child context. This allows easy reclamation of storage
276 during executor shutdown --- rather than messing with retail pfree's and
277 probable storage leaks, we just destroy the memory context.
278
279 In particular, the plan state trees and expression state trees described
280 in the previous section are allocated in the per-query memory context.
281
282 To avoid intra-query memory leaks, most processing while a query runs
283 is done in "per tuple" memory contexts, which are so-called because they
284 are typically reset to empty once per tuple. Per-tuple contexts are usually
285 associated with ExprContexts, and commonly each PlanState node has its own
286 ExprContext to evaluate its qual and targetlist expressions in.
287
288
289 Query Processing Control Flow
290 -----------------------------
291
292 This is a sketch of control flow for full query processing:
293
294 CreateQueryDesc
295
296 ExecutorStart
297 CreateExecutorState
298 creates per-query context
299 switch to per-query context to run ExecInitNode
300 AfterTriggerBeginQuery
301 ExecInitNode --- recursively scans plan tree
302 ExecInitNode
303 recurse into subsidiary nodes
304 CreateExprContext
305 creates per-tuple context
306 ExecInitExpr
307
308 ExecutorRun
309 ExecProcNode --- recursively called in per-query context
310 ExecEvalExpr --- called in per-tuple context
311 ResetExprContext --- to free memory
312
313 ExecutorFinish
314 ExecPostprocessPlan --- run any unfinished ModifyTable nodes
315 AfterTriggerEndQuery
316
317 ExecutorEnd
318 ExecEndNode --- recursively releases resources
319 FreeExecutorState
320 frees per-query context and child contexts
321
322 FreeQueryDesc
323
324 Per above comments, it's not really critical for ExecEndNode to free any
325 memory; it'll all go away in FreeExecutorState anyway. However, we do need to
326 be careful to close relations, drop buffer pins, etc, so we do need to scan
327 the plan state tree to find these sorts of resources.
328
329
330 The executor can also be used to evaluate simple expressions without any Plan
331 tree ("simple" meaning "no aggregates and no sub-selects", though such might
332 be hidden inside function calls). This case has a flow of control like
333
334 CreateExecutorState
335 creates per-query context
336
337 CreateExprContext -- or use GetPerTupleExprContext(estate)
338 creates per-tuple context
339
340 ExecPrepareExpr
341 temporarily switch to per-query context
342 run the expression through expression_planner
343 ExecInitExpr
344
345 Repeatedly do:
346 ExecEvalExprSwitchContext
347 ExecEvalExpr --- called in per-tuple context
348 ResetExprContext --- to free memory
349
350 FreeExecutorState
351 frees per-query context, as well as ExprContext
352 (a separate FreeExprContext call is not necessary)
353
354
355 EvalPlanQual (READ COMMITTED Update Checking)
356 ---------------------------------------------
357
358 For simple SELECTs, the executor need only pay attention to tuples that are
359 valid according to the snapshot seen by the current transaction (ie, they
360 were inserted by a previously committed transaction, and not deleted by any
361 previously committed transaction). However, for UPDATE, DELETE, and MERGE it
362 is not cool to modify or delete a tuple that's been modified by an open or
363 concurrently-committed transaction. If we are running in SERIALIZABLE
364 isolation level then we just raise an error when this condition is seen to
365 occur. In READ COMMITTED isolation level, we must work a lot harder.
366
367 The basic idea in READ COMMITTED mode is to take the modified tuple
368 committed by the concurrent transaction (after waiting for it to commit,
369 if need be) and re-evaluate the query qualifications to see if it would
370 still meet the quals. If so, we regenerate the updated tuple (if we are
371 doing an UPDATE) from the modified tuple, and finally update/delete the
372 modified tuple. SELECT FOR UPDATE/SHARE behaves similarly, except that its
373 action is just to lock the modified tuple and return results based on that
374 version of the tuple.
375
376 To implement this checking, we actually re-run the query from scratch for
377 each modified tuple (or set of tuples, for SELECT FOR UPDATE), with the
378 relation scan nodes tweaked to return only the current tuples --- either
379 the original ones, or the updated (and now locked) versions of the modified
380 tuple(s). If this query returns a tuple, then the modified tuple(s) pass
381 the quals (and the query output is the suitably modified update tuple, if
382 we're doing UPDATE). If no tuple is returned, then the modified tuple(s)
383 fail the quals, so we ignore the current result tuple and continue the
384 original query.
385
386 In UPDATE/DELETE/MERGE, only the target relation needs to be handled this way.
387 In SELECT FOR UPDATE, there may be multiple relations flagged FOR UPDATE,
388 so we obtain lock on the current tuple version in each such relation before
389 executing the recheck.
390
391 It is also possible that there are relations in the query that are not
392 to be locked (they are neither the UPDATE/DELETE/MERGE target nor specified
393 to be locked in SELECT FOR UPDATE/SHARE). When re-running the test query
394 we want to use the same rows from these relations that were joined to
395 the locked rows. For ordinary relations this can be implemented relatively
396 cheaply by including the row TID in the join outputs and re-fetching that
397 TID. (The re-fetch is expensive, but we're trying to optimize the normal
398 case where no re-test is needed.) We have also to consider non-table
399 relations, such as a ValuesScan or FunctionScan. For these, since there
400 is no equivalent of TID, the only practical solution seems to be to include
401 the entire row value in the join output row.
402
403 We disallow set-returning functions in the targetlist of SELECT FOR UPDATE,
404 so as to ensure that at most one tuple can be returned for any particular
405 set of scan tuples. Otherwise we'd get duplicates due to the original
406 query returning the same set of scan tuples multiple times. Likewise,
407 SRFs are disallowed in an UPDATE's targetlist. There, they would have the
408 effect of the same row being updated multiple times, which is not very
409 useful --- and updates after the first would have no effect anyway.
410
411
412 Asynchronous Execution
413 ----------------------
414
415 In cases where a node is waiting on an event external to the database system,
416 such as a ForeignScan awaiting network I/O, it's desirable for the node to
417 indicate that it cannot return any tuple immediately but may be able to do so
418 at a later time. A process which discovers this type of situation can always
419 handle it simply by blocking, but this may waste time that could be spent
420 executing some other part of the plan tree where progress could be made
421 immediately. This is particularly likely to occur when the plan tree contains
422 an Append node. Asynchronous execution runs multiple parts of an Append node
423 concurrently rather than serially to improve performance.
424
425 For asynchronous execution, an Append node must first request a tuple from an
426 async-capable child node using ExecAsyncRequest. Next, it must execute the
427 asynchronous event loop using ExecAppendAsyncEventWait. Eventually, when a
428 child node to which an asynchronous request has been made produces a tuple,
429 the Append node will receive it from the event loop via ExecAsyncResponse. In
430 the current implementation of asynchronous execution, the only node type that
431 requests tuples from an async-capable child node is an Append, while the only
432 node type that might be async-capable is a ForeignScan.
433
434 Typically, the ExecAsyncResponse callback is the only one required for nodes
435 that wish to request tuples asynchronously. On the other hand, async-capable
436 nodes generally need to implement three methods:
437
438 1. When an asynchronous request is made, the node's ExecAsyncRequest callback
439 will be invoked; it should use ExecAsyncRequestPending to indicate that the
440 request is pending for a callback described below. Alternatively, it can
441 instead use ExecAsyncRequestDone if a result is available immediately.
442
443 2. When the event loop wishes to wait or poll for file descriptor events, the
444 node's ExecAsyncConfigureWait callback will be invoked to configure the
445 file descriptor event for which the node wishes to wait.
446
447 3. When the file descriptor becomes ready, the node's ExecAsyncNotify callback
448 will be invoked; like #1, it should use ExecAsyncRequestPending for another
449 callback or ExecAsyncRequestDone to return a result immediately.