Documentation Source Text

Check-in [fee38cf31f]
Login

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

Overview
Comment:Fix typos and clarify the text on the Partial Sorting Using An Index section of queryplanner.html.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fee38cf31fdde875a5c3605bf22d2c9e151a2c4a
User & Date: drh 2014-05-26 21:43:53
Context
2014-05-26
22:49
Update the download page to support DLL snapshots. Update the change log for 3.8.5. check-in: 3eab08af2c user: drh tags: trunk
21:43
Fix typos and clarify the text on the Partial Sorting Using An Index section of queryplanner.html. check-in: fee38cf31f user: drh tags: trunk
15:38
Talk about partial index sorting in the queryplanner.html document. check-in: f81d69fb6a user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to pages/queryplanner.in.

673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
...
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702





703
704
705
706
707
708
709
710



711
712
713
714
715
716
717
<p>
The same basic algorithm is followed, except this time the matching rows
of the index are scanned from bottom to top instead of from top to bottom,
so that the states will appear in descending order.
</p>

<tcl>hd_fragment {partialsort}</tcl>
<h3>3.2 Parital Sorting Using An Index</h3>

<p>
Sometimes only part of an ORDER BY clause an be satisfied using indexes.
Consider, for example, the following query:
</p>

<tcl>
................................................................................
code {SELECT * FROM fruitforsale ORDER BY fruit, price}
</tcl>

<p>
If the covering index is used for the scan, the "fruit" column will appear
naturally in the correct order, but when there are two or more rows with
the same fruit, the price might be out of order.  When this occurs, SQLite
does many small sorts, one each for each distinct value of fruit, rather
than one large sort.  Figure 22 below illustrates the concept.
</p>

<tcl>
figure 22 #fig22 partial-sort.gif {Partial Sort By Index}
</tcl>






<p>
The advantages of doing many smaller sorts instead of a single large sort
are:
<ol>
<li>Multiple small sorts collectively use fewer CPU cycles than a single
    large sort.
<li>Each small sort is run independently, meaning that much less information
    needs to be kept in temporary storage at any one time.



<li>Output rows can be returned to the application before the table scan
    is complete.
<li>If a LIMIT clause is present, it might be possible to avoid scanning
    the entire table.
</ol>
Because of these advantages, SQLite tries to do a partial index sort whenever
it can.</p>







|







 







|







>
>
>
>
>








>
>
>
|
|



|
|
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
...
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
<p>
The same basic algorithm is followed, except this time the matching rows
of the index are scanned from bottom to top instead of from top to bottom,
so that the states will appear in descending order.
</p>

<tcl>hd_fragment {partialsort}</tcl>
<h3>3.2 Partial Sorting Using An Index</h3>

<p>
Sometimes only part of an ORDER BY clause an be satisfied using indexes.
Consider, for example, the following query:
</p>

<tcl>
................................................................................
code {SELECT * FROM fruitforsale ORDER BY fruit, price}
</tcl>

<p>
If the covering index is used for the scan, the "fruit" column will appear
naturally in the correct order, but when there are two or more rows with
the same fruit, the price might be out of order.  When this occurs, SQLite
does many small sorts, one sort for each distinct value of fruit, rather
than one large sort.  Figure 22 below illustrates the concept.
</p>

<tcl>
figure 22 #fig22 partial-sort.gif {Partial Sort By Index}
</tcl>

<p>
In the example, instead of a single sort of 7 elements, there
are 5 sorts of one-element each and 1 sort of 2 elements for the
case of fruit=='Orange'.

<p>
The advantages of doing many smaller sorts instead of a single large sort
are:
<ol>
<li>Multiple small sorts collectively use fewer CPU cycles than a single
    large sort.
<li>Each small sort is run independently, meaning that much less information
    needs to be kept in temporary storage at any one time.
<li>Those columns of the ORDER BY that are already in the correct order
    due to indexes can be omitted from the sort key, further reducing
    storage requirements and CPU time.
<li>Output rows can be returned to the application as each small sort
    completes, and well before the table scan is complete.
<li>If a LIMIT clause is present, it might be possible to avoid scanning
    the entire table.
</ol>
Because of these advantages, SQLite always tries to do a partial sort using an
index even if a complete sort by index is not possible.</p>