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

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

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 года.

Источник

3 ответа

Решение

Был "временный postgres" (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

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

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

Источник

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

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

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

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

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

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

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

                                from (timestamp)
Источник

Проблема в том, что 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. Так что... упоминая здесь, на случай, если тебе повезет больше, чем мне.

Источник
Другие вопросы по тегам