Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita17b537

Browse files
committed
This patch makes a few incremental improvements to geqo.sgml and
arch-dev.sgmlNeil Conway
1 parent04e401f commita17b537

File tree

6 files changed

+101
-65
lines changed

6 files changed

+101
-65
lines changed

‎doc/src/sgml/arch-dev.sgml

Lines changed: 55 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tgl Exp $
2+
$Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.22 2003/09/29 18:18:35 momjian Exp $
33
-->
44

55
<chapter id="overview">
@@ -25,7 +25,7 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
2525
very extensive. Rather, this chapter is intended to help the reader
2626
understand the general sequence of operations that occur within the
2727
backend from the point at which a query is received, to the point
28-
when the results are returned to the client.
28+
at which the results are returned to the client.
2929
</para>
3030

3131
<sect1 id="query-path">
@@ -79,7 +79,7 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
7979
<step>
8080
<para>
8181
The <firstterm>planner/optimizer</firstterm> takes
82-
the (rewritten)querytree and creates a
82+
the (rewritten)query tree and creates a
8383
<firstterm>query plan</firstterm> that will be the input to the
8484
<firstterm>executor</firstterm>.
8585
</para>
@@ -183,12 +183,12 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
183183
<title>Parser</title>
184184

185185
<para>
186-
The parser has to check the query string (which arrives as
187-
plainASCII text) for valid syntax. If the syntax is correct a
188-
<firstterm>parse tree</firstterm> is built up and handed back otherwise an error is
189-
returned. For the implementation the well known Unix
190-
tools <application>lex</application> and<application>yacc</application>
191-
are used.
186+
The parser has to check the query string (which arrives as plain
187+
ASCII text) for valid syntax. If the syntax is correct a
188+
<firstterm>parse tree</firstterm> is built up and handed back;
189+
otherwise an error is returned. The parser and lexer are
190+
implemented using the well-known Unix tools<application>yacc</>
191+
and <application>lex</>.
192192
</para>
193193

194194
<para>
@@ -201,23 +201,22 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
201201
</para>
202202

203203
<para>
204-
The parser is defined in the file <filename>gram.y</filename> and consists of a
205-
set of <firstterm>grammar rules</firstterm> and <firstterm>actions</firstterm>
206-
that are executed
207-
whenever a ruleis fired. The code of the actions (which
208-
is actually C-code) isused to build up the parse tree.
204+
The parser is defined in the file <filename>gram.y</filename> and
205+
consists of aset of <firstterm>grammar rules</firstterm> and
206+
<firstterm>actions</firstterm>that are executed whenever a rule
207+
is fired. The code of the actions (which is actually C code) is
208+
used to build up the parse tree.
209209
</para>
210210

211211
<para>
212-
The file <filename>scan.l</filename> is transformed to
213-
the C-source file <filename>scan.c</filename>
214-
using the program <application>lex</application>
215-
and <filename>gram.y</filename> is transformed to
216-
<filename>gram.c</filename> using <application>yacc</application>.
217-
After these transformations have taken
218-
place a normal C-compiler can be used to create the
219-
parser. Never make any changes to the generated C-files as they will
220-
be overwritten the next time <application>lex</application>
212+
The file <filename>scan.l</filename> is transformed to the C
213+
source file <filename>scan.c</filename> using the program
214+
<application>lex</application> and <filename>gram.y</filename> is
215+
transformed to <filename>gram.c</filename> using
216+
<application>yacc</application>. After these transformations
217+
have taken place a normal C compiler can be used to create the
218+
parser. Never make any changes to the generated C files as they
219+
will be overwritten the next time <application>lex</application>
221220
or <application>yacc</application> is called.
222221

223222
<note>
@@ -334,15 +333,27 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
334333
<title>Planner/Optimizer</title>
335334

336335
<para>
337-
The task of the <firstterm>planner/optimizer</firstterm> is to create an optimal
338-
execution plan.It first considers all possible ways of
339-
<firstterm>scanning</firstterm> and <firstterm>joining</firstterm>
340-
the relations that appear in a
341-
query. All the created paths lead to thesame result and it's the
342-
task of the optimizer to estimate the costofexecuting each path and
343-
find out which one isthecheapest.
336+
The task of the <firstterm>planner/optimizer</firstterm> is to
337+
create an optimalexecution plan.A given SQL query (and hence, a
338+
query tree) can be actually executed in a wide variety of
339+
different ways, each of which will produce the same set of
340+
results. If it is computationally feasible, thequery optimizer
341+
will examine eachofthese possible execution plans, ultimately
342+
selecting the execution plan that will runthefastest.
344343
</para>
345344

