Finding continuous ranges in a set of numbers

Question

I have a fairly large set of phone numbers (about 2 million) in the database table. These numbers were inserted into blocks, so there are many continuous ranges of numbers, from 10 to 10 thousand in a range. Some of these numbers are used and therefore marked as inaccessible, others are available. Given a specific number, I need a way to find continuous ranges of numbers, both above and below that number. The range should continue until it finds an unavailable number or meets the border of two ranges.

For example, the following set is specified:

1000 1001 1002 1010 1011 1012 1013 1020 1021 1022 

Performing a search using 1012 because the parameter should return 1010, 1011, 1012, 1013.

What is a good way to generate a query to search for these ranges? We use NHibernate on top of the SQL server, a solution using either is excellent.

Answer 1

Theoretically, the elements in the set have no special meaning, so I assume that you also have a column with a constant identifier that defines the order of the numbers. Something like that:

 ID Number 1 1000 2 1001 3 1002 4 1010 5 1011 6 1012 7 1013 8 1020 9 1021 10 1022 

You can create an additional column containing the result Number - ID :

 ID Number Diff 1 1000 999 2 1001 999 3 1002 999 4 1010 1006 5 1011 1006 6 1012 1006 7 1013 1006 8 1020 1012 9 1021 1012 10 1022 1012 

Numbers in the same range will have the same result in the Diff column.

Answer 2

SQL cannot do this in one query (except for the presence of built-in SQL improvements that I don’t know about), because SQL cannot access the before or after string.

You need to go through the sequence in a loop.

You can try NHibernates Enumerable , which does not load entities into memory, but creates only proxies from them. Actually, I don’t think this is a good idea, because it will create a proxy for only 2 million numbers.

Plan B, use paging. More or less like this:

 List<PhoneNumber> result = new List<PhoneNumber>(); int input = 1012; int pageSize = 100; int currentPage = 0; int expectedNumber = input; bool carryOn = true; while(carryOn) { var numbers = session .CreateQuery("from PhoneNumber pn where pn.Number > :input") .SetInt("input", input) .SetFirstResult(currentPage * pageSize) .SetMaxResult(pageSize) .List<PhoneNumbers>(); foreach(var number in numbers) { expectNumber++; if (number.Number != expectedNumber) { carryOn = false; break; } result.Add(number); } currentPage++; } 

And the same for the range earlier in the other direction.

Answer 3

If you use a SQL server, you can make a recursive query that will connect to root.number = leaf.number + 1

If you select a number from the root and from the last recursion, and the recursion level should have a work request.

I would first test this performance, and then, if not satisfactory, let's move on to the cursor / line approach (which in this case will complete the task with one full scan, where the recursion may fail, reaching the depth of the recursion depth).

Otherwise, your parameters should store data in different ways and maintain a list of minimum, maximum numbers associated with the table.

This can actually be implemented in triggers with a not so high penalty for single-line updates (updates in one row of the base table will either update, delete, or split the row in the min-max table, this can be determined by querying only the "previous" and "next" lines.

Answer 4

Use a helper table of all possible consecutive values ​​or materialize it in a CTE, for example.

 WITH -- materialize a table of sequential integers l0 AS (SELECT 0 AS c UNION ALL SELECT 0), l1 AS (SELECT 0 AS c FROM l0 AS a, l0 AS b), l2 AS (SELECT 0 AS c FROM l1 AS a, l1 AS b), l3 AS (SELECT 0 AS c FROM l2 AS a, l2 AS b), l4 AS (SELECT 0 AS c FROM l2 AS a, l3 AS b), l5 AS (SELECT 0 AS c FROM l2 AS a, l4 AS b), nums AS (SELECT row_number() OVER(ORDER BY c) AS n FROM l5), -- materialize sample table MyTable (ID) AS ( SELECT 1000 UNION ALL SELECT 1001 UNION ALL SELECT 1002 UNION ALL SELECT 1010 UNION ALL SELECT 1011 UNION ALL SELECT 1012 UNION ALL SELECT 1013 UNION ALL SELECT 1020 UNION ALL SELECT 1021 UNION ALL SELECT 1022 ), -- materialize parameter table params (param) AS (SELECT 1012) SELECT MIN(N1.n) - 1 AS last_in_sequence FROM nums AS N1 CROSS JOIN params AS P1 WHERE N1.n > P1.param AND NOT EXISTS ( SELECT * FROM MyTable AS T1 WHERE N1.n = T1.ID );