begriffs open source - ai-pg/blob - full-docs/html/geqo-intro.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>61.1. Query Handling as a Complex Optimization Problem</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="geqo.html" title="Chapter 61. Genetic Query Optimizer" /><link rel="next" href="geqo-intro2.html" title="61.2. Genetic Algorithms" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">61.1. Query Handling as a Complex Optimization Problem</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Up</a></td><th width="60%" align="center">Chapter 61. Genetic Query Optimizer</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="geqo-intro2.html" title="61.2. Genetic Algorithms">Next</a></td></tr></table><hr /></div><div class="sect1" id="GEQO-INTRO"><div class="titlepage"><div><div><h2 class="title" style="clear: both">61.1. Query Handling as a Complex Optimization Problem <a href="#GEQO-INTRO" class="id_link">#</a></h2></div></div></div><p>
   3     Among all relational operators the most difficult one to process
   4     and optimize is the <em class="firstterm">join</em>. The number of
   5     possible query plans grows exponentially with the
   6     number of joins in the query. Further optimization effort is
   7     caused by the support of a variety of <em class="firstterm">join
   8     methods</em> (e.g., nested loop, hash join, merge join in
   9     <span class="productname">PostgreSQL</span>) to process individual joins
  10     and a diversity of <em class="firstterm">indexes</em> (e.g.,
  11     B-tree, hash, GiST and GIN in <span class="productname">PostgreSQL</span>) as
  12     access paths for relations.
  13    </p><p>
  14     The normal <span class="productname">PostgreSQL</span> query optimizer
  15     performs a <em class="firstterm">near-exhaustive search</em> over the
  16     space of alternative strategies. This algorithm, first introduced
  17     in IBM's System R database, produces a near-optimal join order,
  18     but can take an enormous amount of time and memory space when the
  19     number of joins in the query grows large. This makes the ordinary
  20     <span class="productname">PostgreSQL</span> query optimizer
  21     inappropriate for queries that join a large number of tables.
  22    </p><p>
  23     The Institute of Automatic Control at the University of Mining and
  24     Technology, in Freiberg, Germany, encountered some problems when
  25     it wanted to use <span class="productname">PostgreSQL</span> as the
  26     backend for a decision support knowledge based system for the
  27     maintenance of an electrical power grid. The DBMS needed to handle
  28     large join queries for the inference machine of the knowledge
  29     based system. The number of joins in these queries made using the
  30     normal query optimizer infeasible.
  31    </p><p>
  32     In the following we describe the implementation of a
  33     <em class="firstterm">genetic algorithm</em> to solve the join
  34     ordering problem in a manner that is efficient for queries
  35     involving large numbers of joins.
  36    </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="geqo.html" title="Chapter 61. Genetic Query Optimizer">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="geqo-intro2.html" title="61.2. Genetic Algorithms">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 61. Genetic Query Optimizer </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"> 61.2. Genetic Algorithms</td></tr></table></div></body></html>