|
- <?xml version="1.0" encoding="UTF-8" standalone="no"?>
- <!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>59.3. Genetic Query Optimization (GEQO) in PostgreSQL</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 V1.79.1" /><link rel="prev" href="geqo-intro2.html" title="59.2. Genetic Algorithms" /><link rel="next" href="geqo-biblio.html" title="59.4. Further Reading" /></head><body><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">59.3. Genetic Query Optimization (<acronym xmlns="http://www.w3.org/1999/xhtml" class="acronym">GEQO</acronym>) in PostgreSQL</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="geqo-intro2.html" title="59.2. Genetic Algorithms">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="geqo.html" title="Chapter 59. Genetic Query Optimizer">Up</a></td><th width="60%" align="center">Chapter 59. Genetic Query Optimizer</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 12.4 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="geqo-biblio.html" title="59.4. Further Reading">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="GEQO-PG-INTRO"><div class="titlepage"><div><div><h2 class="title" style="clear: both">59.3. Genetic Query Optimization (<acronym class="acronym">GEQO</acronym>) in PostgreSQL</h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="geqo-pg-intro.html#id-1.10.12.5.6">59.3.1. Generating Possible Plans with <acronym class="acronym">GEQO</acronym></a></span></dt><dt><span class="sect2"><a href="geqo-pg-intro.html#GEQO-FUTURE">59.3.2. Future Implementation Tasks for
- <span class="productname">PostgreSQL</span> <acronym class="acronym">GEQO</acronym></a></span></dt></dl></div><p>
- The <acronym class="acronym">GEQO</acronym> module approaches the query
- optimization problem as though it were the well-known traveling salesman
- problem (<acronym class="acronym">TSP</acronym>).
- Possible query plans are encoded as integer strings. Each string
- represents the join order from one relation of the query to the next.
- For example, the join tree
- </p><pre class="literallayout">
- /\
- /\ 2
- /\ 3
- 4 1
- </pre><p>
- is encoded by the integer string '4-1-3-2',
- which means, first join relation '4' and '1', then '3', and
- then '2', where 1, 2, 3, 4 are relation IDs within the
- <span class="productname">PostgreSQL</span> optimizer.
- </p><p>
- Specific characteristics of the <acronym class="acronym">GEQO</acronym>
- implementation in <span class="productname">PostgreSQL</span>
- are:
-
- </p><div class="itemizedlist"><ul class="itemizedlist compact" style="list-style-type: bullet; "><li class="listitem" style="list-style-type: disc"><p>
- Usage of a <em class="firstterm">steady state</em> <acronym class="acronym">GA</acronym> (replacement of the least fit
- individuals in a population, not whole-generational replacement)
- allows fast convergence towards improved query plans. This is
- essential for query handling with reasonable time;
- </p></li><li class="listitem" style="list-style-type: disc"><p>
- Usage of <em class="firstterm">edge recombination crossover</em>
- which is especially suited to keep edge losses low for the
- solution of the <acronym class="acronym">TSP</acronym> by means of a
- <acronym class="acronym">GA</acronym>;
- </p></li><li class="listitem" style="list-style-type: disc"><p>
- Mutation as genetic operator is deprecated so that no repair
- mechanisms are needed to generate legal <acronym class="acronym">TSP</acronym> tours.
- </p></li></ul></div><p>
- </p><p>
- Parts of the <acronym class="acronym">GEQO</acronym> module are adapted from D. Whitley's
- Genitor algorithm.
- </p><p>
- The <acronym class="acronym">GEQO</acronym> module allows
- the <span class="productname">PostgreSQL</span> query optimizer to
- support large join queries effectively through
- non-exhaustive search.
- </p><div class="sect2" id="id-1.10.12.5.6"><div class="titlepage"><div><div><h3 class="title">59.3.1. Generating Possible Plans with <acronym class="acronym">GEQO</acronym></h3></div></div></div><p>
- The <acronym class="acronym">GEQO</acronym> planning process uses the standard planner
- code to generate plans for scans of individual relations. Then join
- plans are developed using the genetic approach. As shown above, each
- candidate join plan is represented by a sequence in which to join
- the base relations. In the initial stage, the <acronym class="acronym">GEQO</acronym>
- code simply generates some possible join sequences at random. For each
- join sequence considered, the standard planner code is invoked to
- estimate the cost of performing the query using that join sequence.
- (For each step of the join sequence, all three possible join strategies
- are considered; and all the initially-determined relation scan plans
- are available. The estimated cost is the cheapest of these
- possibilities.) Join sequences with lower estimated cost are considered
- <span class="quote">“<span class="quote">more fit</span>”</span> than those with higher cost. The genetic algorithm
- discards the least fit candidates. Then new candidates are generated
- by combining genes of more-fit candidates — that is, by using
- randomly-chosen portions of known low-cost join sequences to create
- new sequences for consideration. This process is repeated until a
- preset number of join sequences have been considered; then the best
- one found at any time during the search is used to generate the finished
- plan.
- </p><p>
- This process is inherently nondeterministic, because of the randomized
- choices made during both the initial population selection and subsequent
- <span class="quote">“<span class="quote">mutation</span>”</span> of the best candidates. To avoid surprising changes
- of the selected plan, each run of the GEQO algorithm restarts its
- random number generator with the current <a class="xref" href="runtime-config-query.html#GUC-GEQO-SEED">geqo_seed</a>
- parameter setting. As long as <code class="varname">geqo_seed</code> and the other
- GEQO parameters are kept fixed, the same plan will be generated for a
- given query (and other planner inputs such as statistics). To experiment
- with different search paths, try changing <code class="varname">geqo_seed</code>.
- </p></div><div class="sect2" id="GEQO-FUTURE"><div class="titlepage"><div><div><h3 class="title">59.3.2. Future Implementation Tasks for
- <span class="productname">PostgreSQL</span> <acronym class="acronym">GEQO</acronym></h3></div></div></div><p>
- Work is still needed to improve the genetic algorithm parameter
- settings.
- In file <code class="filename">src/backend/optimizer/geqo/geqo_main.c</code>,
- routines
- <code class="function">gimme_pool_size</code> and <code class="function">gimme_number_generations</code>,
- we have to find a compromise for the parameter settings
- to satisfy two competing demands:
- </p><div class="itemizedlist"><ul class="itemizedlist compact" style="list-style-type: disc; "><li class="listitem"><p>
- Optimality of the query plan
- </p></li><li class="listitem"><p>
- Computing time
- </p></li></ul></div><p>
- </p><p>
- In the current implementation, the fitness of each candidate join
- sequence is estimated by running the standard planner's join selection
- and cost estimation code from scratch. To the extent that different
- candidates use similar sub-sequences of joins, a great deal of work
- will be repeated. This could be made significantly faster by retaining
- cost estimates for sub-joins. The problem is to avoid expending
- unreasonable amounts of memory on retaining that state.
- </p><p>
- At a more basic level, it is not clear that solving query optimization
- with a GA algorithm designed for TSP is appropriate. In the TSP case,
- the cost associated with any substring (partial tour) is independent
- of the rest of the tour, but this is certainly not true for query
- optimization. Thus it is questionable whether edge recombination
- crossover is the most effective mutation procedure.
- </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="geqo-intro2.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="geqo.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="geqo-biblio.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">59.2. Genetic Algorithms </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 59.4. Further Reading</td></tr></table></div></body></html>
|