345+
<note>
346+
<para>
347+
In some situations, examining each possible way in which a query
348+
may be executed would take an excessive amount of time and memory
349+
space. In particular, this occurs when executing queries
350+
involving large numbers of join operations. In order to determine
351+
a reasonable (not optimal) query plan in a reasonable amount of
352+
time, <productname>PostgreSQL</productname> uses a <xref
353+
linkend="geqo" endterm="geqo-title">.
354+
</para>
355+
</note>
356+
346357
<para>
347358
After the cheapest path is determined, a <firstterm>plan tree</>
348359
is built to pass to the executor. This represents the desired
@@ -373,7 +384,7 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
373384
After all feasible plans have been found for scanning single relations,
374385
plans for joining relations are created. The planner/optimizer
375386
preferentially considers joins between any two relations for which there
376-
exist a corresponding join clause in the WHERE qualification (i.e. for
387+
exist a corresponding join clause in the<literal>WHERE</literal> qualification (i.e. for
377388
which a restriction like <literal>where rel1.attr1=rel2.attr2</literal>
378389
exists). Join pairs with no join clause are considered only when there
379390
is no other choice, that is, a particular relation has no available
@@ -416,17 +427,19 @@ $Header: /cvsroot/pgsql/doc/src/sgml/arch-dev.sgml,v 2.21 2003/06/22 16:16:44 tg
416427
</para>
417428

418429
<para>
419-
The finished plan tree consists of sequential or index scans of the
420-
base relations, plus nestloop, merge, or hash join nodes as needed,
421-
plus any auxiliary steps needed, such as sort nodes or aggregate-function
422-
calculation nodes. Most of these plan node types have the additional
423-
ability to do <firstterm>selection</> (discarding rows that do
424-
not meet a specified boolean condition) and <firstterm>projection</>
425-
(computation of a derived column set based on given column values,
426-
that is, evaluation of scalar expressions where needed). One of
427-
the responsibilities of the planner is to attach selection conditions
428-
from the WHERE clause and computation of required output expressions
429-
to the most appropriate nodes of the plan tree.
430+
The finished plan tree consists of sequential or index scans of
431+
the base relations, plus nestloop, merge, or hash join nodes as
432+
needed, plus any auxiliary steps needed, such as sort nodes or
433+
aggregate-function calculation nodes. Most of these plan node
434+
types have the additional ability to do <firstterm>selection</>
435+
(discarding rows that do not meet a specified boolean condition)
436+
and <firstterm>projection</> (computation of a derived column set
437+
based on given column values, that is, evaluation of scalar
438+
expressions where needed). One of the responsibilities of the
439+
planner is to attach selection conditions from the
440+
<literal>WHERE</literal> clause and computation of required
441+
output expressions to the most appropriate nodes of the plan
442+
tree.
430443
</para>
431444
</sect2>
432445
</sect1>

‎doc/src/sgml/geqo.sgml

Lines changed: 30 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$Header: /cvsroot/pgsql/doc/src/sgml/geqo.sgml,v 1.23 2002/01/20 22:19:56 petere Exp $
2+
$Header: /cvsroot/pgsql/doc/src/sgml/geqo.sgml,v 1.24 2003/09/29 18:18:35 momjian Exp $
33
Genetic Optimizer
44
-->
55

@@ -28,7 +28,7 @@ Genetic Optimizer
2828
<date>1997-10-02</date>
2929
</docinfo>
3030

31-
<title>Genetic QueryOptimization</title>
31+
<title id="geqo-title">Genetic QueryOptimizer</title>
3232

3333
<para>
3434
<note>
@@ -44,24 +44,29 @@ Genetic Optimizer
4444
<title>Query Handling as a Complex Optimization Problem</title>
4545

4646
<para>
47-
Among all relational operators the most difficult one to process and
48-
optimize is the <firstterm>join</firstterm>. The number of alternative plans to answer a query
49-
grows exponentially with the number of joins included in it. Further
50-
optimization effort is caused by the support of a variety of
51-
<firstterm>join methods</firstterm>
52-
(e.g., nested loop, hash join, merge join in <productname>PostgreSQL</productname>) to
53-
process individual joins and a diversity of
54-
<firstterm>indexes</firstterm> (e.g., R-tree,
55-
B-tree, hash in <productname>PostgreSQL</productname>) as access paths for relations.
47+
Among all relational operators the most difficult one to process
48+
and optimize is the <firstterm>join</firstterm>. The number of
49+
alternative plans to answer a query grows exponentially with the
50+
number of joins included in it. Further optimization effort is
51+
caused by the support of a variety of <firstterm>join
52+
methods</firstterm> (e.g., nested loop, hash join, merge join in
53+
<productname>PostgreSQL</productname>) to process individual joins
54+
and a diversity of <firstterm>indexes</firstterm> (e.g., R-tree,
55+
B-tree, hash in <productname>PostgreSQL</productname>) as access
56+
paths for relations.
5657
</para>
5758

5859
<para>
5960
The current <productname>PostgreSQL</productname> optimizer
60-
implementation performs a <firstterm>near-exhaustive search</firstterm>
61-
over the space of alternative strategies. This query
62-
optimization technique is inadequate to support database application
63-
domains that involve the need for extensive queries, such as artificial
64-
intelligence.
61+
implementation performs a <firstterm>near-exhaustive
62+
search</firstterm> over the space of alternative strategies. This
63+
algorithm, first introduced in the <quote>System R</quote>
64+
database, produces a near-optimal join order, but can take an
65+
enormous amount of time and memory space when the number of joins
66+
in the query grows large. This makes the ordinary
67+
<productname>PostgreSQL</productname> query optimizer
68+
inappropriate for database application domains that involve the
69+
need for extensive queries, such as artificial intelligence.
6570
</para>
6671

6772
<para>
@@ -75,12 +80,14 @@ Genetic Optimizer
7580

7681
<para>
7782
Performance difficulties in exploring the space of possible query
78-
plans created the demand for a new optimization techniquebeing developed.
83+
plans created the demand for a new optimization techniqueto be developed.
7984
</para>
8085

8186
<para>
82-
In the following we propose the implementation of a <firstterm>Genetic Algorithm</firstterm>
83-
as an option for the database query optimization problem.
87+
In the following we describe the implementation of a
88+
<firstterm>Genetic Algorithm</firstterm> to solve the join
89+
ordering problem in a manner that is efficient for queries
90+
involving large numbers of joins.
8491
</para>
8592
</sect1>
8693

@@ -208,10 +215,10 @@ Genetic Optimizer
208215

209216
<listitem>
210217
<para>
211-
Usage of <firstterm>edge recombination crossover</firstterm> which is
212-
especially suited
213-
to keep edge losses low for the solutionofthe
214-
<acronym>TSP</acronym> by means of a <acronym>GA</acronym>;
218+
Usage of <firstterm>edge recombination crossover</firstterm>
219+
which isespecially suited to keep edge losses low for the
220+
solution of the <acronym>TSP</acronym> by meansofa
221+
<acronym>GA</acronym>;
215222
</para>
216223
</listitem>
217224

‎doc/src/sgml/gist.sgml

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
<!--
2+
$Header: /cvsroot/pgsql/doc/src/sgml/gist.sgml,v 1.12 2003/09/29 18:18:35 momjian Exp $
3+
-->
4+
15
<Chapter Id="gist">
26
<DocInfo>
37
<AuthorGroup>

‎doc/src/sgml/install-win32.sgml

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
<!--
2+
$Header: /cvsroot/pgsql/doc/src/sgml/install-win32.sgml,v 1.12 2003/09/29 18:18:35 momjian Exp $
3+
-->
4+
15
<chapter id="install-win32">
26
<title>Installation on <productname>Windows</productname></title>
37

‎doc/src/sgml/libpgtcl.sgml

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
<!--
2+
$Header: /cvsroot/pgsql/doc/src/sgml/Attic/libpgtcl.sgml,v 1.38 2003/09/29 18:18:35 momjian Exp $
3+
-->
4+
15
<chapter id="pgtcl">
26
<title><application>pgtcl</application> - Tcl Binding Library</title>
37

‎doc/src/sgml/page.sgml

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
<!--
2+
$Header: /cvsroot/pgsql/doc/src/sgml/Attic/page.sgml,v 1.14 2003/09/29 18:18:35 momjian Exp $
3+
-->
4+
15
<chapter id="page">
26

37
<title>Page Files</title>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp