Поиск непрерывных диапазонов в наборе чисел

Question

У меня есть достаточно большой набор телефонных номеров (около 2 миллионов) в таблице базы данных. Эти числа были вставлены в блоки, поэтому существует множество непрерывных диапазонов чисел, от 10 до 10 тысяч в диапазоне. Некоторые из этих чисел используются и поэтому помечены как недоступные, остальные доступны. Учитывая определенный номер, мне нужен способ найти непрерывные диапазоны чисел, как выше, так и ниже этого числа. Диапазон должен продолжаться до тех пор, пока он не найдет недоступный номер или встретит границу двух диапазонов.

В приведенном примере следующий набор:

1000 
1001 
1002 
1010 
1011 
1012 
1013 
1020 
1021 
1022 

Выполнение поиска с использованием 1012 в качестве параметра должен возвращать 1010, 1011, 1012, 1013.

Что такое хороший способ формирования запроса к найти эти диапазоны? Мы используем NHibernate поверх SQL-сервера, решение с использованием либо отлично.

Answer 1

Теоретически элементы в наборе не имеют особого значения, поэтому я предполагаю, что у вас также есть столбец с постоянным идентификатором, который определяет порядок чисел.Что-то вроде этого:

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

Вы можете создать дополнительный столбец, который содержит результат 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 

Числа в том же диапазоне, будет иметь тот же результат в столбце Diff.

Answer 2

SQL не может действительно сделать это в одном запросе (за исключением наличия встроенных улучшений SQL, о которых я не знаю), поскольку SQL не может получить доступ к строке «before» или «after».

Вам необходимо пройти последовательность в цикле.

Вы можете попробовать NHibernates Enumerable, который не загружает объекты в память, а создает только прокси из них. На самом деле я не думаю, что это хорошая идея, потому что она создаст прокси для всего 2 миллионов номеров.

План Б, используйте пейджинг. Примерно так:

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++; 
} 

И то же самое для диапазона до в другом направлении.

Answer 3

Если вы используете сервер SQL, вы должны быть в состоянии сделать recursive query, присоединяемые на root.number = leaf.number +-

Если вы выберите номер из корня и из последней рекурсии, а уровень рекурсии должен иметь рабочий запрос.

Я бы сначала протестировал производительность, а затем, если неудовлетворительный поворот к подходу на основе курсора/строки (который в этом случае выполнил бы задание с одним полным сканированием, где рекурсия может завершиться неудачей, достигнув глубины глубины рекурсии).

В противном случае ваши варианты должны хранить данные по-разному и поддерживать список минимальных, максимальных номеров, связанных с таблицей.

Это может быть реализовано в триггерах с не столь высоким штрафом за однострочные обновления (обновления в одной строке базовой таблицы будут либо обновлять, удалять, либо разделять строку в таблице min-max, это может быть определяется путем запроса только «предыдущей» и «следующей» строк).

Answer 4

Используйте вспомогательную таблицу всех возможных последовательных значений или материализуйте ее в CTE, например.

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 
     );