Finding nearest numeric value

On 8/17/05 8:50 AM, "Poul Møller Hansen" <freebsd@pbnet.dk> wrote:

Does anyone know how to find the row with the nearest numeric value, not
necessarily an exact match ?

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

Does that do it for you?

Sean

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

Does that do it for you?

Sean

It does ideed, not that I understood how, but I will find out.
Thank you very much.

Poul

[snip]

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

This will scan the whole table and sort the results... and then pick
just one of it. Watch this:

db=> prepare test_01(bigint) as select *, (pk_col - $1) ^ 2 as d from
big_table order by d limit 1;
PREPARE
eb=> explain execute test_01(27163619);
QUERY PLAN
-------------------------------------------------------------------------------------
Limit (cost=31239164.71..31239164.72 rows=1 width=59)
-> Sort (cost=31239164.71..31505657.00 rows=106596914 width=59)
Sort Key: (((pk_col - $1))::double precision ^ 2::double
precision)
-> Seq Scan on big_table (cost=0.00..3149688.00
rows=106596914 width=59)
(4 rows)

The names were changed, this is a production DB, but the idea is:
big_table has around 100 million rows, and pk_col is the primary key on
it. Running the above query would take forever.

If you don't have an index on the numeric column, or if the table is
small, this might be your best choice... but if your table is big, and
you have an index on the numeric column, you should use something along:

select * number_col from big_table where number_col < CONSTANT order by
number_col desc limit 1

select * number_col from big_table where number_col > CONSTANT order by
number_col limit 1

You execute the 2 queries, which are very fast even for big tables if
you have an index on number_col, and then choose the row with the
smallest difference (you do this in your client program).

HTH,
Csaba.

Sean Davis wrote:

On 8/17/05 8:50 AM, "Poul M�ller Hansen" <freebsd@pbnet.dk> wrote:

Does anyone know how to find the row with the nearest numeric value, not
necessarily an exact match ?

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

Save yourself some cycles - use abs() instead of exponentiation.

--
Peter Fein pfein@pobox.com 773-575-0694

Basically, if you're not a utopianist, you're a schmuck. -J. Feldman

Poul Møller Hansen wrote:

Does anyone know how to find the row with the nearest numeric value, not
necessarily an exact match ?

While the other answers all do their job, and in one go too, I'd be
surprised if you found anything faster than:

SELECT myval FROM mytable WHERE myval > 1234 ORDER BY myval LIMIT 1
UNION ALL
SELECT myval FROM mytable WHERE myval < 1234 ORDER BY myval DESC LIMIT 1

That gives you (up to) two values to look at, but should use any index
you have on myval.

You can always sort the results by abs(myval) then if you don't want to
handle two values in the application layer.

--
Richard Huxton
Archonet Ltd

On 8/17/05 10:01 AM, "Poul Møller Hansen" <freebsd@pbnet.dk> wrote:

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

Does that do it for you?

Sean

It does ideed, not that I understood how, but I will find out.
Thank you very much.

Just a word (or several) of explanation, then....

To compute the distance between two points on a line, you can compute the
absolute value of the difference (4-2 is the same distance as 2-4, while the
latter is negative) or you can square the difference (just to make it
positive). You could use absolute value in the above query if you like--I
don't know which is faster, but they will give the same result.

As for the query structure, you can select calculations of columns as well
as the columns themselves. The "as d" part just gives the calculation a
nice name to use in the rest of the query and in the resulting output.

Sean

The only problem is that you can't use the order by/limit syntax inside
the union queries I guess, cause the query you proposed is giving a
syntax error. I also thought first to do it like this, but it won't
work. If it would, then you could wrap the thing in another query which
orders by the difference and limits to the first one ;-)

Cheers,
Csaba.

On Wed, Aug 17, 2005 at 17:35:37 +0200,
Csaba Nagy <nagy@ecircle-ag.com> wrote:

The only problem is that you can't use the order by/limit syntax inside
the union queries I guess, cause the query you proposed is giving a
syntax error. I also thought first to do it like this, but it won't
work. If it would, then you could wrap the thing in another query which
orders by the difference and limits to the first one ;-)

You probably can just add parenthesis. I think that the second ORDER BY
and LIMIT may be being applied to the UNION results which would be a
problem. Putting the second subquery in parens will take care of this if
that is the problem.

Csaba Nagy <nagy@ecircle-ag.com> writes:

The only problem is that you can't use the order by/limit syntax inside
the union queries I guess, cause the query you proposed is giving a
syntax error.

