Слияние интервалов за один проход в SQL

Question

Допустим, у меня есть таблица с двумя столбцами: start и end, оба целые, и таблица упорядочена по первому, а затем по второму столбцу. Каждая строка представляет интервал.

Мне нужна таблица объединенных интервалов : все перекрывающиеся или смежные интервалы сгруппированы в один.

Его можно построить с помощью запроса JOIN, но это квадратичное число строк, которое в моем случае составляет 4 миллиона строк (я решил составить этот вопрос, потому что запрос все еще выполняется).

Это также можно сделать за один один проход, пропуская каждую строку и отслеживая максимальное время окончания - но как это сделать или что-то эквивалентное в стандартном SQL? Есть ли какой-либо O (n) способ сделать это в SQL? Я использую SQLite прямо сейчас; В этот раз мне поможет решение для SQLite.

Из ответов на связанные вопросы ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ) Я не могу сказать, возможно ли это.

Можешь?

Answer 1

Ну, вот решение, которое работает в MySQL (я не знаю, будет ли оно работать в SQlite). Я думаю, но не могу доказать, что это O (n) (отбрасывая время, необходимое для первоначальной сортировки таблицы событий, т. Е. Если она уже отсортирована, как мне кажется, в вопросе.)

> SELECT * from events;
+-------+-----+
| start | end |
+-------+-----+
|     1 |   9 |
|     5 |   8 |
|     8 |  11 |
|    11 |  13 |
|    17 |  25 |
|    18 |  26 |
|    33 |  42 |
|    59 |  81 |
|    61 |  87 |
|    97 | 132 |
|   105 | 191 |
|   107 | 240 |
|   198 | 213 |
|   202 | 215 |
+-------+-----+
14 rows in set (0.00 sec)


SET @interval_id = 0;
SET @interval_end = 0;

SELECT
  MIN(start) AS start,
  MAX(end) AS end
  FROM
    (SELECT
       @interval_id := IF(start > @interval_end,
                          @interval_id + 1,
                          @interval_id) AS interval_id,
       @interval_end := IF(start < @interval_end,
                           GREATEST(@interval_end, end),
                           end) AS interval_end,
       events.*
     FROM events
     ORDER BY start,end) tmp
  GROUP BY interval_id;

+-------+------+
| start | end  |
+-------+------+
|     1 |   13 |
|    17 |   26 |
|    33 |   42 |
|    59 |   87 |
|    97 |  240 |
+-------+------+
5 rows in set (0.00 sec)

Answer 2

В ваших ссылках вы пропустили одно: Можно ли использовать SQL Server CTE для объединения пересекающихся дат? где я представляю решение RECURSIVE CTE для проблемы перекрывающихся интервалов. Рекурсивные CTE могут обрабатываться по-разному (по сравнению с обычными самостоятельными соединениями) и часто работают на удивление быстро.

mysql не имеет рекурсивных CTE. У Postgres они есть, у Oracle они есть, у Microsoft они есть.

Здесь Запрос на «прогон» последовательных столбцов в Postgres - это еще один, с множителем.

Здесь Получить общий временной интервал из нескольких строк, если последовательность не нарушена. - это еще один.

Answer 3

На данный момент лучший ответ, который я нашел: использовать индексацию.Это снижает сложность от квадратичной до O (n log n).

С индексом , охватывающим , запросы оказались достаточно быстрыми для моих нужд;только с индексом в начале или конце столбца, это было медленнее, но все еще в порядке.В каждом случае EXPLAIN QUERY PLAN говорил мне, что сканирование таблицы объединяется с использованием индекса, как и ожидалось.

Нахождение элемента в индексе не совсем O (1), но оказалось, чтобыть достаточно близкоИ построение индекса тоже не медленное.

Остается только доказательство того, что истинный алгоритм O (n) не может быть написан на SQL.

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

• экспортировать таблицу в файл CSV;прочитать файл CSV, применить алгоритм, произвести CSV;импортировать полученный CSV-файл в виде таблицы;
• использовать драйвер SQLite для этого языка (например, DBD :: SQLite для Perl, RSQLite для R)
• написать функцию расширения SQLite, которая каким-либо образом взаимодействует сязык выбора

Answer 4

Судя по ответу на мой вопрос в комментариях, я не думаю, что моя идея сработала бы. так как вы упомянули, что это можно (и я полагаю, вы знаете, как это сделать) с помощью объединений, у меня была идея минимизировать количество строк, которые нужно объединить, сохраняя только диапазоны, принадлежащие различным точкам, как показано ниже:

select start, max(end) as end
from (
      select min(start) as start,end
      from table
      group by end
     ) in_tab
group by in_tab.start

вышеуказанный внутренний выбор гарантирует, что ни одна конечная точка не повторяется, и выбирает самую длинную начальную точку для каждого конца. внешний выбор делает только наоборот. в итоге мы получаем диапазоны, которые начинаются и заканчиваются в разных точках (с полным удалением или полным перекрытием диапазона). Это могло бы сработать, если бы максимальный диапазон не был большим. если бы это были даты, и существует максимальная разница в году между самой низкой датой во всей таблице и самой высокой датой в ней, тогда было бы 365 * 364 вариантов выбора любых двух точек, и это было бы более высоким пределом для возможных строк после вышеизложенного выберите. затем их можно было бы использовать во временной таблице, используя метод соединения, который у вас уже есть. но с числами, которые вы упомянули, теоретически у нас есть огромное число, которое делает эту попытку неуместной. даже несмотря на то, что приведенное выше сводит к минимуму строки, которые будут использоваться в вычислениях, их все равно будет слишком много для использования в объединении.

Я не знаю, как сделать это в ANSI SQL без объединений, если в СУБД нет других нестандартных функций. например, в оракуле это может быть легко достигнуто с помощью аналитических функций. в этом случае лучше всего использовать вышеуказанное, чтобы минимизировать количество используемых строк и перенести их в ваше приложение, и там вы можете написать код, который вычисляет диапазоны и вставить их обратно в базу данных.