Have you ever faced a situation where you needed to fetch data from a large table in SQL Server quickly? If so, you know that scanning a large table can be time-consuming and can negatively impact the performance of your server. In this article, we will explore a technique called the binary search that can help you efficiently search for data in a sorted table.

The Issue at Hand

Imagine a scenario where a coworker from the marketing department approaches you with a request to fetch some data from a specific month a couple of years back. The table containing the data is large, and there is no index on the creation datetime column. Scanning the entire table would take a significant amount of time and could potentially impact the performance of the server.

The Binary Search

The binary search is a simple yet efficient way to search for a value in a sorted array, which in our case is a table column. The search is done by comparing the middle element of the array with the target value. If they are equal, the search is over. If not, you eliminate the half in which the target cannot be and repeat the process with the remaining half. This process continues until the target value is found or until there are no more elements to search.

By using the binary search technique, you can significantly reduce the number of steps required to find the target value, especially when dealing with large tables. The total number of steps required in the worst-case scenario is logarithmic, which is much smaller compared to iterating through each element of the table.

Implementing the Binary Search in SQL Server

To implement the binary search in SQL Server, you can use a combination of SQL statements and variables. Here is an example script that demonstrates how to perform a binary search:

/* 
    Run this script in your database
    It will find the value either equal to or immediately before the target. 
    Note that datetime precision is limited to 3 ms
*/

-- debug flag, if set, it will show the results for every iteration
DECLARE @debug bit = 0

-- @Table is the name of the table you want to search in.
DECLARE @Table varchar(128) = 'TableX' 

-- @Id is the name of the identity (id) column for the table 
DECLARE @ID varchar(128) = 'Id' 

-- @DateTimeColumn is the name of your creation datetime column in the table
DECLARE @DateTimeColumn varchar(128) = 'created_dt'

-- this is the target datetime value
DECLARE @TargetDateTime datetime = '2020-01-03 18:23:03'

DECLARE @Sql varchar(max)
SET @sql = '
-- this is your debug flag
DECLARE @debug bit = 

-- this is your target value
DECLARE @tdt datetime = ''''

-- this is the variable we store the middle value (the result of dividing) 
DECLARE @id bigint 

--this is your left and right boundaries respectively
DECLARE @l bigint, @r bigint

-- these are the variables we store the results of the current step search, datetime and table id respectively
DECLARE @dt datetime, @idr bigint

-- find first "left" and "right" values 
SELECT @l = MIN(), @r = MAX() FROM 

WHILE @l < @r
BEGIN
    -- expected id
    SET @id = @l + FLOOR((@r-@l)/2)
    
    -- find the value and id of the record
    SELECT TOP(1) @dt = , @idr =  FROM  WHERE  <= @id ORDER BY  DESC
    
    -- if debug is requested show current values
    IF( @debug = 1 )
    BEGIN
        SELECT ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
    END
    
    IF(@dt < @tdt)
        SET @l = @id + 1
    ELSE
        SET @r = @id
END

-- check if the neighboring records have a better match
DECLARE @t TABLE(id bigint, dt datetime, dlt float)
INSERT @t(id, dt, dlt)
SELECT TOP(1) , , ABS(CAST( AS float) - CAST(@tdt AS float)) 
  FROM  
 WHERE  < @idr 
ORDER BY  DESC

INSERT @t(id, dt, dlt) 
SELECT TOP(1) , , ABS(CAST( AS float) - CAST(@tdt AS float)) 
  FROM  
 WHERE  > @idr 
ORDER BY 

INSERT @t(id, dt, dlt) 
SELECT @idr, @dt, ABS(CAST(@dt AS float) - CAST(@tdt AS float))

SELECT TOP(1) @dt = dt, @idr = id FROM @t ORDER BY dlt, id 

SELECT 'Found Value' = @dt, 'Record Id' = @idr
'

SET @sql = REPLACE(
            REPLACE(
             REPLACE(
              REPLACE(
               REPLACE(@sql, '', @ID), 
              '', @Table), 
             '', CONVERT(varchar(50), @TargetDateTime, 121)),
            '', @debug),
           '', @DateTimeColumn)

EXEC (@sql)

Make sure to replace the placeholders in the script with the appropriate values for your table and column names. The script will find the value either equal to or immediately before the target datetime value.

Conclusion

The binary search is a powerful technique that can greatly improve the efficiency of searching for data in large tables in SQL Server. By implementing this technique, you can significantly reduce the time required to fetch data and minimize the impact on server performance. Remember to test and optimize your queries to ensure the best possible performance.

Next time you face a challenging data retrieval task, consider using the binary search technique to make your job easier and more efficient.