Parentheses are your friend ;-)

regards, tom lane

Yep, you're right. The following works and uses the index on pk_col:

prepare test_01 (bigint) as
select * from
(
(SELECT * FROM big_table WHERE pk_col > $1 ORDER BY pk_col LIMIT 1)
UNION ALL
(SELECT * FROM big_table WHERE pk_col < $1 ORDER BY pk_col DESC
LIMIT 1)
) as nearest
order by abs(pk_col - $1)
limit 1;

db=> explain execute test_01(12321);

QUERY
PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=2.12..2.12 rows=1 width=112)
-> Sort (cost=2.12..2.13 rows=2 width=112)
Sort Key: abs((pk_col - $1))
-> Subquery Scan nearest (cost=0.00..2.11 rows=2 width=112)
-> Append (cost=0.00..2.08 rows=2 width=59)
-> Subquery Scan "*SELECT* 1" (cost=0.00..1.04
rows=1 width=59)
-> Limit (cost=0.00..1.03 rows=1 width=59)
-> Index Scan using idx_pk_col on
big_table (cost=0.00..36639172.72 rows=35532914 width=59)
Index Cond: (pk_col > $1)
-> Subquery Scan "*SELECT* 2" (cost=0.00..1.04
rows=1 width=59)
-> Limit (cost=0.00..1.03 rows=1 width=59)
-> Index Scan Backward using
idx_pk_col on big_table (cost=0.00..36639172.72 rows=35532914 width=59)
Index Cond: (pk_col < $1)
(13 rows)

Cheers,
Csaba.

Richard Huxton wrote:

While the other answers all do their job, and in one go too, I'd be
surprised if you found anything faster than:

SELECT myval FROM mytable WHERE myval > 1234 ORDER BY myval LIMIT 1

Really? Aren't most things with ORDER BY O(n*log(n))?

Or is the optimizer smart enough to find an index on myval
and stop after the first one (assuming the index returned
things sequentially.

If not, it seems this could do things in O(n) time:
select min(abs(value - CONSTANT)) from tablename
followed by
select * from tablename where abs(value - CONSTANT) = [result]
though I'm sure someone could roll that up into a single statement.

Richard Huxton wrote:

Poul M�ller Hansen wrote:

Does anyone know how to find the row with the nearest numeric value,
not necessarily an exact match ?

While the other answers all do their job, and in one go too, I'd be
surprised if you found anything faster than:

SELECT myval FROM mytable WHERE myval > 1234 ORDER BY myval LIMIT 1
UNION ALL
SELECT myval FROM mytable WHERE myval < 1234 ORDER BY myval DESC LIMIT 1

That gives you (up to) two values to look at, but should use any index
you have on myval.

You can always sort the results by abs(myval) then if you don't want to
handle two values in the application layer.

Ahh, should that be >= and <= ? ;)

--
Peter Fein pfein@pobox.com 773-575-0694

Basically, if you're not a utopianist, you're a schmuck. -J. Feldman

To find the nearest value in number_column to some CONSTANT (where you
replace constant with a number), try:

select *,(number_column - CONSTANT)^2 as d from tablename order by d limit
1;

Does that do it for you?

Sean

It does ideed, not that I understood how, but I will find out.
Thank you very much.

Just a word (or several) of explanation, then....

To compute the distance between two points on a line, you can compute the
absolute value of the difference (4-2 is the same distance as 2-4, while the
latter is negative) or you can square the difference (just to make it
positive). You could use absolute value in the above query if you like--I
don't know which is faster, but they will give the same result.

As for the query structure, you can select calculations of columns as well
as the columns themselves. The "as d" part just gives the calculation a
nice name to use in the rest of the query and in the resulting output.

Sean

Thanks for the explanation, guess I was fast giving up understanding the
query as it is actually quite simple :)

Of course there are the performance issues as argued by others, but the
table do only contain around 800 rows, so this method is adequate.

Thank you all for the inputs.

Poul

On Wed, Aug 17, 2005 at 11:57:52 -0700,
Ron Mayer <rm_pg@cheapcomplexdevices.com> wrote:

Richard Huxton wrote:

While the other answers all do their job, and in one go too, I'd be
surprised if you found anything faster than:

SELECT myval FROM mytable WHERE myval > 1234 ORDER BY myval LIMIT 1

Really? Aren't most things with ORDER BY O(n*log(n))?

No. Index lookups are O(log(n)). And you need to do only a constant number
of index lookups (2 or 4 depending on whether the values are unique).