Как выбрать перекрывающиеся пары значений из БД

Question

В моем postgres db у меня есть таблица с 3 столбцами, подобная этой:

start | end  | sorce
17    | 23   | A
150   | 188  | A
200   | 260  | A
19    | 30   | B
105   | 149  | B
199   | 220  | B
...

Я хотел бы выбрать все строки, где области (от начала до конца) из разных источников A и B перекрываются.

UPDATE:

В Postgres версии 8.4 можно решить проблему с оконными функциями . Это намного быстрее, чем методы объединения или выбора. Ссылка на postgres wiki .

Answer 1

Это работает методом грубой силы (я переименовал ваши столбцы range_start и range_end, чтобы избежать конфликта с зарезервированным словом "конец"):

select *
from t cross join t t2
where t2.source <> t.source
      and box(point(t2.range_start,t2.range_start),point(t2.range_end,t2.range_end))
            && box(point(t.range_start,t.range_start),point(t.range_end,t.range_end))

или

select *
from t
where exists (select 1 from t t2
              where t2.source <> t.source and box(point(t2.range_start,t2.range_start),point(t2.range_end,t2.range_end))
                  && box(point(t.range_start,t.range_start),point(t.range_end,t.range_end)))

После этого вы сможете использовать индекс GiST, который может сделать это более эффективным (seq scan + index scan):

create index t_range_idx on t using gist (box(point(range_start,range_start),point(range_end,range_end))

Эта функция может помочь в понимании путем очистки SQL:

create function range(not_before int, not_after int) returns box
   strict immutable language sql
   as $$ select box(point($1,$1),point($2,$2)) $$;

При этом вы можете написать:

select * from t where range(range_start,range_end) && range(10,20);

и заметить, что оператор box && box означает «перекрытия».

Answer 2

Если вы хотите все пары, тогда ВНУТРЕННЕЕ СОЕДИНЕНИЕ A и B, используя классический тест перекрытия

a.start < b.end and b.start < a.end

т.е.

select a.start a_start, a.end a_end, b.start b_start, b.end b_end
from tbl a
inner join tbl b on a.start < b.end and b.start < a.end and b.source = 'B'
where a.source = 'A'

Если вы не имеете в виду источники literally 'A'и' B ', просто потому, что они разные, вы можете использовать ниже

select a.start a_start, a.end a_end, b.start b_start, b.end b_end
from tbl a
inner join tbl b on a.start < b.end and b.start < a.end and a.source <> b.source

В зависимости от определения перекрытия, поменяйте < на <= (оба раза)

• <: 10-20 не перекрытие 20-30
• <=: 10-20 перекрытие 20-30