How to speed up a search in a large sqlite database

Question

I'm trying to develop a Windows Phone app which is able to search for persons in a large(300,000 persons) sqlite database. The problem is that it takes half a minute to find a person.

Do you have any idea how I could make the search faster?

Here's my code:

var queryname = conn.Table<contacts>().Where(
    x =>
        (
            ((x.firstName.ToLower() == input1) && (x.lastName.ToLower() == input2))
            || ((x.firstName.ToLower() == input2) && (x.lastName.ToLower() == input1))
            || ((x.firstName.ToLower() == input1) && (x.lastName.ToLower().Contains(input2)))
            || ((x.lastName.ToLower().Contains(input1)) && (x.firstName.ToLower() == input2))                                                                                                      
        ));

var resultname = await queryname.ToListAsync();
Person1.Content = null;
foreach (var item in resultname)
{
    outputname = string.Format("{0} {1}", item.firstName, item.lastName);
}

Input 1 and 2 are the two words the user has typed in.

Thank you in advance,

Nadine

How about adding indexes to your table! – Uwe Keim Apr 16 '14 at 08:52 — Uwe Keim, Apr 16 '14 at 08:52

score 0 · Answer 1 · edited May 23 '17 at 12:05

There are several problems with this query.

The first one is ToLower conversion. In SQL this is translated to something like lower(firstname) = :input1 and this prevents sqlite from using of the index on firstname column if such index exists. And in this case sqlite is required to scan all 300k records instead of finding a very small fraction of records directly using index.

To mitigate this you can add additional columns to contacts table lowercase_firstname and lowercase_lastname and set their value from firstname and lastname in trigger on insert or update of contact table. You should add indices for this columns and filter by them to avoid calling lower in where clause.

The second problem is using of Contains. I'm not sure how exactly LINQ translates this to SQL but it doesn't have much options. It either

translates to something like: firstname like '%<input1>%'
or does in memory filtering

The second option requires reading all records from database and that wouldn't be quick. The first option doesn't use existing index on firstname column and requires full table scan.

Unfortunately at the moment there is no way in sqlite to do like search using index. So this can't be quick.

One option is to disallow searching inside first and last name and allow only search by first letters of the name. So that if input1=Rita user is able to find Rita but not Margarita. With this limitation it is possible search using index by issuing range query like this lowercase_firstname between 'Rita' and 'Rita{' (here { is the letter following z). This should help you with expressing between in LINQ.

How to speed up a search in a large sqlite database

1 Answers1