Documentation Source Text

Check-in [47810e77ef]
Login

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

Overview
Comment:Fix another typo in the query planner document.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | branch-3.10
Files: files | file ages | folders
SHA1: 47810e77efe44839b8e390ee9a8ce91f5aa6ddaf
User & Date: drh 2016-01-14 17:58:19.782
Context
2016-01-19
17:07
Add documentation for sqlite3_analyzer.exe and support for the "tools" download bundles. (check-in: dd586d2857 user: drh tags: branch-3.10)
2016-01-14
18:26
Merge updates from the 3.10 branch. (check-in: 885e891911 user: drh tags: trunk)
17:58
Fix another typo in the query planner document. (check-in: 47810e77ef user: drh tags: branch-3.10)
16:10
Fix typos in queryplaner.html (check-in: 316be08907 user: drh tags: branch-3.10)
Changes
Unified Diff Ignore Whitespace Patch
Changes to pages/queryplanner.in.
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
<tcl>figure 18 #fig18 obfruitidx1.gif {Sorting With An Index}</tcl>

<p>
The Idx1 index is scanned from top to bottom (or from bottom to top if
"ORDER BY fruit DESC" is used) in order to find the rowids for each item
in order by fruit.  Then for each rowid, a binary search is done to lookup
and output that row.  In this way, the output appears in the requested order
with the need to gather then entire output and sort it using a separate step.
</p>

<p>
But does this really save time?  The number of steps in the 
<a href="#fig16">original indexless sort</a> is proportional to NlogN since
that is how much time it takes to sort N rows.  But when we use Idx1 as
shown here, we have to do N rowid lookups which take logN time each, so







|







549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
<tcl>figure 18 #fig18 obfruitidx1.gif {Sorting With An Index}</tcl>

<p>
The Idx1 index is scanned from top to bottom (or from bottom to top if
"ORDER BY fruit DESC" is used) in order to find the rowids for each item
in order by fruit.  Then for each rowid, a binary search is done to lookup
and output that row.  In this way, the output appears in the requested order
without the need to gather the entire output and sort it using a separate step.
</p>

<p>
But does this really save time?  The number of steps in the 
<a href="#fig16">original indexless sort</a> is proportional to NlogN since
that is how much time it takes to sort N rows.  But when we use Idx1 as
shown here, we have to do N rowid lookups which take logN time each, so