begriffs open source - ai-pg/blob - full-docs/src/sgml/html/planner-optimizer.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>51.5. Planner/Optimizer</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="rule-system.html" title="51.4. The PostgreSQL Rule System" /><link rel="next" href="executor.html" title="51.6. Executor" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">51.5. Planner/Optimizer</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="rule-system.html" title="51.4. The PostgreSQL Rule System">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="overview.html" title="Chapter 51. Overview of PostgreSQL Internals">Up</a></td><th width="60%" align="center">Chapter 51. Overview of PostgreSQL Internals</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 18.0 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="executor.html" title="51.6. Executor">Next</a></td></tr></table><hr /></div><div class="sect1" id="PLANNER-OPTIMIZER"><div class="titlepage"><div><div><h2 class="title" style="clear: both">51.5. Planner/Optimizer <a href="#PLANNER-OPTIMIZER" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="planner-optimizer.html#PLANNER-OPTIMIZER-GENERATING-POSSIBLE-PLANS">51.5.1. Generating Possible Plans</a></span></dt></dl></div><p>
   3     The task of the <em class="firstterm">planner/optimizer</em> is to
   4     create an optimal execution plan. A given SQL query (and hence, a
   5     query tree) can be actually executed in a wide variety of
   6     different ways, each of which will produce the same set of
   7     results.  If it is computationally feasible, the query optimizer
   8     will examine each of these possible execution plans, ultimately
   9     selecting the execution plan that is expected to run the fastest.
  10    </p><div class="note"><h3 class="title">Note</h3><p>
  11      In some situations, examining each possible way in which a query
  12      can be executed would take an excessive amount of time and memory.
  13      In particular, this occurs when executing queries
  14      involving large numbers of join operations. In order to determine
  15      a reasonable (not necessarily optimal) query plan in a reasonable amount
  16      of time, <span class="productname">PostgreSQL</span> uses a <em class="firstterm">Genetic
  17      Query Optimizer</em> (see <a class="xref" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Chapter 61</a>) when the number of joins
  18      exceeds a threshold (see <a class="xref" href="runtime-config-query.html#GUC-GEQO-THRESHOLD">geqo_threshold</a>).
  19     </p></div><p>
  20     The planner's search procedure actually works with data structures
  21     called <em class="firstterm">paths</em>, which are simply cut-down representations of
  22     plans containing only as much information as the planner needs to make
  23     its decisions. After the cheapest path is determined, a full-fledged
  24     <em class="firstterm">plan tree</em> is built to pass to the executor.  This represents
  25     the desired execution plan in sufficient detail for the executor to run it.
  26     In the rest of this section we'll ignore the distinction between paths
  27     and plans.
  28    </p><div class="sect2" id="PLANNER-OPTIMIZER-GENERATING-POSSIBLE-PLANS"><div class="titlepage"><div><div><h3 class="title">51.5.1. Generating Possible Plans <a href="#PLANNER-OPTIMIZER-GENERATING-POSSIBLE-PLANS" class="id_link">#</a></h3></div></div></div><p>
  29      The planner/optimizer starts by generating plans for scanning each
  30      individual relation (table) used in the query.  The possible plans
  31      are determined by the available indexes on each relation.
  32      There is always the possibility of performing a
  33      sequential scan on a relation, so a sequential scan plan is always
  34      created. Assume an index is defined on a
  35      relation (for example a B-tree index) and a query contains the
  36      restriction
  37      <code class="literal">relation.attribute OPR constant</code>. If
  38      <code class="literal">relation.attribute</code> happens to match the key of the B-tree
  39      index and <code class="literal">OPR</code> is one of the operators listed in
  40      the index's <em class="firstterm">operator class</em>, another plan is created using
  41      the B-tree index to scan the relation. If there are further indexes
  42      present and the restrictions in the query happen to match a key of an
  43      index, further plans will be considered.  Index scan plans are also
  44      generated for indexes that have a sort ordering that can match the
  45      query's <code class="literal">ORDER BY</code> clause (if any), or a sort ordering that
  46      might be useful for merge joining (see below).
  47     </p><p>
  48      If the query requires joining two or more relations,
  49      plans for joining relations are considered
  50      after all feasible plans have been found for scanning single relations.
  51      The three available join strategies are:
  52
  53      </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
  54         <em class="firstterm">nested loop join</em>: The right relation is scanned
  55         once for every row found in the left relation. This strategy
  56         is easy to implement but can be very time consuming.  (However,
  57         if the right relation can be scanned with an index scan, this can
  58         be a good strategy.  It is possible to use values from the current
  59         row of the left relation as keys for the index scan of the right.)
  60        </p></li><li class="listitem"><p>
  61         <em class="firstterm">merge join</em>: Each relation is sorted on the join
  62         attributes before the join starts. Then the two relations are
  63         scanned in parallel, and matching rows are combined to form
  64         join rows. This kind of join is
  65         attractive because each relation has to be scanned only once.
  66         The required sorting might be achieved either by an explicit sort
  67         step, or by scanning the relation in the proper order using an
  68         index on the join key.
  69        </p></li><li class="listitem"><p>
  70         <em class="firstterm">hash join</em>: the right relation is first scanned
  71         and loaded into a hash table, using its join attributes as hash keys.
  72         Next the left relation is scanned and the
  73         appropriate values of every row found are used as hash keys to
  74         locate the matching rows in the table.
  75        </p></li></ul></div><p>
  76     </p><p>
  77      When the query involves more than two relations, the final result
  78      must be built up by a tree of join steps, each with two inputs.
  79      The planner examines different possible join sequences to find the
  80      cheapest one.
  81     </p><p>
  82      If the query uses fewer than <a class="xref" href="runtime-config-query.html#GUC-GEQO-THRESHOLD">geqo_threshold</a>
  83      relations, a near-exhaustive search is conducted to find the best
  84      join sequence.  The planner preferentially considers joins between any
  85      two relations for which there exists a corresponding join clause in the
  86      <code class="literal">WHERE</code> qualification (i.e., for
  87      which a restriction like <code class="literal">where rel1.attr1=rel2.attr2</code>
  88      exists). Join pairs with no join clause are considered only when there
  89      is no other choice, that is, a particular relation has no available
  90      join clauses to any other relation. All possible plans are generated for
  91      every join pair considered by the planner, and the one that is
  92      (estimated to be) the cheapest is chosen.
  93     </p><p>
  94      When <code class="varname">geqo_threshold</code> is exceeded, the join
  95      sequences considered are determined by heuristics, as described
  96      in <a class="xref" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Chapter 61</a>.  Otherwise the process is the same.
  97     </p><p>
  98      The finished plan tree consists of sequential or index scans of
  99      the base relations, plus nested-loop, merge, or hash join nodes as
 100      needed, plus any auxiliary steps needed, such as sort nodes or
 101      aggregate-function calculation nodes.  Most of these plan node
 102      types have the additional ability to do <em class="firstterm">selection</em>
 103      (discarding rows that do not meet a specified Boolean condition)
 104      and <em class="firstterm">projection</em> (computation of a derived column set
 105      based on given column values, that is, evaluation of scalar
 106      expressions where needed).  One of the responsibilities of the
 107      planner is to attach selection conditions from the
 108      <code class="literal">WHERE</code> clause and computation of required
 109      output expressions to the most appropriate nodes of the plan
 110      tree.
 111     </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="rule-system.html" title="51.4. The PostgreSQL Rule System">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="overview.html" title="Chapter 51. Overview of PostgreSQL Internals">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="executor.html" title="51.6. Executor">Next</a></td></tr><tr><td width="40%" align="left" valign="top">51.4. The <span class="productname">PostgreSQL</span> Rule System </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 18.0 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 51.6. Executor</td></tr></table></div></body></html>