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