.sh 1 "Postgres Architecture and Historical Lore"
.pp
.sh 1 "Introduction"
.pp
In the beginning, there was Ingres.  And then, after ways to improve the
relational model made themselves known, and as ways to implement
object-oriented
techniques of data organization without completely throwing out time-honored
ways of doing things became necessary, Postgres came into being.
.pp
The original release of Postgres was partially written in Franz Lisp and
partially written in C.  However, this proved to be a rather difficult
environment in which to work and debug, and was quite a problem for any
potential users - it was painfully slow, and required expensive third-party
licenses for the Lisp environment.  Because of this, Postgres was ported to C,
and the first C-only release went out in late 1988.
.pp
Subsequent releases of the Postgres software have stressed improvements and
complete rewrites of various features including the Postgres rule system,
the transaction system, the executor, access methods, as well as several 
ports to different machines.
.pp
In the following discussions, a general overview of the internal structure
of Postgres will be presented, together with references to directories where
these structures may be found.  This is intended to be a rather quick "tour"
of the Postgres code, stressing general principles and ideas rather than
details such as function names.  For that level of detail, the code itself is
the best (and only) reference.  It must be admitted here that precision is
being avoided as much to keep this document from rapidly getting out of date as
much as anything else.
.pp
.sh 1 "General overview of Postgres at the communication level"
.pp
The three main programs in the Postgres environment are the following:
.pp
.(l
User Applications
The "postmaster"
The Postgres backend
.)l
.sh 2 "User Applications"
.pp
A User Application is any program that uses LIBPQ to send and recieve data from
a Postgres backend.  A User Application can run on any host that can access the
Postgres server from a TCP-IP network.  User applications included in the
Postgres distribution include the terminal monitor (monitor), the database
creation program (createdb), and the database deletion program (destroydb).
.pp
.sh 2 "The postmaster"
.pp
The Postmaster handles most of the network initialization and connection
activities.  Once the Postmaster has handled the network stuff for a user
application, it forks off a Postgres backend.  Once this is done, the
Postmaster is no longer involved, and goes back to waiting for connections
from new user applications.
.pp
The first time the Postmaster is invoked, it allocates shared memory and
semaphores used by Postgres backends for locking and buffer pools.
.pp
The postmaster and the backend have to run on the database server, and the
database directories should be on local disks.
.pp
.sh 2 "The Postgres backend"
.pp
The Postgres backend is the true database engine.  Once it has been forked by
a postmaster, it is ready to recieve queries from and send back answers to the
user application.
.pp
For every user application, there is one Postgres backend forked by the
Postmaster.  
.pp
.sh 1 "Overview of the Postgres Main Modules"
.pp
In this section, the general program flow in Postgres will be discussed, with
a brief description of each program module, together with instructions on
where to find the source code for that module.  All modules discussed here
are part of the Postgres backend, and are relatively tightly coupled at this
time.  The Postgres main modules include:
.pp
.(l
o  The Parser
o  The Query Rewrite Rule System
o  The Planner/Optimizer
o  The Executor
o  The Instance Level Rule System
o  The Access Methods
o  Housekeeping functions 
o  Lock managers, cache utilities, and other miscellaneous functions.
.)l
.pp
In the execution of a Retrieve query, the following general flow is followed.
Appends and other queries that access data (as opposed to "housekeeping" queries
such as createdb, copy, etc) follow a similar flow.
.pp
.l(
                 ----------------
                 |  1.  Parser  |
                 ----------------
                        |
                        | (Initial Query Parse Tree)
                        |
                        v
          +-------------------------------+
          | 2.  Query Rewrite Rule System |
          +-------------------------------+
                        |
                        | (Re-written Query Parse Tree)
                        |
                        |
                        v
              +-----------------------+
              | 3.  Planner/Optimizer |
              +-----------------------+
                        |
                        | (Execution Plan Tree)
                        |
                        v
                +------------------+
                | 4.  Executor     |
                +------------------+
                        |
                        | (Open request)
                        |
                        |
                        |          (get instances until done)
                        v                    
                 +-------------------+              +-----------------+
                 | 5. Access Methods |<-------------| 4.  Executor    |
                 +-------------------+              +-----------------+
                        |                                  ^
                        | (instance)                       |
                        |                                  | (instance)
                        v                                  |
                 +-------------------------------+         |
                 | 6. Instance Level Rule System |---------+
                 +-------------------------------+
.)l
.sh 2 "The Parser"
.pp
The Parser parses a Postquel query and generates a parse-tree.  As long as
a correct parse-tree is generated, other parsers for other query languages
(ie SQL) can be "dropped in" to the Postgres system.  The Postquel query
parser lives in:
.pp
.(l
~/src/parser
.)l
.pp
.sh 2 "The Query Rewrite rule system"
.pp
The Query Rewrite rule system is essentially part of the parser.  It generally
works in the following manner:  If there is a query-rewrite rule on this
class of instances, add the rule to the initial user query through the use of
boolean algebra.  If not, just let the query go through.
.pp
The Query Rewrite rule system is used to implement not only obvious rules, but
also versions, views, and postquel procedures.  The Query Rewrite system
lives in:
.pp
.(l
~/src/rewrite
.)l
.sh 2 "The Planner/Optimizer"
.pp
The Planner/Optimizer takes a parse-tree and, using various cost functions and
heuristics, generates an execution plan.  The Planner/Optimizer also "drives"
the executor in that it calls it once to initialize things and then calls it
subsequently to fetch instances.  The planner lives in:
.pp
.(l
~/src/planner
.)l
.pp
.sh 2 "The Executor"
.pp
The first time the Executor is invoked by the Planner, it initializes itself,
the access methods, and the instance-level rule system.  In subsequent calls by
the Planner, it walks the execution plan, fetching instances by calling the
access methods and checking them against the query qualification (which is
part of the execution plan) to see if they are part of the "answer" to the user
query.  Before doing this, however, it checks to see if a fetched instance
triggers a instance-level rule.  The Executor lives in:
.pp
.(l
~/src/executor
.)l
.pp
.sh 2 "The Access Methods"
.pp
These are the low-level routines that hit the disk and handle any indices (ie
btrees, rtrees) that the user may have defined.  The Heap access method is
used as the primary access method, and other access methods are defined on
indices.  The Executor calls these
routines to fetch instances - the Access Methods then use a scanning mechanism
defined by the Planner to get them and fetch them back to the executor.  The
Access Methods primarily live in:
.pp
.(l
~/src/access/common       (Code used by all access methods)
~/src/access/heap         (Heap access method - the lowest level)

~/src/access/{index index-btree index-ftree index-rtree}
                          (Code to handle indices, and 
                           Various different types of indices)

~/src/access/transam      (The Postgres Transaction System)
.)l
.sh 2 "The Instance-level Rule System"
.pp
The Instance-level rule system operates in the following manner:  in the
"system data" part of each instance, there is a field for instance level
"rule locks".  If a fetched instance has a rule lock, the associated rule(s)
is executed.  Each instance-level rule has an associated execution plan, so
the executor will be
ran from within the instance-level rule system.  The modified instance, if any,
is then handed back to the executor for further processing.  The Instance-level
Rule System lives in:
.pp
.(l
~/src/rules/prs2 (Postgres Rule System 2 - the bulk of the rule system)
~/src/rules/stubs
.)l
.sh 2 "Housekeeping Functions"
.pp
For queries that are not directly related to retrieving or appending, such
as creating databases, defining new operators, rules, and registering user
functions, the parser simply bypasses the planner and executor and directly
calls utility routines to handle these special commands.  The code for these
routines is in:
.pp
.(l
~/src/commands
.)l
.pp
.sh 2 "Lock managers, cache utilities, and other miscellaneous functions"
.pp
There are numerous other functions that are used in Postgres; these include
functions to manage system attributes, lock managers, buffer and cache
managers, hash table handlers, as well as the system built-in functions for
pre-defined types.  For lack of anything better to call these, these live in
the UTIL module, and live in:
.pp
.(l
~/src/utils/adt   (built-in functions)
~/src/utils/cache (cache handlers)
~/src/utils/error (error handlers)
~/src/utils/fmgr  (the "Function Manager" - handles ADT's and user functions)
~/src/utils/hash  (hash table handlers)
~/src/utils/init  (initialization code)
~/src/utils/mmgr  (memory manager code)
~/src/utils/sort  (sort code)
~/src/utils/time  (time range qualification handlers)
.)l
.pp
.sh 2 "'Main' Programs"
.pp
The "main programs" for the Postgres backend, the Postmaster, and other
utilities like the vacuum daemon, etc live in
.pp
.(l
~/src/support (everything but the backend)
~/src/tcop    (the backend main program - in postgres.c)
.)l
.pp
.sh 1 "Postgres internal data structures"
.pp
Since Postgres was originally written in Lisp, and for a time was a Lisp-C
hybrid, many of its internal data structures are rather opaque to the C
programmer.  However, they are not overly difficult to understand and use once
the basic ideas behind them are made clear.  The discussion in this section
will attempt to make these ideas clear, without dwelling excessively on
details and trivia.
.pp
.sh 2 "The CONS-cell abstraction"
.pp
Internally, Postgres passes data about primarily in trees made of Lisp-like
CONS-cell structures.  These CONS-cells can point to interesting data only,
to interesting data and another CONS-cell, or to two other CONS-cells.  In
particualar, parse-trees and execution plans are encoded in these CONS-cell
structures.  Utility functions for handling the Lisp-like structures are in
.pp
.(l
~/src/lib/C
.)l
.sh 2 "The Postgres Node System"
.pp
A collection of data structures that is central to most Postgres operations
is the Postgres "node system".  This is a collection of data structures that
encode various directives for the executor and planner, as well as numerous
other "utility" purposes.  Nodes are declared using a C++-like syntax that
is used by a shell script to generate initialization and accessor functions.
C preprocessor magic is used to ultimately turn this declaration into an
ordinary C typedef.
.pp
.sh 3 "An Example Node"
.pp
An example of a Postgres node is the following:
.pp
.(l
class (Oper) public (Expr) {
/* private: */
	inherits(Expr);
	InstanceId            opno;
	InstanceId            opid;
	bool                oprelationlevel;
	InstanceId            opresulttype;
	int                 opsize;
	FunctionCachePtr    op_fcache;
/* public: */
};

(this particular node is from ~/src/lib/H/nodes/primnodes.h)

.)l
.pp
This particular node is used in execution plans to indicate that an operator
must be executed.  The "inherits" macro is used to inherit fields from the
previously defined Expr (expression) node, and the explicit fields are fields
that are unique to the Oper node itself.  Declarations for all Postgres nodes
are in header files in
.pp
.(l
~/src/lib/H/nodes
.)l
.pp
As stated earlier, shell scripts read the node declarations and generate
initializer and accessor functions for them.  As long as the above declaration
scheme is used, these scripts will work for new nodes as well.  These scripts
are in
.pp
.(l
~/src/lib/Gen
.)l
.sh 3 "Usage of the Node System"
.pp
The different nodes are primarily used to give directives to the Executor in
the execution plan.  Nodes are used to indicate the scan type to be used,
whether sorting is to be used or not, and are used to indicate how query
qualifications are to be handled.  
.pp
.sh 3 "Printing Nodes and Node Structures"
.pp
The best place to figure out what a structure using nodes and CONS-cells
is like is to look carefully at the code in 
.pp
.(l
~/src/lib/C
.)l
.pp
The code in this directory prints node structures into strings and dumps them
into strings.  This code is primarily used by the Instance Level Rule System to
save and restore execution plans that are associated with rules, which it
stores on disk in a system class in string format.  The function
.pp
.(l
LispDisplay(CONS-cell, 0)
.)l
.pp
displays the contents of a CONS-cell structure in a human readable but rather
unfriendly format.
.pp
.sh 2 "Other Important Data Structures"
.pp
Aside from the CONS-cell and Node structures, there are very few other
important global data structures, although there are numerous local structures
that are important if one is modifying variosu functions.  One exception is
the HeapTuple data structure and its associated structures, since it is the
type returned by virtually all the access methods, including those that handle
system classes.  The declaration for the HeapTuple type is in
.pp
.(l
~/src/access/htup.h
.)l
.pp
.sh 1 "The Postgres Function Manager"
.pp
An integral part of Postgres is its ability to use user-defined functions and
operators.  The Postgres Function Manager is responsible for handling this
aspect of Postgres.
.pp
.sh 2 "The Function Manager"
.pp
The Function Manager is used by all parts of Postgres that examine the
internals of user data.  It consists of several parts:
.pp
.(l
o  The Function Manager Interface
o  Data structures containing information about dynamically loaded files
o  The dynamic loader
.)l
.pp
.sh 3 "The Function Manager Interface"
.pp
The basic reason for the existance of the Function Manager is that due to
the nature of user-defined functions, calls to them cannot be hardcoded anywere
in the Postgres backend.  A mechanism must exist which obtains addresses of
user-defined and builtin functions (there is very little difference between
these), handles the task of calling user-defined functions with appropriate
arguments, and returning an appropriate value.  The Function Manager Interface
provides the abstraction from the details of calling user-defined functions
from the rest of Postgres.  The source to the Function Manager Interface is in 
.pp
.(l
~/src/utils/fmgr/fmgr.c
.)l
.pp
.sh 3 "Data Structures used for Function Execution"
.pp
In the Function Manager, there are two in-memory data structures used for
looking up function addresses.  One is an array of builtin functions that
is sorted by function OID.  Another is a list of dynamically loaded files,
which contains the addresses of each function in these files.  Functions that
populate and access these data structures are in
.pp
.(l
~/src/utils/fmgr/dfmgr.c
~/src/port/*/dynloader.c
.)l
.pp
and the data structures themselves are defined in
.pp
.(l
~/src/lib/H/utils/dynamic_loader.h
~/src/lib/H/utils/fmgr.h
~/src/lib/H/utils/builtins.h
~/src/lib/H/catalog/pg_type.h
.)l
.p
and
.p
.(l
~/src/utils/fmgr/fmgr.c
.)l
.pp
.sh 3 "The Dynamic Loader"
.pp
The Dynamic Loader loads a user-defined function from a file and determines
the names and addresses of each function in that file.  It then populates
appropriate data structures with this information.  The source to the Dynamic
Loader is in
.pp
.(l
~/src/utils/fmgr/dfmgr.c
~/src/port/*/dynloader.c
.)l
.sh 2 "General Algorithm"
.pp
The Postgres Function Manager uses the following general algorithm for
determining the addresses of functions.  Once the address is found, the
Function Manager Interface has functions which actually call the function.
.pp
.b General algorithm
.pp
Is function in builtin list?  If it is, return its address from this list
.pp
If the function is not in the list of builtins, it is a dynamically loaded
function.  If so, look for the function name in the list of dynamically
loaded functions.  If it is, return its address.
.pp
If the function has not yet been found, dynamically load it and determine
its address.  Return this address.
.pp
.sh 1 "How does a user-defined function get executed?"
.pp
The program flow discussed in Section 3 - with the exception of the rule
systems - is essentially similar to that of any data manager.  How, then, is
Postgres so different?  The main differences between Postgres and other data
managers is in its concept of what data is.  In Postgres, data is whatever
the user says it is - the Postgres backend itself imposes no arbitrary
definitions on data other than that it is a blob of memory of a known size.
.pp
The user defines what data is by defining functions and binding them to
various operators.  These operators are then bound to user-defined types, and
thus the system is complete.  In this section, how a user-defined function
is executed will be discussed.
.pp
For the sake of this discussion (since operators will be discussed later), 
assume that Postgres is operating on the following query
.pp
.(l
* retrieve (emp.all) where overpaid(emp.salary)
.)l
and that overpaid(x) is a user-defined function taking an integer as an
argument.  
.pp
Initially, the Parser will walk this query, and generate a parse tree.  While
doing this, it will examine the following system classes:
.pp
.(l
o  PG_PROC - information about Postgres functions is stored here.
o  PG_TYPE - information about Postgres types is stored here.  
.)l
.pp
PG_PROC contains information about the C file containing the function (if any),
its return value, its number of arguments, its argument types, and other
information.  The Parser will also check PG_TYPE to make sure that emp.salary
is an appropriate argument for overpaid().  Once everything has been found to
be proper, appropriate nodes containing information about the function will
be inserted into the parsetree.
.pp
After the Planner has turned the parsetree into an execution plan, the Executor
will walk the plan, executing overpaid() on each instance fetched from the "emp"
class.  
.pp
The first time overpaid() is executed, the Executor will call the Postgres
Function Manager to obtain the address of the function.  (See discussion in
Section 5 for details on the Function Manager).  In subsequent calls, it will
simply give Function Manager the address of the function so it can be called.
.pp
A user function like overpaid() is "registered" in Postgres using the Postquel
.pp
.(l
DEFINE C FUNCTION
.)l
.pp
query.
.pp
.sh 1 "How does a User Defined Operator get executed?"
.pp
When a user defines an operator, a user-defined function is associated with
it.  Therefore, execution of an operator is little different than execution
of a function, with only one major exception:  the Planner knows how to
optimize operator queries but does not know how to deal with functions. 
.pp
The major system class dealing with operators is
.pp
.(l
PG_OPERATOR
.)l
.pp
Additionally, the same classes discussed in Section 6 are used in the execution
of operators.  Binding of user functions to operators is handled with the
Postquel
.pp
.(l
DEFINE OPERATOR
.)l
.pp
query.
.pp
.sh 1 "How is a User Defined Type handled?"
.pp
A User Defined Type minimally consists of two functions, the input function
for the type, and the output function for the type.  Additionally, ordering
(less than, greater than) and equality functions are necessary if the type is
to be used in qualified queries, or if an index is to be defined on the type.  
.pp
In the system class
.pp
.(l
PG_TYPE
.)l
.pp
is information related to user-defined types, such as
.pp
.(l
o  The names of the registered functions for input and output of the type.
o  The size of the type
.)l
.pp
The Postquel query
.pp
.(l
DEFINE TYPE
.)l
populates the PG_TYPE class.
