How to retrieve closest value based on look-up table?

Question

I'm attempting to create a query that will find the closest value from one table and return its ID into the resulting table.

Below is an example that should describe the situation better.

Sample Data

These two tables will exist in the SQL database.

Main Table

+----+-------------+
| ID | Measurement |
+----+-------------+
|  1 | 0.24        |
|  2 | 0.5         |
|  3 | 0.14        |
|  4 | 0.68        |
+----+-------------+

Look-up Table

+----+---------------+
| ID | Nominal Value |
+----+---------------+
|  1 | 0.1           |
|  2 | 0.2           |
|  3 | 0.3           |
|  4 | 0.4           |
|  5 | 0.5           |
|  6 | 0.6           |
|  7 | 0.7           |
|  8 | 0.8           |
|  9 | 0.9           |
+----+---------------+

Goal

This will be the result of a query. Measurements should not be on the border (0.25 for example).

+----+-------------+-----------+
| ID | Measurement | Lookup ID |
+----+-------------+-----------+
|  1 | 0.24        |         2 |
|  2 | 0.5         |         5 |
|  3 | 0.14        |         1 |
|  4 | 0.68        |         7 |
+----+-------------+-----------+

Is there a query that would be able to return this kind of result?

This sounds very much like a spatial "nearest" search, which can be implemented to use certain special types of indexes. — Colin 't Hart, Aug 12 '14 at 20:59
Do you need this for a whole table at once or for a single or selected rows only? Also, always declare your RDBMS and version, please. — Erwin Brandstetter, Aug 13 '14 at 4:43
Nice to see all of the different approaches here. And it's nice to have solutions for different DBMSes too. — Colin 't Hart, Aug 13 '14 at 9:25
I would specify the RDBMS and version, if I could. I'm working on migrating an Excel file with multiple tables over to some type of database. However, this is an internship and doubt a RDBMS will be selected before I leave. Currently, I'm making a mock-up of the table structures and queries in Microsoft Access 2010. — pjbollinger, Aug 13 '14 at 11:59

Lennart · Accepted Answer · 2014-08-12 21:04:51Z

Not sure what DBMS you use, but quite a few support window functions these days:

SELECT id, measurement, lookupid
FROM (
    SELECT t1.id, t1.measurement, t2.id as lookupid
         , row_number() over (partition by t1.id
                              order by abs(t1.measurement - t2.nominal) desc
                             ) as rn
    FROM main t1
    CROSS JOIN lookup t2
) AS T
WHERE rn = 1;

Community · Accepted Answer · 2017-04-13 12:42:51Z

A couple of queries tested and optimized for Postgres 9.3. All return the same, all are basically standard SQL, but no RDBMS supports the standard completely.

In particular, the first one uses a LATERAL JOIN, which is missing in Oracle or MySQL. Test which performs best.
All of them use index-only scans on the lookup table in Postgres. Obviously, lookup.nominal_value needs to be indexed. I suggest to make it UNIQUE because it seems like the column should be unique, and because that also creates the all-important index automatically.

LATERAL JOIN

SELECT m.id, m.measurement, l.nominal_value
FROM   measurement m
JOIN LATERAL (
   (
   SELECT nominal_value - m.measurement AS diff, nominal_value
   FROM   lookup
   WHERE  nominal_value >= m.measurement
   ORDER  BY nominal_value
   LIMIT  1
   )
   UNION  ALL
   (
   SELECT m.measurement - nominal_value, nominal_value
   FROM   lookup
   WHERE  nominal_value <= m.measurement
   ORDER  by nominal_value DESC
   LIMIT  1
   )
   ORDER  BY 1  -- NULLS LAST is default
   LIMIT  1
   ) l ON TRUE;

All parentheses required for UNION. Related answer:
Postgres 9.2 select multiple specific rows in one query

Correlated subqueries in a subquery

SELECT id, measurement
      ,CASE WHEN hi - measurement > measurement - lo
         THEN lo
         ELSE COALESCE(hi, lo)  -- cover all possible NULL values
       END AS nominal_value
FROM (
   SELECT id, measurement
         ,(SELECT nominal_value
           FROM   lookup
           WHERE  nominal_value >= m.measurement
           ORDER  BY nominal_value
           LIMIT  1) AS hi
         ,(SELECT nominal_value
           FROM   lookup
           WHERE  nominal_value <= m.measurement
           ORDER  by nominal_value DESC
           LIMIT  1) AS lo   -- cover possible NULL values
   FROM   measurement m
   ) sub;

Correlated subqueries in a CTE

WITH cte AS (
   SELECT id, measurement
         ,(SELECT nominal_value
           FROM   lookup
           WHERE  nominal_value >= m.measurement
           ORDER  BY nominal_value
           LIMIT  1) AS hi
         ,(SELECT nominal_value
           FROM   lookup
           WHERE  nominal_value <= m.measurement
           ORDER  by nominal_value DESC
           LIMIT  1) AS lo
   FROM   measurement m
   )
SELECT id, measurement
      ,CASE WHEN hi - measurement > measurement - lo
         THEN lo
         ELSE COALESCE(hi, lo)  -- cover all possible NULL values
       END AS nominal_value
