/ Check-in [ccd12e9e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Refinements to the optimizer overview and integration into the website. (CVS 2649)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ccd12e9e790e271cb1dbbae1c13e9cb980eaf11d
User & Date: drh 2005-08-31 03:13:12
Context
2005-08-31
13:13
Explicit typecasts to silence nuisance compiler warnings. Ticket #1398. (CVS 2650) check-in: 90712ea7 user: drh tags: trunk
03:13
Refinements to the optimizer overview and integration into the website. (CVS 2649) check-in: ccd12e9e user: drh tags: trunk
02:46
Update the FAQ to include an entry about binary versus decimal numbers. (CVS 2648) check-in: 0bbe73fc user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to www/docs.tcl.

1
2
3
4
5
6
7
8
9
10
11
..
34
35
36
37
38
39
40






41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
..
93
94
95
96
97
98
99
















100
101
102
103
104
105
106
# This script generates the "docs.html" page that describes various
# sources of documentation available for SQLite.
#
set rcsid {$Id: docs.tcl,v 1.11 2005/03/19 14:45:50 drh Exp $}
source common.tcl
header {SQLite Documentation}
puts {
<h2>Available Documentation</h2>
<table width="100%" cellpadding="5">
}

................................................................................
  A very quick introduction to programming with SQLite.
}

doc {SQL Syntax} {lang.html} {
  This document describes the SQL language that is understood by
  SQLite.  
}







doc {Pragma commands} {pragma.html} {
  This document describes SQLite performance tuning options and other 
  special purpose database commands.
}

doc {Version 2 C/C++ API} {c_interface.html} {
  A description of the C/C++ interface bindings for SQLite through version 
  2.8
}
doc {SQLite Version 3} {version3.html} {
  A summary of of the changes between SQLite version 2.8 and SQLite version 3.0.
}
doc {Version 3 C/C++ API} {capi3.html} {
  A description of the C/C++ interface bindings for SQLite version 3.0.0
  and following.
}
doc {Version 3 C/C++ API<br>Reference} {capi3ref.html} {
  This document describes each API function separately.
}

doc {Tcl API} {tclsqlite.html} {
  A description of the TCL interface bindings for SQLite.
}

doc {Locking And Concurrency<br>In SQLite Version 3} {lockingv3.html} {
  A description of how the new locking code in version 3 increases
  concurrancy and decreases the problem of writer starvation.
}

doc {Version 2 DataTypes } {datatypes.html} {
  A description of how SQLite version 2 handles SQL datatypes.
  Short summary:  Everything is a string.
}
doc {Version 3 DataTypes } {datatype3.html} {
  SQLite version 3 introduces the concept of manifest typing, where the
  type of a value is associated with the value itself, not the column that
  it is stored in.
  This page describes data typing for SQLite version 3 in further detail.
}

doc {Release History} {changes.html} {
  A chronology of SQLite releases going back to version 1.0.0
}

doc {Null Handling} {nulls.html} {
  Different SQL database engines handle NULLs in different ways.  The
  SQL standards are ambiguous.  This document describes how SQLite handles
  NULLs in comparison with other SQL database engines.
}

................................................................................
  SQLite is in the public domain.  This document describes what that means
  and the implications for contributors.
}

doc {Unsupported SQL} {omitted.html} {
  This page describes features of SQL that SQLite does not support.
}

















doc {Speed Comparison} {speed.html} {
  The speed of version 2.7.6 of SQLite is compared against PostgreSQL and
  MySQL.
}

doc {Architecture} {arch.html} {



|







 







>
>
>
>
>
>





<
<
<
<
<







|
|
|
|
|
<







|
|
|

<
<
<
<
<
|
<
<
<
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
..
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51





52
53
54
55
56
57
58
59
60
61
62
63

64
65
66
67
68
69
70
71
72
73
74





75




76
77
78
79
80
81
82
..
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# This script generates the "docs.html" page that describes various
# sources of documentation available for SQLite.
#
set rcsid {$Id: docs.tcl,v 1.12 2005/08/31 03:13:12 drh Exp $}
source common.tcl
header {SQLite Documentation}
puts {
<h2>Available Documentation</h2>
<table width="100%" cellpadding="5">
}

................................................................................
  A very quick introduction to programming with SQLite.
}

doc {SQL Syntax} {lang.html} {
  This document describes the SQL language that is understood by
  SQLite.  
}
doc {Version 3 C/C++ API<br>Reference} {capi3ref.html} {
  This document describes each API function separately.
}
doc {Tcl API} {tclsqlite.html} {
  A description of the TCL interface bindings for SQLite.
}

