Documentation Source Text

Check-in [78db9f1266]
Login

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

Overview
Comment:Fix typos in queryplanner.in
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 78db9f1266a0a465d4aac36e02968903226a5fc9
User & Date: drh 2010-11-30 18:13:24
Context
2010-12-01
11:23
Change a testable statement mark in lang.in. check-in: 05fc2c982b user: dan tags: trunk
2010-11-30
18:13
Fix typos in queryplanner.in check-in: 78db9f1266 user: drh tags: trunk
12:11
Minor changes to lang_dropview.html. Add section to lang.in describing resolution of object names. check-in: 6ec0e9720c user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/queryplanner.in.

236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
...
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
...
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
figure 7 #fig7 idx1lu3.gif {Indexed Lookup Of California Oranges}
</tcl>

<p>
One approach to this query is to use the fruit='Orange' term of the WHERE
clause to find all rows dealing with oranges, then filter those rows
by rejecting any that are from states other than California.  This
process is shows by <a href="#fig7">figure 7</a> above.  This is a perfectly
reasonable approach in most cases.  Yes, the database engine did have
to do an extra binary search for the Florida orange row that was
later rejected, so it was not as efficient as we might hope, though
for many applications it is efficient enough.  
</p>

<p>
................................................................................
might as well do it on the original table and get all of the results in
a single pass without having to mess with union operations and follow-on
binary searches.
</p>

<p>
One can see how the OR-by-UNION technique could also be leveraged to
use multiple indices on query where the WHERE clause has terms connected
by AND, by using an intersect operator in place of union.  Many SQL
database engines will do just that.  But the performance gain over using
just a single index is slight and so SQLite does not implement that technique
at this time.  However, a future version SQLite might be enhanced to support
AND-by-INTERSECT.
</p>

................................................................................
of solving the same query, SQLite tries to estimate the total amount of
time needed to run the query using each plan, and then uses the plan with
the lowest estimated cost.  A cost is computed mostly from the estimated
time, and so this case could go either way depending on the table size and
what WHERE clause constraints were available, and so forth.  But generally
speaking, the indexed sort would probably be chosen, if for no other
reason, because it does not need to accumulate the entire result set in
temporary before sorting and thus uses much less temporary storage.
</p>

<h3>2.3 Sorting By Covering Index</h3>

<p>
If a covering index can be used for a query, then the multiple rowid looks
can be avoided and the cost of the query drops dramatically.
</p>

<tcl>
figure 19 #fig19 obfruitidx4.gif {Sorting With A Covering Index}
</tcl>

................................................................................
As before, SQLite does single binary search
for the range of rows in the covering
index that satisfy the WHERE clause, the scans that range from top to 
bottom to get the desired results.  
The rows that satisfy the WHERE clause are guaranteed to be adjacent
since the WHERE clause is an equality constraint on the left-most
column of the index.  And by scanning the matching index rows from
top to bottom, the output is guaranteed to be order by state since the
state column is the very next column to the right of the fruit column.
And so the resulting query is very efficient.
</p>

<p>
SQLite can pull a similar trick for a descending ORDER BY:
</p>







|







 







|







 







|





|







 







|







236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
...
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
...
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
figure 7 #fig7 idx1lu3.gif {Indexed Lookup Of California Oranges}
</tcl>

<p>
One approach to this query is to use the fruit='Orange' term of the WHERE
clause to find all rows dealing with oranges, then filter those rows
by rejecting any that are from states other than California.  This
process is shown by <a href="#fig7">figure 7</a> above.  This is a perfectly
reasonable approach in most cases.  Yes, the database engine did have
to do an extra binary search for the Florida orange row that was
later rejected, so it was not as efficient as we might hope, though
for many applications it is efficient enough.  
</p>

<p>
................................................................................
might as well do it on the original table and get all of the results in
a single pass without having to mess with union operations and follow-on
binary searches.
</p>

<p>
One can see how the OR-by-UNION technique could also be leveraged to
use multiple indices on queries where the WHERE clause has terms connected
by AND, by using an intersect operator in place of union.  Many SQL
database engines will do just that.  But the performance gain over using
just a single index is slight and so SQLite does not implement that technique
at this time.  However, a future version SQLite might be enhanced to support
AND-by-INTERSECT.
</p>

................................................................................
of solving the same query, SQLite tries to estimate the total amount of
time needed to run the query using each plan, and then uses the plan with
the lowest estimated cost.  A cost is computed mostly from the estimated
time, and so this case could go either way depending on the table size and
what WHERE clause constraints were available, and so forth.  But generally
speaking, the indexed sort would probably be chosen, if for no other
reason, because it does not need to accumulate the entire result set in
temporary storage before sorting and thus uses much less temporary storage.
</p>

<h3>2.3 Sorting By Covering Index</h3>

<p>
If a covering index can be used for a query, then the multiple rowid lookups
can be avoided and the cost of the query drops dramatically.
</p>

<tcl>
figure 19 #fig19 obfruitidx4.gif {Sorting With A Covering Index}
</tcl>

................................................................................
As before, SQLite does single binary search
for the range of rows in the covering
index that satisfy the WHERE clause, the scans that range from top to 
bottom to get the desired results.  
The rows that satisfy the WHERE clause are guaranteed to be adjacent
since the WHERE clause is an equality constraint on the left-most
column of the index.  And by scanning the matching index rows from
top to bottom, the output is guaranteed to be ordered by state since the
state column is the very next column to the right of the fruit column.
And so the resulting query is very efficient.
</p>

<p>
SQLite can pull a similar trick for a descending ORDER BY:
</p>