Debian Codegraph @

www/queryplanner.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>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