Documentation Source Text

Changes On Branch branch-3.8.0
Login

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

Changes In Branch branch-3.8.0 Excluding Merge-Ins

This is equivalent to a diff from 9747293881 to 46516308c7

2013-10-19
13:51
Merge the changes from the 3.8.0.x branch into trunk. (check-in: 2faf39e6c4 user: drh tags: trunk)
2013-10-01
01:01
Fix a typo on the release date for 3.8.0.2. (Closed-Leaf check-in: 46516308c7 user: drh tags: branch-3.8.0)
2013-09-30
12:14
Update the timeline link on the snapshot downloads so that it works if the previous release was on a branch. (check-in: aa3aec51de user: drh tags: branch-3.8.0)
2013-08-29
14:29
Preparations for the 3.8.0.1 patch release. (check-in: 8d74017a56 user: drh tags: branch-3.8.0)
2013-08-28
14:13
Add documentation for STAT4. (check-in: 04ab4fa5ec user: drh tags: trunk)
2013-08-27
13:34
Fix typos in the queryplanner-ng document. (check-in: 9747293881 user: drh tags: trunk)
2013-08-26
12:54
Version-3.8.0 (check-in: e672a5f4d8 user: drh tags: trunk, release, version-3.8.0)

Changes to pages/changes.in.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

46




47







48




49
50
51
52
53
54
55
http://www.sqlite.org/src/timeline</a> and
<a href="http://www.sqlite.org/src/timeline?t=release">
http://www.sqlite.org/src/timeline?t=release</a>
</p>

<tcl>
set nChng 0
proc chng {date desc} {
  global DEST nChng
  if {[regexp {\(([0-9.]+)\)} $date all vers]} {
    set label [string map {. _} $vers]
    hd_fragment version_$label
  }
  hd_puts "<h3>$date</h3>"
  hd_resolve "<p><ul>$desc</ul></p>"
  if {[regexp {\((3\.\d+\.[.0-9]+)[ a-zA-Z]*\)} $date all vers]} {
    set tag [string trim [string map {. _} $vers]]
    file mkdir $DEST/releaselog
    set filename releaselog/$tag.html
    hd_open_aux $filename
    hd_header "SQLite Release $vers On $date"
    hd_keywords "Version $vers" "*version $vers"
    hd_enable_main 0
    hd_puts "<h2>SQLite Release $vers On $date</h2>"
    regsub -all {<a href="(?!http:)} $desc {<a href="../} desc
    hd_resolve "<p><ul>$desc</ul></p>"
    hd_puts {
      <p>A <a href="../changes.html">complete list of SQLite releases</a>
      in a single page is also available.  A detailed history of every
      check-in is available at
      <a href="http://www.sqlite.org/src/timeline">
      http://www.sqlite.org/src/timeline</a>.</p>
    }
    hd_close_aux
    hd_enable_main 1
    incr nChng
    if {$nChng==1 && [file exists $DEST/$filename]} {
      file copy -force $DEST/$filename $DEST/releaselog/current.html

    }




  }







}





