If I use SQLite auto increment on a column, does it automatically maintain an index on that column?

Question

I am using auto increment on an integer data column in SQLite. Since it is auto increment, the data is already sorted by that column in ascending order. So, I was wondering if SQLite will perform a binary search over the auto increment column whenever a data is searched by that column.

Answer 1

Effectively yes, but not really.

That is, all AUTOINCREMENT does is add a constraint that requires the value assigned to the column to be higher than any existing value, or higher than any value that has been used, in that column.

But there's more to it than that it is your_column INTEGER PRIMARY KEY (AUTOINCREMENT can only be used on such a column and there can only be 1 such column per table) makes that column an alias of the hidden rowid column.

The rowid is what is indexed, and is basically the most primary index and the most efficient, which always exists unless the table is defined using the WITHOUT ROWID keyword.

So an AUTOINCREMENT column is an alias of the rowid column and uses a differnt, more expensive algorithm than an alias of the rowid without AUTOINCREMENT.

That is without AUTOINCREMENT the value generated for the rowid column will find the maximum value in the table and increment it. Unless that value exceeds 9223372036854775807 in which case SQlite will make some attempts to find an unused lower value (normally between 1 and 9223372036854775807).

With AUTOINCREMENT the algorithm takes the higher value of the maximum value and a value stored in the table sqlite_sequence for the respective table and uses that (thus any deleted higher valueswill not be re-used). However if 9223372036854775807 has been used then an SQLITE_FULL error will be raised.

The following should be noted :-

The AUTOINCREMENT keyword imposes extra CPU, memory, disk space, and disk I/O overhead and should be avoided if not strictly needed. It is usually not needed.

SQLite Autoincrement you may well want to read this.

Additional

regrading the comment :-

If I don't use AUTOINCREMENT I have to explicitly create unique integer IDs and then insert them in database each time a new row is inserted.

The following demonstrates that there is no requirement for AUTOINCREMENT:-

CREATE TABLE IF NOT EXISTS xyz (ID INTEGER PRIMARY KEY);
INSERT INTO xyz VALUES(null);
SELECT * FROM xyz;

After running twice the result is :-