title: How can I select the nearest value less-than and greater-than a given value efficiently?
body: <p>I have two tables, one for values one for location and am trying to interpolate location.  The tables have been simplified to the following:</p>
  
  <pre><code>CREATE TABLE value(
      Timestamp DATETIME2,
      Value float NOT NULL,
      PRIMARY KEY(Timestamp)
  );
  
  CREATE TABLE location(
      Timestamp DATETIME2,
      Position INT NOT NULL,
      PRIMARY KEY(Timestamp)
  ); 
  
  INSERT INTO value VALUES 
      ('2011/12/1 16:55:01', 1),
      ('2011/12/1 16:55:02', 5),
      ('2011/12/1 16:55:05', 10),
      ('2011/12/1 16:55:08', 6);
  
  INSERT INTO location VALUES 
      ('2011/12/1 16:55:00', 0),
      ('2011/12/1 16:55:05', 10),
      ('2011/12/1 16:55:10', 5)
  </code></pre>
  
  <p>The expected results would be</p>
  
  <pre><code>TimeStamp, Value, LowerTime, LowerLocation, UpperTime, UpperLocation
  2011-12-01 16:55:01,  1, 2011-12-01 16:55:00,  0, 2011-12-01 16:55:05, 10
  2011-12-01 16:55:02,  5, 2011-12-01 16:55:00,  0, 2011-12-01 16:55:05, 10
  2011-12-01 16:55:05, 10, 2011-12-01 16:55:05, 10, 2011-12-01 16:55:05, 10
  2011-12-01 16:55:08,  6, 2011-12-01 16:55:05, 10, 2011-12-01 16:55:10,  5
  </code></pre>
  
  <p>(Keep in mind this is simplified sample data to get the idea of the query I am trying to perform across.)</p>
  
  <p>To do the interpolation, I need to figure out the time and locations before and after a given values time.  I am currently doing this with a query that looks like:</p>
  
  <pre><code>SELECT 
      V.Timestamp, 
      V.Value, 
      (SELECT MAX(Timestamp) FROM dbo.location WHERE Timestamp &lt;= V.Timestamp) as LowerTime,
      (SELECT TOP 1 Position FROM dbo.location WHERE Timestamp &lt;= V.Timestamp ORDER BY timestamp DESC) as LowerLocation,
      (SELECT MIN(Timestamp) FROM dbo.location WHERE Timestamp &gt;= V.Timestamp) as UpperTime,
      (SELECT TOP 1 Position FROM dbo.location WHERE Timestamp &gt;= V.Timestamp ORDER BY timestamp ASC) as UpperLocation
   FROM 
      dbo.value V 
  </code></pre>
  
  <p>Now this works, but this obviously is doing a lot of work.  I'm thinking there must be a query simplification that I'm missing but I've been playing with it all morning and haven't come up with anything concrete.  Hoping someone here has a better idea.</p>
  
  <p>I am currently exploring if there is a way to figure out the LowerTime and UpperTime and use those in determining the Locations.  Something like:</p>
  
  <pre><code>SELECT 
      V.Timestamp, 
      V.Value, 
      (SELECT MAX(Timestamp) FROM dbo.location WHERE Timestamp &lt;= V.Timestamp) as LowerTime,
      (SELECT Position FROM dbo.location WHERE Timestamp = LowerTime) as LowerLocation,
      (SELECT MIN(Timestamp) FROM dbo.location WHERE Timestamp &gt;= V.Timestamp) as UpperTime,
      (SELECT Position FROM dbo.location WHERE Timestamp = UpperTime) as UpperLocation
   FROM 
      dbo.value V 
  </code></pre>
  
  <p>but this doesn't work.  </p>
  
  <p>EDIT1: Updated query as suggested.  However no visible change in execution time.</p>
  
  <p>EDIT2: Added my thoughts of the approach I am currently trying.</p>