chng {2013-08-26 (3.8.0)} {
<li>Add support for [partial indexes]</li>
<li>Cut-over to the [next generation query planner] for faster and better query plans.
<li>The [EXPLAIN QUERY PLAN] output no longer shows an estimate of the number of 
    rows generated by each loop in a join.
<li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.







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







8
9
10
11
12
13
14
15
16
17
18

19



















20


21


22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
http://www.sqlite.org/src/timeline</a> and
<a href="http://www.sqlite.org/src/timeline?t=release">
http://www.sqlite.org/src/timeline?t=release</a>
</p>

<tcl>
set nChng 0
proc chng {date desc {options {}}} {
  global nChng aChng
  set aChng($nChng) [list $date $desc $options]
  incr nChng

}






















chng {2013-09-03 (3.8.0.2)} {


<li>Fix a bug in the optimization that attempts to omit unused LEFT JOINs

<li>SQLITE_SOURCE_ID: 
    "2013-09-03 17:11:13 7dd4968f235d6e1ca9547cda9cf3bd570e1609ef"
<li>SHA1 for sqlite3.c: 6cf0c7b46975a87a0dc3fba69c229a7de61b0c21
} {inadditionto 2 inadditionto 1}

chng {2013-08-29 (3.8.0.1)} {
<li>Fix an off-by-one error that caused quoted empty string at the end of a 
CRNL-terminated line of CSV input to be misread by the command-line shell.
<li>Fix a query planner bug involving a LEFT JOIN with a BETWEEN or LIKE/GLOB
constraint and then another INNER JOIN to the right that involves an OR constraint.
<li>Fix a query planner bug that could result in a segfault when querying tables
with a UNIQUE or PRIMARY KEY constraint with more than four columns.

<li>SQLITE_SOURCE_ID: 
    "2013-08-29 17:35:01 352362bc01660edfbda08179d60f09e2038a2f49"
<li>SHA1 for sqlite3.c: 99906bf63e6cef63d6f3d7f8526ac4a70e76559e
} {inadditionto 1}

chng {2013-08-26 (3.8.0)} {
<li>Add support for [partial indexes]</li>
<li>Cut-over to the [next generation query planner] for faster and better query plans.
<li>The [EXPLAIN QUERY PLAN] output no longer shows an estimate of the number of 
    rows generated by each loop in a join.
<li>Added the [FTS4 notindexed option], allowing non-indexed columns in an FTS4 table.
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
    to that same file.  See ticket 
    [http://www.sqlite.org/src/info/7ff3120e4f | 7ff3120e4f] for further
    information.

<li>SQLITE_SOURCE_ID: 
    "2013-04-12 11:52:43 cbea02d93865ce0e06789db95fd9168ebac970c7"
<li>SHA1 for sqlite3.c: d466b54789dff4fb0238b9232e74896deaefab94
}

chng {2013-03-29 (3.7.16.1)} {
<li>Fix for a bug in the ORDER BY optimizer that was introduced in
    [version 3.7.15] which would sometimes optimize out the sorting step
    when in fact the sort was required.
    Ticket [http://www.sqlite.org/src/info/a179fe7465 | a179fe7465]
<li>Fix a long-standing bug in the [CAST expression] that would recognize UTF16







|







183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
    to that same file.  See ticket 
    [http://www.sqlite.org/src/info/7ff3120e4f | 7ff3120e4f] for further
    information.

<li>SQLITE_SOURCE_ID: 
    "2013-04-12 11:52:43 cbea02d93865ce0e06789db95fd9168ebac970c7"
<li>SHA1 for sqlite3.c: d466b54789dff4fb0238b9232e74896deaefab94
} {inadditionto 2 inadditionto 1}

chng {2013-03-29 (3.7.16.1)} {
<li>Fix for a bug in the ORDER BY optimizer that was introduced in
    [version 3.7.15] which would sometimes optimize out the sorting step
    when in fact the sort was required.
    Ticket [http://www.sqlite.org/src/info/a179fe7465 | a179fe7465]
<li>Fix a long-standing bug in the [CAST expression] that would recognize UTF16
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
    Ticket [http://www.sqlite.org/src/info/6bfb98dfc0c | 6bfb98dfc0c].
<li>The SQLITE_OMIT_MERGE_SORT option has been removed.  The merge sorter is
    now a required component of SQLite.
<li>Fixed lots of spelling errors in the source-code comments
<li>SQLITE_SOURCE_ID: 
    "2013-03-29 13:44:34 527231bc67285f01fb18d4451b28f61da3c4e39d"
<li>SHA1 for sqlite3.c: 7a91ceceac9bcf47ceb8219126276e5518f7ff5a
}

chng {2013-03-18 (3.7.16)} {
<li>Added the [PRAGMA foreign_key_check] command.
<li>Added new extended error codes for all SQLITE_CONSTRAINT errors
<li>Added the SQLITE_READONLY_ROLLBACK extended error code for when a database
    cannot be opened because it needs rollback recovery but is read-only.
<li>Added SQL functions [unicode(A)] and [char(X1,...,XN)].







|







205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
    Ticket [http://www.sqlite.org/src/info/6bfb98dfc0c | 6bfb98dfc0c].
<li>The SQLITE_OMIT_MERGE_SORT option has been removed.  The merge sorter is
    now a required component of SQLite.
<li>Fixed lots of spelling errors in the source-code comments
<li>SQLITE_SOURCE_ID: 
    "2013-03-29 13:44:34 527231bc67285f01fb18d4451b28f61da3c4e39d"
<li>SHA1 for sqlite3.c: 7a91ceceac9bcf47ceb8219126276e5518f7ff5a
} {inadditionto 1}

chng {2013-03-18 (3.7.16)} {
<li>Added the [PRAGMA foreign_key_check] command.
<li>Added new extended error codes for all SQLITE_CONSTRAINT errors
<li>Added the SQLITE_READONLY_ROLLBACK extended error code for when a database
    cannot be opened because it needs rollback recovery but is read-only.
<li>Added SQL functions [unicode(A)] and [char(X1,...,XN)].
3163
3164
3165
3166
3167
3168
3169












































3170
3171
files.</li>
<li>And many, many bug fixes...</li>
}

chng {2000-05-29} {
<li>Initial Public Release of Alpha code</li>
}












































</tcl>
</dl>







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


3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
files.</li>
<li>And many, many bug fixes...</li>
}

chng {2000-05-29} {
<li>Initial Public Release of Alpha code</li>
}

# Generate the change log documents
#
for {set i 0} {$i<$nChng} {incr i} {
  foreach {date desc options} $aChng($i) break
  if {[regexp {\(([0-9.]+)\)} $date all vers]} {
    set label [string map {. _} $vers]
    hd_fragment version_$label
  }
  hd_puts "<h3>$date</h3>"
  hd_resolve "<p><ul>$desc</ul></p>"
  if {[regexp {\((3\.\d+\.[.0-9]+)[ a-zA-Z]*\)} $date all vers]} {
    set tag [string trim [string map {. _} $vers]]
    file mkdir $DEST/releaselog
    set filename releaselog/$tag.html
    hd_open_aux $filename
    hd_header "SQLite Release $vers On $date"
    hd_keywords "Version $vers" "*version $vers"
    hd_enable_main 0
    hd_puts "<h2>SQLite Release $vers On $date</h2>"
    regsub -all {<a href="(?!http:)} $desc {<a href="../} desc
    foreach {key value} $options {
      if {$key=="inadditionto"} {
        set d2 [lindex $aChng([expr {$i+$value}]) 1]
        regsub {<li>SQLITE_SOURCE_ID.*$} $d2 {} d2
        hd_resolve "<p><ul>$d2</ul></p>"
      }
    }
    hd_resolve "<p><ul>$desc</ul></p>"
    hd_puts {
      <p>A <a href="../changes.html">complete list of SQLite releases</a>
      in a single page is also available.  A detailed history of every
      check-in is available at
      <a href="http://www.sqlite.org/src/timeline">
      http://www.sqlite.org/src/timeline</a>.</p>
    }
    hd_close_aux
    hd_enable_main 1
    if {$nChng==0 && [file exists $DEST/$filename]} {
      file copy -force $DEST/$filename $DEST/releaselog/current.html
    }
  }
}

</tcl>
</dl>

Changes to pages/download.in.

65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
    if {$frag!=""} {
      eval hd_fragment $frag
      set frag {}
    }
    global href href_cnt
    incr href_cnt
    set href(a$href_cnt) $file
    hd_puts "<a id='a$href_cnt'>[file tail $file]</a><br>($size $units)</td>\n"
    hd_puts "<td width=\"5\"></td>"
    regsub -all VERSION $desc $version d2
    hd_puts "\n<td valign=\"top\">"
    hd_resolve [string trim $d2]
    hd_puts "<br>(sha1: $sha1sum)</td></tr>\n"
    incr ::nDownload
  }







|







65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
    if {$frag!=""} {
      eval hd_fragment $frag
      set frag {}
    }
    global href href_cnt
    incr href_cnt
    set href(a$href_cnt) $file
    hd_puts "<a id='a$href_cnt' href='hp1.html'>[file tail $file]</a><br>($size $units)</td>\n"
    hd_puts "<td width=\"5\"></td>"
    regsub -all VERSION $desc $version d2
    hd_puts "\n<td valign=\"top\">"
    hd_resolve [string trim $d2]
    hd_puts "<br>(sha1: $sha1sum)</td></tr>\n"
    incr ::nDownload
  }
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110


Product {snapshot/sqlite-amalgamation-DATE.zip} {
  This is a snapshot (as of VERSION) of the current SQLite source code under 
  development.
  See the <a href="http://www.sqlite.org/draft/releaselog/current.html">pending
  change log</a> or the
  <a href="http://www.sqlite.org/src/timeline?t=trunk&n=1000&a=release">timeline</a>
  for a summary of updates since the last release.
  This ZIP archive contains all preprocessed C code combined into a
  single source file (the [amalgamation]).
}
Product {snapshot/sqlite-amalgamation32k-DATE.zip} {
  This is a snapshot (as of VERSION) of the current SQLite source code under 
  development.







|







96
97
98
99
100
101
102
103
104
105
106
107
108
109
110


Product {snapshot/sqlite-amalgamation-DATE.zip} {
  This is a snapshot (as of VERSION) of the current SQLite source code under 
  development.
  See the <a href="http://www.sqlite.org/draft/releaselog/current.html">pending
  change log</a> or the
  <a href="http://www.sqlite.org/src/timeline?from=release&to=trunk">timeline</a>
  for a summary of updates since the last release.
  This ZIP archive contains all preprocessed C code combined into a
  single source file (the [amalgamation]).
}
Product {snapshot/sqlite-amalgamation32k-DATE.zip} {
  This is a snapshot (as of VERSION) of the current SQLite source code under 
  development.
263
264
265
266
267
268
269












270
271
272
273
274
275
276
}

Product YEAR/sqlite-winrt-VVV.vsix {
  A complete VSIX package with an extension SDK and all other components
  needed to use SQLite for WinRT application development with Visual Studio
  2012.
}













if {$nDownload>$start} {
  hd_puts {<tr><td colspan="4"><b>Precompiled Binaries for .NET</b></td></tr>}
  hd_puts "<tr><td width=\"10\"></td>"
  hd_puts "<td valign=\"top\" align=\"right\">"
  set url http://system.data.sqlite.org/index.html/doc/trunk/www/downloads.wiki
  hd_puts "<a href=\"$url\">System.Data.SQLite</a></td>"







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







263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
}

Product YEAR/sqlite-winrt-VVV.vsix {
  A complete VSIX package with an extension SDK and all other components
  needed to use SQLite for WinRT application development with Visual Studio
  2012.
}

Product YEAR/sqlite-winrt80-VVV.vsix {
  A complete VSIX package with an extension SDK and all other components
  needed to use SQLite for WinRT 8.0 application development with Visual Studio
  2012.
}

Product YEAR/sqlite-winrt81-VVV.vsix {
  A complete VSIX package with an extension SDK and all other components
  needed to use SQLite for WinRT 8.1 application development with Visual Studio
  2013.
}

if {$nDownload>$start} {
  hd_puts {<tr><td colspan="4"><b>Precompiled Binaries for .NET</b></td></tr>}
  hd_puts "<tr><td width=\"10\"></td>"
  hd_puts "<td valign=\"top\" align=\"right\">"
  set url http://system.data.sqlite.org/index.html/doc/trunk/www/downloads.wiki
  hd_puts "<a href=\"$url\">System.Data.SQLite</a></td>"

Changes to pages/fts3.in.

2060
2061
2062
2063
2064
2065
2066
















2067
2068
2069
2070
2071
2072
2073
  The "unicode61" tokenizer is available beginning with SQLite [version 3.7.13].
  Unicode61 works very much like "simple" except that it does full unicode
  case folding according to rules in Unicode Version 6.1 and it recognizes
  unicode space and punctuation characters and uses those to separate tokens.
  The simple tokenizer only does case folding of ASCII characters and only
  recognizes ASCII space and punctuation characters as token separators.

















<h2>Custom (User Implemented) Tokenizers</h2>

<p>
  As well as the built-in "simple", "porter" and (possibly) "icu" and
  "unicode61" tokenizers,
  FTS exports an interface that allows users to implement custom tokenizers
  using C. The interface used to create a new tokenizer is defined and 







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







2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
  The "unicode61" tokenizer is available beginning with SQLite [version 3.7.13].
  Unicode61 works very much like "simple" except that it does full unicode
  case folding according to rules in Unicode Version 6.1 and it recognizes
  unicode space and punctuation characters and uses those to separate tokens.
  The simple tokenizer only does case folding of ASCII characters and only
  recognizes ASCII space and punctuation characters as token separators.

<p>
  By default, "unicode61" also removes all diacritics from Latin script
  characters. This behaviour can be overriden by adding the tokenizer argument
  "remove_diacritics=0". For example:

<codeblock>
    <i>-- Create tables that remove diacritics from Latin script characters</i>
    <i>-- as part of tokenization.</i>
    CREATE VIRTUAL TABLE txt1 USING fts4(tokenize=unicode61);
    CREATE VIRTUAL TABLE txt2 USING fts4(tokenize=unicode61 "remove_diacritics=1");

    <i>-- Create a tables that does not remove diacritics from Latin script</i>
    <i>-- characters as part of tokenization.</i>
    CREATE VIRTUAL TABLE txt3 USING fts4(tokenize=unicode61 "remove_diacritics=0");
</codeblock>

<h2>Custom (User Implemented) Tokenizers</h2>

<p>
  As well as the built-in "simple", "porter" and (possibly) "icu" and
  "unicode61" tokenizers,
  FTS exports an interface that allows users to implement custom tokenizers
  using C. The interface used to create a new tokenizer is defined and 

Added pages/hp1.in.











>
>
>
>
>
1
2
3
4
5
<title>Javascript Required</title>

<b>Note:</b>
The hyperlinks on the download page only work if you have Javascript
enabled in your web browser.

Changes to pages/index.in.

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

</td>
<td width="20"></td><td bgcolor="#044a64" width="1"></td><td width="20"></td>
<td valign="top">
<h3>Current Status</h3>

<p><ul>
<li><a href="releaselog/3_8_0.html">Version 3.8.0</a>
of SQLite is recommended for all new development.
Upgrading from version 3.7.17 is optional.
Upgrading from all other prior versions of SQLite
is recommended.</li>
</ul></p>

<h3>Common Links</h3>

<p><ul>







|

|







91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

</td>
<td width="20"></td><td bgcolor="#044a64" width="1"></td><td width="20"></td>
<td valign="top">
<h3>Current Status</h3>

<p><ul>
<li><a href="releaselog/3_8_0_2.html">Version 3.8.0.2</a>
of SQLite is recommended for all new development.
Upgrading from version 3.7.17, 3.8.0, and 3.8.0.1 is optional.
Upgrading from all other prior versions of SQLite
is recommended.</li>
</ul></p>

<h3>Common Links</h3>

<p><ul>

Changes to pages/news.in.

14
15
16
17
18
19
20










21
22
23
24
25
26
27
  hd_puts "<h3>$date - $title</h3>"
  regsub -all "\n( *\n)+" $text "</p>\n\n<p>" txt
  regsub -all {[Tt]icket #(\d+)} $txt \
      {<a href="http://www.sqlite.org/cvstrac/tktview?tn=\1">\0</a>} txt
  hd_resolve "<blockquote>$txt</blockquote>"
  hd_puts "<hr width=\"50%\">"
}











newsitem {2013-08-26} {Release 3.8.0} {
  <b>Do not fear the zero!</b>

  <p>SQLite [version 3.8.0] might easily have been called "3.7.18" instead.
  However, this release features the cutover of the
  [next generation query planner] or [NGQP], and there is a small chance of







>
>
>
>
>
>
>
>
>
>







14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
  hd_puts "<h3>$date - $title</h3>"
  regsub -all "\n( *\n)+" $text "</p>\n\n<p>" txt
  regsub -all {[Tt]icket #(\d+)} $txt \
      {<a href="http://www.sqlite.org/cvstrac/tktview?tn=\1">\0</a>} txt
  hd_resolve "<blockquote>$txt</blockquote>"
  hd_puts "<hr width=\"50%\">"
}

newsitem {2013-09-03} {Release 3.8.0.2} {
  <p>SQLite [version 3.8.0.2] contains a one-line fix to a bug in the
  new optimization that tries to omit unused LEFT JOINs from a query.
}

newsitem {2013-08-29} {Release 3.8.0.1} {
  <p>SQLite [version 3.8.0.1] fixes some obscure bugs that were uncovered by
  users in the 3.8.0 release.  Changes from 3.8.0 are minimal.
}

newsitem {2013-08-26} {Release 3.8.0} {
  <b>Do not fear the zero!</b>

  <p>SQLite [version 3.8.0] might easily have been called "3.7.18" instead.
  However, this release features the cutover of the
  [next generation query planner] or [NGQP], and there is a small chance of

Changes to pages/queryplanner-ng.in.

201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
nodes in the graph.</p>

<p>The problem of finding the best query plan is equivalent to finding
a minimum-cost path through the graph that visits each node
exactly once.</p>

<p>(Side note:  The costs estimates in the TPC-H Q8 graph were computed
by the query planner in SQLite 3.7.16 and converted using a base-10 logarithm.)
</p>

<h3>3.2 Complications</h3>

<p>The presentation of the query planner problem above is a simplification.
The costs are estimates.  We cannot
know what the true cost of running a loop is until we actually run the loop.







|







201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
nodes in the graph.</p>

<p>The problem of finding the best query plan is equivalent to finding
a minimum-cost path through the graph that visits each node
exactly once.</p>

<p>(Side note:  The costs estimates in the TPC-H Q8 graph were computed
by the query planner in SQLite 3.7.16 and converted using a natural logarithm.)
</p>

<h3>3.2 Complications</h3>

<p>The presentation of the query planner problem above is a simplification.
The costs are estimates.  We cannot
know what the true cost of running a loop is until we actually run the loop.
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
GROUP BY, or DISTINCT clause. So for TPC-H Q8,
the graph above is a reasonable representation of what needs to be computed.
The general case involves a lot of extra complication, which for clarity
is neglected in the remainder of this article.</p>

<h3>3.3 Finding The Best Query Plan</h3>

<p>Prior to version 3.8.0, SQLite always used the
the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
The NN heuristic makes a single traversal of the graph, always choosing
the lowest-cost arc as the next step.  
The NN heuristic works surprisingly well in most cases.
And NN is fast, so that SQLite is able to quickly find good plans
for even large 64-way joins.  In contrast, other SQL database engines that
do more extensive searching tend to bog down when the
number of tables in a join goes above 10 or 15.</p>

<p>Unfortunately, the query plan computed by NN for TPC-H Q8 is not optimal.
The plan computed using NN is R-N1-N2-S-C-O-L-P with a cost of 36.92.  
The notation
in the previous sentence means that the R table is run in the outer loop,
N1 is in the next inner loop, N2 is in the third loop, and so forth down
to P which is in the inner-most loop.  The shortest path through the
graph (as found via exhaustive search) is  P-L-O-C-N1-R-S-N2
with a cost of 27.38.  The difference might not seem like much, but 
remember that
the costs are logarithmic, so the shortest path is nearly 14,000 times
faster than that path found using the NN heuristic.</p>

<p>One solution to this problem is to change SQLite to do an exhaustive
search for the best path.  But an exhaustive search requires time 
proportional to
K! (where K is the number of tables in the join) and so when you get 
beyond a 10-way join, the time







|


















|







253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
GROUP BY, or DISTINCT clause. So for TPC-H Q8,
the graph above is a reasonable representation of what needs to be computed.
The general case involves a lot of extra complication, which for clarity
is neglected in the remainder of this article.</p>

<h3>3.3 Finding The Best Query Plan</h3>

<p>Prior to version 3.8.0, SQLite always used
the "Nearest Neighbor" or "NN" heuristic when searching for the best query plan.
The NN heuristic makes a single traversal of the graph, always choosing
the lowest-cost arc as the next step.  
The NN heuristic works surprisingly well in most cases.
And NN is fast, so that SQLite is able to quickly find good plans
for even large 64-way joins.  In contrast, other SQL database engines that
do more extensive searching tend to bog down when the
number of tables in a join goes above 10 or 15.</p>

<p>Unfortunately, the query plan computed by NN for TPC-H Q8 is not optimal.
The plan computed using NN is R-N1-N2-S-C-O-L-P with a cost of 36.92.  
The notation
in the previous sentence means that the R table is run in the outer loop,
N1 is in the next inner loop, N2 is in the third loop, and so forth down
to P which is in the inner-most loop.  The shortest path through the
graph (as found via exhaustive search) is  P-L-O-C-N1-R-S-N2
with a cost of 27.38.  The difference might not seem like much, but 
remember that
the costs are logarithmic, so the shortest path is nearly 750 times
faster than that path found using the NN heuristic.</p>

<p>One solution to this problem is to change SQLite to do an exhaustive
search for the best path.  But an exhaustive search requires time 
proportional to
K! (where K is the number of tables in the join) and so when you get 
beyond a 10-way join, the time
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
<center>
<img src="images/qp/fqp1.gif">
</center>

<p>
In the "without ANALYZE" case on the left, the NN algorithm chooses 
loop P (PLINK) as the outer loop because 4.9 is less than 5.2, resulting
in path P-T which is algorithm-1. NN only looks a the single best choice
at each step so it completely misses the fact that 
5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the N3 algorithm
keeps track of the 5 best paths for a 2-way join, so it ends up
selecting path T-P because of its slightly lower overall cost.
Path T-P is algorithm-2.
</p>








|







560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
<center>
<img src="images/qp/fqp1.gif">
</center>

<p>
In the "without ANALYZE" case on the left, the NN algorithm chooses 
loop P (PLINK) as the outer loop because 4.9 is less than 5.2, resulting
in path P-T which is algorithm-1. NN only looks at the single best choice
at each step so it completely misses the fact that 
5.2+4.4 makes a slightly cheaper plan than 4.9+4.8. But the N3 algorithm
keeps track of the 5 best paths for a 2-way join, so it ends up
selecting path T-P because of its slightly lower overall cost.
Path T-P is algorithm-2.
</p>

586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
in the TPC-H Q8 graph.)</p>

<h3>4.2 Fixing The Problem</h3>

<p>Running [ANALYZE] on the repository database immediately fixed the
performance problem.  However, we want Fossil to be robust and to always
work quickly regardless of whether or not its repository has been analyzed.
For this reason, the query was modify to use the CROSS JOIN operator 
instead of the plain JOIN operator.
SQLite will not reorder the tables of a CROSS JOIN.
This is a long-standing feature of SQLite that is specifically designed
to allow knowledgeable programmers
to enforce a particular loop nesting order.  Once the join
was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
forced to chose the faster algorithm-1 regardless of whether or not







|







586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
in the TPC-H Q8 graph.)</p>

<h3>4.2 Fixing The Problem</h3>

<p>Running [ANALYZE] on the repository database immediately fixed the
performance problem.  However, we want Fossil to be robust and to always
work quickly regardless of whether or not its repository has been analyzed.
For this reason, the query was modified to use the CROSS JOIN operator 
instead of the plain JOIN operator.
SQLite will not reorder the tables of a CROSS JOIN.
This is a long-standing feature of SQLite that is specifically designed
to allow knowledgeable programmers
to enforce a particular loop nesting order.  Once the join
was changed to CROSS JOIN (the addition of a single keyword) the NGQP was
forced to chose the faster algorithm-1 regardless of whether or not