<!--

$Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.22 2003/09/29 18:18:35 momjian Exp $

$Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.23 2003/11/01 01:56:28 petere Exp $

-->

<chapter id="overview">

<para>

The executor recursively steps through

the <firstterm>plan tree</firstterm> and

retrievestuples in the way represented by the plan.

retrievesrows in the way represented by the plan.

The executor makes use of the

<firstterm>storage system</firstterm> while scanning

relations, performs <firstterm>sorts</firstterm> and <firstterm>joins</firstterm>,

evaluates <firstterm>qualifications</firstterm> and finally hands back thetuples derived.

evaluates <firstterm>qualifications</firstterm> and finally hands back therows derived.

</para>

</step>

</procedure>

to the <firstterm>backend</firstterm> (server). The query is transmitted using plain text,

i.e. there is no parsing done in the <firstterm>frontend</firstterm> (client). The

server parses the query, creates an <firstterm>execution plan</firstterm>,

executes the plan and returns the retrievedtuples to the client

executes the plan and returns the retrievedrows to the client

by transmitting them over the established connection.

</para>

</sect1>

The <firstterm>lexer</firstterm> is defined in the file

<filename>scan.l</filename> and is responsible

for recognizing <firstterm>identifiers</firstterm>,

the <firstterm>SQLkeywords</firstterm> etc. For

everykeyword or identifier that is found, a <firstterm>token</firstterm>

the <firstterm>SQLkey words</firstterm> etc. For

everykey word or identifier that is found, a <firstterm>token</firstterm>

is generated and handed to the parser.

</para>

call. This may be transformed to either a <structname>FuncExpr</>

or <structname>Aggref</> node depending on whether the referenced

name turns out to be an ordinary function or an aggregate function.

Also, information about the actualdatatypes of columns and expression

Also, information about the actualdata types of columns and expression

results is added to the query tree.

</para>

</sect2>

<itemizedlist>

<listitem>

<para>

The first one worked using <firstterm>tuple level</firstterm> processing and was

The first one worked using <firstterm>row level</firstterm> processing and was

implemented deep in the <firstterm>executor</firstterm>. The rule system was

called whenever an individualtuple had been accessed. This

called whenever an individualrow had been accessed. This

implementation was removed in 1995 when the last official release

of the <productname>Berkeley Postgres</productname> project was

transformed into <productname>Postgres95</productname>.

<listitem>

<para>

<firstterm>nested loop join</firstterm>: The right relation is scanned

once for everytuple found in the left relation. This strategy

once for everyrow found in the left relation. This strategy

is easy to implement but can be very time consuming. (However,

if the right relation can be scanned with anindexscan, this can

if the right relation can be scanned with anindex scan, this can

be a good strategy. It is possible to use values from the current

row of the left relation as keys for theindexscan of the right.)

row of the left relation as keys for theindex scan of the right.)

</para>

</listitem>

<firstterm>hash join</firstterm>: the right relation is first scanned

and loaded into a hash table, using its join attributes as hash keys.

Next the left relation is scanned and the

appropriate values of everytuple found are used as hash keys to

locate the matchingtuples in the table.

appropriate values of everyrow found are used as hash keys to

locate the matchingrows in the table.

</para>

</listitem>

</itemizedlist>

</para>

<para>

The finished plan tree consists of sequential or index scans of

the base relations, plusnestloop, merge, or hash join nodes as

the base relations, plusnested-loop, merge, or hash join nodes as

needed, plus any auxiliary steps needed, such as sort nodes or

aggregate-function calculation nodes. Most of these plan node

types have the additional ability to do <firstterm>selection</>

The <firstterm>executor</firstterm> takes the plan handed back by the

planner/optimizer and recursively processes it to extract the required set

of rows. This is essentially a demand-pull pipeline mechanism.

Each time a plan node is called, it must deliver one moretuple, or

report that it is done deliveringtuples.

Each time a plan node is called, it must deliver one morerow, or

report that it is done deliveringrows.

</para>

<para>

To provide a concrete example, assume that the top

node is a <literal>MergeJoin</literal> node.

Before any merge can be done twotuples have to be fetched (one from

Before any merge can be done tworows have to be fetched (one from

each subplan). So the executor recursively calls itself to

process the subplans (it starts with the subplan attached to

<literal>lefttree</literal>). The new top node (the top node of the left

subplan) is, let's say, a

<literal>Sort</literal> node and again recursion is needed to obtain

an inputtuple. The child node of the <literal>Sort</literal> might

an inputrow. The child node of the <literal>Sort</literal> might

be a <literal>SeqScan</> node, representing actual reading of a table.

Execution of this node causes the executor to fetch a row from the

table and return it up to the calling node. The <literal>Sort</literal>

node will repeatedly call its child to obtain all the rows to be sorted.

When the input is exhausted (as indicated by the child node returning

a NULL instead of atuple), the <literal>Sort</literal> code performs

a NULL instead of arow), the <literal>Sort</literal> code performs

the sort, and finally is able to return its first output row, namely

the first one in sorted order. It keeps the remaining rows stored so

that it can deliver them in sorted order in response to later demands.

result row. But <command>INSERT ... SELECT</> may demand the full power

of the executor mechanism.) For <command>UPDATE</>, the planner arranges

that each computed row includes all the updated column values, plus

the <firstterm>TID</> (tuple ID, orlocation) of the original target row;

the <firstterm>TID</> (tuple ID, orrow ID) of the original target row;

the executor top level uses this information to create a new updated row

