Fast binary search on text column in SQLite

Question

I have a table with about 80000 rows. I need to do searches like: SELECT * FROM names WHERE name LIKE 'abc%'. The wildcard is always at the end. Even with an index, it's too slow on Android. How can I make it faster? Can sqlite be forced to internally perform binary search on the text column?

Answer 1

A normal index does not order the entries case-insensitively, which would be required for LIKE.

To allow the LIKE optimization to work, you need a NOCASE index:

> CREATE TABLE names(name TEXT);
> CREATE INDEX i1 ON names(name);
> EXPLAIN QUERY PLAN SELECT * FROM names WHERE name LIKE 'abc%';
SCAN TABLE names USING COVERING INDEX i1 (~500000 rows)
> CREATE INDEX i2 ON names(name COLLATE NOCASE);
> EXPLAIN QUERY PLAN SELECT * FROM names WHERE name LIKE 'abc%';
SEARCH TABLE names USING COVERING INDEX i2 (name>? AND name<?) (~31250 rows)

If you'd want a case-sensitive search, you could use GLOB instead:

> EXPLAIN QUERY PLAN SELECT * FROM names WHERE name GLOB 'abc*';
SEARCH TABLE names USING COVERING INDEX i1 (name>? AND name<?) (~31250 rows)