| 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> > </b><i>expression</i><b> |
| 234 |
</b><i>column</i><b> >= </b><i>expression</i><b> |
| 235 |
</b><i>column</i><b> < </b><i>expression</i><b> |
| 236 |
</b><i>column</i><b> <= </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> > </b><i>column</i><b> |
| 240 |
</b><i>expression</i><b> >= </b><i>column</i><b> |
| 241 |
</b><i>expression</i><b> < </b><i>column</i><b> |
| 242 |
</b><i>expression</i><b> <= </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> >= </b><i>expr2</i><b> AND </b><i>expr1</i><b> <= </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>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<10 but '9'>'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> >= </b><i>x</i><b> AND </b><i>column</i><b> < </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<100) WHERE a>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<100 AND a>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 |
|