doc {Pragma commands} {pragma.html} {
  This document describes SQLite performance tuning options and other 
  special purpose database commands.
}





doc {SQLite Version 3} {version3.html} {
  A summary of of the changes between SQLite version 2.8 and SQLite version 3.0.
}
doc {Version 3 C/C++ API} {capi3.html} {
  A description of the C/C++ interface bindings for SQLite version 3.0.0
  and following.
}
doc {Version 3 DataTypes } {datatype3.html} {
  SQLite version 3 introduces the concept of manifest typing, where the
  type of a value is associated with the value itself, not the column that
  it is stored in.
  This page describes data typing for SQLite version 3 in further detail.

}

doc {Locking And Concurrency<br>In SQLite Version 3} {lockingv3.html} {
  A description of how the new locking code in version 3 increases
  concurrancy and decreases the problem of writer starvation.
}

doc {Overview Of The Optimizer} {optoverview.html} {
  A quick overview of the various query optimizations that are
  attempted by the SQLite code generator.
}











doc {Null Handling} {nulls.html} {
  Different SQL database engines handle NULLs in different ways.  The
  SQL standards are ambiguous.  This document describes how SQLite handles
  NULLs in comparison with other SQL database engines.
}

................................................................................
  SQLite is in the public domain.  This document describes what that means
  and the implications for contributors.
}

doc {Unsupported SQL} {omitted.html} {
  This page describes features of SQL that SQLite does not support.
}

doc {Version 2 C/C++ API} {c_interface.html} {
  A description of the C/C++ interface bindings for SQLite through version 
  2.8
}


doc {Version 2 DataTypes } {datatypes.html} {
  A description of how SQLite version 2 handles SQL datatypes.
  Short summary:  Everything is a string.
}

doc {Release History} {changes.html} {
  A chronology of SQLite releases going back to version 1.0.0
}


doc {Speed Comparison} {speed.html} {
  The speed of version 2.7.6 of SQLite is compared against PostgreSQL and
  MySQL.
}

