Documentation Source Text

Check-in [f81d69fb6a]
Login

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

Overview
Comment:Talk about partial index sorting in the queryplanner.html document.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f81d69fb6a98d6fcb9df195d455330a3cbf72a0b
User & Date: drh 2014-05-26 15:38:42
Context
2014-05-26
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
13:58
Fix typos in the new ALTER TABLE documentation and in the queryplanner.html document. check-in: be73465c0f user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Added images/qp/partial-sort.gif.

cannot compute difference between binary files

Changes to pages/queryplanner.in.

672
673
674
675
676
677
678
679

680
681




682




683
684
685
686
687
688
689





690



















691

<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>

<h2>To Be Continued...</h2>


<p>Further topics:</p>









<p><ul>
<li>How to construct a good index
<li>Joins and join-order
<li>Automatic transient indices
<li>How to determine what query plan SQLite is using
<li>Automatic detection of inefficient query plans
<li>Techniques for influencing what query plan SQLite chooses





</ul>



















</p>







|
>

<
>
>
>
>

>
>
>
>
|
<
<
<
<
<
<
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
672
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>