SQLite - getting closest value

Question

I have SQLite database and I have in it certain column of type "double". I want to get a row that has in this column value closest to a specified one.

For example, in my table I have:

id: 1; value: 47
id: 2; value: 56
id: 3; value: 51

And I want to get a row that has its value closest to 50. So I want to receive id: 3 (value = 51).

How can I achieve this goal?

Thanks.

Answer 1

Using an order-by, SQLite will scan the entire table and load all the values into a temporary b-tree to order them, making any index useless. This will be very slow and use a lot of memory on large tables:

explain query plan select * from 'table' order by abs(10 - value) limit 1;
0|0|0|SCAN TABLE table
0|0|0|USE TEMP B-TREE FOR ORDER BY

You can get the next lower or higher value using the index like this:

select min(value) from 'table' where x >= N;
select max(value) from 'table' where x <= N;

And you can use union to get both from a single query:

explain query plan 
        select min(value) from 'table' where value >= 10
  union select max(value) from 'table' where value <= 10;
1|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value>?)
2|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value<?)
0|0|0|COMPOUND SUBQUERIES 1 AND 2 USING TEMP B-TREE (UNION)

This will be pretty fast even on large tables. You could simply load both values and evaluate them in your code, or use even more sql to select one in various ways:

explain query plan select v from
   (      select min(value) as v from 'table' where value >= 10
    union select max(value) as v from 'table' where value <= 10)
  order by abs(10-v) limit 1;
2|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value>?)
3|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value<?)
1|0|0|COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)
0|0|0|SCAN SUBQUERY 1
0|0|0|USE TEMP B-TREE FOR ORDER BY

or

explain query plan select 10+v from
   (      select min(value)-10 as v from 'table' where value >= 10
    union select max(value)-10 as v from 'table' where value <= 10)
  group by v having max(abs(v)) limit 1;
2|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value>?)
3|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value<?)
1|0|0|COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)
0|0|0|SCAN SUBQUERY 1
0|0|0|USE TEMP B-TREE FOR GROUP BY

Since you're interested in values both arbitrarily greater and less than the target, you can't avoid doing two index searches. If you know that the target is within a small range, though, you could use "between" to only hit the index once:

explain query plan select * from 'table' where value between 9 and 11 order by abs(10-value) limit 1;
0|0|0|SEARCH TABLE table USING COVERING INDEX value_index (value>? AND value<?)
0|0|0|USE TEMP B-TREE FOR ORDER BY

This will be around 2x faster than the union query above when it only evaluates 1-2 values, but if you start having to load more data it will quickly become slower.

Answer 2

This should work:

SELECT * FROM table
ORDER BY ABS(? - value)
LIMIT 1

Where ? represents the value you want to compare against.