| 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>Query Planning</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 |
Query Planning |
| 122 |
</div> |
| 123 |
<details class="fancy_toc"> |
| 124 |
<summary>Table Of Contents</summary> |
| 125 |
<div id="toc_sub"><div class="fancy-toc1"><a href="#_searching">1. Searching</a></div> |
| 126 |
<div class="fancy-toc2"><a href="#_tables_without_indices">1.1. Tables Without Indices</a></div> |
| 127 |
<div class="fancy-toc2"><a href="#_lookup_by_rowid">1.2. Lookup By Rowid</a></div> |
| 128 |
<div class="fancy-toc2"><a href="#_lookup_by_index">1.3. Lookup By Index</a></div> |
| 129 |
<div class="fancy-toc2"><a href="#_multiple_result_rows">1.4. Multiple Result Rows</a></div> |
| 130 |
<div class="fancy-toc2"><a href="#_multiple_and_connected_where_clause_terms">1.5. Multiple AND-Connected WHERE-Clause Terms</a></div> |
| 131 |
<div class="fancy-toc2"><a href="#_multi_column_indices">1.6. Multi-Column Indices</a></div> |
| 132 |
<div class="fancy-toc2"><a href="#_covering_indexes">1.7. Covering Indexes</a></div> |
| 133 |
<div class="fancy-toc2"><a href="#_or_connected_terms_in_the_where_clause">1.8. OR-Connected Terms In The WHERE Clause</a></div> |
| 134 |
<div class="fancy-toc1"><a href="#_sorting">2. Sorting</a></div> |
| 135 |
<div class="fancy-toc2"><a href="#_sorting_by_rowid">2.1. Sorting By Rowid</a></div> |
| 136 |
<div class="fancy-toc2"><a href="#_sorting_by_index">2.2. Sorting By Index</a></div> |
| 137 |
<div class="fancy-toc2"><a href="#_sorting_by_covering_index">2.3. Sorting By Covering Index</a></div> |
| 138 |
<div class="fancy-toc1"><a href="#_searching_and_sorting_at_the_same_time">3. Searching And Sorting At The Same Time</a></div> |
| 139 |
<div class="fancy-toc2"><a href="#_searching_and_sorting_with_a_multi_column_index">3.1. Searching And Sorting With A Multi-Column Index</a></div> |
| 140 |
<div class="fancy-toc2"><a href="#_searching_and_sorting_with_a_covering_index">3.2. Searching And Sorting With A Covering Index</a></div> |
| 141 |
<div class="fancy-toc2"><a href="#_partial_sorting_using_an_index_a_k_a_block_sorting_">3.3. Partial Sorting Using An Index (a.k.a. Block Sorting)</a></div> |
| 142 |
<div class="fancy-toc1"><a href="#_without_rowid_tables">4. WITHOUT ROWID tables</a></div> |
| 143 |
</div> |
| 144 |
</details> |
| 145 |
</div> |
| 146 |
|
| 147 |
|
| 148 |
|
| 149 |
|
| 150 |
|
| 151 |
|
| 152 |
<h2 style="margin-left:1.0em" notoc="1" id="overview"> Overview</h2> |
| 153 |
|
| 154 |
<p> |
| 155 |
The best feature of SQL (in <u>all</u> its implementations, not just SQLite) |
| 156 |
is that it is a <i>declarative</i> language, not a <i>procedural</i> |
| 157 |
language. When programming in SQL you tell the system <i>what</i> you |
| 158 |
want to compute, not <i>how</i> to compute it. The task of figuring out |
| 159 |
the <i>how</i> is delegated to the <i>query planner</i> subsystem within |
| 160 |
the SQL database engine.</p> |
| 161 |
|
| 162 |
<p>For any given SQL statement, there might be hundreds or thousands or |
| 163 |
even millions of different algorithms of performing the operation. All |
| 164 |
of these algorithms will get the correct answer, though some will run |
| 165 |
faster than others. |
| 166 |
The query planner is an |
| 167 |
<a href="https://en.wikipedia.org/wiki/Artificial_intelligence">AI</a> that |
| 168 |
tries to pick the fastest and most efficient algorithm for each SQL |
| 169 |
statement. |
| 170 |
</p> |
| 171 |
|
| 172 |
<p> |
| 173 |
Most of the time, the query planner in SQLite does a good job. |
| 174 |
However, the query planner needs indices to |
| 175 |
work with. |
| 176 |
These indices must normally be added by programmers. |
| 177 |
Rarely, the query planner AI will make a suboptimal algorithm |
| 178 |
choice. |
| 179 |
In those cases, programmers may want to provide additional |
| 180 |
hints to help the query planner do a better job. |
| 181 |
</p> |
| 182 |
|
| 183 |
<p> |
| 184 |
This document provides background information about how the |
| 185 |
SQLite query planner and query engine work. |
| 186 |
Programmers can use this information to help create better |
| 187 |
indexes, and provide hints to help the query planner when |
| 188 |
needed. |
| 189 |
</p> |
| 190 |
|
| 191 |
<p> |
| 192 |
Additional information is provided in the |
| 193 |
<a href="optoverview.html">SQLite query planner</a> and |
| 194 |
<a href="queryplanner-ng.html">next generation query planner</a> documents. |
| 195 |
</p> |
| 196 |
|
| 197 |
<a name="searching"></a> |
| 198 |
|
| 199 |
<h1 id="_searching"><span>1. </span> Searching</h1> |
| 200 |
|
| 201 |
<h2 id="_tables_without_indices"><span>1.1. </span> Tables Without Indices</h2> |
| 202 |
|
| 203 |
<p> |
| 204 |
Most tables in SQLite consist of zero or more rows with a unique integer |
| 205 |
key (the <a href="lang_createtable.html#rowid">rowid</a> or <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a>) followed by content. |
| 206 |
(The exception is <a href="withoutrowid.html">WITHOUT ROWID</a> tables.) |
| 207 |
The rows |
| 208 |
are logically stored in order of increasing rowid. As an example, this |
| 209 |
article uses a table named "FruitsForSale" which relates various fruits |
| 210 |
to the state |
| 211 |
where they are grown and their unit price at market. The schema is this: |
| 212 |
</p> |
| 213 |
|
| 214 |
<center><table><tr><td><pre> |
| 215 |
CREATE TABLE FruitsForSale( |
| 216 |
Fruit TEXT, |
| 217 |
State TEXT, |
| 218 |
Price REAL |
| 219 |
); |
| 220 |
</pre></table></center> |
| 221 |
|
| 222 |
|
| 223 |
<p> |
| 224 |
With some (arbitrary) data, such a table might be logically stored on disk |
| 225 |
as shown in figure 1: |
| 226 |
</p> |
| 227 |
|
| 228 |
<a name='fig1'></a> |
| 229 |
<p><center> |
| 230 |
<img src="images/qp/tab.gif" alt="figure 1"><br> |
| 231 |
Figure 1: Logical Layout Of Table "FruitsForSale" |
| 232 |
</center></p> |
| 233 |
|
| 234 |
|
| 235 |
<p> |
| 236 |
In this example, the rowids are not |
| 237 |
consecutive but they are ordered. SQLite usually creates rowids beginning |
| 238 |
with one and increasing by one with each added row. But if rows are |
| 239 |
deleted, gaps can appear in the sequence. And the application can control |
| 240 |
the rowid assigned if desired, so that rows are not necessarily inserted |
| 241 |
at the bottom. But regardless of what happens, the rowids are always |
| 242 |
unique and in strictly ascending order. |
| 243 |
</p> |
| 244 |
|
| 245 |
<p> |
| 246 |
Suppose you want to look up the price of peaches. The query would |
| 247 |
be as follows: |
| 248 |
</p> |
| 249 |
|
| 250 |
<center><table><tr><td><pre> |
| 251 |
SELECT price FROM fruitsforsale WHERE fruit='Peach'; |
| 252 |
</pre></table></center> |
| 253 |
|
| 254 |
|
| 255 |
<p> |
| 256 |
To satisfy this query, SQLite reads every row out of the |
| 257 |
table, checks to see if the "fruit" column has the value of "Peach" and if |
| 258 |
so, outputs the "price" column from that row. The process is illustrated |
| 259 |
by <a href="#fig2">figure 2</a> below. |
| 260 |
This algorithm is called a <i>full table scan</i> |
| 261 |
since the entire content of the |
| 262 |
table must be read and examined in order to find the one row of interest. |
| 263 |
With a table of only 7 rows, a full table scan is acceptable, |
| 264 |
but if the table contained 7 million rows, a full table scan might read |
| 265 |
megabytes of content in order to find a single 8-byte number. |
| 266 |
For that reason, one normally tries to avoid full table scans. |
| 267 |
</p> |
| 268 |
|
| 269 |
<a name='fig2'></a> |
| 270 |
<p><center> |
| 271 |
<img src="images/qp/fullscan.gif" alt="figure 2"><br> |
| 272 |
Figure 2: Full Table Scan |
| 273 |
</center></p> |
| 274 |
|
| 275 |
|
| 276 |
<h2 id="_lookup_by_rowid"><span>1.2. </span> Lookup By Rowid</h2> |
| 277 |
|
| 278 |
<p> |
| 279 |
One technique for avoiding a full table scan is to do lookups by |
| 280 |
rowid (or by the equivalent <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a>). To lookup the |
| 281 |
price of peaches, one would query for the entry with a rowid of 4: |
| 282 |
</p> |
| 283 |
|
| 284 |
<center><table><tr><td><pre> |
| 285 |
SELECT price FROM fruitsforsale WHERE rowid=4; |
| 286 |
</pre></table></center> |
| 287 |
|
| 288 |
|
| 289 |
<p> |
| 290 |
Since the information is stored in the table in rowid order, SQLite |
| 291 |
can find the correct row using a binary search. |
| 292 |
If the table contains N elements, the time required to look up the |
| 293 |
desired row is proportional to logN rather than being proportional |
| 294 |
to N as in a full table scan. If the table contains 10 million elements, |
| 295 |
that means the query will be on the order of N/logN or about 1 million |
| 296 |
times faster. |
| 297 |
</p> |
| 298 |
|
| 299 |
<a name='fig3'></a> |
| 300 |
<p><center> |
| 301 |
<img src="images/qp/rowidlu.gif" alt="figure 3"><br> |
| 302 |
Figure 3: Lookup By Rowid |
| 303 |
</center></p> |
| 304 |
|
| 305 |
|
| 306 |
<h2 id="_lookup_by_index"><span>1.3. </span> Lookup By Index</h2> |
| 307 |
<p> |
| 308 |
The problem with looking up information by rowid is that you probably |
| 309 |
do not care what the price of "item 4" is - you want to know the price |
| 310 |
of peaches. And so a rowid lookup is not helpful. |
| 311 |
</p> |
| 312 |
|
| 313 |
<p> |
| 314 |
To make the original query more efficient, we can add an index on the |
| 315 |
"fruit" column of the "fruitsforsale" table like this: |
| 316 |
</p> |
| 317 |
|
| 318 |
<center><table><tr><td><pre> |
| 319 |
CREATE INDEX Idx1 ON fruitsforsale(fruit); |
| 320 |
</pre></table></center> |
| 321 |
|
| 322 |
|
| 323 |
<p> |
| 324 |
An index is another table similar to the original "fruitsforsale" table |
| 325 |
but with the content (the fruit column in this case) stored in front of the |
| 326 |
rowid and with all rows in content order. |
| 327 |
<a href="#fig4">Figure 4</a> gives a logical view of the Idx1 index. |
| 328 |
The "fruit" column is the primary key used to order the elements of the |
| 329 |
table and the "rowid" is the secondary key used to break the tie when |
| 330 |
two or more rows have the same "fruit". In the example, the rowid |
| 331 |
has to be used as a tie-breaker for the "Orange" rows. |
| 332 |
Notice that since the rowid |
| 333 |
is always unique over all elements of the original table, the composite key |
| 334 |
of "fruit" followed by "rowid" will be unique over all elements of the index. |
| 335 |
</p> |
| 336 |
|
| 337 |
<a name='fig4'></a> |
| 338 |
<p><center> |
| 339 |
<img src="images/qp/idx1.gif" alt="figure 4"><br> |
| 340 |
Figure 4: An Index On The Fruit Column |
| 341 |
</center></p> |
| 342 |
|
| 343 |
|
| 344 |
<p> |
| 345 |
This new index can be used to implement a faster algorithm for the |
| 346 |
original "Price of Peaches" query. |
| 347 |
</p> |
| 348 |
|
| 349 |
<center><table><tr><td><pre> |
| 350 |
SELECT price FROM fruitsforsale WHERE fruit='Peach'; |
| 351 |
</pre></table></center> |
| 352 |
|
| 353 |
|
| 354 |
<p> |
| 355 |
The query starts by doing a binary search on the Idx1 index for entries |
| 356 |
that have fruit='Peach'. SQLite can do this binary search on the Idx1 index |
| 357 |
but not on the original FruitsForSale table because the rows in Idx1 are sorted |
| 358 |
by the "fruit" column. Having found a row in the Idx1 index that has |
| 359 |
fruit='Peach', the database engine can extract the rowid for that row. |
| 360 |
Then the database engines does a second binary search |
| 361 |
on the original FruitsForSale table to find the |
| 362 |
original row that contains fruit='Peach'. |
| 363 |
From the row in the FruitsForSale table, |
| 364 |
SQLite can then extract the value of the price column. |
| 365 |
This procedure is illustrated by <a href="#fig5">figure 5</a>. |
| 366 |
</p> |
| 367 |
|
| 368 |
<a name='fig5'></a> |
| 369 |
<p><center> |
| 370 |
<img src="images/qp/idx1lu1.gif" alt="figure 5"><br> |
| 371 |
Figure 5: Indexed Lookup For The Price Of Peaches |
| 372 |
</center></p> |
| 373 |
|
| 374 |
|
| 375 |
<p> |
| 376 |
SQLite has to do two binary searches to find the price of peaches using |
| 377 |
the method show above. But for a table with a large number of rows, this |
| 378 |
is still much faster than doing a full table scan. |
| 379 |
</p> |
| 380 |
|
| 381 |
<h2 id="_multiple_result_rows"><span>1.4. </span> Multiple Result Rows</h2> |
| 382 |
|
| 383 |
<p> |
| 384 |
In the previous query the fruit='Peach' constraint narrowed the result |
| 385 |
down to a single row. But the same technique works even if multiple |
| 386 |
rows are obtained. Suppose we looked up the price of Oranges instead of |
| 387 |
Peaches: |
| 388 |
</p> |
| 389 |
|
| 390 |
<center><table><tr><td><pre> |
| 391 |
SELECT price FROM fruitsforsale WHERE fruit='Orange' |
| 392 |
</pre></table></center> |
| 393 |
<a name='fig6'></a> |
| 394 |
<p><center> |
| 395 |
<img src="images/qp/idx1lu2.gif" alt="figure 6"><br> |
| 396 |
Figure 6: Indexed Lookup For The Price Of Oranges |
| 397 |
</center></p> |
| 398 |
|
| 399 |
|
| 400 |
<p> |
| 401 |
In this case, SQLite still does a single binary search to find the first |
| 402 |
entry of the index where fruit='Orange'. Then it extracts the rowid from |
| 403 |
the index and uses that rowid to lookup the original table entry via |
| 404 |
binary search and output the price from the original table. But instead |
| 405 |
of quitting, the database engine then advances to the next row of index |
| 406 |
to repeat the process for next fruit='Orange' entry. Advancing to the |
| 407 |
next row of an index (or table) is much less costly than doing a binary |
| 408 |
search since the next row is often located on the same database page as |
| 409 |
the current row. In fact, the cost of advancing to the next row is so |
| 410 |
cheap in comparison to a binary search that we usually ignore it. So |
| 411 |
our estimate for the total cost of this query is 3 binary searches. |
| 412 |
If the number of rows of output is K and the number of rows in the table |
| 413 |
is N, then in general the cost of doing the query is proportional |
| 414 |
to (K+1)*logN. |
| 415 |
</p> |
| 416 |
|
| 417 |
<h2 id="_multiple_and_connected_where_clause_terms"><span>1.5. </span> Multiple AND-Connected WHERE-Clause Terms</h2> |
| 418 |
|
| 419 |
<p> |
| 420 |
Next, suppose that you want to look up the price of not just any orange, |
| 421 |
but specifically California-grown oranges. The appropriate query would |
| 422 |
be as follows: |
| 423 |
</p> |
| 424 |
|
| 425 |
<center><table><tr><td><pre> |
| 426 |
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA' |
| 427 |
</pre></table></center> |
| 428 |
<a name='fig7'></a> |
| 429 |
<p><center> |
| 430 |
<img src="images/qp/idx1lu3.gif" alt="figure 7"><br> |
| 431 |
Figure 7: Indexed Lookup Of California Oranges |
| 432 |
</center></p> |
| 433 |
|
| 434 |
|
| 435 |
<p> |
| 436 |
One approach to this query is to use the fruit='Orange' term of the WHERE |
| 437 |
clause to find all rows dealing with oranges, then filter those rows |
| 438 |
by rejecting any that are from states other than California. This |
| 439 |
process is shown by <a href="#fig7">figure 7</a> above. This is a perfectly |
| 440 |
reasonable approach in most cases. Yes, the database engine did have |
| 441 |
to do an extra binary search for the Florida orange row that was |
| 442 |
later rejected, so it was not as efficient as we might hope, though |
| 443 |
for many applications it is efficient enough. |
| 444 |
</p> |
| 445 |
|
| 446 |
<p> |
| 447 |
Suppose that in addition to the index on "fruit" there was also |
| 448 |
an index on "state". |
| 449 |
</p> |
| 450 |
|
| 451 |
<center><table><tr><td><pre> |
| 452 |
CREATE INDEX Idx2 ON fruitsforsale(state); |
| 453 |
</pre></table></center> |
| 454 |
<a name='fig8'></a> |
| 455 |
<p><center> |
| 456 |
<img src="images/qp/idx2.gif" alt="figure 8"><br> |
| 457 |
Figure 8: Index On The State Column |
| 458 |
</center></p> |
| 459 |
|
| 460 |
|
| 461 |
<p> |
| 462 |
The "state" index works just like the "fruit" index in that it is a |
| 463 |
new table with an extra column in front of the rowid and sorted by |
| 464 |
that extra column as the primary key. The only difference is that |
| 465 |
in Idx2, the first column is "state" instead of "fruit" as it is with |
| 466 |
Idx1. In our example data set, there is more redundancy in the "state" |
| 467 |
column and so there are more duplicate entries. The ties are still |
| 468 |
resolved using the rowid. |
| 469 |
</p> |
| 470 |
|
| 471 |
<p> |
| 472 |
Using the new Idx2 index on "state", SQLite has another option for |
| 473 |
lookup up the price of California oranges: it can look up every row |
| 474 |
that contains fruit from California and filter out those rows that |
| 475 |
are not oranges. |
| 476 |
</p> |
| 477 |
|
| 478 |
<a name='fig9'></a> |
| 479 |
<p><center> |
| 480 |
<img src="images/qp/idx2lu1.gif" alt="figure 9"><br> |
| 481 |
Figure 9: Indexed Lookup Of California Oranges |
| 482 |
</center></p> |
| 483 |
|
| 484 |
|
| 485 |
<p> |
| 486 |
Using Idx2 instead of Idx1 causes SQLite to examine a different set of |
| 487 |
rows, but it gets the same answer in the end (which is very important - |
| 488 |
remember that indices should never change the answer, only help SQLite to |
| 489 |
get to the answer more quickly) and it does the same amount of work. |
| 490 |
So the Idx2 index did not help performance in this case. |
| 491 |
</p> |
| 492 |
|
| 493 |
<p> |
| 494 |
The last two queries take the same amount of time, in our example. |
| 495 |
So which index, Idx1 or Idx2, will SQLite choose? If the |
| 496 |
<a href="lang_analyze.html">ANALYZE</a> command has been run on the database, so that SQLite has |
| 497 |
had an opportunity to gather statistics about the available indices, |
| 498 |
then SQLite will know that the Idx1 index usually narrows the search |
| 499 |
down to a single item (our example of fruit='Orange' is the exception |
| 500 |
to this rule) whereas the Idx2 index will normally only narrow the |
| 501 |
search down to two rows. So, if all else is equal, SQLite will |
| 502 |
choose Idx1 with the hope of narrowing the search to as small |
| 503 |
a number of rows as possible. This choice is only possible because |
| 504 |
of the statistics provided by <a href="lang_analyze.html">ANALYZE</a>. If <a href="lang_analyze.html">ANALYZE</a> has not been |
| 505 |
run then the choice of which index to use is arbitrary. |
| 506 |
</p> |
| 507 |
|
| 508 |
<h2 id="_multi_column_indices"><span>1.6. </span> Multi-Column Indices</h2> |
| 509 |
|
| 510 |
<p> |
| 511 |
To get the maximum performance out of a query with multiple AND-connected |
| 512 |
terms in the WHERE clause, you really want a multi-column index with |
| 513 |
columns for each of the AND terms. In this case we create a new index |
| 514 |
on the "fruit" and "state" columns of FruitsForSale: |
| 515 |
</p> |
| 516 |
|
| 517 |
<center><table><tr><td><pre> |
| 518 |
CREATE INDEX Idx3 ON FruitsForSale(fruit, state); |
| 519 |
</pre></table></center> |
| 520 |
<a name='fig10'></a> |
| 521 |
<p><center> |
| 522 |
<img src="images/qp/idx3.gif" alt="figure 1"><br> |
| 523 |
Figure 1: A Two-Column Index |
| 524 |
</center></p> |
| 525 |
|
| 526 |
|
| 527 |
<p> |
| 528 |
A multi-column index follows the same pattern as a single-column index; |
| 529 |
the indexed columns are added in front of the rowid. The only difference |
| 530 |
is that now multiple columns are added. The left-most column is the |
| 531 |
primary key used for ordering the rows in the index. The second column is |
| 532 |
used to break ties in the left-most column. If there were a third column, |
| 533 |
it would be used to break ties for the first two columns. And so forth for |
| 534 |
all columns in the index. Because rowid is guaranteed |
| 535 |
to be unique, every row of the index will be unique even if all of the |
| 536 |
content columns for two rows are the same. That case does not happen |
| 537 |
in our sample data, but there is one case (fruit='Orange') where there |
| 538 |
is a tie on the first column which must be broken by the second column. |
| 539 |
</p> |
| 540 |
|
| 541 |
<p> |
| 542 |
Given the new multi-column Idx3 index, it is now possible for SQLite |
| 543 |
to find the price of California oranges using only 2 binary searches: |
| 544 |
</p> |
| 545 |
|
| 546 |
<center><table><tr><td><pre> |
| 547 |
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA' |
| 548 |
</pre></table></center> |
| 549 |
<a name='fig11'></a> |
| 550 |
<p><center> |
| 551 |
<img src="images/qp/idx3lu1.gif" alt="figure 11"><br> |
| 552 |
Figure 11: Lookup Using A Two-Column Index |
| 553 |
</center></p> |
| 554 |
|
| 555 |
|
| 556 |
<p> |
| 557 |
With the Idx3 index on both columns that are constrained by the WHERE clause, |
| 558 |
SQLite can do a single binary search against Idx3 to find the one rowid |
| 559 |
for California oranges, then do a single binary search to find the price |
| 560 |
for that item in the original table. There are no dead-ends and no |
| 561 |
wasted binary searches. This is a more efficient query. |
| 562 |
</p> |
| 563 |
|
| 564 |
<p> |
| 565 |
Note that Idx3 contains all the same information as the original |
| 566 |
<a href="#fig3">Idx1</a>. And so if we have Idx3, we do not really need Idx1 |
| 567 |
any more. The "price of peaches" query can be satisfied using Idx3 |
| 568 |
by simply ignoring the "state" column of Idx3: |
| 569 |
</p> |
| 570 |
|
| 571 |
<center><table><tr><td><pre> |
| 572 |
SELECT price FROM fruitsforsale WHERE fruit='Peach' |
| 573 |
</pre></table></center> |
| 574 |
<a name='fig12'></a> |
| 575 |
<p><center> |
| 576 |
<img src="images/qp/idx3lu2.gif" alt="figure 12"><br> |
| 577 |
Figure 12: Single-Column Lookup On A Multi-Column Index |
| 578 |
</center></p> |
| 579 |
|
| 580 |
|
| 581 |
<p> |
| 582 |
Hence, a good rule of thumb is that your database schema should never |
| 583 |
contain two indices where one index is a prefix of the other. Drop the |
| 584 |
index with fewer columns. SQLite will still be able to do efficient |
| 585 |
lookups with the longer index. |
| 586 |
</p> |
| 587 |
|
| 588 |
<a name="covidx"></a> |
| 589 |
|
| 590 |
<h2 id="_covering_indexes"><span>1.7. </span> Covering Indexes</h2> |
| 591 |
|
| 592 |
<p> |
| 593 |
The "price of California oranges" query was made more efficient through |
| 594 |
the use of a two-column index. But SQLite can do even better with a |
| 595 |
three-column index that also includes the "price" column: |
| 596 |
</p> |
| 597 |
|
| 598 |
<center><table><tr><td><pre> |
| 599 |
CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price); |
| 600 |
</pre></table></center> |
| 601 |
<a name='fig13'></a> |
| 602 |
<p><center> |
| 603 |
<img src="images/qp/idx4.gif" alt="figure 13"><br> |
| 604 |
Figure 13: A Covering Index |
| 605 |
</center></p> |
| 606 |
|
| 607 |
|
| 608 |
<p> |
| 609 |
This new index contains all the columns of the original FruitsForSale table that |
| 610 |
are used by the query - both the search terms and the output. We call |
| 611 |
this a "covering index". Because all of the information needed is in |
| 612 |
the covering index, SQLite never needs to consult the original table |
| 613 |
in order to find the price. |
| 614 |
</p> |
| 615 |
|
| 616 |
<center><table><tr><td><pre> |
| 617 |
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'; |
| 618 |
</pre></table></center> |
| 619 |
<a name='fig14'></a> |
| 620 |
<p><center> |
| 621 |
<img src="images/qp/idx4lu1.gif" alt="figure 14"><br> |
| 622 |
Figure 14: Query Using A Covering Index |
| 623 |
</center></p> |
| 624 |
|
| 625 |
|
| 626 |
<p> |
| 627 |
Hence, by adding extra "output" columns onto the end of an index, one |
| 628 |
can avoid having to reference the original table and thereby |
| 629 |
cut the number of binary searches for a query in half. This is a |
| 630 |
constant-factor improvement in performance (roughly a doubling of |
| 631 |
the speed). But on the other hand, it is also just a refinement; |
| 632 |
A two-fold performance increase is not nearly as dramatic as the |
| 633 |
one-million-fold increase seen when the table was first indexed. |
| 634 |
And for most queries, the difference between 1 microsecond and |
| 635 |
2 microseconds is unlikely to be noticed. |
| 636 |
</p> |
| 637 |
|
| 638 |
<a name="or_in_where"></a> |
| 639 |
|
| 640 |
<h2 id="_or_connected_terms_in_the_where_clause"><span>1.8. </span> OR-Connected Terms In The WHERE Clause</h2> |
| 641 |
|
| 642 |
<p> |
| 643 |
Multi-column indices only work if the constraint terms in the WHERE |
| 644 |
clause of the query are connected by AND. |
| 645 |
So Idx3 and Idx4 are helpful when the search is for items that |
| 646 |
are both Oranges and grown in California, but neither index would |
| 647 |
be that useful if we wanted all items that were either oranges |
| 648 |
<i>or</i> are grown in California. |
| 649 |
</p> |
| 650 |
|
| 651 |
<center><table><tr><td><pre> |
| 652 |
SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA'; |
| 653 |
</pre></table></center> |
| 654 |
|
| 655 |
|
| 656 |
<p> |
| 657 |
When confronted with OR-connected terms in a WHERE clause, SQLite |
| 658 |
examines each OR term separately and tries to use an index to |
| 659 |
find the rowids associated with each term. |
| 660 |
It then takes the union of the resulting rowid sets to find |
| 661 |
the end result. The following figure illustrates this process: |
| 662 |
</p> |
| 663 |
|
| 664 |
<a name='fig15'></a> |
| 665 |
<p><center> |
| 666 |
<img src="images/qp/orquery.gif" alt="figure 15"><br> |
| 667 |
Figure 15: Query With OR Constraints |
| 668 |
</center></p> |
| 669 |
|
| 670 |
|
| 671 |
<p> |
| 672 |
The diagram above implies that SQLite computes all of the rowids first |
| 673 |
and then combines them with a union operation before starting to do |
| 674 |
rowid lookups on the original table. In reality, the rowid lookups |
| 675 |
are interspersed with rowid computations. SQLite uses one index at |
| 676 |
a time to find rowids while remembering which rowids it has seen |
| 677 |
before so as to avoid duplicates. That is just an implementation |
| 678 |
detail, though. The diagram, while not 100% accurate, provides a good |
| 679 |
overview of what is happening. |
| 680 |
</p> |
| 681 |
|
| 682 |
<p> |
| 683 |
In order for the OR-by-UNION technique shown above to be useful, there |
| 684 |
must be an index available that helps resolve every OR-connected term |
| 685 |
in the WHERE clause. If even a single OR-connected term is not indexed, |
| 686 |
then a full table scan would have to be done in order to find the rowids |
| 687 |
generated by the one term, and if SQLite has to do a full table scan, it |
| 688 |
might as well do it on the original table and get all of the results in |
| 689 |
a single pass without having to mess with union operations and follow-on |
| 690 |
binary searches. |
| 691 |
</p> |
| 692 |
|
| 693 |
<p> |
| 694 |
One can see how the OR-by-UNION technique could also be leveraged to |
| 695 |
use multiple indices on queries where the WHERE clause has terms connected |
| 696 |
by AND, by using an intersect operator in place of union. Many SQL |
| 697 |
database engines will do just that. But the performance gain over using |
| 698 |
just a single index is slight and so SQLite does not implement that technique |
| 699 |
at this time. However, a future version SQLite might be enhanced to support |
| 700 |
AND-by-INTERSECT. |
| 701 |
</p> |
| 702 |
|
| 703 |
<a name="sorting"></a> |
| 704 |
|
| 705 |
<h1 id="_sorting"><span>2. </span> Sorting</h1> |
| 706 |
|
| 707 |
<p> |
| 708 |
SQLite (like all other SQL database engines) can also use indices to |
| 709 |
satisfy the ORDER BY clauses in a query, in addition to expediting |
| 710 |
lookup. In other words, indices can be used to speed up sorting as |
| 711 |
well as searching. |
| 712 |
</p> |
| 713 |
|
| 714 |
<p> |
| 715 |
When no appropriate indices are available, a query with an ORDER BY |
| 716 |
clause must be sorted as a separate step. Consider this query: |
| 717 |
</p> |
| 718 |
|
| 719 |
<center><table><tr><td><pre> |
| 720 |
SELECT * FROM fruitsforsale ORDER BY fruit; |
| 721 |
</pre></table></center> |
| 722 |
|
| 723 |
|
| 724 |
<p> |
| 725 |
SQLite processes this by gathering all the output of the query and then |
| 726 |
running that output through a sorter. |
| 727 |
</p> |
| 728 |
|
| 729 |
<a name='fig16'></a> |
| 730 |
<p><center> |
| 731 |
<img src="images/qp/obfruitnoidx.gif" alt="figure 16"><br> |
| 732 |
Figure 16: Sorting Without An Index |
| 733 |
</center></p> |
| 734 |
|
| 735 |
|
| 736 |
<p> |
| 737 |
If the number of output rows is K, then the time needed to sort is |
| 738 |
proportional to KlogK. If K is small, the sorting time is usually |
| 739 |
not a factor, but in a query such as the above where K==N, the time |
| 740 |
needed to sort can be much greater than the time needed to do a |
| 741 |
full table scan. Furthermore, the entire output is accumulated in |
| 742 |
temporary storage (which might be either in main memory or on disk, |
| 743 |
depending on various compile-time and run-time settings) |
| 744 |
which can mean that a lot of temporary storage is required to complete |
| 745 |
the query. |
| 746 |
</p> |
| 747 |
|
| 748 |
<h2 id="_sorting_by_rowid"><span>2.1. </span> Sorting By Rowid</h2> |
| 749 |
|
| 750 |
<p> |
| 751 |
Because sorting can be expensive, SQLite works hard to convert ORDER BY |
| 752 |
clauses into no-ops. If SQLite determines that output will |
| 753 |
naturally appear in the order specified, then no sorting is done. |
| 754 |
So, for example, if you request the output in rowid order, no sorting |
| 755 |
will be done: |
| 756 |
</p> |
| 757 |
|
| 758 |
<center><table><tr><td><pre> |
| 759 |
SELECT * FROM fruitsforsale ORDER BY rowid; |
| 760 |
</pre></table></center> |
| 761 |
<a name='fig17'></a> |
| 762 |
<p><center> |
| 763 |
<img src="images/qp/obrowid.gif" alt="figure 17"><br> |
| 764 |
Figure 17: Sorting By Rowid |
| 765 |
</center></p> |
| 766 |
|
| 767 |
|
| 768 |
<p> |
| 769 |
You can also request a reverse-order sort like this: |
| 770 |
</p> |
| 771 |
|
| 772 |
<center><table><tr><td><pre> |
| 773 |
SELECT * FROM fruitsforsale ORDER BY rowid DESC; |
| 774 |
</pre></table></center> |
| 775 |
|
| 776 |
|
| 777 |
<p> |
| 778 |
SQLite will still omit the sorting step. But in order for output to |
| 779 |
appear in the correct order, SQLite will do the table scan starting at |
| 780 |
the end and working toward the beginning, rather than starting at the |
| 781 |
beginning and working toward the end as shown in |
| 782 |
<a href="#fig17">figure 17</a>. |
| 783 |
</p> |
| 784 |
|
| 785 |
<h2 id="_sorting_by_index"><span>2.2. </span> Sorting By Index</h2> |
| 786 |
|
| 787 |
<p> |
| 788 |
Of course, ordering the output of a query by rowid is seldom useful. |
| 789 |
Usually one wants to order the output by some other column. |
| 790 |
</p> |
| 791 |
|
| 792 |
<p> |
| 793 |
If an index is available on the ORDER BY column, that index can be used |
| 794 |
for sorting. Consider the request for all items sorted by "fruit": |
| 795 |
</p> |
| 796 |
|
| 797 |
<center><table><tr><td><pre> |
| 798 |
SELECT * FROM fruitsforsale ORDER BY fruit; |
| 799 |
</pre></table></center> |
| 800 |
|
| 801 |
|
| 802 |
<a name='fig18'></a> |
| 803 |
<p><center> |
| 804 |
<img src="images/qp/obfruitidx1.gif" alt="figure 18"><br> |
| 805 |
Figure 18: Sorting With An Index |
| 806 |
</center></p> |
| 807 |
|
| 808 |
|
| 809 |
<p> |
| 810 |
The Idx1 index is scanned from top to bottom (or from bottom to top if |
| 811 |
"ORDER BY fruit DESC" is used) in order to find the rowids for each item |
| 812 |
in order by fruit. Then for each rowid, a binary search is done to lookup |
| 813 |
and output that row. In this way, the output appears in the requested order |
| 814 |
without the need to gather the entire output and sort it using a separate step. |
| 815 |
</p> |
| 816 |
|
| 817 |
<p> |
| 818 |
But does this really save time? The number of steps in the |
| 819 |
<a href="#fig16">original indexless sort</a> is proportional to NlogN since |
| 820 |
that is how much time it takes to sort N rows. But when we use Idx1 as |
| 821 |
shown here, we have to do N rowid lookups which take logN time each, so |
| 822 |
the total time of NlogN is the same! |
| 823 |
</p> |
| 824 |
|
| 825 |
<p> |
| 826 |
SQLite uses a cost-based query planner. When there are two or more ways |
| 827 |
of solving the same query, SQLite tries to estimate the total amount of |
| 828 |
time needed to run the query using each plan, and then uses the plan with |
| 829 |
the lowest estimated cost. A cost is computed mostly from the estimated |
| 830 |
time, and so this case could go either way depending on the table size and |
| 831 |
what WHERE clause constraints were available, and so forth. But generally |
| 832 |
speaking, the indexed sort would probably be chosen, if for no other |
| 833 |
reason, because it does not need to accumulate the entire result set in |
| 834 |
temporary storage before sorting and thus uses much less temporary storage. |
| 835 |
</p> |
| 836 |
|
| 837 |
<h2 id="_sorting_by_covering_index"><span>2.3. </span> Sorting By Covering Index</h2> |
| 838 |
|
| 839 |
<p> |
| 840 |
If a covering index can be used for a query, then the multiple rowid lookups |
| 841 |
can be avoided and the cost of the query drops dramatically. |
| 842 |
</p> |
| 843 |
|
| 844 |
<a name='fig19'></a> |
| 845 |
<p><center> |
| 846 |
<img src="images/qp/obfruitidx4.gif" alt="figure 19"><br> |
| 847 |
Figure 19: Sorting With A Covering Index |
| 848 |
</center></p> |
| 849 |
|
| 850 |
|
| 851 |
<p> |
| 852 |
With a covering index, SQLite can simply walk the index from one end to the |
| 853 |
other and deliver the output in time proportional to N and without having to |
| 854 |
allocate a large buffer to hold the result set. |
| 855 |
</p> |
| 856 |
|
| 857 |
<h1 id="_searching_and_sorting_at_the_same_time"><span>3. </span> Searching And Sorting At The Same Time</h1> |
| 858 |
|
| 859 |
<p> |
| 860 |
The previous discussion has treated searching and sorting as separate |
| 861 |
topics. But in practice, it is often the case that one wants to search |
| 862 |
and sort at the same time. Fortunately, it is possible to do this |
| 863 |
using a single index. |
| 864 |
</p> |
| 865 |
|
| 866 |
<h2 id="_searching_and_sorting_with_a_multi_column_index"><span>3.1. </span> Searching And Sorting With A Multi-Column Index</h2> |
| 867 |
|
| 868 |
<p> |
| 869 |
Suppose we want to find the prices of all kinds of oranges sorted in |
| 870 |
order of the state where they are grown. The query is this: |
| 871 |
</p> |
| 872 |
|
| 873 |
<center><table><tr><td><pre> |
| 874 |
SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state |
| 875 |
</pre></table></center> |
| 876 |
|
| 877 |
|
| 878 |
<p> |
| 879 |
The query contains both a search restriction in the WHERE clause |
| 880 |
and a sort order in the ORDER BY clause. Both the search and the sort |
| 881 |
can be accomplished at the same time using the two-column index Idx3. |
| 882 |
</p> |
| 883 |
|
| 884 |
<a name='fig20'></a> |
| 885 |
<p><center> |
| 886 |
<img src="images/qp/fruitobstate0.gif" alt="figure 20"><br> |
| 887 |
Figure 20: Search And Sort By Multi-Column Index |
| 888 |
</center></p> |
| 889 |
|
| 890 |
|
| 891 |
<p> |
| 892 |
The query does a binary search on the index to find the subset of rows |
| 893 |
that have fruit='Orange'. (Because the fruit column is the left-most column |
| 894 |
of the index and the rows of the index are in sorted order, all such |
| 895 |
rows will be adjacent.) Then it scans the matching index rows from top to |
| 896 |
bottom to get the rowids for the original table, and for each rowid does |
| 897 |
a binary search on the original table to find the price. |
| 898 |
</p> |
| 899 |
|
| 900 |
<p> |
| 901 |
You will notice that there is no "sort" box anywhere in the above diagram. |
| 902 |
The ORDER BY clause of the query has become a no-op. No sorting has to be |
| 903 |
done here because the output order is by the state column and the state |
| 904 |
column also happens to be the first column after the fruit column in the |
| 905 |
index. So, if we scan entries of the index that have the same value for |
| 906 |
the fruit column from top to bottom, those index entries are guaranteed to |
| 907 |
be ordered by the state column. |
| 908 |
</p> |
| 909 |
|
| 910 |
<a name="srchsortcovidx"></a> |
| 911 |
|
| 912 |
<h2 id="_searching_and_sorting_with_a_covering_index"><span>3.2. </span> Searching And Sorting With A Covering Index</h2> |
| 913 |
|
| 914 |
<p> |
| 915 |
A <a href="queryplanner.html#covidx">covering index</a> can also be used to search and sort at the same time. |
| 916 |
Consider the following: |
| 917 |
</p> |
| 918 |
|
| 919 |
<center><table><tr><td><pre> |
| 920 |
SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state |
| 921 |
</pre></table></center> |
| 922 |
<a name='fig21'></a> |
| 923 |
<p><center> |
| 924 |
<img src="images/qp/fruitobstate.gif" alt="figure 21"><br> |
| 925 |
Figure 21: Search And Sort By Covering Index |
| 926 |
</center></p> |
| 927 |
|
| 928 |
|
| 929 |
<p> |
| 930 |
As before, SQLite does a single binary search |
| 931 |
for the range of rows in the covering |
| 932 |
index that satisfy the WHERE clause, then scans that range from top to |
| 933 |
bottom to get the desired results. |
| 934 |
The rows that satisfy the WHERE clause are guaranteed to be adjacent |
| 935 |
since the WHERE clause is an equality constraint on the left-most |
| 936 |
column of the index. And by scanning the matching index rows from |
| 937 |
top to bottom, the output is guaranteed to be ordered by state since the |
| 938 |
state column is the very next column to the right of the fruit column. |
| 939 |
And so the resulting query is very efficient. |
| 940 |
</p> |
| 941 |
|
| 942 |
<p> |
| 943 |
SQLite can pull a similar trick for a descending ORDER BY: |
| 944 |
</p> |
| 945 |
|
| 946 |
<center><table><tr><td><pre> |
| 947 |
SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC |
| 948 |
</pre></table></center> |
| 949 |
|
| 950 |
|
| 951 |
<p> |
| 952 |
The same basic algorithm is followed, except this time the matching rows |
| 953 |
of the index are scanned from bottom to top instead of from top to bottom, |
| 954 |
so that the states will appear in descending order. |
| 955 |
</p> |
| 956 |
|
| 957 |
<a name="partialsort"></a> |
| 958 |
|
| 959 |
<h2 id="_partial_sorting_using_an_index_a_k_a_block_sorting_"><span>3.3. </span> Partial Sorting Using An Index (a.k.a. Block Sorting)</h2> |
| 960 |
|
| 961 |
<p> |
| 962 |
Sometimes only part of an ORDER BY clause can be satisfied using indexes. |
| 963 |
Consider, for example, the following query: |
| 964 |
</p> |
| 965 |
|
| 966 |
<center><table><tr><td><pre> |
| 967 |
SELECT * FROM fruitforsale ORDER BY fruit, price |
| 968 |
</pre></table></center> |
| 969 |
|
| 970 |
|
| 971 |
<p> |
| 972 |
If the covering index is used for the scan, the "fruit" column will appear |
| 973 |
naturally in the correct order, but when there are two or more rows with |
| 974 |
the same fruit, the price might be out of order. When this occurs, SQLite |
| 975 |
does many small sorts, one sort for each distinct value of fruit, rather |
| 976 |
than one large sort. Figure 22 below illustrates the concept. |
| 977 |
</p> |
| 978 |
|
| 979 |
<a name='fig22'></a> |
| 980 |
<p><center> |
| 981 |
<img src="images/qp/partial-sort.gif" alt="figure 22"><br> |
| 982 |
Figure 22: Partial Sort By Index |
| 983 |
</center></p> |
| 984 |
|
| 985 |
|
| 986 |
<p> |
| 987 |
In the example, instead of a single sort of 7 elements, there |
| 988 |
are 5 sorts of one-element each and 1 sort of 2 elements for the |
| 989 |
case of fruit=='Orange'. |
| 990 |
|
| 991 |
</p><p> |
| 992 |
The advantages of doing many smaller sorts instead of a single large sort |
| 993 |
are: |
| 994 |
</p><ol> |
| 995 |
<li>Multiple small sorts collectively use fewer CPU cycles than a single |
| 996 |
large sort. |
| 997 |
</li><li>Each small sort is run independently, meaning that much less information |
| 998 |
needs to be kept in temporary storage at any one time. |
| 999 |
</li><li>Those columns of the ORDER BY that are already in the correct order |
| 1000 |
due to indexes can be omitted from the sort key, further reducing |
| 1001 |
storage requirements and CPU time. |
| 1002 |
</li><li>Output rows can be returned to the application as each small sort |
| 1003 |
completes, and well before the table scan is complete. |
| 1004 |
</li><li>If a LIMIT clause is present, it might be possible to avoid scanning |
| 1005 |
the entire table. |
| 1006 |
</li></ol> |
| 1007 |
|
| 1008 |
<p>Because of these advantages, SQLite always tries to do a partial sort using an |
| 1009 |
index even if a complete sort by index is not possible.</p> |
| 1010 |
|
| 1011 |
<h1 id="_without_rowid_tables"><span>4. </span> WITHOUT ROWID tables</h1> |
| 1012 |
|
| 1013 |
<p> |
| 1014 |
The basic principles described above apply to both ordinary rowid tables |
| 1015 |
and <a href="withoutrowid.html">WITHOUT ROWID</a> tables. |
| 1016 |
The only difference is that the rowid column that serves as the key for |
| 1017 |
tables and that appears as the right-most term in indexes is replaced by |
| 1018 |
the PRIMARY KEY. |
| 1019 |
</p> |
| 1020 |
<p align="center"><small><i>This page was last updated on 2026-03-22 10:09:38Z </small></i></p> |
| 1021 |
|