ボックス間の距離を決定する

Question

この問題は、しばらく頭痛を引き起こしています。 PostgreSQL 8.4データベースは、4.000.000を超えるレコードを含む1つのテーブルのみで構成されています。この表は以下のように構成されています。

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のデカルト積は本当に大きくなっています。これらのクエリをより効率的に実行する方法はありますか？私は、スライディングウィンドウのアプローチのいくつかの並べ替えがトリックを行うだろうと想像することができます。次のような多分何か：

SELECT *, rank() OVER (
PARTITION BY "value" ORDER BY (segment_box[1])[0], (segment_box[0])[0] 
) FROM metadata WHERE value='X' OR value='Y' 

アップデート：私は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; 

しかし、この機能は、何度も実行する必要があるサブクエリのため、上記の基本的な解決策と同じくらい遅いです。これについての他の考え？

Answer 1

私はある種のスイープラインアルゴリズムで問題を自分で解決しました。 1つのクエリのみが実行されます。カーソルを使用して、クエリの結果セットを前後にスイープします。次のように結果のアルゴリズムは動作します：

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ミリ秒の代わりに、（4+百万行のデータベース上）6+分を必要とし、この機能を使用します！