Skip to content

P
Postgres FD Implementation
Switch branch/tag
Find file Normal viewHistoryPermalink
index.html 7.03 KB
Newer Older
Bruce Momjian's avatar
New backend_dir html source.  
Bruce Momjian committed
1 2 
<HTML>
<HEAD>
Bruce Momjian's avatar
update  
Bruce Momjian committed
3 
<TITLE>How PostgreSQL Processes a Query</TITLE>
Bruce Momjian's avatar
New backend_dir html source.  
Bruce Momjian committed
4 5 6 
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#FF0000" VLINK="#A00000" ALINK="#0000FF">
<H1 ALIGN=CENTER>
Bruce Momjian's avatar
update  
Bruce Momjian committed
7 
How PostgreSQL Processes a Query
Bruce Momjian's avatar
New backend_dir html source.  
Bruce Momjian committed
8 9 10 
</H1>
<H2 ALIGN=CENTER>
by Bruce Momjian
Bruce Momjian's avatar
backend update.  
Bruce Momjian committed
11 
</H2>
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
12 
<P>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
13 14 15 
<CENTER>
<BR>
<BR>
Bruce Momjian's avatar
Update flow chart.  
Bruce Momjian committed
16 
<IMG src="flow.jpg" usemap="#flowmap" alt="flowchart" border=0>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
17 18 
</CENTER>
<MAP name="flowmap">
Bruce Momjian's avatar
OPTIMIZER_DEBUG additions.  
Bruce Momjian committed
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
<AREA COORDS="70,0,230,40" HREF="backend_dirs.html#main">
<AREA COORDS="70,80,230,120" HREF="backend_dirs.html#postmaster">
<AREA COORDS="330,40,490,80" HREF="backend_dirs.html#libpq">
<AREA COORDS="70,160,230,200" HREF="backend_dirs.html#tcop">
<AREA COORDS="330,160,490,200" HREF="backend_dirs.html#tcop">
<AREA COORDS="70,260,230,300" HREF="backend_dirs.html#parser">
<AREA COORDS="70,340,230,380" HREF="backend_dirs.html#tcop">
<AREA COORDS="70,420,230,460" HREF="backend_dirs.html#optimizer">
<AREA COORDS="70,400,230,540" HREF="backend_dirs.html#optimizer/plan">
<AREA COORDS="70,580,230,620" HREF="backend_dirs.html#executor">
<AREA COORDS="330,340,490,380" HREF="backend_dirs.html#commands">
<AREA COORDS="0,690,160,740" HREF="backend_dirs.html#utils">
<AREA COORDS="210,690,370,730" HREF="backend_dirs.html#catalog">
<AREA COORDS="420,690,590,740" HREF="backend_dirs.html#storage">
<AREA COORDS="100,770,270,820" HREF="backend_dirs.html#access">
<AREA COORDS="330,770,490,820" HREF="backend_dirs.html#nodes">
<AREA COORDS="10,860,170,900" HREF="backend_dirs.html#bootstrap">
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
36 
</MAP>
Bruce Momjian's avatar
Update mark/reset index code for multiple indexes, (OR code).  
Bruce Momjian committed
37 38 39 40 
<CENTER><EM>
Click on an item to see more detail or look at the full
<A HREF="backend_dirs.html">index.</A>
</EM></CENTER>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
41 
<BR>
Bruce Momjian's avatar
Update flow chart.  
Bruce Momjian committed
42 
<BR>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
43
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
44 
<P>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
45 46 47 

