granicus.if.org Git - postgresql/blob - src/tools/backend/index.html

   1 <HTML>
   2 <HEAD>
   3 <TITLE>How PostgreSQL Processes a Query</TITLE>
   4 </HEAD>
   5 <BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#FF0000" VLINK="#A00000" ALINK="#0000FF">
   6 <H1 ALIGN=CENTER>
   7 How PostgreSQL Processes a Query
   8 </H1>
   9 <H2 ALIGN=CENTER>
  10 by Bruce Momjian
  11 </H2>
  12 <P>
  13 <CENTER>
  14 <BR>
  15 <BR>
  16 <IMG src="flow.jpg" usemap="#flowmap" alt="flowchart">
  17 </CENTER>
  18 <MAP name="flowmap">
  19 <AREA COORDS="80,130,240,170" HREF="backend_dirs.html#main">
  20 <AREA COORDS="80,210,240,250" HREF="backend_dirs.html#postmaster">
  21 <AREA COORDS="340,170,500,210" HREF="backend_dirs.html#libpq">
  22 <AREA COORDS="80,290,240,330" HREF="backend_dirs.html#tcop">
  23 <AREA COORDS="340,290,500,330" HREF="backend_dirs.html#tcop">
  24 <AREA COORDS="80,390,240,430" HREF="backend_dirs.html#parser">
  25 <AREA COORDS="80,470,240,510" HREF="backend_dirs.html#tcop">
  26 <AREA COORDS="80,550,240,590" HREF="backend_dirs.html#optimizer">
  27 <AREA COORDS="80,530,240,670" HREF="backend_dirs.html#optimizer/plan">
  28 <AREA COORDS="80,710,240,750" HREF="backend_dirs.html#executor">
  29 <AREA COORDS="340,470,500,510" HREF="backend_dirs.html#commands">
  30 <AREA COORDS="10,820,170,870" HREF="backend_dirs.html#utils">
  31 <AREA COORDS="220,820,380,860" HREF="backend_dirs.html#catalog">
  32 <AREA COORDS="430,820,600,870" HREF="backend_dirs.html#storage">
  33 <AREA COORDS="110,900,280,950" HREF="backend_dirs.html#access">
  34 <AREA COORDS="340,900,500,950" HREF="backend_dirs.html#nodes">
  35 <AREA COORDS="20,990,180,1030" HREF="backend_dirs.html#bootstrap">
  36 </MAP>
  37 <CENTER><EM>
  38 Click on an item to see more detail or look at the full
  39 <A HREF="backend_dirs.html">index.</A>
  40 </EM></CENTER>
  41 <BR>
  42
  43 <P>
  44
  45 A query comes to the backend via data packets arriving through TCP/IP or
  46 Unix Domain sockets.   It is loaded into a string, and passed to the
  47 <A HREF="../../backend/parser">parser,</A> where the lexical scanner,
  48 <A HREF="../../backend/parser/scan.l">scan.l,</A> breaks the query up
  49 into tokens(words).  The parser uses <A
  50 HREF="../../backend/parser/gram.y">gram.y</A> and the tokens to identify
  51 the query type, and load the proper query-specific structure, like <A
  52 HREF="../../include/nodes/parsenodes.h">CreateStmt</A> or <A
  53 HREF="../../include/nodes/parsenodes.h">SelectStmt.</A><P>
  54
  55
  56 The query is then identified as a <I>Utility</I> query or a more complex
  57 query.  A <I>Utility</I> query is processed by a query-specific function
  58 in <A HREF="../../backend/commands"> commands.</A> A complex query, like
  59 <I>SELECT, UPDATE,</I> and <I>DELETE</I> requires much more handling.<P>
  60
  61
  62 The parser takes a complex query, and creates a
  63 <A HREF="../../include/nodes/parsenodes.h">Query</A> structure that
  64 contains all the elements used by complex queries.  Query.qual holds the
  65 <I>WHERE</I> clause qualification, which is filled in by <A
  66 HREF="../../backend/parser/parse_clause.c">transformWhereClause().</A>
  67 Each table referenced in the query is represented by a <A
  68 HREF="../../include/nodes/parsenodes.h"> RangeTableEntry,</A> and they
  69 are linked together to form the <I>range table</I> of the query, which
  70 is generated by <A HREF="../../backend/parser/parse_clause.c">
  71 makeRangeTable().</A>  Query.rtable holds the query's range table.<P>
  72
  73
  74 Certain queries, like <I>SELECT,</I> return columns of data.  Other
  75 queries, like <I>INSERT</I> and <I>UPDATE,</I> specify the columns
  76 modified by the query.  These column references are converted to <A
  77 HREF="../../include/nodes/primnodes.h">Resdom</A> entries, which are
  78 placed in <A HREF="../../include/nodes/parsenodes.h">target list
  79 entries,</A> and linked together to make up the <I>target list</I> of
  80 the query. The target list is stored in Query.targetList, which is
  81 generated by <A
  82 HREF="../../backend/parser/parse_target.c">transformTargetList().</A><P>
  83
  84
  85 Other query elements, like aggregates(<I>SUM()</I>), <I>GROUP BY,</I>
  86 and <I>ORDER BY</I> are also stored in their own Query fields.<P>
  87
  88
  89 The next step is for the Query to be modified by any <I>VIEWS</I> or
  90 <I>RULES</I> that may apply to the query.  This is performed by the <A
  91 HREF="../../backend/rewrite">rewrite</A> system.<P>
  92
  93
  94 The <A HREF="../../backend/optimizer">optimizer</A> takes the Query
  95 structure and generates an optimal <A
  96 HREF="../..//include/nodes/plannodes.h">Plan,</A> which contains the
  97 operations to be performed to execute the query.  The <A
  98 HREF="../../backend/optimizer/path">path</A> module determines the best
  99 table join order and join type of each table in the RangeTable, using
 100 Query.qual(<I>WHERE</I> clause) to consider optimal index usage.<P>
 101
 102
 103 The Plan is then passed to the <A
 104 HREF="../../backend/executor">executor</A> for execution, and the result
 105 returned to the client.  The Plan actually as set of nodes, arranged in
 106 a tree structure with a top-level node, and various sub-nodes as
 107 children.<P>
 108
 109
 110 There are many other modules that support this basic functionality. They
 111 can be accessed by clicking on the flowchart.<P>
 112
 113
 114 <HR><P>
 115
 116
 117 Another area of interest is the shared memory area, which contains data
 118 accessable to all backends.  It has recently used data/index blocks,
 119 locks, backend process information, and lookup tables for these
 120 structures:
 121
 122 <UL>
 123 <LI>ShmemIndex - lookup shared memory addresses using structure names
 124 <LI><A HREF="../../include/storage/buf_internals.h">Buffer
 125 Descriptor</A> - control header for buffer cache block
 126 <LI><A HREF="../../include/storage/buf_internals.h">Buffer Block</A> -
 127 data/index buffer cache block
 128 <LI>Shared Buffer Lookup Table - lookup of buffer cache block addresses
 129 using table name and block number(<A
 130 HREF="../../include/storage/buf_internals.h"> BufferTag</A>)
 131 <LI>MultiLevelLockTable (ctl) - control structure for each locking
 132 method.  Currently, only multi-level locking is used(<A
 133 HREF="../../include/storage/lock.h">LOCKMETHODCTL</A>).
 134 <LI>MultiLevelLockTable (lock hash) - the <A
 135 HREF="../../include/storage/lock.h">LOCK</A> structure, looked up using
 136 relation, database object ids(<A
 137 HREF="../../include/storage/lock.h">LOCKTAG)</A>.  The lock table
 138 structure contains the lock modes(read/write or shared/exclusive) and
 139 circular linked list of backends (<A
 140 HREF="../../include/storage/proc.h">PROC</A> structure pointers) waiting
 141 on the lock.
 142 <LI>MultiLevelLockTable (xid hash) - lookup of LOCK structure address
 143 using transaction id, LOCK address.  It is used to quickly check if the
 144 current transaction already has any locks on a table, rather than having
 145 to search through all the held locks.  It also stores the modes
 146 (read/write) of the locks held by the current transaction.  The returned
 147 <A HREF="../../include/storage/lock.h">XIDLookupEnt</A> structure also
 148 contains a pointer to the backend's PROC.lockQueue.
 149 <LI><A HREF="../../include/storage/proc.h">Proc Header</A> - information
 150 about each backend, including locks held/waiting, indexed by process id
 151 </UL>
 152
 153 Each data structure is created by calling <A
 154 HREF="../../backend/storage/ipc/shmem.c">ShmemInitStruct(),</A> and the
 155 lookups are created by <A
 156 HREF="../../backend/storage/ipc/shmem.c">ShmemInitHash().</A><P>
 157
 158
 159 <HR SIZE="2" NOSHADE>
 160 <SMALL>
 161 <ADDRESS>
 162 Maintainer:     Bruce Momjian (<A
 163 HREF="mailto:maillist@candle.pha.pa.us">maillist@candle.pha.pa.us</A>)<BR>
 164 Last updated:           Tue Dec  9 17:56:08 EST 1997
 165 </ADDRESS>
 166 </SMALL>
 167 </BODY>
 168 </HTML>