Generating sequential numbers - the fast way
It is often necessary to generate a table with sequential numbers, up to a specified upper limit N. For small N, a simple INSERT in a WHILE loop will do. But, for large N, that solution becomes too slow. This script presents a different approach. It generates sequential numbers from the binary representation of N, as a polynom. In each iteration it doubles the number of records in the resulting table. Thus, the time required to generate sequential numbers decreases dramatically, compared to the WHILE-loop approach.
The script contains:
- a stored procedure with a fixed structure of the resulting table,
- a UDF (MS SQL 2000 only), which is more suitable for use on the fly, and
- stored procedures for performing comparation tests.
CREATE FUNCTION dbo.udf_Table_Of_Numbers_Seq (@from int, @to int)
RETURNS @res TABLE (num int)
-- Returns a table of sequential numbers within specified limits
-- The result table is populated sequentially
AS
BEGIN
DECLARE @i int
SET @i = @from
WHILE @i <= @to
BEGIN
INSERT INTO @res (num) VALUES (@i)
SET @i = @i + 1
END
RETURN
END
GO
CREATE FUNCTION dbo.dec2bin (@n10 bigint) RETURNS varchar(100)
-- Returns a string with the binary representation of @n10
AS
BEGIN
DECLARE @res varchar(100)
DECLARE @tmp bigint
SET @res = ''
SET @tmp = @n10;
WHILE @tmp > 0
BEGIN
SET @res = CONVERT(char(1), @tmp % 2) + @res
SET @tmp = @tmp / 2
END
RETURN (@res)
END
GO
CREATE FUNCTION dbo.udf_Table_Of_Numbers_Bin (@from bigint, @to bigint)
RETURNS @res TABLE (num int)
-- Returns a table of sequential numbers within specified limits
-- The result table is populated using the Horner polynom formula
-- P(x) = A[n] * X^n + A[n-1] * X^(n-1) + ... + A[1] * X + A[0] =
-- = ((...(((A[n] * X + A[n-1]) * X) + A[n-2]) ...) * X + A[1]) * X + A[0]
-- The binary representation (for X = 2) is used.
-- In each iteration the number of records in the table is doubled and
-- one more record is added if A[i] = 1.
AS
BEGIN
-- Returns a
DECLARE @total bigint
DECLARE @current bigint
DECLARE @n2 varchar(100)
SET @total = @to - @from + 1
SET @n2 = dbo.dec2bin(@total) -- A string of 0's na 1' (the binary representation of @total)
SET @current = 0
WHILE @current < @total
BEGIN
-- Double the number of records in the result table
INSERT INTO @res (num)
SELECT @current + num AS num FROM @res
SET @current = 2 * @current
-- If the binary digit is 1, add one record
IF SUBSTRING(@n2, 1, 1) = '1'
BEGIN
INSERT INTO @res (num) VALUES (@from + @current)
SET @current = @current + 1
END
SET @n2 = STUFF(@n2, 1, 1, '')
END -- WHILE
RETURN
END
GO
CREATE TABLE Seq_Num (num int NOT NULL PRIMARY KEY)
GO
CREATE PROCEDURE Gen_Num_Bin (@from bigint, @to bigint)
AS
BEGIN
DECLARE @n2 varchar(100)
DECLARE @total bigint, @current bigint
SET NOCOUNT ON
DELETE FROM Seq_Num
SET @total = @to - @from + 1
-- Convert @total to binary representation
SET @n2 = ''
SET @current = @total;
WHILE @current > 0
BEGIN
SET @n2 = CONVERT(char(1), @current % 2) + @n2
SET @current = @current / 2
END
SET @current = 0
WHILE @current < @total
BEGIN
-- Double the number of records in the result table
INSERT INTO Seq_Num (num)
SELECT @current + num AS num FROM Seq_Num
SET @current = 2 * @current
-- If the binary digit is 1, add one record
IF SUBSTRING(@n2, 1, 1) = '1'
BEGIN
INSERT INTO Seq_Num (num) VALUES (@from + @current)
SET @current = @current + 1
END
SET @n2 = STUFF(@n2, 1, 1, '')
END -- WHILE
END
GO
CREATE PROCEDURE TEST_SEQ_NUM (@from bigint, @to bigint)
AS
BEGIN
DECLARE @start_time datetime
DECLARE @end_time datetime
DECLARE @elapsed_seq bigint
DECLARE @elapsed_bin bigint
DECLARE @total bigint
SET NOCOUNT ON
SET @start_time = GETDATE()
SELECT @total = count(*) FROM dbo.udf_Table_Of_Numbers_Seq(@from, @to)
SET @end_time = GETDATE()
SET @elapsed_seq = DATEDIFF(millisecond, @start_time, @end_time)
SET @start_time = GETDATE()
SELECT @total = count(*) FROM dbo.udf_Table_Of_Numbers_Bin(@from, @to)
SET @end_time = GETDATE()
SET @elapsed_bin = DATEDIFF(millisecond, @start_time, @end_time)
PRINT 'Generating sequential numbers from ' + CONVERT(varchar, @from) + ' to ' + CONVERT(varchar, @to)
PRINT 'Sequential: ' + CONVERT(varchar, @elapsed_seq) + ' ms'
PRINT 'Binary: ' + CONVERT(varchar, @elapsed_bin) + ' ms'
END
GO
CREATE PROCEDURE RUN_ALL_TESTS (@from bigint, @to bigint, @step bigint)
AS
BEGIN
DECLARE @current bigint
SET @current = @from
WHILE @current <= @to
BEGIN
EXECUTE TEST_SEQ_NUM 1, @current
SET @current = @current + @step
END
END
GO
-- EXECUTE RUN_ALL_TESTS 5000, 100000, 5000 