A query comes to the backend via data packets arriving through TCP/IP or
Unix Domain sockets.   It is loaded into a string, and passed to the
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
48 
<A HREF="../../backend/parser">parser,</A> where the lexical scanner,
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
49 50 51 52 53 54 55 
<A HREF="../../backend/parser/scan.l">scan.l,</A> breaks the query up
into tokens(words).  The parser uses <A
HREF="../../backend/parser/gram.y">gram.y</A> and the tokens to identify
the query type, and load the proper query-specific structure, like <A
HREF="../../include/nodes/parsenodes.h">CreateStmt</A> or <A
HREF="../../include/nodes/parsenodes.h">SelectStmt.</A><P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
56
Bruce Momjian's avatar
update  
Bruce Momjian committed
57 58 59 
The query is then identified as a <I>Utility</I> query or a more complex
query.  A <I>Utility</I> query is processed by a query-specific function
in <A HREF="../../backend/commands"> commands.</A> A complex query, like
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
60 61 
<I>SELECT, UPDATE,</I> and <I>DELETE</I> requires much more handling.<P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
62
Bruce Momjian's avatar
backend update.  
Bruce Momjian committed
63 
The parser takes a complex query, and creates a
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
64 65 
<A HREF="../../include/nodes/parsenodes.h">Query</A> structure that
contains all the elements used by complex queries.  Query.qual holds the
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
66 67 
<I>WHERE</I> clause qualification, which is filled in by <A
HREF="../../backend/parser/parse_clause.c">transformWhereClause().</A>
Bruce Momjian's avatar
Update flowchart and backend descriptions.  
Bruce Momjian committed
68 69 
Each table referenced in the query is represented by a <A
HREF="../../include/nodes/parsenodes.h"> RangeTableEntry,</A> and they
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
70 71 72 73 
are linked together to form the <I>range table</I> of the query, which
is generated by <A HREF="../../backend/parser/parse_clause.c">
makeRangeTable().</A>  Query.rtable holds the query's range table.<P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
74
Bruce Momjian's avatar
change <CODE> to <I>.  
Bruce Momjian committed
75 76 
Certain queries, like <I>SELECT,</I> return columns of data.  Other
queries, like <I>INSERT</I> and <I>UPDATE,</I> specify the columns
Bruce Momjian's avatar
backend update.  
Bruce Momjian committed
77 78 
modified by the query.  These column references are converted to <A
HREF="../../include/nodes/primnodes.h">Resdom</A> entries, which are
Bruce Momjian's avatar
update  
Bruce Momjian committed
79 
placed in <A HREF="../../include/nodes/parsenodes.h">target list
Bruce Momjian's avatar
I'm sorry, but I think I introduced a little bug with my last patch.  
Bruce Momjian committed
80 
entries,</A> and linked together to make up the <I>target list</I> of
Bruce Momjian's avatar
update  
Bruce Momjian committed
81 
the query. The target list is stored in Query.targetList, which is
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
82 83 84 
generated by <A
HREF="../../backend/parser/parse_target.c">transformTargetList().</A><P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
85
Bruce Momjian's avatar
change <CODE> to <I>.  
Bruce Momjian committed
86 
Other query elements, like aggregates(<I>SUM()</I>), <I>GROUP BY,</I>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
87 88 
and <I>ORDER BY</I> are also stored in their own Query fields.<P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
89
Bruce Momjian's avatar
change <CODE> to <I>.  
Bruce Momjian committed
90 91 
The next step is for the Query to be modified by any <I>VIEWS</I> or
<I>RULES</I> that may apply to the query.  This is performed by the <A
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
92 93 
HREF="../../backend/rewrite">rewrite</A> system.<P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
94
Bruce Momjian's avatar
Update flowchart and backend descriptions.  
Bruce Momjian committed
95 
The <A HREF="../../backend/optimizer">optimizer</A> takes the Query
Bruce Momjian's avatar
backend update.  
Bruce Momjian committed
96 97 98 99 100 
structure and generates an optimal <A
HREF="../..//include/nodes/plannodes.h">Plan,</A> which contains the
operations to be performed to execute the query.  The <A
HREF="../../backend/optimizer/path">path</A> module determines the best
table join order and join type of each table in the RangeTable, using
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
101 
Query.qual(<I>WHERE</I> clause) to consider optimal index usage.<P>
Bruce Momjian's avatar
update  
Bruce Momjian committed
102
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
103
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
104 105 
The Plan is then passed to the <A
HREF="../../backend/executor">executor</A> for execution, and the result
Bruce Momjian's avatar
update  
Bruce Momjian committed
106 107 
returned to the client.  The Plan actually as set of nodes, arranged in
a tree structure with a top-level node, and various sub-nodes as
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
108 
children.<P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
109 110
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
111 112 113 114 115 116 
There are many other modules that support this basic functionality. They
can be accessed by clicking on the flowchart.<P>


