Определить расстояние между ящиками - PullRequest
Новая
       4

Определить расстояние между ящиками

1 голос
/ 27 июля 2011

Эта проблема на некоторое время вызывает у меня головную боль. У меня есть база данных PostgreSQL 8.4, которая состоит только из одной таблицы, содержащей более 4.000.000 записей. Эта таблица структурирована следующим образом: 

CREATE TABLE metadata (
  id serial NOT NULL,
  "value" text NOT NULL DEFAULT ''::text,
  segment_box box NOT NULL DEFAULT box(point(((-9223372036854775808)::bigint)::double precision, (1)::double precision), point((9223372036854775807::bigint)::double precision, ((-1))::double precision)),
  CONSTRAINT metadata_pk PRIMARY KEY (id)
)

CREATE INDEX metadata_segment_box_ix
  ON metadata
  USING gist
  (segment_box);

CREATE INDEX metadata_tag_value_ix
  ON metadata
  USING btree
  (value);

Таблица содержит сегменты (по времени), представленные в виде прямоугольных прямоугольников. Эти сегменты аннотируются с использованием столбца «значение».

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

SELECT * FROM (SELECT * FROM metadata WHERE value='X') a, 
(SELECT * FROM metadata WHERE AND value='Y') b 
WHERE a.segment_box <-> b.segment_box <= 3000

Но, как вы, наверное, заметили, этот запрос не может быть эффективно выполнен базой данных. Декартово произведение подзапросов a и b становится действительно большим. Есть ли способ выполнить эти запросы более эффективно? Я могу себе представить, что какой-то подход со скользящим окном сработает. Может быть что-то вроде следующего:

* * 1010

Обновление: После публикации этого вопроса я попытался создать пользовательскую функцию в Postgres. Я попробовал: 

CREATE OR REPLACE FUNCTION within_window(size bigint DEFAULT 0)
  RETURNS setof metadata AS
$BODY$DECLARE
  segment RECORD;
  neighbour RECORD;
  newwindow box;
BEGIN
  FOR segment IN (
    SELECT * FROM metadata WHERE value='X' OR value='Y' 
      ORDER BY (segment_box[1])[0], (segment_box[0])[0]
  ) LOOP
    newwindow := box(segment.segment_box[0], 
      point((((segment.segment_box[1])[0]) + size), (segment.segment_box[1])[1]));
    FOR neighbour IN (
      SELECT DISTINCT ON (metadata_id) * FROM metadata WHERE value='X' OR value='Y') 
        AND segment_box &< newwindow
        AND segment_box &> newwindow 
    ) LOOP
      RETURN NEXT neighbour;
    END LOOP;
  END LOOP;
END;$BODY$
  LANGUAGE plpgsql;

Однако эта функция работает медленнее, чем базовое решение, которое я описал выше, из-за подзапроса, который должен выполняться много раз. Любые другие мысли по этому поводу?

1 Ответ

2 голосов
/ 29 июля 2011

Я сам решил проблему с помощью своего рода алгоритма линии развертки. Только один запрос выполняется. Я использую курсор для перемещения по наборам результатов запроса. Полученный алгоритм работает следующим образом: 

CREATE OR REPLACE FUNCTION within_window(size bigint DEFAULT 0)
  RETURNS setof metadata AS
$BODY$DECLARE 
crsr SCROLL CURSOR FOR (SELECT * FROM metadata WHERE value='X' OR value='Y' ORDER BY (segment_box[1])[0], (segment_box[0])[0]);
rc RECORD;
rcc RECORD;
crsr_position int;
last_crsr int;
BEGIN
    OPEN crsr;
    crsr_position := 0;
    LOOP FETCH NEXT FROM crsr INTO rc;
        IF NOT FOUND THEN
            EXIT;
        END IF;
        last_crsr := crsr_position;
        LOOP FETCH NEXT FROM crsr INTO rcc;
            IF NOT FOUND THEN
                EXIT;
            ELSEIF 
                rcc.segment_box &< box(rc.segment_box[0], point((((rc.segment_box[1])[0]) + size), (rc.segment_box[1])[1])) AND
                rcc.segment_box &> box(rc.segment_box[0], point((((rc.segment_box[1])[0]) + size), (rc.segment_box[1])[1]))
            THEN
                RETURN NEXT rcc;
            ELSE 
                EXIT;
            END IF;
        END LOOP;
        crsr_position := last_crsr + 1;
        MOVE ABSOLUTE crsr_position FROM crsr;
    END LOOP;
    CLOSE crsr;
END;$BODY$
  LANGUAGE plpgsql;

При использовании этой функции запросу требуется только 476 мс вместо 6+ минут (в базе данных с 4 миллионами строк)

...