FROM cte;

Nested correlated subqueries

SELECT id, measurement
      ,(SELECT nominal_value FROM (
         (
         SELECT nominal_value - m.measurement, nominal_value
         FROM   lookup
         WHERE  nominal_value >= m.measurement
         ORDER  BY nominal_value
         LIMIT  1
         )
         UNION  ALL
         (
         SELECT m.measurement - nominal_value, nominal_value
         FROM   lookup
         WHERE  nominal_value <= m.measurement
         ORDER  by nominal_value DESC
         LIMIT  1
         )
         ORDER  BY 1
         LIMIT  1
         ) sub
         ) AS nominal_value
FROM   measurement m;

SQL Fiddle.

Oracle supports lateral joins since 12c (include Microsoft's keyword using apply) docs.oracle.com/database/121/SQLRF/… — a_horse_with_no_name, Apr 8 '16 at 16:14

Daniel Hutmacher · Accepted Answer · 2014-08-12 20:44:04Z

This is entirely possible, although the only way I can think of to solve this is quite inefficient and really doesn't scale very well.

SELECT t.ID, t.Measurement,
    (SELECT TOP 1 lkp.ID
     FROM lookupTable AS lkp
     ORDER BY ABS(lkp.NominalValue-t.Measurement)) AS LookupID
FROM mainTable AS t

Another solution, that might scale/perform better, uses ordered window functions (available on SQL Server 2012 and 2014 as well as a few other database platforms, but not Azure).

WITH lkp AS (
    SELECT ID,
           --- fromValue is the average of the previous NominalValue and this one:
           (NominalValue+LAG(NominalValue, 1) OVER (ORDER BY NominalValue))/2.0 AS fromValue,
           --- toValue is the average of the next NominalValue and this one:
           (NominalValue+LEAD(NominalValue, 1) OVER (ORDER BY NominalValue))/2.0 AS toValue
    FROM dbo.LookupTable)

SELECT t.ID, t.Measurement, lkp.ID AS LookupID
FROM MainTable AS t
LEFT JOIN lkp ON
    --- The first lookup value will have fromValue=NULL
    (t.Measurement>=lkp.fromValue OR lkp.fromValue IS NULL) AND
    --- The last lookup value will have toValue=NULL
    (t.Measurement<lkp.toValue OR lkp.toValue IS NULL);

If this query still gives you performance issues, try creating a temporary lookup table, populate it with the rows from "lkp", then join "t" and "lkp" as above. I would probably give the temp table an index like

CREATE UNIQUE INDEX IX_temptable ON #temptable (fromValue) INCLUDE (toValue, ID);

Which solution is best for you is dependent primarily on how much data you have. Try the different solutions.

Colin 't Hart · Accepted Answer · 2014-08-12 21:18:20Z

I hope I'm not missing something obvious but the way I would query this so that it would scale for a very large lookup table is by observing the following:

It's possible to get a competent DBMS (I know PostgreSQL can do this) to use an index to

search for the largest lookup value smaller than our measurement, and to
search for the smallest lookup value larger than our measurement.

Once we have these two values we can determine which of the two is closer.

So, something like, untested:

with candidates as (
  select id, nominal_value
  from lookup_table
  where nominal_value >= measurement
  order by nominal_value
  limit 1
  union
  select id, nominal_value
  from lookup_table
  where nominal_value <= measurement
  order by nominal_value desc
  limit 1
)
select id
from candidates
order by abs(nominal_value - measurement)
limit 1;

should be lightning fast -- it's always basically two index lookups and nothing more.

Having written all this, it should be possible to use a window function to do just one index scan for the two candidate values on either side of the "measurement" value, but the above approach doesn't require window functions and should work on any DBMS which can "walk" an index instead of performing an order by.

It's late here. I hope the above isn't brainfart. – Colin 't Hart Aug 12 '14 at 21:19 — Colin 't Hart, Aug 12 '14 at 21:19

NMDJ · Accepted Answer · 2018-06-28 15:27:30Z

I used Lennart's answer, only needed to change desc to asc in the order by. It worked beautifully and was not overly complicated.

SEL

ECT id, measurement, lookupid 
FROM (
    SELECT t1.id, t1.measurement, t2.id as lookupid
         , row_number() over (partition by t1.id
                              order by abs(t1.measurement - t2.nominal) asc
                             ) as rn
    FROM main t1
    CROSS JOIN lookup t2
) AS T
WHERE rn = 1

Stack Exchange Network

current community

your communities

more stack exchange communities

How to retrieve closest value based on look-up table?

Sample Data

Main Table

Look-up Table

Goal

5 Answers 5

LATERAL JOIN

Correlated subqueries in a subquery

Correlated subqueries in a CTE

Nested correlated subqueries

Your Answer

Not the answer you're looking for? Browse other questions tagged table or ask your own question.

Linked

Hot Network Questions

How to retrieve closest value based on look-up table?

Sample Data

Main Table

Look-up Table

Goal

5 Answers 5

LATERAL JOIN

Correlated subqueries in a subquery

Correlated subqueries in a CTE

Nested correlated subqueries

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged table or ask your own question.

Linked

Related

Hot Network Questions