<HR><P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
117
Bruce Momjian's avatar
update  
Bruce Momjian committed
118 
Another area of interest is the shared memory area, which contains data
Bruce Momjian's avatar
Update mark/reset index code for multiple indexes, (OR code).  
Bruce Momjian committed
119 120 
accessable to all backends.  It has recently used data/index blocks,
locks, backend process information, and lookup tables for these
Bruce Momjian's avatar
update  
Bruce Momjian committed
121 
structures:
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
122
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
123 
<UL>
Bruce Momjian's avatar
update  
Bruce Momjian committed
124 
<LI>ShmemIndex - lookup shared memory addresses using structure names
Bruce Momjian's avatar
Update flowchart and backend descriptions.  
Bruce Momjian committed
125 
<LI><A HREF="../../include/storage/buf_internals.h">Buffer
Bruce Momjian's avatar
update  
Bruce Momjian committed
126 127 
Descriptor</A> - control header for buffer cache block
<LI><A HREF="../../include/storage/buf_internals.h">Buffer Block</A> -
Bruce Momjian's avatar
backend update.  
Bruce Momjian committed
128 
data/index buffer cache block
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
129 130 131 132 133 
<LI>Shared Buffer Lookup Table - lookup of buffer cache block addresses
using table name and block number(<A
HREF="../../include/storage/buf_internals.h"> BufferTag</A>)
<LI>MultiLevelLockTable (ctl) - control structure for each locking
method.  Currently, only multi-level locking is used(<A
Bruce Momjian's avatar
update  
Bruce Momjian committed
134 
HREF="../../include/storage/lock.h">LOCKMETHODCTL</A>).
Bruce Momjian's avatar
Rename locking structure names to be clearer. Add narrative to  
Bruce Momjian committed
135 136 137 
<LI>MultiLevelLockTable (lock hash) - the <A
HREF="../../include/storage/lock.h">LOCK</A> structure, looked up using
relation, database object ids(<A
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
138 139 140 
HREF="../../include/storage/lock.h">LOCKTAG)</A>.  The lock table
structure contains the lock modes(read/write or shared/exclusive) and
circular linked list of backends (<A
Bruce Momjian's avatar
Rename locking structure names to be clearer. Add narrative to  
Bruce Momjian committed
141 142 143 144 145 146 147 148 149 
HREF="../../include/storage/proc.h">PROC</A> structure pointers) waiting
on the lock.
<LI>MultiLevelLockTable (xid hash) - lookup of LOCK structure address
using transaction id, LOCK address.  It is used to quickly check if the
current transaction already has any locks on a table, rather than having
to search through all the held locks.  It also stores the modes
(read/write) of the locks held by the current transaction.  The returned
<A HREF="../../include/storage/lock.h">XIDLookupEnt</A> structure also
contains a pointer to the backend's PROC.lockQueue.
Bruce Momjian's avatar
Update flowchart and backend descriptions.  
Bruce Momjian committed
150 
<LI><A HREF="../../include/storage/proc.h">Proc Header</A> - information
Bruce Momjian's avatar
Rename locking structure names to be clearer. Add narrative to  
Bruce Momjian committed
151 
about each backend, including locks held/waiting, indexed by process id
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
152 
</UL>
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
153
Bruce Momjian's avatar
Update flowchart and backend descriptions.  
Bruce Momjian committed
154 
Each data structure is created by calling <A
Bruce Momjian's avatar
Update.  
Bruce Momjian committed
155 156 157 158 
HREF="../../backend/storage/ipc/shmem.c">ShmemInitStruct(),</A> and the
lookups are created by <A
HREF="../../backend/storage/ipc/shmem.c">ShmemInitHash().</A><P>
Bruce Momjian's avatar
Update version.  
Bruce Momjian committed
159
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
160 161 
<HR SIZE="2" NOSHADE>
<SMALL>
Bruce Momjian's avatar
New backend_dir html source.  
Bruce Momjian committed
162 
<ADDRESS>
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
163 164 165 
Maintainer:	Bruce Momjian (<A
HREF="mailto:maillist@candle.pha.pa.us">maillist@candle.pha.pa.us</A>)<BR>
Last updated:		Tue Dec  9 17:56:08 EST 1997
Bruce Momjian's avatar
New backend_dir html source.  
Bruce Momjian committed
166 
</ADDRESS>
Bruce Momjian's avatar
Update backend flowchart.  
Bruce Momjian committed
167 168 169 
</SMALL>
</BODY>
</HTML>