Documentation Source Text

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