and mark the old row deleted. For <command>DELETE</>, the only column

that is actually returned by the plan is the TID, and the executor top

<!-- $Header: /cvsroot/pgsql/doc/src/sgml/array.sgml,v 1.31 2003/08/31 17:32:18 petere Exp $ -->

<!-- $Header: /cvsroot/pgsql/doc/src/sgml/array.sgml,v 1.32 2003/11/01 01:56:28 petere Exp $ -->

<sect1 id="arrays">

<title>Arrays</title>

<para>

When a single element is pushed on to the beginning of a one-dimensional

array, the result is an array with a lower bound subscript equal to

therighthand operand's lower bound subscript, minus one. When a single

theright-hand operand's lower bound subscript, minus one. When a single

element is pushed on to the end of a one-dimensional array, the result is

an array retaining the lower bound of thelefthand operand. For example:

an array retaining the lower bound of theleft-hand operand. For example:

<programlisting>

SELECT array_dims(1 || ARRAY[2,3]);

array_dims

<para>

When two arrays with an equal number of dimensions are concatenated, the

result retains the lower bound subscript of thelefthand operand's outer

dimension. The result is an array comprising every element of thelefthand

operand followed by every element of therighthand operand. For example:

result retains the lower bound subscript of theleft-hand operand's outer

dimension. The result is an array comprising every element of theleft-hand

operand followed by every element of theright-hand operand. For example:

<programlisting>

SELECT array_dims(ARRAY[1,2] || ARRAY[3,4,5]);

array_dims

<!--

Documentation of the system catalogs, directed toward PostgreSQL developers

$Header: /cvsroot/pgsql/doc/src/sgml/catalogs.sgml,v 2.76 2003/10/17 22:38:20 tgl Exp $

$Header: /cvsroot/pgsql/doc/src/sgml/catalogs.sgml,v 2.77 2003/11/01 01:56:28 petere Exp $

-->

<chapter id="catalogs">

<entry><type>int4</type></entry>

<entry></entry>

<entry>

Always -1 in storage, but when loaded into atuple descriptor

Always -1 in storage, but when loaded into arow descriptor

in memory this may be updated to cache the offset of the attribute

within thetuple.

within therow.

</entry>

</row>

<entry></entry>

<entry>

If true, this attribute is a set. In that case, what is really

stored in the attribute is the OID of atuple in the

stored in the attribute is the OID of arow in the

<structname>pg_proc</structname> catalog. The

<structname>pg_proc</structname>tuple contains the query

<structname>pg_proc</structname>row contains the query

string that defines this set, i.e., the query to run to get

the set. So the <structfield>atttypid</structfield> (see

above) refers to the type returned by this query, but the

<entry><type>float4</type></entry>

<entry></entry>

<entry>

Number oftuples in the table.

Number ofrows in the table.

This is only an estimate used by the planner.

It is updated by <command>VACUUM</command>,

<command>ANALYZE</command>, and <command>CREATE INDEX</command>.

<entry><type>xid</type></entry>

<entry></entry>

<entry>

Alltuples inserted or deleted by transaction IDs before this one

Allrows inserted or deleted by transaction IDs before this one

have been marked as known committed or known aborted in this database.

This is used to determine when commit-log space can be recycled.

</entry>

<entry><type>xid</type></entry>

<entry></entry>

<entry>

Alltuples inserted by transaction IDs before this one have been

Allrows inserted by transaction IDs before this one have been

relabeled with a permanent (<quote>frozen</>) transaction ID in this

database. This is useful to check whether a database must be vacuumed

soon to avoid transaction ID wrap-around problems.

<row>

<entry><structfield>refobjid</structfield></entry>

<entry><type>oid</type></entry>

<entry>anyoid attribute</entry>

<entry>anyOID column</entry>

<entry>The OID of the specific referenced object</entry>

</row>

<row>

<entry><structfield>indkey</structfield></entry>

<entry><type>int2vector</type></entry>

<entry><link linkend="catalog-pg-attribute"><structname>pg_attribute</structname></link>.attnum</entry>

<entry><literal><link linkend="catalog-pg-attribute"><structname>pg_attribute</structname></link>.attnum</literal></entry>

<entry>

This is an array of <structfield>indnatts</structfield> (up to

<symbol>INDEX_MAX_KEYS</symbol>) values that indicate which

<entry><structfield>opcamid</structfield></entry>

<entry><type>oid</type></entry>

<entry><literal><link linkend="catalog-pg-am"><structname>pg_am</structname></link>.oid</literal></entry>

<entry>Index access methodopclass is for</entry>

<entry>Index access methodoperator class is for</entry>

</row>

<row>

<entry><structfield>tgtype</structfield></entry>

<entry><type>int2</type></entry>

<entry></entry>

<entry>Bitmask identifying trigger conditions</entry>

<entry>Bit mask identifying trigger conditions</entry>

</row>

<row>

For types used in system tables, it is critical that the size

and alignment defined in <structname>pg_type</structname>

agree with the way that the compiler will lay out the column in

astruct representing a table row.

astructure representing a table row.

</para>

</note></entry>

</row>

<entry></entry>

<entry><para>

<structfield>typndims</structfield> is the number of array dimensions

for a domain that is an array (that is, typbasetype is an array type;

the domain's typelem will match the base type's typelem).

for a domain that is an array (that is,<structfield>typbasetype</> is an array type;

the domain's<structfield>typelem</> will match the base type's<structfield>typelem</structfield>).

Zero for types other than array domains.

</para></entry>

</row>