PostgreSQL сопоставляет интервал между временем начала и окончания с отметкой времени

Question

Я разрабатываю систему, в которой будут храниться записи, содержащие время начала и окончания.Например:

CREATE TABLE test (
  id bigserial PRIMARY KEY,
  ts_start timestamp NOT NULL,
  ts_end timestamp NOT NULL,
  foo bar NOT NULL,
  ...
);

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

WHERE ts_start <= '2006-4-6 12:34:56' AND ts_end > '2006-4-6 12:34:56'

Я проверил это с огромным количеством сгенерированных тестовых данных, и производительность довольно плохая.Я протестировал его с индексом ts_start и другим индексом ts_end, а также с индексом из нескольких столбцов ts_start и ts_end.Последний дал лучший результат, но он все еще далек от оптимального.

Проблема в том, что postgresql не знает, что ts_end гарантированно больше ts_start, поэтому он использует план, способный находить строки, где ts_end меньше ts_start.

Любые предложения, как решить эту проблему?

Редактировать: Для людей, имеющих эту проблему тоже, если вы можете подождать немного дольше, тогда PostgreSQL 9.2 имеет идеальное решение: типы диапазонов .9.2 находится в бета-версии, а окончательный выпуск, скорее всего, будет в конце 2012 года.

Answer 1

Был "временной постгрес" (Google google), но я не знаю, поддерживается ли он до сих пор ... Я думаю, что обсуждался вопрос о включении этого типа поиска в postgres, но я не помню окончательное состояниеэтогоВ любом случае:

Пример использования box и gist:

CREATE TABLE segments( start INTEGER NOT NULL, stop INTEGER NOT NULL, range_box BOX NOT NULL );
INSERT INTO segments SELECT n,n+1,BOX(POINT(n,-1),POINT(n+1,1)) FROM generate_series( 1, 1000000 ) n;
CREATE INDEX segments_box ON segments USING gist( range_box );
CREATE INDEX segments_start ON segments(start);
CREATE INDEX segments_stop ON segments(stop);

EXPLAIN ANALYZE SELECT * FROM segments WHERE 300000 BETWEEN start AND stop;
 Index Scan using segments_start on segments  (cost=0.00..12959.24 rows=209597 width=72) (actual time=91.990..91.990 rows=2 loops=1)
   Index Cond: (300000 >= start)
   Filter: (300000 <= stop)
 Total runtime: 92.023 ms

EXPLAIN ANALYZE SELECT * FROM segments WHERE range_box && '(300000,0,300000,0)'::BOX;
 Bitmap Heap Scan on segments  (cost=283.49..9740.27 rows=5000 width=72) (actual time=0.036..0.037 rows=2 loops=1)
   Recheck Cond: (range_box && '(300000,0),(300000,0)'::box)
   ->  Bitmap Index Scan on segments_box  (cost=0.00..282.24 rows=5000 width=0) (actual time=0.032..0.032 rows=2 loops=1)
         Index Cond: (range_box && '(300000,0),(300000,0)'::box)
 Total runtime: 0.064 ms

Как вы можете видеть, индекс gist смехотворно быстр (1500 раз! Lol) (и вы можете использовать много операторов, таких как перекрытия, этосодержится, содержит и т. д.

http://www.postgresql.org/docs/8.2/static/functions-geometry.html

Answer 2

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

Я не уверен, есть ли у PG какой-либо встроенный тип данных для поддержки диапазонов дат,но я уверен, что если вы используете PostGIS для представления временных диапазонов в виде точек в 2D-пространстве, а затем сообщаете PG о геоиндексике, вы получите максимально возможную производительность из этого запроса.

Возможнов pg есть встроенный в мою дату эквивалент моего предложения, но, как я уже сказал, я не знаком с ним.Я знаком с возможностями геометрического индексирования pg, и думаю, что вы должны серьезно отнестись к этому как к оптимизации.

Вот наивный пример (хотя я уверен, что запрос будет выполняться очень быстро):

1. Представляет каждый временной диапазон в виде прямоугольника от начала координат (0,0) до точки (от, до).
2. Включить геоиндексацию.
3. Учитывая период времени P, вы можете запросить, находится ли он во времени, проверив, находится ли точка (P, P) внутри прямоугольника с помощью функции, подобной ST_Contains.Этот запрос будет O (log (количество диапазонов)).

Иллюстрация:

               |
               |
               |
               |
        to     |
  (timestamp)  |
               |
               |
               |_________________  (from,to)
               |__               |
               |  |(p,p)         |
               |__|______________|_______________________

                                from (timestamp)

Answer 3

Проблема в том, что postgresql не знает, что ts_end гарантированно будет больше ts_start, поэтому он использует план, который способен находить строки, где ts_end меньше, чем ts_start.

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

Это очень похоже на то, что вы делаете при запросе к lft / rgt во вложенном наборе: если вы 'Если дерево проиндексировано с использованием lft / rgt таким образом, что у детей есть parent_lft < lft и lft < rgt и parent_lft < parent_rgt, оптимальный запрос будет опираться на parent_lft < lft и lft < parent_rgt (который ищет индекс на lftдля небольшого диапазона), а не parent_lft < lft и rgt < parent_rgt (который ищет индекс на lft с одной точки и далее).

Вы находитесь в аналогичной ситуации, когда добавляете индекс,Если вы не ограничиваете ts_start или ts_end или оба, вы будете смотреть на большой набор строк.

Теперь я хочу выполнить запросы по этому, чтобы найти все строки, которые перекрываются с определеннымметка времени.Это может привести к выражению where, например:

WHERE ts_start <= '2006-4-6 12:34:56' AND ts_end > '2006-4-6 12:34:56'

Для этого конкретного запроса вы можете захотеть изучить типы геометрии и использовать индекс GIST.

В частности, если вы установите ts_start и ceil ts_end в полночь, вы можете получить целочисленное представление (например, количество дней с начала эпохи).Затем сохраните последний как индексируемый тип и запросите его, используя условие перекрытия.

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