<HTML> <HEAD> <TITLE>How PostgreSQL Processes a Query</TITLE> </HEAD> <BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#FF0000" VLINK="#A00000" ALINK="#0000FF"> <H1 ALIGN=CENTER> How PostgreSQL Processes a Query </H1> <H2 ALIGN=CENTER> by Bruce Momjian </H2> <P> 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 <A HREF="../../backend/parser">parser,</A> where the lexical scanner, <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> 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 <CODE>SELECT, UPDATE,</CODE> and <CODE>DELETE</CODE> requires much more handling. <P> The parser takes a complex query, and creates a <A HREF="../../include/nodes/parsenodes.h">Query</A> structure that contains all the elements used by complex queries. Query.qual holds the <CODE>WHERE</CODE> clause qualification, which is filled in by <A HREF="../../backend/parser/parse_clause.c">transformWhereClause().</A> Each table referenced in the query is represented by a <A HREF="../../include/nodes/parsenodes.h"> RangeTableEntry,</A> and they 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> Certain queries, like <CODE>SELECT,</CODE> return columns of data. Other queries, like <CODE>INSERT</CODE> and <CODE>UPDATE,</CODE> specify the columns modified by the query. These column references are converted to <A HREF="../../include/nodes/primnodes.h">Resdom</A> entries, which are linked together to make up the <I>target list</I> of the query. The target list is stored in Query.targetList, which is generated by <A HREF="../../backend/parser/parse_target.c">transformTargetList().</A> <P> Other query elements, like aggregates(<CODE>SUM()</CODE>), <CODE>GROUP BY,</CODE> and <CODE>ORDER BY</CODE> are also stored in their own Query fields. <P> The next step is for the Query to be modified by any <CODE>VIEWS</CODE> or <CODE>RULES</CODE> that may apply to the query. This is performed by the <A HREF="../../backend/rewrite">rewrite</A> system. <P> The <A HREF="../../backend/optimizer">optimizer</A> takes the Query 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 Query.qual(<CODE>WHERE</CODE> clause) to consider optimal index usage. <P> The Plan is then passed to the <A HREF="../../backend/executor">executor</A> for execution, and the result returned to the client. <P> There are many other modules that support this basic functionality. They can be accessed by clicking on the flowchart. <P> Another area of interest is the shared memory area, which contains data accessable to all backends. It has table recently used data/index blocks, locks, backend information, and lookup tables for these structures: <UL> <LI>ShmemIndex - lookup shared memory addresses using structure names <LI><A HREF="../../include/storage/buf_internals.h">Buffer Descriptor</A> - control header for buffer cache block <LI><A HREF="../../include/storage/buf_internals.h">Buffer Block</A> - data/index buffer cache block <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 HREF="../../include/storage/lock.h">LOCKMETHODCTL</A>). <LI>MultiLevelLockTable (lock hash) - the <A HREF="../../include/storage/lock.h">LOCK</A> structure, looked up using relation, database object ids(<A HREF="../../include/storage/lock.h">LOCKTAG)</A>. The lock table structure contains the lock modes(read, write) and circular linked list of backends (<A 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. <LI><A HREF="../../include/storage/proc.h">Proc Header</A> - information about each backend, including locks held/waiting, indexed by process id </UL> Each data structure is created by calling <A HREF="../../backend/storage/ipc/shmem.c">ShmemInitStruct(),</A> and the lookups are created by <A HREF="../../backend/storage/ipc/shmem.c">ShmemInitHash().</A> <P> <HR> <P> <CENTER> <EM><BIG> Click on an item to see more detail or <A HREF="backend_dirs.html">click</A> to see the full index. </BIG></EM> <BR> <BR> <IMG src="flow.jpg" usemap="#flowmap" alt="flowchart"> </CENTER> <MAP name="flowmap"> <AREA COORDS="290,10,450,50" HREF="backend_dirs.html#main"> <AREA COORDS="550,10,710,50" HREF="backend_dirs.html#bootstrap"> <AREA COORDS="290,90,450,130," HREF="backend_dirs.html#postmaster"> <AREA COORDS="550,90,710,130," HREF="backend_dirs.html#libpq"> <AREA COORDS="290,170,450,210" HREF="backend_dirs.html#tcop"> <AREA COORDS="550,170,710,210" HREF="backend_dirs.html#tcop"> <AREA COORDS="290,270,450,310" HREF="backend_dirs.html#parser"> <AREA COORDS="290,350,450,390" HREF="backend_dirs.html#tcop"> <AREA COORDS="290,430,450,470" HREF="backend_dirs.html#optimizer"> <AREA COORDS="290,510,450,550" HREF="backend_dirs.html#optimizer/plan"> <AREA COORDS="290,570,450,630" HREF="backend_dirs.html#executor"> <AREA COORDS="550,350,710,390" HREF="backend_dirs.html#commands"> <AREA COORDS="10,330,170,370" HREF="backend_dirs.html#access"> <AREA COORDS="10,390,170,430" HREF="backend_dirs.html#catalog"> <AREA COORDS="10,450,170,490" HREF="backend_dirs.html#utils"> <AREA COORDS="10,510,170,550" HREF="backend_dirs.html#nodes"> <AREA COORDS="10,570,170,610" HREF="backend_dirs.html#storage"> </MAP> <BR> <HR SIZE="2" NOSHADE> <SMALL> <ADDRESS> 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 </ADDRESS> </SMALL> </BODY> </HTML>