index.html 7.03 KB
Newer Older
Bruce Momjian's avatar
Bruce Momjian committed
1 2
<HTML>
<HEAD>
Bruce Momjian's avatar
Bruce Momjian committed
3
<TITLE>How PostgreSQL Processes a Query</TITLE>
Bruce Momjian's avatar
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
Bruce Momjian committed
7
How PostgreSQL Processes a Query
Bruce Momjian's avatar
Bruce Momjian committed
8 9 10
</H1>
<H2 ALIGN=CENTER>
by Bruce Momjian
Bruce Momjian's avatar
Bruce Momjian committed
11
</H2>
Bruce Momjian's avatar
Bruce Momjian committed
12
<P>
Bruce Momjian's avatar
Bruce Momjian committed
13 14 15
<CENTER>
<BR>
<BR>
Bruce Momjian's avatar
Bruce Momjian committed
16
<IMG src="flow.jpg" usemap="#flowmap" alt="flowchart" border=0>
Bruce Momjian's avatar
Bruce Momjian committed
17 18
</CENTER>
<MAP name="flowmap">
Bruce Momjian's avatar
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
Bruce Momjian committed
36
</MAP>
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
Bruce Momjian committed
41
<BR>
Bruce Momjian's avatar
Bruce Momjian committed
42
<BR>
Bruce Momjian's avatar
Bruce Momjian committed
43

Bruce Momjian's avatar
Bruce Momjian committed
44
<P>
Bruce Momjian's avatar
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
Bruce Momjian committed
48
<A HREF="../../backend/parser">parser,</A> where the lexical scanner,
Bruce Momjian's avatar
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
Bruce Momjian committed
56

Bruce Momjian's avatar
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
Bruce Momjian committed
60 61
<I>SELECT, UPDATE,</I> and <I>DELETE</I> requires much more handling.<P>

Bruce Momjian's avatar
Bruce Momjian committed
62

Bruce Momjian's avatar
Bruce Momjian committed
63
The parser takes a complex query, and creates a
Bruce Momjian's avatar
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
Bruce Momjian committed
66 67
<I>WHERE</I> clause qualification, which is filled in by <A
HREF="../../backend/parser/parse_clause.c">transformWhereClause().</A>
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
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
Bruce Momjian committed
74

Bruce Momjian's avatar
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
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
Bruce Momjian committed
79
placed in <A HREF="../../include/nodes/parsenodes.h">target list
80
entries,</A> and linked together to make up the <I>target list</I> of
Bruce Momjian's avatar
Bruce Momjian committed
81
the query. The target list is stored in Query.targetList, which is
Bruce Momjian's avatar
Bruce Momjian committed
82 83 84
generated by <A
HREF="../../backend/parser/parse_target.c">transformTargetList().</A><P>

Bruce Momjian's avatar
Bruce Momjian committed
85

Bruce Momjian's avatar
Bruce Momjian committed
86
Other query elements, like aggregates(<I>SUM()</I>), <I>GROUP BY,</I>
Bruce Momjian's avatar
Bruce Momjian committed
87 88
and <I>ORDER BY</I> are also stored in their own Query fields.<P>

Bruce Momjian's avatar
Bruce Momjian committed
89

Bruce Momjian's avatar
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
Bruce Momjian committed
92 93
HREF="../../backend/rewrite">rewrite</A> system.<P>

Bruce Momjian's avatar
Bruce Momjian committed
94

95
The <A HREF="../../backend/optimizer">optimizer</A> takes the Query
Bruce Momjian's avatar
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
Bruce Momjian committed
101
Query.qual(<I>WHERE</I> clause) to consider optimal index usage.<P>
Bruce Momjian's avatar
Bruce Momjian committed
102

Bruce Momjian's avatar
Bruce Momjian committed
103

Bruce Momjian's avatar
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
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
Bruce Momjian committed
108
children.<P>
Bruce Momjian's avatar
Bruce Momjian committed
109 110


Bruce Momjian's avatar
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
Bruce Momjian committed
117

Bruce Momjian's avatar
Bruce Momjian committed
118
Another area of interest is the shared memory area, which contains data
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
Bruce Momjian committed
121
structures:
Bruce Momjian's avatar
Bruce Momjian committed
122

Bruce Momjian's avatar
Bruce Momjian committed
123
<UL> 
Bruce Momjian's avatar
Bruce Momjian committed
124
<LI>ShmemIndex - lookup shared memory addresses using structure names
125
<LI><A HREF="../../include/storage/buf_internals.h">Buffer
Bruce Momjian's avatar
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
Bruce Momjian committed
128
data/index buffer cache block
Bruce Momjian's avatar
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
Bruce Momjian committed
134
HREF="../../include/storage/lock.h">LOCKMETHODCTL</A>).
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
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
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.
150
<LI><A HREF="../../include/storage/proc.h">Proc Header</A> - information
151
about each backend, including locks held/waiting, indexed by process id
Bruce Momjian's avatar
Bruce Momjian committed
152
</UL>
Bruce Momjian's avatar
Bruce Momjian committed
153

154
Each data structure is created by calling <A
Bruce Momjian's avatar
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
Bruce Momjian committed
159

Bruce Momjian's avatar
Bruce Momjian committed
160 161
<HR SIZE="2" NOSHADE>
<SMALL>
Bruce Momjian's avatar
Bruce Momjian committed
162
<ADDRESS>
Bruce Momjian's avatar
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
Bruce Momjian committed
166
</ADDRESS>
Bruce Momjian's avatar
Bruce Momjian committed
167 168 169
</SMALL>
</BODY>
</HTML>