SQLite, Sort by Index, faster without index

Question

I'm just reading this excellent guide to relational database query planners and indexes on SQLite site. In section 2.2. Sort By Index it says the following about sorting by index:

But does this really save time? The number of steps in the original indexless sort 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 the total time of NlogN is the same!

SQLite uses a cost-based query planner. When there are two or more ways of solving the same query, SQLite tries to estimate the total amount of time needed to run the query using each plan, and then uses the plan with the lowest estimated cost. A cost is computed mostly from the estimated time, and so this case could go either way depending on the table size and what WHERE clause constraints were available, and so forth. But generally speaking, the indexed sort would probably be chosen, if for no other reason, because it does not need to accumulate the entire result set in temporary storage before sorting and thus uses much less temporary storage.

So it says that amortized time complexity of sort with or without index should be same, O(N*logN), unless it's covering index in which case it's going to be O(N) as there will be no need to reference the table (this latter part is in next section).

However, from my testing it seems that sort with non-covering index is actually non-negligibly slower than sort without any index. I've used table with following schema for testing:

create table strings (a char(2), b char(4));

with 10 million records of random lowercase strings and I compared run times of select queries sorted by first column a for all possible cases:

1. sort without any index
2. sort with index on a
3. sort with covering index (on (a, b))

The runs time for these cases on my laptop with CPU Intel i5-7200U (4) @ 3.100GHz, 24 GiB of memory, and SQLite version 3.35.5, are:

1. Run Time: real 6.334 user 6.101944 sys 0.219462
2. Run Time: real 15.594 user 8.722529 sys 6.839844
3. Run Time: real 1.749 user 1.684229 sys 0.063246

I've tried to run this test several times, and the times are roughly same. Why is the sort with non-covering index so slow?

Here's the test script:

#!/bin/bash

file=test-index.sqlite
rows=$((10*1000*1000))

create_db_sql()
{
    cat <<-EOF
    create table strings (a, b);
    insert into strings values
    EOF
    tr -Cd a-z < /dev/urandom \
        | fold -b6 \
        | sed -E "s/(.{2})(.{4})/('\1','\2'),/; $rows{s/,$/;/;q}"
}

if [[ ! -f $file ]]; then
    create_db_sql | sqlite3 -batch $file
fi

sqlite3 -batch $file <<EOF
drop index if exists idxa;
drop index if exists idxab;
.output /dev/null

.timer on
select * from strings order by a;
.timer off

create index idxa on strings(a);
.timer on
select * from strings order by a;
.timer off

create index idxab on strings(a, b);
.timer on
select * from strings order by a;
.timer off
EOF

Answer 1

(This is an old unanswered question but I will answer anyway since it's a generic one and not related to a specific case).

As you noted from the docs:

generally speaking, the indexed sort would probably be chosen, if for no other reason, because it does not need to accumulate the entire result set in temporary storage before sorting and thus uses much less temporary storage.

Sometimes, using ANALYZE will have sqlite choose a better plan, if the stats show that the index is not very selective, but in this case even analyzing the database still yields the same plan: sqlite will scan the index in a order and then, for each row of the index, will go fetch the corresponding b value from the actual table.

However, this particular table is actually the worst situation for an index search:

• Millions of records;
• no WHERE clause to filter part of them using the index;
• since the values were inserted in random order, every a value correspond to one or more rows scattered along all pages of the table, thus needing to read a different page from disk for each returned row.

If the values were inserted in the table differently, the index sort would be faster, even if sqlite doesn't know it, just because the fetching of table pages would be much less scattered.

You can try it by using these queries:

CREATE TABLE strings2 AS SELECT * FROM strings ORDER BY a;
CREATE INDEX idxa2 ON strings2(a);

now compare times from

SELECT * FROM strings ORDER BY a;

and

SELECT * FROM strings2 ORDER BY a;

Sqlite will use the same plan and the same indexes for both query (it doesn't knows that strings2 is already sorted and it can't take advantage of it), but just the fact that the desired values are in the same disk page will speed up the query up to the same time of sorting without an index.