.\"----------------------------------------------------------------------
.\" FILE
.\"	query-tree.t
.\"
.\" DESCRIPTION
.\"	Specification for the query (parser => planner) and plan 
.\"	(planner => executor) trees
.\"
.\" RCS ID
.\"	$Header: /usr/local/devel/postgres/doc/implementation/RCS/query-tree.me,v 1.1 1990/07/30 13:50:41 kemnitz Exp $
.\"----------------------------------------------------------------------
.ds ar <\\(em\\(em
.nr pp 11
.nr sp 12
.nr tp 12
.nr fp 10
.ll 6.5i
.(l C
.sz \n(sp
.ft B
QUERY TREE / QUERY PLAN SPECIFICATION
(Printed: \*(td)
.ft R
.)l
.sp
.sz \n(pp
.sp
For notational purposes, anything appearing in italics is defined
elsewhere in this document.
Anything in bold face surrounded by quotes appears explicitly within a
runtime query tree/plan as a LISP string.
Anything appearing as a list is represented literally as a LISP list.
[] indicates something that is optional; {} indicates 0 or more.
.sp
.he 'Query Tree / Query Plan Specification''%'
.sh 1 "Query Tree Representation"
.sp
The parser will produce the following query tree for each query that
requires optimization:
.(l
(\fIRoot TargetList Qualification\fR)
.)l
Each of the above three components is a list containing further information.
.sh 2 "Root"
.sp
\fBRoot\fR looks like:
.(l
(\fINumLevels CommandType ResultRelation RangeTable Priority RuleInfo\fR)
.)l
This list contains information required by the planner as well as the
executor.
The planner itself does not modify any of these elements,
although some of its preprocessing routines may change portions of 
root before it is seen by the executor.
.sh 3 "NumLevels"
.sp
\fBNumLevels\fR indicates the maximum attribute nesting in a query.
That is, it indicates the maximum number of \*(lqnested dot\*(rq
fields found in any variable in that query.
For example, a query without range variables such as
.(l
retrieve (x = 1 + 2)
.)l
will have \fBNumLevels\fR = 0,
a query such as 
.(l
retrieve (pinhead.name) where pinhead.saying = "Yow!!!"
.)l
that contains normal range variables will have \fBNumLevels\fR = 1,
a query such as 
.(l
retrieve (sorority.all) where sorority.members.name = "Marti"
.)l
will have \fBNumLevels\fR = 2,
and so on.
.sh 3 "CommandType"
.sp
\fBCommandType\fR indicates what kind of query is being executed.
\fBCommandType\fR will be a single symbol from:
.(l
retrieve append replace delete
.)l
(other POSTQUEL commands are not optimized, so the planner should
never see them).
.sh 3 "ResultRelation"
.sp
\fBResultRelation\fR specifies the target relation of a 
\*(lqretrieve\*(rq
or the update relation for
\*(lqappend\*(rq, \*(lqreplace\*(rq, and \*(lqdelete\*(rq.
It may take one of three forms:
.np
If the query is a \*(lqretrieve\*(rq and no result relation is
specified, then \fBResultRelation\fR is nil.
.np
If the query is a \*(lqretrieve into\*(rq, then \fBResultRelation\fR
is a list containing a string representing the result relation's name
and a string from:
.(l
\fB\*(lqHEAVY\*(rq \*(lqLIGHT\*(rq \*(lqNONE\*(rq\fR
.)l
which represents the level of archiving which has been specified for the
result relation.
.np
If the query is an update, \fBResultRelation\fR will always be the
index into the \fIrangetable\fR corresponding to the relation to be
updated.
.sh 3 "RangeTable"
.sp
\fBRangeTable\fR is a list containing a \fIrangetable entry\fR for
each instance of a relation (i.e., range variable) in a query.  Every
\fIrelid\fR and \fIvarno\fR within the query tree, and almost every one
within the resulting query plan, is an integer index within the
query's rangetable.  This index is 1-based (e.g., var nodes that refer
to the first relation in the rangetable are given varno ``1'').
.sp
A rangetable entry looks like:
.(l
( \fIRelationName RelationOID TimeRange Flags RuleLocks\fR )
.)l
\fBRelationName\fR is a string corresponding to the relation's catalog
name, \fBRelationOID\fR is an integer corresponding to the OID of the
RELATION relation tuple that describes the given relation,
\fBTimeRange\fR is an internal structure that describes the historical
time span over which this rangetable entry is valid,
\fBFlags\fR is a list of zero or more symbols from:
.(l
archive inheritance union version
.)l
that specifies special treatment from the planner, and 
\fBRuleLocks\fR holds the rule lock information for that relation
(since this is generated by a planner preprocessor, the parser simply
puts nil here).
In the case of archival, inheritance, union and version queries,
the planner generates an \fBAPPEND\fR query plan node (see below) that
contains a set of rangetable entries which must be substituted in turn
for this rangetable entry, as well as separate query plans to be
executed.
.sh 3 "Priority"
.sp
\fBPriority\fR is simply an integer from 0..7 that indicates the
query priority.  Only rule plans can have priorities greater than 0.
.sh 3 "RuleInfo"
.sp
If the query is part of a \*(lqdefine rule\*(rq query, \fBRuleInfo\fR
is a containing a \fIrule identifier\fR and exactly one symbol from:
.(l
always once never
.)l
The rule identifier is an object identifier from the RULE relation;
the symbol is the tag associated with the rule definition.
For example, \fBRuleInfo\fR might look like:
.(l
( 387457893 always )
.)l
The rule identifier will be filled in by a traffic cop or planner
preprocessor routine.
For all other queries, \fBRuleInfo\fR is nil.
.sh 2 "TargetList"
.sp
A targetlist describes the structure of a tuple
and consists of a list of (\fIresdom expr\fR) pairs, one for
each attribute in the tuple to be constructed.
A \fBresdom\fR (result domain) node contains information about the
attribute, and
an \fBexpr\fR (expression) describes how to set the value of the
attribute.
.sp
The initial targetlist from the query tree describes what the final
result tuples should look like (targetlists are also used in
query plans to describe intermediate results such as scan projections,
join results, and temporaries).
In the case of the delete command, the initial targetlist is always nil.
For the other update queries, the planner's preprocessor fills in any
missing attributes that the user has not specified, either with
constants corresponding to the default values of the missing
attributes\**
.(f
\** If no default value exists for an attribute type, the attribute
will have a null value.
.)f
(for \*(lqappend\*(rq) or with variables corresponding to
the unchanged attributes of a tuple (for \*(lqreplace\*(rq).
.sp
The structure of the \fBresdom\fR node is described below;
an \fBexpr\fR can consist of a combination of nodes:
.(l
\fIexpr\fR = \fIvar\fR | \fIconst\fR | \fIparam\fR | (\fIoper expr\fR [\fIexpr\fR]) | (\fIfunc\fR {\fIexpr\fR})
.)l
.sp
The structures of the different nodes in an expr are described
below, but the function of the nodes may be briefly summarized as:
.nr zz \n(ii
.nr ii 6m
.sp
.ip \fIvar\fR
Refer to some relation attribute entry which corresponds to the target
list entry (i.e., the contents of a relation's tuple).
.ip \fIconst\fR
Constant values.
.ip \fIparam\fR
Used as parameters \(em placeholders for constants \(em within a
query.  The planner treats them as if they are constants of unknown
value (i.e., null constants) for optimization purposes.
.ip \fIoper\fR
Describes the system- or user-defined unary or binary operator that
will be applied to the argument exprs to produce a new value.
.ip \fIfunc\fR
Correspond to calls to system- or user-defined functions, which
may have zero or more arguments.
.nr ii \n(zz
.lp
Example:  ((\fIresdom var\fR) (\fIresdom\fR (\fIoper var var\fR)))
.br
is a targetlist with two attributes, where the second element involves
a computation between two tuple attributes.
.sh 2 "Qualification"
.sp
A qualification consists of restriction and join clauses which are
evaluated before the final result is returned.
.sp
The qualifications produced by the parser are not normalized in any
way.
That is, the parsed qualification will be an arbitrary boolean
expression:
.(l
\fIqualification\fR = ({\fIqual\fR})
\fIqual\fR = \fIexpr\fR | (\*(lq\fBNOT\fR\*(rq \fIqual\fR) | (\*(lq\fBOR\fR\*(rq \fIqual \fR{\fIqual\fR}) | (\*(lq\fBAND\fR\*(rq \fIqual \fR{\fIqual\fR})
.)l
.sp
The qualification supplied to the planner must be normalized in
certain ways.\**
.(f
\** This normalization occurs in yet another preprocessing module.
.)f
A qualification must be specified in conjunctive normal form.
Furthermore, if it is at all possible, all \*(lqnot\*(rqs are removed
and all variables are placed on the left hand side of the clause
operator.
If it is not possible to remove a \*(lqnot\*(rq (perhaps because a
negator is unavailable),
then the \*(lqnot\*(rq must be pushed to the innermost comparison,
e.g.,
\*(lq(not ((a = b) and (c = d)))\*(rq
might become
\*(lq(not (a = b) or not (c = d))\*(rq
if the operator \*(lq!=\*(rq does not exist for the appropriate types.
.sp
A qualification as seen by the planner is:
.(l
\fIqualification\fR = ({\fIqual\fR | \fIorqual\fR})
\fIqual\fR = \fIexpr\fR | (\*(lq\fBNOT\fR\*(rq \fIexpr\fR)
\fIorqual\fR = (\*(lq\fBOR\fR\*(rq \fIqual qual \fR{\fIqual\fR})
.)l
.sp
Example: If a user specifies the following clause:
.(l
not (r.f = 1) or (r.f2 > 1 and 2 > r.f2),
.)l
then in conjunctive normal form with \*(lqnot\*(rqs removed
and variables on the left hand side, we have the following equivalent clause:
.(l
(r.f != 1 or r.f2 > 1) and (r.f != 1 or r.f2 < 2)
.)l
In LISP form, it would look like:
.(l
((or (!= r.f 1) (> r.f2 1)) (or (!= r.f 1) (< r.f2 2)))
.)l
.sp
A set of macros for manipulating clause entries is contained in:
.(l
~postgres/src/planner/clauses.l
.)l
Additional parse tree manipulation routines are in:
.(l
~postgres/src/planner/nodeDefs.l
.)l
.bp
.sh 1 "Query Plan Representation"
.sp
A query plan is represented as a node.
Every plan node contains the following slots:
.(l
.ft B
state
qptargetlist
lefttree
righttree
.ft R
.)l
Thus, while a query plan is externally a single object, it may in fact
constitute a tree of plan nodes because of the child tree fields.
.sp
A \fIplan\fP consists of \fIsubplans\fP interconnected together with
\fBRESULT\fR,
\fBEXISTENTIAL\fP,
and
\fBAPPEND\fR
nodes.  These nodes may also have each other as children.
.sp
\fBRESULT\fR nodes interconnect plan levels.
The planner generates subqueries for all variables which operate at a
given level of nesting (that is, all non-nested variables are handled
in one plan level, all variables of the form \*(lqfoo.bar.baz\*(rq are
handled in another, and so on).
Thus, \fBRESULT\fR nodes indicate which attributes should be selected
from lower levels in the plan tree.
If a \fBRESULT\fR node has subtrees,
then the left tree always is a \fIsubplan\fR,
and the right tree is a \fIplan\fR for processing the
(more deeply nested) remainder of the query.
It is also possible for a \fBRESULT\fR node to have only a single left
subtree.
This occurs when the \fBRESULT\fR node is needed solely for storing
relation-level clauses.
A query plan can be a single \fBRESULT\fR node with no subtrees if the
query contains no variables.
.sp
\fBEXISTENTIAL\fP nodes also connect subplans.
The left subtree of an \fBEXISTENTIAL\fP node is a special
subplan which determines whether the existential members
of the subplan qualification are all true or not.
The right subtree is the actual query plan for the
subquery (minus the existential qualification clauses).
\fBEXISTENTIAL\fP nodes may also have one (left) or zero subtrees.
.sp
\fBAPPEND\fR nodes indicate that the executor should use the subplans it
contains sequentially, returning the appropriate tuples in a seamless
manner (at least as far as the external interface is concerned).
\fBAPPEND\fR nodes may be thought of as taking the place of N
scan nodes, each of which are substituted for the \fBAPPEND\fR node in turn.
.sp
A \fIsubplan\fR is an access plan for processing the (current)
topmost level of attributes in a query and consists of join and scan
nodes.
.sp
Joins are represented such that the left tree is the outer join relation
and the right tree is the inner join relation.
The three types of join nodes are:
.(l
.ft B
NESTLOOP
MERGESORT
HASHJOIN
.ft R
.)l
The two types of scan nodes are:
.(l
.ft B
SEQSCAN
INDEXSCAN
.ft R
.)l
.sp
Lastly, there are two types of nodes which involve the creation of
temporary relations:
.(l
.ft B
SORT
HASH
.ft R
.)l
If a stream of tuples must be sorted into a temporary prior
to join processing, its parent is a \fBSORT\fR node and the parent of
the \fBSORT\fR node is a \fBSEQSCAN\fR node:
.(l
<some-join> \fB\*(ar SEQSCAN \*(ar SORT \*(ar\fR <some-scan>
.)l
Similarly, if the relation is to be hashed, its corresponding scan
node's parent is a \fBHASH\fR node.
.(l
<some-join> \fB\*(ar SEQSCAN \*(ar HASH \*(ar\fR <some-scan>
.)l
Example: A \*(lqretrieve\*(rq involving a single mergesort join that
uses an index as an ordered inner path and a sorted outer path might
look like:
.(l
.ft B
MERGE	\*(ar SEQSCAN \*(ar SORT \*(ar SEQSCAN
SORT		\*(ar INDEXSCAN
.ft R
.)l
.sp
The same idea applies to sorts in general.  The node is simply
preceded by a \fBSORT\fR and then a \fBSEQSCAN\fR node in the plan
tree.  However, if a retrieve result is to be sorted into a relation,
the \fBSEQSCAN\fR node is omitted.
.sp
Example: The top level nodes for a plan that returns a set of tuples
that must be sorted into a particular order might look like:
.(l
\fBRESULT	\*(ar SORT \*(ar\fR ...rest of plan...
.)l
.bp
.sh 1 "Primitive Nodes"
.sp
The following is a description of the primitive nodes, which are used
in both the input query tree and the final query plan.
.sp
Each type of node is implemented as a defstruct vector.  To access
slots within a node, use:
.(l
(get_\fIslotname node\fR)
.)l
where \fIslotname\fR is the desired slot name as described in this
section and \fInode\fR is an appropriate defstruct node.
.sp
To set a slot field, use:
.(l
(set_\fIslotname node new-slot-value\fR)
.)l
For details see
.(l
~postgres/src/planner/nodeDefs.l
.)l
.sp
.sh 2 "RESDOM"
.ip "1)"
\fBresno\fR - result domain number.  This is equivalent to the
attribute number for a (temporary or result) tuple.  Just as attribute
numbers being at 1, a \fBresno\fR of 1 denotes the first attribute in
a targetlist.
.ip "2)"
\fBrestype\fR - either:
.br
(1) the OID corresponding to the type of the result, or
.br
(2) *UNION-TYPE-ID*, an identifier for a type internal to the planner
that describes multi-dot attributes (since it cannot determine the
final attribute type until the nesting is eliminated by the executor).
.ip "3)"
\fBreslen\fR - length of a domain element in bytes (-1 if it is
variable length).
.ip "4)"
\fBresname\fR - result domain name, either user-specified or the
corresponding name of an attribute (if applicable).
.ip "5)"
\fBreskey\fR - ordinality of the result domain as a sort or hash key,
e.g.,
0 if the domain won't be included as a sort or hash key;
1 if the domain is the first key,
2 if it is the second,
and so on.
.ip "6)"
\fBreskeyop\fR - OID of the operator on which \fBreskey\fR will be
sorted or hashed.
.sp
.lp
To create a \fBRESDOM\fR node:
.sp
(make_resdom \fIresno restype reslen resname reskey reskeyop\fR)
.sp
.sh 2 "VAR"
.ip "1)"
\fBvarno\fR - From the parser's standpoint, \fBvarno\fR is simply the
index into the rangetable corresponding to the relation an attribute
belongs to.
.sp
For the query processor, \fBvarno\fR may take on one of three values
depending on the attribute entry under consideration.
.br
(1) If \fBVAR\fR belongs to the relation currently being scanned
(either a cataloged or temporary relation, but not a materialized
one), \fBvarno\fR is still the \fIindex into the rangetable\fP
corresponding to the relation being scanned.
.br
(2) If \fBVAR\fR is associated with some join node, varno is the
\fIname of the temporary join relation\fP accessed.  If \fBVAR\fR
originates from the outer join relation, \fBvarno\fR =
\fB\*(lqOUTER\*(rq\fR.  If it originated from the inner join relation,
\fBvarno\fR = \fB\*(lqINNER\*(rq\fR.
.br
(3) For \fBVAR\fRs corresponding to entries within relations that are
materialized from a POSTQUEL field or attributes from some previous
nesting level, \fBvarno\fR is a \fIreference pair\fP, i.e., a list
(\fIlevelnum resno\fR), that corresponds to the attribute entry where
either the query field or desired value can be found.  \fIlevelnum\fR
refers to the processing level number (where \fI0\fR is the topmost),
and \fIresno\fR refers to the result domain number within the tuple
where the entry is stored.
.sp
Therefore, whether a relation should be materialized is implicit in
the \fBvarno\fR value and information in the attribute entry
corresponding to the query field.
.ip "2)"
\fBvarattno\fR - as with \fBvarno\fR, the meaning of this field
depends on the node's position in the plan tree.
.br
(1) For attributes at the topmost nesting level, \fBvarattno\fR
corresponds to the \fIattribute number\fR within a relation (or domain
number within a tuple if this is a join tuple \(em that is, if
\fBvarno\fR = \fB\*(lqOUTER\*(rq\fR or \fB\*(lqINNER\*(rq\fR).
.br
(2) If the attribute corresponds to some attribute from a previous
nesting level, \fBvarattno\fR = \fInil\fR.
.br
(3) For nested attributes, the value of \fBvarattno\fR is a
\fIstring\fR identical to the attribute name since the attribute
number will not be known until the POSTQUEL field is materialized.
Note that at the lowest nesting level, \fBvarattno\fR may be
\*(lq\fBALL\fR\*(rq (again, since neither the parser nor the planner
know what the attributes of the field's parent are \(em it must be
determined at run-time by the query processor when the appropriate
POSTQUEL field is retrieved).
.ip "3)"
\fBvartype\fR - either:
.br
(1) the OID of the type of the attribute referred to by \fBvarattno\fR,
or
.br
(2) *UNION-TYPE-ID*
.ip "4)"
\fBvardotfields\fR - list of attribute names beyond the first nesting
level.
.br
(\fIThis field is internal to the parser and planner\fR)
.ip "5)"
\fBvararrayindex\fR - array index of a variable, nil if this is not an
array attribute.
.br
Since arrays can only contain primitive types, only the bottommost
attribute in a nesting will be array indexed.  The parser will set
the \fBvararrayindex\fR field if a variable contains an array index.
The planner will only set this field if the query processor is to
retrieve an array element within some attribute entry.
.ip "6)"
\fBvarid\fR - a list containing \fBvarno\fR and \fBvarattno\fR, as
well as \fBvardotfields\fR and \fBvararrayindex\fR (if the latter two
exist).
.br
(\fIThis field is internal to the planner\fR)
.sp
.nf
Example: w.x.y.z[a]
.sp
.nf
The parser will set the following fields:
.sp
\fBvarno\fR = identifier of w, \fBvarattno\fR = attribute number of x, 
.br
\fBvardotfields\fR = (y z), \fBvararrayindex\fR = a,
.br
\fBvarid\fR = (\fBvarno varattno\fR y z (a)),
\fBvartype\fR = type of attribute x
.fi
.sp
.lp
To create a \fBVAR\fR node:
.sp
(make_var \fIvarno varattno vartype vardotfields vararrayindex varid\fR)
.sp
.sh 2 "OPER"
.ip "1)"
\fBopno\fR - for the parser, \fBopno\fR is the OID of the operator to
which this node corresponds.  For the executor, \fBopno\fR is the OID
of the operator \fIprocedure\fR.  The conversion occurs in the planner
(which needs the operator OID to determine selectivities).
.ip "2)"
\fBoprelationlevel\fR - t if an operator is a relation level operator.
.ip "3)"
\fBopresulttype\fR - OID of the result type of this particular
operator.
.sp
.lp
To create a \fBOPER\fR node:
.sp
(make_oper \fIopno oprelationlevel opresulttype\fR)
.sp
.sh 2 "CONST"
.ip "1)"
\fBconsttype\fR - OID of the constant's type.
.ip "2)"
\fBconstlen\fR - length in bytes (-1 if it is a variable-length type).
.ip "3)"
\fBconstvalue\fR - actual value of the constant (i.e., the internal
representation).
.br
\fBconstvalue\fR is nil if the constant is null.  Objects represented
by pointers must appear as palloc'ed LISP vectori-bytes.
.ip "4)"
\fBconstisnull\fR - t if the constant has the null value.
.br
This is set by the planner when filling in \*(lqreplace\*(rq and
\*(lqappend\*(rq targetlist entries which are unspecified by the user.
If the typdefault field of the \fBTYPE\fR relation is not specified,
\fBconstisnull\fR is set to t and \fBconstvalue\fR is set to nil.
.sp
.lp
To create a \fBCONST\fR node:
.sp
(make_const \fIconsttype constlen constvalue constisnull\fR)
.sp
.sh 2 "PARAM"
.ip "1)"
\fBparamid\fR - either:
.br
(1) a fixnum corresponding to the parameter name for constant value
substitution, e.g., \*(lq1\*(rq in the case of \*(lq$1\*(rq
.br
(2) a string corresponding to the attribute name for relation name
substitution, e.g, \*(lqattname\*(rq in the case of
\*(lq$.attname\*(rq
.sp
.lp
To create a \fBPARAM\fR node:
.sp
(make_param \fIparamid\fR)
.sp
.sh 2 "FUNC"
.ip "1)"
\fBfuncid\fR - OID of the function to which this node corresponds.
.ip "2)"
\fBfunctype\fR - OID of the type of the function's return value.
.sp
.lp
To create a \fBFUNC\fR node:
.sp
(make_func \fIfuncid functype\fR)
.bp
.sh 1 "Plan Nodes"
.sp
The following is a description of each type of plan node.  Each type
of node is implemented as a defstruct vector.  To access slots within
a node, use:
.(l
(get_\fIslotname node\fR)
.)l
where \fIslotname\fR is the desired slot name as described in this
section and \fInode\fR is an appropriate defstruct node.
.sp
To set a slot field, use:
.(l
(set_\fIslotname node new-slot-value\fR)
.)l
For details see
.(l
~postgres/src/planner/nodeDefs.l
.)l
.sp
.sh 2 "RESULT"
.ip "1)"
\fBstate\fR - used by the query executor to store runtime-specific
information.
.ip "2)"
\fBqptargetlist\fR - the target list for a sublevel of the query; the
attributes in node \fBRESULT\fI(i)\fR are derived from values returned
by \fIsubplan(i)\fR, and either \fBRESULT\fI(i+1)\fR or
\fIsubplan(i+1)\fR, depending on whether or not there is an i+1'th
nesting level.
.ip "3)"
\fBlefttree\fR - \fIsubplan(i)\fR.
.ip "4)"
\fBrighttree\fR - either \fBRESULT\fI(i+1)\fR or \fIsubplan(i+1)\fR,
depending on whether or not there are deeper nesting levels.
.ip "5)"
\fBresrellevelqual\fR - list of any relation level clauses that must
be satisfied (e.g., \*(lqR1.f1 = R2.f2\*(rq or \*(lqfoo.bar = 2\*(rq)
.ip "6)"
\fBresconstantqual\fR - a list containing all qualifications which
contain no var nodes.
.br
This field will only be set at the topmost \fBRESULT\fR node.  These
qualifications should always be tested first at runtime; if they are
false, then the rest of the query plan need not be processed because
no tuples will be returned.
.sp
To create a \fBRESULT\fR node:
.sp
(make_result \fIqptargetlist resrellevelqual lefttree righttree\fR)
.sp
.sh 2 "EXISTENTIAL"
.ip "1)"
\fBstate\fR
.ip "2)"
\fBqptargetlist\fR - always nil.
.ip "3)"
\fBlefttree\fR - subplan for the existential query.
.br
This is planned as a \*(lqretrieve\*(rq with a null target list.
.ip "4)"
\fBrighttree\fR - subplan for the non-existential query.
.sp
.lp
To create a \fBEXISTENTIAL\fR node:
.sp
(make_existential \fIlefttree righttree\fR)
.sp
.sh 2 "APPEND"
.ip "1)"
\fBstate\fR
.ip "2) - 4) \fBqptargetlist\fR, \fBlefttree\fR, \fBrighttree\fR - always nil"
.ip "5)"
\fBplans\fR - a list of plans which are to be executed sequentially.
.ip "6)"
\fBrelid\fR - the rangetable index of the variable which caused this
node to be formed.  For example, if this is a query that uses the
\fBfrom\fR clause \*(lqfrom p in person*\*(rq, then this would contain
the rangetable index of the entry for \*(lqperson\*(rq.
.ip "7)"
\fBrtentries\fR - a list of rangetable entries which must be
substituted into the executor's rangetable in conjunction with
execution of the plans stored in the \fBplans\fR field.
.ip "8)"
\fBflags\fR - a symbol from 
\fBarchive\fR, \fBinheritance\fR, \fBunion\fR, or \fBversion\fR
that specifies how the executor should execute each entry in the
\fBplans\fR.
.sp
.lp
To create a \fBAPPEND\fR node:
.sp
(make_append \fIplans relid rtentries flags\fR)
.sp
.sh 2 "NESTLOOP"
.ip "1)"
\fBstate\fR
.ip "2)"
\fBqptargetlist\fR - attributes to be retrieved into the join result
from attributes in the inner and outer join relations.
.ip "3)"
\fBlefttree\fR - outer join path.
.ip "4)"
\fBrighttree\fR - inner join path.
.ip "5)"
\fBqpqual\fR - a list of join clauses to be satisfied.
.sp
.lp
To create a \fBNESTLOOP\fR node:
.sp
(make_nestloop \fIqptargetlist qpqual lefttree righttree\fR)
.sp
.sh 2 "HASHJOIN"
.ip "1) - 5) from above"
.ip "6)"
\fBmergehashclauses\fR - join clauses to be used in performing the
hash join; if there are multiple clauses, the clauses are arranged in
the order of the hash keys, from primary downward.
.br
Note: These clauses are not contained in \fBqpqual\fR above to avoid
redundant checking.
.sp
.lp
To create a \fBHASHJOIN\fR node:
.sp
(make_hashjoin \fIqptargetlist qpqual mergehashclauses lefttree righttree\fR)
.sp
.sh 2 "MERGESORT"
.ip "1) - 5) from above"
.ip "6)"
\fBmergehashclauses\fR - join clauses to be used in performing the
merge join; if there are multiple clauses, the clauses are arranged in
the order of the merge keys, from the primary ordering key downward.
.br
(Again, these clauses are not contained in \fBqpqual\fR)
.ip "7)"
\fBmergesortop\fR - OID of the operator procedure used to merge the
tuples.
.sp
.lp
To create a \fBMERGESORT\fR node:
.sp
(make_mergesort \fIqptargetlist qpqual mergehashclauses mergesortop lefttree righttree\fR)
.sp
.sh 2 "SEQSCAN"
.ip "1)"
\fBstate\fR
.ip "2)"
\fBqptargetlist\fR - attributes to be retrieved into scan result.
.ip "3)"
\fBlefttree\fR - either nil, a \fBSORT\fR node, or a \fBHASH\fR node.
.ip "4)"
\fBrighttree\fR - always nil.
.ip "5)"
\fBqpqual\fR - list of restriction clauses on the relation.
.ip "6)"
\fBscanrelid\fR - either:
.br
(1) an index into the rangetable corresponding to the relation to be
scanned, or
.br
(2) a reference to an attribute from a previous level that corresponds
to a relation to be materialized from some POSTQUEL field.
.sp
.lp
To create a \fBSEQSCAN\fR node:
.sp
(make_seqscan \fIqptargetlist qpqual scanrelid lefttree\fR)
.sp
.sh 2 "INDEXSCAN"
.ip "1) - 2) from above"
.ip "3) - 4) \fBlefttree\fR, \fBrighttree\fR - always nil.
.ip "5) - 6) from above"
.ip "7)"
\fBindxid\fR - list of the OIDs of all indices to be used to scan a
relation: (OID1 OID2 ... ).  The idea here is that more than one index
may be used to scan a relation.  For example, if we have the clause
\*(lqR.foo = foo or R.foo = foobar\*(rq, the first index might use
\*(lqfoo\*(rq as a key and the second could use \*(lqfoobar\*(rq.
Currently, this tactic is only used as just described (in conjunction
with \*(lqor\*(rq clauses).
.ip "8)"
\fBindxqual\fR - list of qualifications to be used in conjunction with
each index (e.g., ((qual1) (qual2)), where qual1 corresponds to ID1
and qual2 corresponds to ID2).  For multi-key indices, subclauses are
arranged in the order of the index keys.
.br
Note, again, that the clauses here are not contained in the
\fBqpqual\fR field above to avoid redundant checking.
.sp
If \fBindxqual\fR is nil, but \fBindxid\fR isn't, then the entire
relation is to be scanned starting at the first key of the index.
This is used when the ordering of an indexscan is needed for a
mergesort.
.sp
If an index is defined on an inner join relation, \fBindxqual\fR may
be a join clause.  If this is the case, the query processor must
substitute values for the outer relation at runtime.  The outer join
attribute is identified by its relative position of within the
resulting tuple of the outer join relation.  This type of
qualification is also omitted from \fBqpqual\fR above to avoid
redundant checking.
.sp
.lp
To create a \fBINDEXSCAN\fR node:
.sp
(make_indexscan \fIqptargetlist qpqual scanrelid indxid indxqual\fR)
.sp
.sh 2 "SORT"
.ip "1)"
\fBstate\fR
.ip "2)"
\fBqptargetlist\fR - targetlist for the tuples which are to be placed
into the temporary relation.
.ip "3)"
\fBlefttree\fR - plan node whose result is to be sorted.
.ip "4)"
\fBrighttree\fR - always nil.
.ip "5)"
\fBtempid\fR - either:
.br
(1) a string corresponding to a user-specified result relation, or 
.br
(2) *TEMP-RELATION-ID* (a special identifier indicating a temporary
relation).
.ip "6)"
\fBkeycount\fR - the number of sort keys.
.sp
.lp
To create a \fBSORT\fR node:
.sp
(make_sort \fIqptargetlist tempid lefttree\fR)
.sp
.sh 2 "HASH"
.ip "1) - 6) from above"
.sp 2
.lp
To create a \fBHASH\fR node:
.sp
(make_hash \fIqptargetlist tempid lefttree\fR)