doc {Architecture} {arch.html} {

Changes to www/optoverview.tcl.

1
2
3
4
5
6
7
8
9
10
11
..
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
...
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
...
437
438
439
440
441
442
443
444
445












446
447
448


























449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467


468
469
#
# Run this TCL script to generate HTML for the goals.html file.
#
set rcsid {$Id: optoverview.tcl,v 1.1 2005/08/31 01:50:00 drh Exp $}
source common.tcl
header {The SQLite Query Optimizer Overview}

proc CODE {text} {
  puts "<blockquote><pre>"
  puts $text
  puts "</pre></blockquote>"
................................................................................
  puts "<h$n>$num $name</h$n>"
}

HEADING 0 {The SQLite Query Optimizer Overview}

PARAGRAPH {
  This document provides a terse overview of how the query optimizer
  for SQLite works.  This is not a tutoral.  Some prior knowledge of how
  database engines operate is likely needed in order to fully understand
  this text.
}

HEADING 1 {WHERE clause analysis} where_clause

PARAGRAPH {
................................................................................
  do a binary search on the index to find the index entry, then extract
  the rowid from the index and use that rowid to do a binary search on
  the original table.  Thus a typical indexed lookup involves two
  binary searches.
  If, however, all columns that were to be fetched from the table are
  already available in the index itself, SQLite will use the values
  contained in the index and will never look up the original table
  row.  This saves a binary search for each table and can make many
  queries run twice as fast.
}

HEADING 1 {ORDER BY optimizations} order_by

PARAGRAPH {
  SQLite attempts to use an index to satisfy the ORDER BY clause of a
................................................................................
  and the outer query (which is likely a join) will be forced to do a
  full table scan on the transient table.
}
PARAGRAPH {
  To overcome this problem, SQLite attempts to flatten subqueries in
  the FROM clause of a SELECT.
  This involves inserting the FROM clause of the subquery into the
  FROM clause of the outer query and rewriting certain expressions in
  the outer query.












  There is a long list of conditions that must be met in order for
  query flattening to occur.  These conditions are fully documented in
  source code comments in the select.c source file.


























}
PARAGRAPH {
  Query flattening is an important optimization when views are used as
  each use of a view is translated into a subquery.
}

HEADING 1 {The MIN/MAX optimization} minmax

PARAGRAPH {
  Queries of the following forms will be optimized to run in logorithmic
  time assuming appropriate indices exist:
}
CODE {
  SELECT MIN(x) FROM table;
  SELECT MAX(x) FROM table;
}
PARAGRAPH {
  In order for these optimizations to occur, they must appear in exactly
  the form shown above - changing only the name of the table and column.


  And the column in the MIN or MAX function must be an indexed column.
}



|







 







|







 







|







 







|
|
>
>
>
>
>
>
>
>
>
>
>
>
|
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>









|









>
>


1
2
3
4
5
6
7
8
9
10
11
..
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
...
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
...
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459

460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
#
# Run this TCL script to generate HTML for the goals.html file.
#
set rcsid {$Id: optoverview.tcl,v 1.2 2005/08/31 03:13:12 drh Exp $}
source common.tcl
header {The SQLite Query Optimizer Overview}

proc CODE {text} {
  puts "<blockquote><pre>"
  puts $text
  puts "</pre></blockquote>"
................................................................................
  puts "<h$n>$num $name</h$n>"
}

HEADING 0 {The SQLite Query Optimizer Overview}

PARAGRAPH {
  This document provides a terse overview of how the query optimizer
  for SQLite works.  This is not a tutorial.  Some prior knowledge of how
  database engines operate is likely needed in order to fully understand
  this text.
}

HEADING 1 {WHERE clause analysis} where_clause

PARAGRAPH {
................................................................................
  do a binary search on the index to find the index entry, then extract
  the rowid from the index and use that rowid to do a binary search on
  the original table.  Thus a typical indexed lookup involves two
  binary searches.
  If, however, all columns that were to be fetched from the table are
  already available in the index itself, SQLite will use the values
  contained in the index and will never look up the original table
  row.  This saves one binary search for each row and can make many
  queries run twice as fast.
}

HEADING 1 {ORDER BY optimizations} order_by

PARAGRAPH {
  SQLite attempts to use an index to satisfy the ORDER BY clause of a
................................................................................
  and the outer query (which is likely a join) will be forced to do a
  full table scan on the transient table.
}
PARAGRAPH {
  To overcome this problem, SQLite attempts to flatten subqueries in
  the FROM clause of a SELECT.
  This involves inserting the FROM clause of the subquery into the
  FROM clause of the outer query and rewriting expressions in
  the outer query that refer to the result set of the subquery.
  For example:
}
CODE {
  SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
}
PARAGRAPH {
  Would be rewritten using query flattening as:
}
CODE {
  SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
}
PARAGRAPH {
  There is a long list of conditions that must all be met in order for
  query flattening to occur.

}
PARAGRAPH {
  <ol>
  <li> The subquery and the outer query do not both use aggregates.</li>
  <li> The subquery is not an aggregate or the outer query is not a join. </li>
  <li> The subquery is not the right operand of a left outer join, or
          the subquery is not itself a join. </li>
  <li>  The subquery is not DISTINCT or the outer query is not a join. </li>
  <li>  The subquery is not DISTINCT or the outer query does not use
          aggregates. </li>
  <li>  The subquery does not use aggregates or the outer query is not
          DISTINCT. </li>
  <li>  The subquery has a FROM clause. </li>
  <li>  The subquery does not use LIMIT or the outer query is not a join. </li>
  <li>  The subquery does not use LIMIT or the outer query does not use
         aggregates. </li>
  <li>  The subquery does not use aggregates or the outer query does not
         use LIMIT. </li>
  <li>  The subquery and the outer query do not both have ORDER BY clauses.</li>
  <li>  The subquery is not the right term of a LEFT OUTER JOIN or the
         subquery has no WHERE clause.  </li>
  </ol>
}
PARAGRAPH {
  The proof that query flattening may safely occur if all of the the
  above conditions are met is left as an exercise to the reader.
}
PARAGRAPH {
  Query flattening is an important optimization when views are used as
  each use of a view is translated into a subquery.
}

HEADING 1 {The MIN/MAX optimization} minmax

PARAGRAPH {
  Queries of the following forms will be optimized to run in logarithmic
  time assuming appropriate indices exist:
}
CODE {
  SELECT MIN(x) FROM table;
  SELECT MAX(x) FROM table;
}
PARAGRAPH {
  In order for these optimizations to occur, they must appear in exactly
  the form shown above - changing only the name of the table and column.
  It is not permissible to add a WHERE clause or do any arithmetic on the
  result.  The result set must contain a single column.
  And the column in the MIN or MAX function must be an indexed column.
}