Debian Codegraph @

www/optoverview.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>The SQLite Query Optimizer Overview</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 The SQLite Query Optimizer Overview
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#introduction">1. Introduction</a></div>
126 <div class="fancy-toc1"><a href="#where_clause_analysis">2. WHERE Clause Analysis</a></div>
127 <div class="fancy-toc2"><a href="#index_term_usage_examples">2.1. Index Term Usage Examples</a></div>
128 <div class="fancy-toc1"><a href="#the_between_optimization">3. The BETWEEN Optimization</a></div>
129 <div class="fancy-toc1"><a href="#or_optimizations">4. OR Optimizations</a></div>
130 <div class="fancy-toc2"><a href="#converting_or_connected_constraint_into_an_in_operator">4.1. Converting OR-connected constraint into an IN operator</a></div>
131 <div class="fancy-toc2"><a href="#evaluating_or_constraints_separately_and_taking_the_union_of_the_result">4.2. Evaluating OR constraints separately and taking the UNION of the result</a></div>
132 <div class="fancy-toc1"><a href="#the_like_optimization">5. The LIKE Optimization</a></div>
133 <div class="fancy-toc1"><a href="#the_skip_scan_optimization">6. The Skip-Scan Optimization</a></div>
134 <div class="fancy-toc1"><a href="#joins">7. Joins</a></div>
135 <div class="fancy-toc2"><a href="#manual_control_of_join_order">7.1. Manual Control Of Join Order</a></div>
136 <div class="fancy-toc3"><a href="#manual_control_of_query_plans_using_sqlite_stat_tables">7.1.1. Manual Control Of Query Plans Using SQLITE_STAT Tables</a></div>
137 <div class="fancy-toc3"><a href="#manual_control_of_query_plans_using_cross_join">7.1.2. Manual Control of Query Plans using CROSS JOIN</a></div>
138 <div class="fancy-toc1"><a href="#choosing_between_multiple_indexes">8. Choosing Between Multiple Indexes</a></div>
139 <div class="fancy-toc2"><a href="#disqualifying_where_clause_terms_using_unary_">8.1. Disqualifying WHERE Clause Terms using Unary-"+"</a></div>
140 <div class="fancy-toc2"><a href="#range_queries">8.2. Range Queries</a></div>
141 <div class="fancy-toc1"><a href="#covering_indexes">9. Covering Indexes</a></div>
142 <div class="fancy-toc1"><a href="#order_by_optimizations">10. ORDER BY Optimizations</a></div>
143 <div class="fancy-toc2"><a href="#partial_order_by_via_index">10.1. Partial ORDER BY via Index</a></div>
144 <div class="fancy-toc1"><a href="#subquery_flattening">11. Subquery Flattening</a></div>
145 <div class="fancy-toc1"><a href="#subquery_co_routines">12. Subquery Co-routines</a></div>
146 <div class="fancy-toc2"><a href="#using_co_routines_to_defer_work_until_after_the_sorting">12.1. Using Co-routines to Defer Work until after the Sorting</a></div>
147 <div class="fancy-toc1"><a href="#the_min_max_optimization">13. The MIN/MAX Optimization</a></div>
148 <div class="fancy-toc1"><a href="#automatic_query_time_indexes">14. Automatic Query-Time Indexes</a></div>
149 <div class="fancy-toc2"><a href="#hash_joins">14.1. Hash Joins</a></div>
150 <div class="fancy-toc1"><a href="#the_predicate_push_down_optimization">15. The Predicate Push-Down Optimization</a></div>
151 <div class="fancy-toc1"><a href="#the_outer_join_strength_reduction_optimization">16. The OUTER JOIN Strength Reduction Optimization</a></div>
152 <div class="fancy-toc1"><a href="#the_omit_outer_join_optimization">17. The Omit OUTER JOIN Optimization</a></div>
153 <div class="fancy-toc1"><a href="#the_constant_propagation_optimization">18. The Constant Propagation Optimization</a></div>
154 </div>
155 </details>
156 </div>
157
158
159
160
161
162 <h1 id="introduction"><span>1. </span>Introduction</h1>
163 <p>
164 This document provides an overview of how the query planner and optimizer
165 for SQLite works.
166
167
168 </p><p>
169 Given a single SQL statement, there might be dozens, hundreds, or even
170 thousands of ways to implement that statement, depending on the complexity
171 of the statement itself and of the underlying database schema. The
172 task of the query planner is to select the algorithm that minimizes
173 disk I/O and CPU overhead.
174
175
176 </p><p>
177 Additional background information is available in the
178 <a href="queryplanner.html">indexing tutorial</a> document.
179 The <a href="queryplanner-ng.html">Next Generation Query Planner</a> document provides more detail on
180 how the <a href="optoverview.html#joins">join order</a> is chosen.
181
182
183
184 <a name="where_clause"></a>
185
186 </p><h1 id="where_clause_analysis"><span>2. </span>WHERE Clause Analysis</h1>
187
188 <p>
189 Prior to analysis, the following transformations are made
190 to shift all join constraints into the WHERE clause:
191
192 </p><p>
193 </p><ul>
194 <li>All NATURAL joins are converted into joins with a USING clause.
195 </li><li>All USING clauses (including ones created by the previous step)
196 are converted into equivalent ON clauses.
197 </li><li>All ON clauses (include ones created by the previous step)
198 are added as new conjuncts (AND-connected terms) in the WHERE clause.
199 </li></ul>
200
201
202 <p>
203 SQLite makes no distinction between join constraints that occur in the
204 WHERE clause and constraints in the ON clause of an inner join, since that
205 distinction does not affect the outcome. However, there is
206 a difference between ON clause constraints and WHERE clause constraints for
207 outer joins. Therefore, when SQLite moves an ON clause constraint from an
208 outer join over to the WHERE clause it adds special tags to the Abstract
209 Syntax Tree (AST) to indicate that the constraint came from an outer join
210 and from which outer join it came. There is no way to add those tags in
211 pure SQL text. Hence, the SQL input must use ON clauses on outer joins.
212 But in the internal AST, all constraints are part of the WHERE clause,
213 because having everything in one place simplifies processing.
214
215 </p><p>
216 After all constraints have been shifted into the WHERE clause,
217 The WHERE clause is broken up into conjuncts (hereafter called
218 "terms"). In other words, the WHERE clause is broken up into pieces
219 separated from the others by an AND operator.
220 If the WHERE clause is composed of constraints separated by the OR
221 operator (disjuncts) then the entire clause is considered to be a single "term"
222 to which the <a href="#or_opt">OR-clause optimization</a> is applied.
223
224 </p><p>
225 All terms of the WHERE clause are analyzed to see if they can be
226 satisfied using indexes.
227 To be usable by an index a term must usually be of one of the following
228 forms:
229
230 <blockquote><pre><b>
231 </b><i>column</i><b> = </b><i>expression</i><b>
232 </b><i>column</i><b> IS </b><i>expression</i><b>
233 </b><i>column</i><b> &gt; </b><i>expression</i><b>
234 </b><i>column</i><b> &gt;= </b><i>expression</i><b>
235 </b><i>column</i><b> &lt; </b><i>expression</i><b>
236 </b><i>column</i><b> &lt;= </b><i>expression</i><b>
237 </b><i>expression</i><b> = </b><i>column</i><b>
238 </b><i>expression</i><b> IS </b><i>column</i><b>
239 </b><i>expression</i><b> &gt; </b><i>column</i><b>
240 </b><i>expression</i><b> &gt;= </b><i>column</i><b>
241 </b><i>expression</i><b> &lt; </b><i>column</i><b>
242 </b><i>expression</i><b> &lt;= </b><i>column</i><b>
243 </b><i>column</i><b> IN (</b><i>expression-list</i><b>)
244 </b><i>column</i><b> IN (</b><i>subquery</i><b>)
245 </b><i>column</i><b> IS NULL
246 </b><i>column</i><b> LIKE </b><i>pattern</i><b>
247 </b><i>column</i><b> GLOB </b><i>pattern</i><b>
248 </b></pre></blockquote>
249
250 </p><p>
251 If an index is created using a statement like this:
252
253 </p><div class="codeblock"><pre>CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);
254 </pre></div>
255
256 <p>
257 Then the index might be used if the initial columns of the index
258 (columns a, b, and so forth) appear in WHERE clause terms.
259 The initial columns of the index must be used with
260 the <b>=</b> or <b>IN</b> or <b>IS</b> operators.
261 The right-most column that is used can employ inequalities.
262 For the right-most
263 column of an index that is used, there can be up to two inequalities
264 that must sandwich the allowed values of the column between two extremes.
265
266 </p><p>
267 It is not necessary for every column of an index to appear in a
268 WHERE clause term in order for that index to be used.
269 However, there cannot be gaps in the columns of the index that are used.
270 Thus for the example index above, if there is no WHERE clause term
271 that constrains column c, then terms that constrain columns a and b can
272 be used with the index but not terms that constrain columns d through z.
273 Similarly, index columns will not normally be used (for indexing purposes)
274 if they are to the right of a
275 column that is constrained only by inequalities.
276 (See the <a href="optoverview.html#skipscan">skip-scan optimization</a> below for the exception.)
277
278 </p><p>
279 In the case of <a href="expridx.html">indexes on expressions</a>, whenever the word "column" is
280 used in the foregoing text, one can substitute "indexed expression"
281 (meaning a copy of the expression that appears in the <a href="lang_createindex.html">CREATE INDEX</a>
282 statement) and everything will work the same.
283
284
285 <a name="idxexamp"></a>
286
287 </p><h2 id="index_term_usage_examples"><span>2.1. </span>Index Term Usage Examples</h2>
288 <p>
289 For the index above and WHERE clause like this:
290
291 </p><div class="codeblock"><pre>... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
292 </pre></div>
293 <p>
294 The first four columns a, b, c, and d of the index would be usable since
295 those four columns form a prefix of the index and are all bound by
296 equality constraints.
297
298 </p><p>
299 For the index above and WHERE clause like this:
300
301 </p><div class="codeblock"><pre>... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'
302 </pre></div>
303 <p>
304 Only columns a, b, and c of the index would be usable. The d column
305 would not be usable because it occurs to the right of c and c is
306 constrained only by inequalities.
307
308 </p><p>
309 For the index above and WHERE clause like this:
310
311 </p><div class="codeblock"><pre>... WHERE a=5 AND b IN (1,2,3) AND d='hello'
312 </pre></div>
313 <p>
314 Only columns a and b of the index would be usable. The d column
315 would not be usable because column c is not constrained and there can
316 be no gaps in the set of columns that usable by the index.
317
318 </p><p>
319 For the index above and WHERE clause like this:
320
321 </p><div class="codeblock"><pre>... WHERE b IN (1,2,3) AND c NOT NULL AND d='hello'
322 </pre></div>
323 <p>
324 The index is not usable at all because the left-most column of the
325 index (column "a") is not constrained. Assuming there are no other
326 indexes, the query above would result in a full table scan.
327
328 </p><p>
329 For the index above and WHERE clause like this:
330
331 </p><div class="codeblock"><pre>... WHERE a=5 OR b IN (1,2,3) OR c NOT NULL OR d='hello'
332 </pre></div>
333 <p>
334 The index is not usable because the WHERE clause terms are connected
335 by OR instead of AND. This query would result in a full table scan.
336 However, if three additional indexes are added that contain columns
337 b, c, and d as their left-most columns, then the
338 <a href="#or_opt">OR-clause optimization</a> might apply.
339
340
341 <a name="between_opt"></a>
342
343 </p><h1 id="the_between_optimization"><span>3. </span>The BETWEEN Optimization</h1>
344
345 <p>
346 If a term of the WHERE clause is of the following form:
347
348 <blockquote><pre><b>
349 </b><i>expr1</i><b> BETWEEN </b><i>expr2</i><b> AND </b><i>expr3</i><b>
350 </b></pre></blockquote>
351 </p><p>
352 Then two "virtual" terms are added as follows:
353
354 <blockquote><pre><b>
355 </b><i>expr1</i><b> &gt;= </b><i>expr2</i><b> AND </b><i>expr1</i><b> &lt;= </b><i>expr3</i><b>
356 </b></pre></blockquote>
357 </p><p>
358 Virtual terms are used for analysis only and do not cause any byte-code
359 to be generated.
360 If both virtual terms end up being used as constraints on an index,
361 then the original BETWEEN term is omitted and the corresponding test
362 is not performed on input rows.
363 Thus if the BETWEEN term ends up being used as an index constraint
364 no tests are ever performed on that term.
365 On the other hand, the
366 virtual terms themselves never causes tests to be performed on
367 input rows.
368 Thus if the BETWEEN term is not used as an index constraint and
369 instead must be used to test input rows, the <i>expr1</i> expression is
370 only evaluated once.
371
372 <a name="or_opt"></a>
373
374 </p><h1 id="or_optimizations"><span>4. </span>OR Optimizations</h1>
375
376 <p>
377 WHERE clause constraints that are connected by OR instead of AND can
378 be handled in two different ways.
379
380 </p><h2 id="converting_or_connected_constraint_into_an_in_operator"><span>4.1. </span>Converting OR-connected constraint into an IN operator</h2>
381
382 <p>
383 If a term consists of multiple subterms containing a common column
384 name and separated by OR, like this:
385
386 <blockquote><pre><b>
387 </b><i>column</i><b> = </b><i>expr1</i><b> OR </b><i>column</i><b> = </b><i>expr2</i><b> OR </b><i>column</i><b> = </b><i>expr3</i><b> OR ...
388 </b></pre></blockquote>
389 </p><p>
390 Then that term is rewritten as follows:
391
392 <blockquote><pre><b>
393 </b><i>column</i><b> IN (</b><i>expr1</i><b>,</b><i>expr2</i><b>,</b><i>expr3</i><b>,...)
394 </b></pre></blockquote>
395 </p><p>
396 The rewritten term then might go on to constrain an index using the
397 normal rules for <b>IN</b> operators. Note that <i>column</i> must be
398 the same column in every OR-connected subterm,
399 although the column can occur on either the left or the right side of
400 the <b>=</b> operator.
401
402 </p><h2 id="evaluating_or_constraints_separately_and_taking_the_union_of_the_result"><span>4.2. </span>Evaluating OR constraints separately and taking the UNION of the result</h2>
403
404 <p>
405 If and only if the previously described conversion of OR to an IN operator
406 does not work, the second OR-clause optimization is attempted.
407 Suppose the OR clause consists of multiple subterms as follows:
408
409 <blockquote><pre><b>
410 </b><i>expr1</i><b> OR </b><i>expr2</i><b> OR </b><i>expr3</i><b>
411 </b></pre></blockquote>
412 </p><p>
413 Individual subterms might be a single comparison expression like
414 <b>a=5</b> or <b>x&gt;y</b> or they can be
415 LIKE or BETWEEN expressions, or a subterm
416 can be a parenthesized list of AND-connected sub-subterms.
417 Each subterm is analyzed as if it were itself the entire WHERE clause
418 in order to see if the subterm is indexable by itself.
419 If <u>every</u> subterm of an OR clause is separately indexable
420 then the OR clause might be coded such that a separate index is used
421 to evaluate each term of the OR clause. One way to think about how
422 SQLite uses separate indexes for each OR clause term is to imagine
423 that the WHERE clause where rewritten as follows:
424
425 <blockquote><pre><b>
426 rowid IN (SELECT rowid FROM </b><i>table</i><b> WHERE </b><i>expr1</i><b>
427 UNION SELECT rowid FROM </b><i>table</i><b> WHERE </b><i>expr2</i><b>
428 UNION SELECT rowid FROM </b><i>table</i><b> WHERE </b><i>expr3</i><b>)
429 </b></pre></blockquote>
430 </p><p>
431 The rewritten expression above is conceptual; WHERE clauses containing
432 OR are not really rewritten this way.
433 The actual implementation of the OR clause uses a mechanism that is
434 more efficient and that works even for <a href="withoutrowid.html">WITHOUT ROWID</a> tables or
435 tables in which the "rowid" is inaccessible. Nevertheless,
436 the essence of the implementation is captured by the statement
437 above: Separate indexes are used to find candidate result rows
438 from each OR clause term and the final result is the union of
439 those rows.
440
441 </p><p>
442 Note that in most cases, SQLite will only use a single index for each
443 table in the FROM clause of a query. The second OR-clause optimization
444 described here is the exception to that rule. With an OR-clause,
445 a different index might be used for each subterm in the OR-clause.
446
447 </p><p>
448 For any given query, the fact that the OR-clause optimization described
449 here can be used does not guarantee that it will be used.
450 SQLite uses a cost-based query planner that estimates the CPU and
451 disk I/O costs of various competing query plans and chooses the plan
452 that it thinks will be the fastest. If there are many OR terms in
453 the WHERE clause or if some of the indexes on individual OR-clause
454 subterms are not very selective, then SQLite might decide that it is
455 faster to use a different query algorithm, or even a full-table scan.
456 Application developers can use the
457 <a href="lang_explain.html">EXPLAIN QUERY PLAN</a> prefix on a statement to get a
458 high-level overview of the chosen query strategy.
459
460 <a name="like_opt"></a>
461
462 </p><h1 id="the_like_optimization"><span>5. </span>The LIKE Optimization</h1>
463
464 <p>
465 A WHERE-clause term that uses the <a href="lang_expr.html#like">LIKE</a> or <a href="lang_expr.html#glob">GLOB</a> operator
466 can sometimes be used with an index to do a range search,
467 almost as if the LIKE or GLOB were an alternative to a <a href="lang_expr.html#between">BETWEEN</a>
468 operator.
469 There are many conditions on this optimization:
470
471 </p><p>
472 </p><ol>
473 <li>The right-hand side of the LIKE or GLOB must be either a string literal
474 or a <a href="lang_expr.html#varparam">parameter</a> bound to a string literal
475 that does not begin with a wildcard character.</li>
476 <li>It must not be possible to make the LIKE or GLOB operator true by
477 having a numeric value (instead of a string or blob) on the
478 left-hand side. This means that either:
479 <ol type="A">
480 <li> the left-hand side of the LIKE or GLOB operator is the name
481 of an indexed column with <a href="datatype3.html#affinity">TEXT affinity</a>, or</li>
482 <li> the right-hand side pattern argument does not begin with a
483 minus sign ("-") or a digit.</li>
484 </ol>
485 This constraint arises from the fact that numbers do not sort in
486 lexicographical order. For example: 9&lt;10 but '9'&gt;'10'.</li>
487 <li>The built-in functions used to implement LIKE and GLOB must not
488 have been overloaded using the <a href="c3ref/create_function.html">sqlite3_create_function()</a> API.</li>
489 <li>For the GLOB operator, the column must be indexed using the
490 built-in BINARY collating sequence.</li>
491 <li>For the LIKE operator, if <a href="pragma.html#pragma_case_sensitive_like">case_sensitive_like</a> mode is enabled then
492 the column must be indexed using the built-in BINARY collating sequence,
493 or if <a href="pragma.html#pragma_case_sensitive_like">case_sensitive_like</a> mode is disabled then the column must be
494 indexed using the built-in NOCASE collating sequence.</li>
495 <li>If the ESCAPE option is used, the ESCAPE character must be ASCII,
496 or a single-byte character in UTF-8.
497 </li></ol>
498
499 <p>
500 The LIKE operator has two modes that can be set by a
501 <a href="pragma.html#pragma_case_sensitive_like">pragma</a>. The
502 default mode is for LIKE comparisons to be insensitive to differences
503 of case for latin1 characters. Thus, by default, the following
504 expression is true:
505
506 </p><div class="codeblock"><pre>'a' LIKE 'A'
507 </pre></div>
508 <p>
509 If the case_sensitive_like pragma is enabled as follows:
510
511 </p><div class="codeblock"><pre>PRAGMA case_sensitive_like=ON;
512 </pre></div>
513 <p>
514 Then the LIKE operator pays attention to case and the example above would
515 evaluate to false. Note that case insensitivity only applies to
516 latin1 characters - basically the upper and lower case letters of English
517 in the lower 127 byte codes of ASCII. International character sets
518 are case sensitive in SQLite unless an application-defined
519 <a href="datatype3.html#collation">collating sequence</a> and <a href="lang_corefunc.html#like">like() SQL function</a> are provided that
520 take non-ASCII characters into account.
521 If an application-defined collating sequence and/or like() SQL
522 function are provided, the LIKE optimization described here will never
523 be taken.
524
525 </p><p>
526 The LIKE operator is case insensitive by default because this is what
527 the SQL standard requires. You can change the default behavior at
528 compile time by using the <a href="compile.html#case_sensitive_like">SQLITE_CASE_SENSITIVE_LIKE</a> command-line option
529 to the compiler.
530
531 </p><p>
532 The LIKE optimization might occur if the column named on the left of the
533 operator is indexed using the built-in BINARY collating sequence and
534 case_sensitive_like is turned on. Or the optimization might occur if
535 the column is indexed using the built-in NOCASE collating sequence and the
536 case_sensitive_like mode is off. These are the only two combinations
537 under which LIKE operators will be optimized.
538
539 </p><p>
540 The GLOB operator is always case sensitive. The column on the left side
541 of the GLOB operator must always use the built-in BINARY collating sequence
542 or no attempt will be made to optimize that operator with indexes.
543
544 </p><p>
545 The LIKE optimization will only be attempted if
546 the right-hand side of the GLOB or LIKE operator is either a
547 literal string or a <a href="lang_expr.html#varparam">parameter</a> that has been <a href="c3ref/bind_blob.html">bound</a>
548 to a string literal. The string literal must not
549 begin with a wildcard; if the right-hand side begins with a wildcard
550 character then this optimization is not attempted. If the right-hand side
551 is a <a href="lang_expr.html#varparam">parameter</a> that is bound to a string, then this optimization is
552 only attempted if the <a href="c3ref/stmt.html">prepared statement</a> containing the expression
553 was compiled with <a href="c3ref/prepare.html">sqlite3_prepare_v2()</a> or <a href="c3ref/prepare.html">sqlite3_prepare16_v2()</a>.
554 The LIKE optimization is not attempted if the
555 right-hand side is a <a href="lang_expr.html#varparam">parameter</a> and the statement was prepared using
556 <a href="c3ref/prepare.html">sqlite3_prepare()</a> or <a href="c3ref/prepare.html">sqlite3_prepare16()</a>.
557
558 </p><p>
559 Suppose the initial sequence of non-wildcard characters on the right-hand
560 side of the LIKE or GLOB operator is <i>x</i>. We are using a single
561 character to denote this non-wildcard prefix but the reader should
562 understand that the prefix can consist of more than 1 character.
563 Let <i>y</i> be the smallest string that is the same length as /x/ but which
564 compares greater than <i>x</i>. For example, if <i>x</i> is
565 <tt>'hello'</tt> then
566 <i>y</i> would be <tt>'hellp'</tt>.
567 The LIKE and GLOB optimizations consist of adding two virtual terms
568 like this:
569
570 <blockquote><pre><b>
571 </b><i>column</i><b> &gt;= </b><i>x</i><b> AND </b><i>column</i><b> &lt; </b><i>y</i><b>
572 </b></pre></blockquote>
573 </p><p>
574 Under most circumstances, the original LIKE or GLOB operator is still
575 tested against each input row even if the virtual terms are used to
576 constrain an index. This is because we do not know what additional
577 constraints may be imposed by characters to the right
578 of the <i>x</i> prefix. However, if there is only a single
579 global wildcard to the right of <i>x</i>, then the original LIKE or
580 GLOB test is disabled.
581 In other words, if the pattern is like this:
582
583 <blockquote><pre><b>
584 </b><i>column</i><b> LIKE </b><i>x</i><b>%
585 </b><i>column</i><b> GLOB </b><i>x</i><b>*
586 </b></pre></blockquote>
587 </p><p>
588 then the original LIKE or GLOB tests are disabled when the virtual
589 terms constrain an index because in that case we know that all of the
590 rows selected by the index will pass the LIKE or GLOB test.
591
592 </p><p>
593 Note that when the right-hand side of a LIKE or GLOB operator is
594 a <a href="lang_expr.html#varparam">parameter</a> and the statement is prepared using <a href="c3ref/prepare.html">sqlite3_prepare_v2()</a>
595 or <a href="c3ref/prepare.html">sqlite3_prepare16_v2()</a> then the statement is automatically reparsed
596 and recompiled on the first <a href="c3ref/step.html">sqlite3_step()</a> call of each run if the binding
597 to the right-hand side parameter has changed since the previous run.
598 This reparse and recompile is essentially the same action that occurs
599 following a schema change. The recompile is necessary so that the query
600 planner can examine the new value bound to the right-hand side of the
601 LIKE or GLOB operator and determine whether or not to employ the
602 optimization described above.
603
604 <a name="skipscan"></a>
605
606 </p><h1 id="the_skip_scan_optimization"><span>6. </span>The Skip-Scan Optimization</h1>
607
608 <p>
609 The general rule is that indexes are only useful if there are
610 WHERE-clause constraints on the left-most columns of the index.
611 However, in some cases,
612 SQLite is able to use an index even if the first few columns of
613 the index are omitted from the WHERE clause but later columns
614 are included.
615
616
617 </p><p>
618 Consider a table such as the following:
619
620 </p><div class="codeblock"><pre>CREATE TABLE people(
621 name TEXT PRIMARY KEY,
622 role TEXT NOT NULL,
623 height INT NOT NULL, -- in cm
624 CHECK( role IN ('student','teacher') )
625 );
626 CREATE INDEX people_idx1 ON people(role, height);
627 </pre></div>
628
629 <p>
630 The people table has one entry for each person in a large
631 organization. Each person is either a "student" or a "teacher",
632 as determined by the "role" field. The table also records the height in
633 centimeters of each person. The role and height are indexed.
634 Notice that the left-most column of the index is not very
635 selective - it only contains two possible values.
636
637
638 </p><p>
639 Now consider a query to find the names of everyone in the
640 organization that is 180cm tall or taller:
641
642
643 </p><div class="codeblock"><pre>SELECT name FROM people WHERE height>=180;
644 </pre></div>
645
646 <p>
647 Because the left-most column of the index does not appear in the
648 WHERE clause of the query, one is tempted to conclude that the
649 index is not usable here. However, SQLite is able to use the index.
650 Conceptually, SQLite uses the index as if the query were more
651 like the following:
652
653
654 </p><div class="codeblock"><pre>SELECT name FROM people
655 WHERE role IN (SELECT DISTINCT role FROM people)
656 AND height>=180;
657 </pre></div>
658
659 <p>
660 Or this:
661
662 </p><div class="codeblock"><pre>SELECT name FROM people WHERE role='teacher' AND height>=180
663 UNION ALL
664 SELECT name FROM people WHERE role='student' AND height>=180;
665 </pre></div>
666
667 <p>
668 The alternative query formulations shown above are conceptual only.
669 SQLite does not really transform the query.
670 The actual query plan is like this:
671 SQLite locates the first possible value for "role", which it
672 can do by rewinding the "people_idx1" index to the beginning and reading
673 the first record. SQLite stores this first "role" value in an
674 internal variable that we will here call "$role". Then SQLite
675 runs a query like: "SELECT name FROM people WHERE role=$role AND height>=180".
676 This query has an equality constraint on the left-most column of the
677 index and so the index can be used to resolve that query. Once
678 that query is finished, SQLite then uses the "people_idx1" index to
679 locate the next value of the "role" column, using code that is logically
680 similar to "SELECT role FROM people WHERE role>$role LIMIT 1".
681 This new "role" value overwrites the $role variable, and the process
682 repeats until all possible values for "role" have been examined.
683
684 </p><p>
685 We call this kind of index usage a "skip-scan" because the database
686 engine is basically doing a full scan of the index but it optimizes the
687 scan (making it less than "full") by occasionally skipping ahead to the
688 next candidate value.
689
690 </p><p>
691 SQLite might use a skip-scan on an index if it knows that the first
692 one or more columns contain many duplication values.
693 If there are too few duplicates
694 in the left-most columns of the index, then it would
695 be faster to simply step ahead to the next value, and thus do
696 a full table scan, than to do a binary search on an index to locate
697 the next left-column value.
698
699 </p><p>
700 The only way that SQLite can know that there are many duplicates
701 in the left-most columns of an index
702 is if the <a href="lang_analyze.html">ANALYZE</a> command has been run
703 on the database.
704 Without the results of ANALYZE, SQLite has to guess at the "shape" of
705 the data in the table, and the default guess is that there are an average
706 of 10 duplicates for every value in the left-most column of the index.
707 Skip-scan only becomes profitable (it only gets to be faster than
708 a full table scan) when the number of duplicates is about 18 or more.
709 Hence, a skip-scan is never used on a database that has not been analyzed.
710
711 <a name="joins"></a>
712
713 </p><h1 id="joins"><span>7. </span>Joins</h1>
714
715 <p>
716 SQLite implements joins as nested loops.
717 The default order of the nested loops in a join is for the left-most
718 table in the FROM clause to form the outer loop and the right-most
719 table to form the inner loop.
720 However, SQLite will nest the loops in a different order if doing so
721 will help it to select better indexes.
722
723 </p><p>
724 Inner joins can be freely reordered. However outer joins are
725 neither commutative nor associative and hence will not be reordered.
726 Inner joins to the left and right of an outer join might be reordered
727 if the optimizer thinks that is advantageous but outer joins are
728 always evaluated in the order in which they occur.
729
730 </p><p>
731 SQLite <a href="lang_select.html#crossjoin">treats the CROSS JOIN operator specially</a>.
732 The CROSS JOIN operator is commutative, in theory. However, SQLite chooses to
733 never reorder tables in a CROSS JOIN. This provides a mechanism
734 by which the programmer can force SQLite to choose a particular loop nesting
735 order.
736
737 </p><p>
738 When selecting the order of tables in a join, SQLite uses an efficient
739 polynomial-time algorithm graph algorithm described in
740 the <a href="queryplanner-ng.html">Next Generation Query Planner</a> document. Because of this,
741 SQLite is able to plan queries with 50- or 60-way joins in a matter of
742 microseconds
743
744 </p><p>
745 Join reordering is automatic and usually works well enough that
746 programmers do not have to think about it, especially if <a href="lang_analyze.html">ANALYZE</a>
747 has been used to gather statistics about the available indexes,
748 though occasionally some hints from the programmer are needed.
749 Consider, for example, the following schema:
750
751 </p><div class="codeblock"><pre>CREATE TABLE node(
752 id INTEGER PRIMARY KEY,
753 name TEXT
754 );
755 CREATE INDEX node_idx ON node(name);
756 CREATE TABLE edge(
757 orig INTEGER REFERENCES node,
758 dest INTEGER REFERENCES node,
759 PRIMARY KEY(orig, dest)
760 );
761 CREATE INDEX edge_idx ON edge(dest,orig);
762 </pre></div>
763 <p>
764 The schema above defines a directed graph with the ability to store a
765 name at each node. Now consider a query against this schema:
766
767 </p><div class="codeblock"><pre>SELECT *
768 FROM edge AS e,
769 node AS n1,
770 node AS n2
771 WHERE n1.name = 'alice'
772 AND n2.name = 'bob'
773 AND e.orig = n1.id
774 AND e.dest = n2.id;
775 </pre></div>
776 <p>
777 This query asks for is all information about edges that go from
778 nodes labeled "alice" to nodes labeled "bob".
779 The query optimizer in SQLite has basically two choices on how to
780 implement this query. (There are actually six different choices, but
781 we will only consider two of them here.)
782 Pseudocode below demonstrating these two choices.
783
784 <a name="option1"></a>
785
786 </p><p>Option 1:
787 </p><div class="codeblock"><pre>foreach n1 where n1.name='alice' do:
788 foreach n2 where n2.name='bob' do:
789 foreach e where e.orig=n1.id and e.dest=n2.id
790 return n1.*, n2.*, e.*
791 end
792 end
793 end
794 </pre></div>
795 <a name="option2"></a>
796
797 <p>Option 2:
798 </p><div class="codeblock"><pre>foreach n1 where n1.name='alice' do:
799 foreach e where e.orig=n1.id do:
800 foreach n2 where n2.id=e.dest and n2.name='bob' do:
801 return n1.*, n2.*, e.*
802 end
803 end
804 end
805 </pre></div>
806 <p>
807 The same indexes are used to speed up every loop in both implementation
808 options.
809 The only difference in these two query plans is the order in which
810 the loops are nested.
811
812 </p><p>
813 So which query plan is better? It turns out that the answer depends on
814 what kind of data is found in the node and edge tables.
815
816 </p><p>
817 Let the number of alice nodes be M and the number of bob nodes be N.
818 Consider two scenarios. In the first scenario, M and N are both 2 but
819 there are thousands of edges on each node. In this case, option 1 is
820 preferred. With option 1, the inner loop checks for the existence of
821 an edge between a pair of nodes and outputs the result if found.
822 Because there are only 2 alice and bob nodes each, the inner loop
823 only has to run four times and the query is very quick. Option 2 would
824 take much longer here. The outer loop of option 2 only executes twice,
825 but because there are a large number of edges leaving each alice node,
826 the middle loop has to iterate many thousands of times. It will be
827 much slower. So in the first scenario, we prefer to use option 1.
828
829 </p><p>
830 Now consider the case where M and N are both 3500. Alice nodes are
831 abundant. This time suppose each of these nodes is connected by only one
832 or two edges. Now option 2 is preferred. With option 2,
833 the outer loop still has to run 3500 times, but the middle loop only
834 runs once or twice for each outer loop and the inner loop will only
835 run once for each middle loop, if at all. So the total number of
836 iterations of the inner loop is around 7000. Option 1, on the other
837 hand, has to run both its outer loop and its middle loop 3500 times
838 each, resulting in 12 million iterations of the middle loop.
839 Thus in the second scenario, option 2 is nearly 2000 times faster
840 than option 1.
841
842 </p><p>
843 So you can see that depending on how the data is structured in the table,
844 either query plan 1 or query plan 2 might be better. Which plan does
845 SQLite choose by default? As of version 3.6.18, without running <a href="lang_analyze.html">ANALYZE</a>,
846 SQLite will choose option 2.
847 If the <a href="lang_analyze.html">ANALYZE</a> command is run in order to gather statistics,
848 a different choice might be made if the statistics indicate that the
849 alternative is likely to run faster.
850
851 </p><h2 id="manual_control_of_join_order"><span>7.1. </span>Manual Control Of Join Order</h2>
852
853 <p>
854 SQLite almost always picks the best join order automatically. It is
855 very rare that a developer needs to intervene to give the query planner
856 hints about the best join order. The best policy is to make use
857 of <a href="pragma.html#pragma_optimize">PRAGMA optimize</a> to ensure that the query planner has access to
858 up-to-date statistics on the shape of the data in the database.
859
860 </p><p>
861 This section describes techniques by which developers can control the
862 join order in SQLite, to work around any performance problems that may
863 arise. However, the use of these techniques is not recommended, except
864 as a last resort.
865
866 </p><p>
867 If you do encounter a situation where SQLite is picking a suboptimal
868 join order even after running <a href="pragma.html#pragma_optimize">PRAGMA optimize</a>, please report your
869 situation on the <a href="https://sqlite.org/forum">SQLite Community Forum</a> so
870 that the SQLite maintainers can make new refinements to the query planner
871 such that manual intervention is not required.
872
873 <a name="manctrl"></a>
874
875 </p><h3 id="manual_control_of_query_plans_using_sqlite_stat_tables"><span>7.1.1. </span>Manual Control Of Query Plans Using SQLITE_STAT Tables</h3>
876
877 <p>
878 SQLite provides the ability for advanced programmers to exercise control
879 over the query plan chosen by the optimizer. One method for doing this
880 is to fudge the <a href="lang_analyze.html">ANALYZE</a> results in the <a href="fileformat2.html#stat1tab">sqlite_stat1</a> table.
881
882 <a name="crossjoin"></a>
883
884 </p><h3 id="manual_control_of_query_plans_using_cross_join"><span>7.1.2. </span>Manual Control of Query Plans using CROSS JOIN</h3>
885
886 <p>
887 Programmers can force SQLite to use a particular loop nesting order
888 for a join by using the CROSS JOIN operator instead of just JOIN,
889 INNER JOIN, NATURAL JOIN, or a "," join. Though CROSS JOINs are
890 commutative in theory, SQLite chooses to never reorder the tables in
891 a CROSS JOIN. Hence, the left table of a CROSS JOIN will always be
892 in an outer loop relative to the right table.
893
894 </p><p>
895 In the following query, the optimizer is free to reorder the
896 tables of FROM clause any way it sees fit:
897
898 </p><div class="codeblock"><pre>SELECT *
899 FROM node AS n1,
900 edge AS e,
901 node AS n2
902 WHERE n1.name = 'alice'
903 AND n2.name = 'bob'
904 AND e.orig = n1.id
905 AND e.dest = n2.id;
906 </pre></div>
907 <p>
908 In the following logically equivalent formulation of the same query,
909 the substitution of "CROSS JOIN" for the "," means that the order
910 of tables must be N1, E, N2.
911
912 </p><div class="codeblock"><pre>SELECT *
913 FROM node AS n1 CROSS JOIN
914 edge AS e CROSS JOIN
915 node AS n2
916 WHERE n1.name = 'alice'
917 AND n2.name = 'bob'
918 AND e.orig = n1.id
919 AND e.dest = n2.id;
920 </pre></div>
921 <p>
922 In the latter query, the query plan must be
923 <a href="#option2">option 2</a>. Note that
924 you must use the keyword "CROSS" in order to disable the table reordering
925 optimization; INNER JOIN, NATURAL JOIN, JOIN, and other similar
926 combinations work just like a comma join in that the optimizer is
927 free to reorder tables as it sees fit. (Table reordering is also
928 disabled on an outer join, but that is because outer joins are not
929 associative or commutative. Reordering tables in OUTER JOIN changes
930 the result.)
931
932 </p><p>
933 See "<a href="queryplanner-ng.html#fossilcasestudy">The Fossil NGQP Upgrade Case Study</a>" for another real-world example
934 of using CROSS JOIN to manually control the nesting order of a join.
935 The <a href="queryplanner-ng.html#howtofix">query planner checklist</a> found later in the same document provides
936 further guidance on manual control of the query planner.
937
938 <a name="multi_index"></a>
939
940 </p><h1 id="choosing_between_multiple_indexes"><span>8. </span>Choosing Between Multiple Indexes</h1>
941
942 <p>
943 Each table in the FROM clause of a query can use at most one index
944 (except when the <a href="#or_opt">OR-clause optimization</a> comes into
945 play)
946 and SQLite strives to use at least one index on each table. Sometimes,
947 two or more indexes might be candidates for use on a single table.
948 For example:
949
950 </p><div class="codeblock"><pre>CREATE TABLE ex2(x,y,z);
951 CREATE INDEX ex2i1 ON ex2(x);
952 CREATE INDEX ex2i2 ON ex2(y);
953 SELECT z FROM ex2 WHERE x=5 AND y=6;
954 </pre></div>
955 <p>
956 For the SELECT statement above, the optimizer can use the ex2i1 index
957 to lookup rows of ex2 that contain x=5 and then test each row against
958 the y=6 term. Or it can use the ex2i2 index to lookup rows
959 of ex2 that contain y=6 then test each of those rows against the
960 x=5 term.
961
962 </p><p>
963 When faced with a choice of two or more indexes, SQLite tries to estimate
964 the total amount of work needed to perform the query using each option.
965 It then selects the option that gives the least estimated work.
966
967 </p><p>
968 To help the optimizer get a more accurate estimate of the work involved
969 in using various indexes, the user may optionally run the <a href="lang_analyze.html">ANALYZE</a> command.
970 The <a href="lang_analyze.html">ANALYZE</a> command scans all indexes of database where there might
971 be a choice between two or more indexes and gathers statistics on the
972 selectiveness of those indexes. The statistics gathered by
973 this scan are stored in special database tables names shows names all
974 begin with "<b>sqlite_stat</b>".
975 The content of these tables is not updated as the database
976 changes so after making significant changes it might be prudent to
977 rerun <a href="lang_analyze.html">ANALYZE</a>.
978 The results of an ANALYZE command are only available to database connections
979 that are opened after the ANALYZE command completes.
980
981 </p><p>
982 The various <b>sqlite_stat</b><i>N</i> tables contain information on how
983 selective the various indexes are. For example, the <a href="fileformat2.html#stat1tab">sqlite_stat1</a>
984 table might indicate that an equality constraint on column x reduces the
985 search space to 10 rows on average, whereas an equality constraint on
986 column y reduces the search space to 3 rows on average. In that case,
987 SQLite would prefer to use index ex2i2 since that index is more selective.
988
989 <a name="uplus"></a>
990
991 </p><h2 id="disqualifying_where_clause_terms_using_unary_"><span>8.1. </span>Disqualifying WHERE Clause Terms using Unary-"+"</h2>
992
993 <p>
994 <i>Note: Disqualifying WHERE clause terms this way is not recommended.
995 This is a work-around.
996 Only do this as a last resort to get the performance you need. If you
997 find a situation where this work-around is necessary, please report the
998 situation on the <a href="https://sqlite.org/forum">SQLite Community Forum</a> so
999 that the SQLite maintainers can try to improve the query planner such
1000 that the work-around is no longer required for your situation.</i>
1001
1002 </p><p>
1003 Terms of the WHERE clause can be manually disqualified for use with
1004 indexes by prepending a unary <b>+</b> operator to the column name. The
1005 unary <b>+</b> is a no-op and will not generate any byte code in the prepared
1006 statement.
1007 However, the unary <b>+</b> operator will prevent the term from
1008 constraining an index.
1009 So, in the example above, if the query were rewritten as:
1010
1011 </p><div class="codeblock"><pre>SELECT z FROM ex2 WHERE +x=5 AND y=6;
1012 </pre></div>
1013 <p>
1014 The <b>+</b> operator on the <b>x</b> column will prevent that term from
1015 constraining an index. This would force the use of the ex2i2 index.
1016
1017 </p><p>
1018 Note that the unary <b>+</b> operator also removes
1019 <a href="datatype3.html#affinity">type affinity</a> from
1020 an expression, and in some cases this can cause subtle changes in
1021 the meaning of an expression.
1022 In the example above,
1023 if column <b>x</b> has <a href="datatype3.html#affinity">TEXT affinity</a>
1024 then the comparison "x=5" will be done as text. The <b>+</b> operator
1025 removes the affinity. So the comparison "<b>+x=5</b>" will compare the text
1026 in column <b>x</b> with the numeric value 5 and will always be false.
1027
1028 <a name="rangequery"></a>
1029
1030 </p><h2 id="range_queries"><span>8.2. </span>Range Queries</h2>
1031
1032 <p>
1033 Consider a slightly different scenario:
1034
1035 </p><div class="codeblock"><pre>CREATE TABLE ex2(x,y,z);
1036 CREATE INDEX ex2i1 ON ex2(x);
1037 CREATE INDEX ex2i2 ON ex2(y);
1038 SELECT z FROM ex2 WHERE x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;
1039 </pre></div>
1040 <p>
1041 Further suppose that column x contains values spread out
1042 between 0 and 1,000,000 and column y contains values
1043 that span between 0 and 1,000. In that scenario,
1044 the range constraint on column x should reduce the search space by
1045 a factor of 10,000 whereas the range constraint on column y should
1046 reduce the search space by a factor of only 10. So the ex2i1 index
1047 should be preferred.
1048
1049 </p><p>
1050 SQLite will make this determination, but only if it has been compiled
1051 with <a href="compile.html#enable_stat3">SQLITE_ENABLE_STAT3</a> or <a href="compile.html#enable_stat4">SQLITE_ENABLE_STAT4</a>.
1052 The <a href="compile.html#enable_stat3">SQLITE_ENABLE_STAT3</a> and <a href="compile.html#enable_stat4">SQLITE_ENABLE_STAT4</a> options causes
1053 the <a href="lang_analyze.html">ANALYZE</a> command to collect a histogram of column content in the
1054 <a href="fileformat2.html#stat3tab">sqlite_stat3</a> or <a href="fileformat2.html#stat4tab">sqlite_stat4</a> tables and to use this histogram to
1055 make a better guess at the best query to use for range constraints
1056 such as the above. The main difference between STAT3 and STAT4 is
1057 that STAT3 records histogram data for only the left-most column of
1058 an index whereas STAT4 records histogram data for all columns of an
1059 index. For single-column indexes, STAT3 and STAT4 work the same.
1060
1061 </p><p>
1062 The histogram data is only useful if the right-hand side of the constraint
1063 is a simple compile-time constant or <a href="lang_expr.html#varparam">parameter</a> and not an expression.
1064
1065 </p><p>
1066 Another limitation of the histogram data is that it only applies to the
1067 left-most column on an index. Consider this scenario:
1068
1069 </p><div class="codeblock"><pre>CREATE TABLE ex3(w,x,y,z);
1070 CREATE INDEX ex3i1 ON ex2(w, x);
1071 CREATE INDEX ex3i2 ON ex2(w, y);
1072 SELECT z FROM ex3 WHERE w=5 AND x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;
1073 </pre></div>
1074 <p>
1075 Here the inequalities are on columns x and y which are not the
1076 left-most index columns. Hence, the histogram data is useless in helping
1077 to choose between the range constraints on columns x and y.
1078
1079 <a name="covidx"></a>
1080
1081 </p><h1 id="covering_indexes"><span>9. </span>Covering Indexes</h1>
1082
1083 <p>
1084 When doing an indexed lookup of a row, the usual procedure is to
1085 do a binary search on the index to find the index entry, then extract
1086 the <a href="lang_createtable.html#rowid">rowid</a> from the index and use that <a href="lang_createtable.html#rowid">rowid</a> to do a binary search on
1087 the original table. Thus a typical indexed lookup involves two
1088 binary searches.
1089 If, however, all columns that were to be fetched from the table are
1090 already available in the index itself, SQLite will use the values
1091 contained in the index and will never look up the original table
1092 row. This saves one binary search for each row and can make many
1093 queries run twice as fast.
1094
1095 </p><p>
1096 When an index contains all of the data needed for a query and when the
1097 original table never needs to be consulted, we call that index a
1098 "covering index".
1099
1100 <a name="order_by"></a>
1101
1102 </p><h1 id="order_by_optimizations"><span>10. </span>ORDER BY Optimizations</h1>
1103
1104 <p>
1105 SQLite attempts to use an index to satisfy the ORDER BY clause of a
1106 query when possible.
1107 When faced with the choice of using an index to satisfy WHERE clause
1108 constraints or satisfying an ORDER BY clause, SQLite does the same
1109 cost analysis described above
1110 and chooses the index that it believes will result in the fastest answer.
1111
1112 </p><p>
1113 SQLite will also attempt to use indexes to help satisfy GROUP BY clauses
1114 and the DISTINCT keyword. If the nested loops of the join can be arranged
1115 such that rows that are equivalent for the GROUP BY or for the DISTINCT are
1116 consecutive, then the GROUP BY or DISTINCT logic can determine if the
1117 current row is part of the same group or if the current row is distinct
1118 simply by comparing the current row to the previous row.
1119 This can be much faster than the alternative of comparing each row to
1120 all prior rows.
1121
1122 <a name="partsort"></a>
1123
1124 </p><h2 id="partial_order_by_via_index"><span>10.1. </span>Partial ORDER BY via Index</h2>
1125
1126 <p>
1127 If a query contains an ORDER BY clause with multiple terms, it might
1128 be that SQLite can use indexes to cause rows to come out in the order
1129 of some prefix of the terms in the ORDER BY but that later terms in
1130 the ORDER BY are not satisfied. In that case, SQLite does block sorting.
1131 Suppose the ORDER BY clause has four terms and the natural order of the
1132 query results in rows appearing in order of the first two terms. As
1133 each row is output by the query engine and enters the sorter, the
1134 outputs in the current row corresponding to the first two terms of
1135 the ORDER BY are compared against the previous row. If they have
1136 changed, the current sort is finished and output and a new sort is
1137 started. This results in a slightly faster sort. Even bigger
1138 advantages are that many fewer rows need to be held in memory,
1139 reducing memory requirements, and outputs can begin to appear before
1140 the core query has run to completion.
1141
1142 <a name="flattening"></a>
1143
1144 </p><h1 id="subquery_flattening"><span>11. </span>Subquery Flattening</h1>
1145
1146 <p>
1147 When a subquery occurs in the FROM clause of a SELECT, the simplest
1148 behavior is to evaluate the subquery into a transient table, then run
1149 the outer SELECT against the transient table. Such a plan
1150 can be suboptimal since the transient table will not have any indexes
1151 and the outer query (which is likely a join) will be forced to either
1152 do a full table scan on the transient table or else construct a
1153 <a href="optoverview.html#autoindex">query-time index</a> on the transient table, neither of which is
1154 is particularly fast.
1155
1156 </p><p>
1157 To overcome this problem, SQLite attempts to flatten subqueries in
1158 the FROM clause of a SELECT.
1159 This involves inserting the FROM clause of the subquery into the
1160 FROM clause of the outer query and rewriting expressions in
1161 the outer query that refer to the result set of the subquery.
1162 For example:
1163
1164 </p><div class="codeblock"><pre>SELECT t1.a, t2.b FROM t2, (SELECT x+y AS a FROM t1 WHERE z&lt;100) WHERE a&gt;5
1165 </pre></div>
1166 <p>
1167 Would be rewritten using query flattening as:
1168
1169 </p><div class="codeblock"><pre>SELECT t1.x+t1.y AS a, t2.b FROM t2, t1 WHERE z&lt;100 AND a&gt;5
1170 </pre></div>
1171 <p>
1172 There is a long list of conditions that must all be met in order for
1173 query flattening to occur. Some of the constraints are marked as
1174 obsolete by italic text. These extra constraints are retained in the
1175 documentation to preserve the numbering of the other constraints.
1176
1177 </p><p>
1178 Casual readers are not expected to understand all of these rules.
1179 The point here is that flattening rules are subtle and complex.
1180 There have been multiple bugs over the years caused by
1181 over-aggressive query flattening. On the other hand, performance
1182 of complex queries and/or queries involving views tends to suffer
1183 if query flattening is more conservative.
1184
1185 </p><p>
1186 </p><ol>
1187 <li value="1"> <i>(Obsolete)</i>
1188 </li><li value="2"> <i>(Obsolete)</i>
1189 </li><li value="3">
1190 If the subquery is the right operand of a LEFT JOIN then
1191 <ol type="a"><li> the subquery may not be a join, and
1192 </li><li> the FROM clause of the subquery may
1193 not contain a virtual table, and
1194 </li><li> the outer query may not be DISTINCT.</li></ol>
1195 </li><li value="4"> The subquery is not DISTINCT.
1196 </li><li value="5"> <i>(Obsolete - subsumed into constraint 4)</i>
1197 </li><li value="6"> <i>(Obsolete)</i>
1198 </li><li value="7"> The subquery has a FROM clause.
1199 </li><li value="8"> The subquery does not use LIMIT or the outer query is
1200 not a join.
1201 </li><li value="9"> The subquery does not use LIMIT or the outer query
1202 does not use aggregates.
1203 </li><li value="10"> <i>(Obsolete)</i>
1204 </li><li value="11">
1205 The subquery and the outer query do not both have ORDER BY clauses.
1206 </li><li value="12"> <i>(Obsolete - subsumed into constraint 3)</i>
1207 </li><li value="13"> The subquery and outer query do not both use LIMIT.
1208 </li><li value="14"> The subquery does not use OFFSET.
1209 </li><li value="15">
1210 If the outer query is part of a compound select, then the
1211 subquery may not have a LIMIT clause.
1212
1213 </li><li value="16">
1214 If the outer query is an aggregate, then the subquery may
1215 not contain ORDER BY.
1216
1217 </li><li value="17">
1218 If the sub-query is a compound SELECT, then
1219 <ol type="a">
1220 <li> all compound operators must be UNION ALL, and
1221 </li><li> no terms with the subquery compound may be aggregate
1222 or DISTINCT, and
1223 </li><li> every term within the subquery must have a FROM clause, and
1224 </li><li> the outer query may not be an aggregateor DISTINCT query.
1225 </li><li> the subquery may not contain window functions.
1226 </li><li> the subquery must not be the right-hand side of a LEFT JOIN.
1227 </li><li> either the subquery is the first element of the outer query
1228 or there are not RIGHT or FULL JOINs in any arm of the subquery.
1229 </li><li> the corresponding result set expressions in all arms of the
1230 compound subquery must have the same <a href="datatype3.html#affinity">affinity</a>.
1231 </li></ol>
1232
1233 The parent and sub-query may contain WHERE clauses. Subject to
1234 rules (11), (12) and (13), they may also contain ORDER BY,
1235 LIMIT and OFFSET clauses.
1236
1237 </li><li value="18">
1238 If the sub-query is a compound select, then all terms of the
1239 ORDER by clause of the parent must be simple references to
1240 columns of the sub-query.
1241
1242 </li><li value="19">
1243 If the subquery uses LIMIT then the outer query may not
1244 have a WHERE clause.
1245
1246 </li><li value="20">
1247 If the sub-query is a compound select, then it must not use
1248 an ORDER BY clause.
1249
1250 </li><li value="21">
1251 If the subquery uses LIMIT, then the outer query may not be
1252 DISTINCT.
1253
1254 </li><li value="22"> The subquery may not be a recursive CTE.
1255
1256 </li><li value="23"> If the outer query is a recursive CTE, then the sub-query
1257 may not be a compound query.
1258
1259 </li><li value="24"> <i>(Obsolete)</i>
1260
1261 </li><li value="25"> Neither the subquery nor the outer query may contain
1262 a <a href="windowfunctions.html">window function</a> in the result set nor the ORDER BY clause.
1263
1264 </li><li value="26"> The subquery may not be the right operand of a RIGHT
1265 or FULL OUTER JOIN.
1266 </li><li value="27"> The subquery may not contain a FULL or RIGHT JOIN unless it
1267 is the first element of the parent query. Two subcases:
1268 <ol type="a">
1269 <li> the subquery is not a compound query.
1270 </li><li> the subquery is a compound query and the RIGHT JOIN occurs
1271 in any arm of the compound query. (See also (17g)).
1272 </li></ol>
1273 </li><li value="28"> The subquery is not a MATERIALIZED CTE.
1274 </li></ol>
1275
1276
1277 <p>
1278 Query flattening is an important optimization when views are used as
1279 each use of a view is translated into a subquery.
1280
1281 <a name="coroutines"></a>
1282
1283 </p><h1 id="subquery_co_routines"><span>12. </span>Subquery Co-routines</h1>
1284
1285 <p>
1286 SQLite implements FROM-clause subqueries in one of three ways:
1287 </p><ol>
1288 <li> <a href="optoverview.html#flattening">Flatten</a> the subquery into its outer query
1289 </li><li> Evaluate the subquery into a transient table that exists for
1290 the duration of the one SQL statement that is being evaluated,
1291 then run the outer query against that transient table.
1292 </li><li> Evaluate the subquery in a co-routine that runs in parallel with
1293 the outer query, providing rows to the outer query as needed.
1294 </li></ol>
1295
1296 <p>
1297 This section describes the third technique: implementing the subquery
1298 as a co-routine.
1299
1300 </p><p>
1301 A co-routine is like a subroutine in that it runs in the same thread
1302 as the caller and eventually returns control back to the caller. The
1303 difference is that a co-routine also has the ability to return
1304 before it has finished, and then resume where it left off the next
1305 time it is called.
1306
1307 </p><p>
1308 When a subquery is implemented as a co-routine, byte-code is generated
1309 to implement the subquery as if it were a standalone query, except
1310 instead of returning rows of results back to the application, the
1311 co-routine yields control back to the caller after each row is computed.
1312 The caller can then use that one computed row as part of its computation,
1313 then invoke the co-routine again when it is ready for the next row.
1314
1315 </p><p>
1316 Co-routines are better than storing the complete result set of the subquery
1317 in a transient table because co-routines use less memory. With a co-routine,
1318 only a single row of the result needs to be remembered, whereas all rows of
1319 the result must be stored for a transient table. Also, because the
1320 co-routine does not need to run to completion before the outer query
1321 begins its work, the first rows of output can appear much sooner, and if
1322 the overall query is abandoned before it has finished, less work is done
1323 overall.
1324
1325 </p><p>
1326 On the other hand, if the result of the subquery must be scanned multiple
1327 times (because, for example, it is just one table in a join) then it
1328 is better to use a transient table to remember the entire result of the
1329 subquery, in order to avoid computing the subquery more than once.
1330
1331 <a name="deferred_work"></a>
1332
1333 </p><h2 id="using_co_routines_to_defer_work_until_after_the_sorting"><span>12.1. </span>Using Co-routines to Defer Work until after the Sorting</h2>
1334
1335 <p>
1336 As of SQLite version 3.21.0 (2017-10-24), the query planner will
1337 always prefer to use a co-routine to implement FROM-clause subqueries
1338 that contains an ORDER BY clause and that are not part of a join when
1339 the result set of the outer query is "complex". This feature allows
1340 applications to shift expensive computations from before the
1341 sorter until after the sorter, which can result in faster operation.
1342 For example, consider this query:
1343
1344 </p><div class="codeblock"><pre>SELECT expensive_function(a) FROM tab ORDER BY date DESC LIMIT 5;
1345 </pre></div>
1346 <p>
1347 The goal of this query is to compute some value for the five most
1348 recent entries in the table. In the query above, the
1349 "expensive_function()" is invoked prior to the sort and thus is
1350 invoked on every row of the table, even
1351 rows that are ultimately omitted due to the LIMIT clause.
1352 A co-routine can be used to work around this:
1353
1354 </p><div class="codeblock"><pre>SELECT expensive_function(a) FROM (
1355 SELECT a FROM tab ORDER BY date DESC LIMIT 5
1356 );
1357 </pre></div>
1358 <p>
1359 In the revised query, the subquery implemented by a co-routine computes
1360 the five most recent values for "a". Those five values are passed from the
1361 co-routine up into the outer query where the "expensive_function()" is
1362 invoked on only the specific rows that the application cares about.
1363
1364 </p><p>
1365 The query planner in future versions of SQLite might grow smart enough
1366 to make transformations such as the above automatically, in both directions.
1367 That is to say, future versions of SQLite might transform queries of the
1368 first form into the second, or queries written the second way into the
1369 first. As of SQLite version 3.22.0 (2018-01-22), the query planner
1370 will flatten the subquery if the outer query does not make use of any
1371 user-defined functions or subqueries in its result set. For the examples
1372 shown above, however, SQLite implements each of the queries as
1373 written.
1374
1375 <a name="minmax"></a>
1376
1377 </p><h1 id="the_min_max_optimization"><span>13. </span>The MIN/MAX Optimization</h1>
1378
1379 <p>
1380 Queries that contain a single MIN() or MAX() aggregate function whose
1381 argument is the left-most column of an index might be satisfied
1382 by doing a single index lookup rather than by scanning the entire table.
1383 Examples:
1384
1385 </p><div class="codeblock"><pre>SELECT MIN(x) FROM table;
1386 SELECT MAX(x)+1 FROM table;
1387 </pre></div>
1388
1389 <a name="autoindex"></a>
1390
1391 <h1 id="automatic_query_time_indexes"><span>14. </span>Automatic Query-Time Indexes</h1>
1392
1393 <p>
1394 When no indexes are available to aid the evaluation of a query, SQLite
1395 might create an automatic index that lasts only for the duration
1396 of a single SQL statement.
1397 Automatic indexes are also sometimes called "Query-time indexes".
1398 Since the cost of constructing the automatic or query-time index is
1399 O(NlogN) (where N is the number of entries in the table) and the cost of
1400 doing a full table scan is only O(N), an automatic index will
1401 only be created if SQLite expects that the lookup will be run more than
1402 logN times during the course of the SQL statement. Consider an example:
1403
1404 </p><div class="codeblock"><pre>CREATE TABLE t1(a,b);
1405 CREATE TABLE t2(c,d);
1406 -- Insert many rows into both t1 and t2
1407 SELECT * FROM t1, t2 WHERE a=c;
1408 </pre></div>
1409 <p>
1410 In the query above, if both t1 and t2 have approximately N rows, then
1411 without any indexes the query will require O(N*N) time. On the other
1412 hand, creating an index on table t2 requires O(NlogN) time and using
1413 that index to evaluate the query requires an additional O(NlogN) time.
1414 In the absence of <a href="lang_analyze.html">ANALYZE</a> information, SQLite guesses that N is one
1415 million and hence it believes that constructing the automatic index will
1416 be the cheaper approach.
1417
1418 </p><p>
1419 An automatic query-time index might also be used for a subquery:
1420
1421 </p><div class="codeblock"><pre>CREATE TABLE t1(a,b);
1422 CREATE TABLE t2(c,d);
1423 -- Insert many rows into both t1 and t2
1424 SELECT a, (SELECT d FROM t2 WHERE c=b) FROM t1;
1425 </pre></div>
1426 <p>
1427 In this example, the t2 table is used in a subquery to translate values
1428 of the t1.b column. If each table contains N rows, SQLite expects that
1429 the subquery will run N times, and hence it will believe it is faster
1430 to construct an automatic, transient index on t2 first and then use
1431 that index to satisfy the N instances of the subquery.
1432
1433 </p><p>
1434 The automatic indexing capability can be disabled at run-time using
1435 the <a href="pragma.html#pragma_automatic_index">automatic_index pragma</a>. Automatic indexing is turned on by
1436 default, but this can be changed so that automatic indexing is off
1437 by default using the <a href="compile.html#default_automatic_index">SQLITE_DEFAULT_AUTOMATIC_INDEX</a> compile-time option.
1438 The ability to create automatic indexes can be completely disabled by
1439 compiling with the <a href="compile.html#omit_automatic_index">SQLITE_OMIT_AUTOMATIC_INDEX</a> compile-time option.
1440
1441 </p><p>
1442 In SQLite <a href="releaselog/3_8_0.html">version 3.8.0</a> (2013-08-26) and later,
1443 an <a href="rescode.html#warning_autoindex">SQLITE_WARNING_AUTOINDEX</a> message is sent
1444 to the <a href="errlog.html">error log</a> every time a statement is prepared that uses an
1445 automatic index. Application developers can and should use these warnings
1446 to identify the need for new persistent indexes in the schema.
1447
1448 </p><p>
1449 Do not confuse automatic indexes with the <a href="fileformat2.html#intschema">internal indexes</a> (having names
1450 like "sqlite_autoindex_<i>table</i>_<i>N</i>") that are sometimes
1451 created to implement a <a href="lang_createtable.html#primkeyconst">PRIMARY KEY constraint</a> or <a href="lang_createtable.html#uniqueconst">UNIQUE constraint</a>.
1452 The automatic indexes described here exist only for the duration of a
1453 single query, are never persisted to disk, and are only visible to a
1454 single database connection. Internal indexes are part of the implementation
1455 of PRIMARY KEY and UNIQUE constraints, are long-lasting and persisted
1456 to disk, and are visible to all database connections. The term "autoindex"
1457 appears in the names of <a href="fileformat2.html#intschema">internal indexes</a> for legacy reasons and does
1458 not indicate that internal indexes and automatic indexes are related.
1459
1460 <a name="hashjoin"></a>
1461
1462 </p><h2 id="hash_joins"><span>14.1. </span>Hash Joins</h2>
1463
1464 <p>
1465 An automatic index is almost the same thing as a
1466 <a href="https://en.wikipedia.org/wiki/Hash_join">hash join</a>. The only difference
1467 is that a B-Tree is used instead of a hash table. If you are willing to
1468 say that the transient B-Tree constructed for an automatic index is
1469 really just a fancy hash table, then a query that uses an automatic
1470 index is just a hash join.
1471
1472 </p><p>
1473 SQLite constructs a transient index instead of a hash table in this
1474 instance because it already has a robust and high performance B-Tree
1475 implementation at hand, whereas a hash-table would need to be added.
1476 Adding a separate hash table implementation to handle this one case
1477 would increase the size of the library (which is designed for use on
1478 low-memory embedded devices) for minimal performance gain. SQLite might
1479 be enhanced with a hash-table implementation someday, but for now it seems
1480 better to continue using automatic indexes in cases where client/server
1481 database engines might use a hash join.
1482
1483 <a name="pushdown"></a>
1484
1485 </p><h1 id="the_predicate_push_down_optimization"><span>15. </span>The Predicate Push-Down Optimization</h1>
1486
1487 <p>
1488 If a subquery cannot be <a href="optoverview.html#flattening">flattened</a> into the outer query, it might
1489 still be possible to enhance performance by "pushing down" WHERE clause
1490 terms from the outer query into the subquery. Consider an example:
1491
1492 </p><div class="codeblock"><pre>CREATE TABLE t1(a INT, b INT);
1493 CREATE TABLE t2(x INT, y INT);
1494 CREATE VIEW v1(a,b) AS SELECT DISTINCT a, b FROM t1;
1495
1496 SELECT x, y, b
1497 FROM t2 JOIN v1 ON (x=a)
1498 WHERE b BETWEEN 10 AND 20;
1499 </pre></div>
1500
1501 <p>
1502 The view v1 cannot be <a href="optoverview.html#flattening">flattened</a> because it is DISTINCT. It must
1503 instead be run as a subquery with the results being stored in a
1504 transient table, then the join is performed between t2 and the
1505 transient table. The push-down optimization pushes down the
1506 "b BETWEEN 10 AND 20" term into the view. This makes the transient
1507 table smaller, and helps the subquery to run faster if there
1508 is an index on t1.b. The resulting evaluation is like this:
1509
1510 </p><div class="codeblock"><pre>SELECT x, y, b
1511 FROM t2
1512 JOIN (SELECT DISTINCT a, b FROM t1 WHERE b BETWEEN 10 AND 20)
1513 WHERE b BETWEEN 10 AND 20;
1514 </pre></div>
1515
1516 <p>
1517 The WHERE-clause push-down optimization cannot always be used. For example,
1518 if the subquery contains a LIMIT, then pushing down any part of
1519 the WHERE clause from the outer query could change the result of
1520 the inner query. There are other restrictions, explained in a
1521 comment in the source code on the pushDownWhereTerms() routine
1522 that implements this optimization.
1523
1524 </p><p>
1525 Do not confuse this optimization with the optimization by a similar name
1526 in MySQL. The MySQL push-down optimization changes the order of evaluation
1527 of WHERE-clause constraints such that those that can be evaluated using
1528 only the index and without having to find the corresponding table row are
1529 evaluated first, thus avoiding an unnecessary table row lookup if the
1530 constraint fails. For disambiguation, SQLite calls this the
1531 "MySQL push-down optimization". SQLite does do the MySQL push-down
1532 optimization too, in addition to the WHERE-clause push-down optimization.
1533 But the focus of this section is the WHERE-clause push-down optimization.
1534
1535 <a name="leftjoinreduction"></a>
1536
1537 </p><h1 id="the_outer_join_strength_reduction_optimization"><span>16. </span>The OUTER JOIN Strength Reduction Optimization</h1>
1538
1539 <p>
1540 An OUTER JOIN (either a LEFT JOIN, a RIGHT JOIN, or a FULL JOIN)
1541 can sometimes be simplified. A LEFT or RIGHT JOIN can be converted
1542 into an ordinary (INNER) JOIN, or a FULL JOIN might be converted into
1543 either a LEFT or a RIGHT JOIN. This can happen if there are terms
1544 in the WHERE clause that guarantee the same result after simplification.
1545 For example, if any
1546 column in the right-hand table of the LEFT JOIN must be non-NULL
1547 in order for the WHERE clause to be true, then the LEFT JOIN is
1548 demoted to an ordinary JOIN.
1549
1550 </p><p>
1551 The theorem prover that determines whether a join can be simplified is
1552 imperfect. It sometimes returns a false negative. In other words,
1553 it sometimes fails to prove that reducing the strength of an OUTER JOIN
1554 is safe when in fact it is safe.
1555 For example, the prover does not know
1556 the <a href="lang_datefunc.html#dttm">datetime() SQL function</a> will always return NULL if its first
1557 argument is NULL, and so it will not recognize that the LEFT JOIN
1558 in the following query could be strength-reduced:
1559
1560 </p><div class="codeblock"><pre>SELECT urls.url
1561 FROM urls
1562 LEFT JOIN
1563 (SELECT *
1564 FROM (SELECT url_id AS uid, max(retrieval_time) AS rtime
1565 FROM lookups GROUP BY 1 ORDER BY 1)
1566 WHERE uid IN (358341,358341,358341)
1567 ) recent
1568 ON u.source_seed_id = recent.xyz OR u.url_id = recent.xyz
1569 WHERE
1570 DATETIME(recent.rtime) > DATETIME('now', '-5 days');
1571 </pre></div>
1572
1573 <p>
1574 It is possible that future enhancements to the prover might enable it
1575 to recognize that NULL inputs to certain built-in functions
1576 always result in a NULL answer. However, not all built-in
1577 functions have that property (for example <a href="lang_corefunc.html#coalesce">coalesce()</a>) and, of
1578 course, the prover will never be able to reason about
1579 <a href="appfunc.html">application-defined SQL functions</a>.
1580
1581 <a name="omitnoopjoin"></a>
1582
1583 </p><h1 id="the_omit_outer_join_optimization"><span>17. </span>The Omit OUTER JOIN Optimization</h1>
1584
1585 <p>
1586 Sometimes a LEFT or RIGHT JOIN can be completely omitted from a query without
1587 changing the result. This can happen if all of the following are
1588 true:
1589
1590 </p><p>
1591 </p><ol>
1592 <li> The query is not an aggregate
1593 </li><li> Either the query is DISTINCT or else the ON or USING clause
1594 on the OUTER JOIN constrains the join such that it matches
1595 only a single row
1596 </li><li> The right-hand table of the LEFT JOIN or the left-hand table of
1597 a RIGHT JOIN is not be used anywhere
1598 in the query outside of its own USING or ON clause.
1599 </li></ol>
1600
1601 <p>
1602 OUTER JOIN elimination often comes up when OUTER JOINs are used
1603 inside of views, and then the view is used in such as way that
1604 none of the columns on the right-hand table of the LEFT JOIN or
1605 on the left-hand table of a RIGHT JOIN are referenced.
1606
1607 </p><p>
1608 Here is a simple example of omitting a LEFT JOIN:
1609
1610 </p><div class="codeblock"><pre>CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
1611 CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
1612 CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
1613
1614 SELECT v1, v3 FROM t1
1615 LEFT JOIN t2 ON (t1.ipk=t2.ipk)
1616 LEFT JOIN t3 ON (t1.ipk=t3.ipk)
1617 </pre></div>
1618
1619 <p>
1620 The t2 table is completely unused in the query above, and so the
1621 query planner is able to implement the query as if it were written:
1622
1623 </p><div class="codeblock"><pre>SELECT v1, v3 FROM t1
1624 LEFT JOIN t3 ON (t1.ipk=t3.ipk)
1625 </pre></div>
1626
1627 <p>
1628 As of this writing, only LEFT JOINs are eliminated. This optimize
1629 has not yet been generalized to work with RIGHT JOINs as RIGHT JOIN
1630 is a relatively new addition to SQLite. That asymmetry will probably
1631 be corrected in a future release.
1632
1633
1634 <a name="constprop"></a>
1635
1636 </p><h1 id="the_constant_propagation_optimization"><span>18. </span>The Constant Propagation Optimization</h1>
1637
1638 <p>
1639 When a WHERE clause contains two or more equality constraints connected
1640 by the AND operator such that all of the <a href="datatype3.html#affinity">affinities</a> of the various
1641 constraints are the same, then SQLite might use the transitive property
1642 of equality to construct new "virtual" constraints that can be used to
1643 simplify expressions and/or improve performance. This is called the
1644 "constant-propagation optimization".
1645
1646 </p><p>
1647 For example, consider the following schema and query:
1648
1649 </p><div class="codeblock"><pre>CREATE TABLE t1(a INTEGER PRIMARY KEY, b INT, c INT);
1650 SELECT * FROM t1 WHERE a=b AND b=5;
1651 </pre></div>
1652
1653 <p>
1654 SQLite looks at the "a=b" and "b=5" constraints and deduces that
1655 if those two constraints are true, then it must also be the case
1656 that "a=5" is true. This means that the desired row can be looked up
1657 quickly using a value of 5 for the INTEGER PRIMARY KEY.
1658 </p><p align="center"><small><i>This page was last updated on 2025-05-31 13:08:22Z </small></i></p>
1659