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

Question

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

Например, учитывая следующий набор:

1000
1001
1002
1010
1011
1012
1013
1020
1021
1022

Выполнение поиска с использованием 1012 в качестве параметра должноreturn 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

Числа в одном диапазоне будут иметь одинаковый результат в столбце Разница.

Answer 2

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

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

Вы можете попробовать 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

Используйте вспомогательную таблицу всех возможных последовательных значений или материализуйте одну в 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
       );

Answer 4

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

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

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

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

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