SQL как объединить интервалы в одно чтение?

Question

Есть интервалы, для простоты пусть будут целые числа, хранятся в табличке Itr:

t1	t2
1	5
3	7
8	9

Нужен запрос, который объединит интервалы, т.е. выдаст:

t1	t2
1	7
8	9

Повторное чтение из таблицы Itr не предлагать(самоджойны и прочее), интересует именно решение через ранжирующие функции.

Т.е. сложность O(N^2) не нужна, должна быть сложность сортировки O(N*Ln(N)) (псевдолинейная)

Answer 1

CREATE TABLE test (t1 INT, t2 INT);
INSERT INTO test VALUES (1, 5), (3, 7), (8, 9);
SELECT * FROM test;

t1	t2
1	5
3	7
8	9

WITH
cte1 (point, weight) AS (
  SELECT t1, 1 FROM test
  UNION ALL
  SELECT t2, -1 FROM test
  ),
cte2 (point, weight) AS (
  SELECT DISTINCT point, SUM(weight) OVER (ORDER BY point)
  FROM cte1
  ),
cte3 (point, pgroup) AS (
  SELECT point, SUM(CASE WHEN weight = 0 THEN 1 ELSE 0 END) OVER (ORDER BY point DESC)
  FROM cte2
  )
SELECT MIN(point) AS t1, MAX(point) AS t2
FROM cte3
GROUP BY pgroup
ORDER BY t1

t1	t2
1	7
8	9

fiddle

Чтобы понять происходящее, исследуйте последовательно вывод каждого CTE.

Answer 2

Можно в одно чтение:

Считаем накопительный по t2, RM
Сравниваем предыдущее значение RM c t1, таким образом высчитываем индикатр начала группы FLG
Считаем накопительный итог по FLG - получаем для каждого интервала свой номер группы
группируем по GRP - профит.

IF OBJECT_ID('test')IS NOT NULL DROP TABLE test CREATE TABLE test (t1 INT, t2 INT) INSERT INTO test VALUES (1, 5), (2, 7), (3, 5), (8, 10), (9, 9), (10, 11), (12, 12) SELECT * FROM test

t1	t2
1	5
2	7
3	5
8	10
9	9
10	11
12	12

SELECT GRP, MIN(t1)t1, MAX(t2)t2
FROM(
  SELECT *, SUM(FLG)OVER(ORDER BY t1,t2 ROWS UNBOUNDED PRECEDING)GRP
  FROM(
    SELECT *, IIF(LAG(RM)OVER(ORDER BY t1,t2)>=t1,0,1)FLG
    FROM(
      SELECT *, MAX(t2)OVER(ORDER BY t1,t2)RM
      FROM test
)T)T)T
GROUP BY GRP

GRP	t1	t2
1	1	7
2	8	11
3	12	12

При включенном SET STATISTICS IO ON получаем один скан таблицы Test;

Table 'test'. Scan count 1, logical reads 1

БЛОГ НА HUSL

SQL как объединить интервалы в одно чтение?

Ответы (2 шт):