Abfrage über alle überlappenden Polygone ist zu langsam

L

lapadula

Aktiver Benutzer
Beiträge
33
Hallo,

ich habe eine Tabelle mit vielen Polygonen (bis zu 80 000 Stück). Ich möchte wissen, welche davon überlappen.

Dazu habe ich folgende Query:

Code: 
SELECT
   distinct t1.id, t2.id
FROM
   objekt AS t1, objekt AS t2
WHERE
   polygon(replace(replace(t1.shape ->> 'coordinates', '[', '('), ']', ')')) && polygon(replace(replace(t2.shape ->> 'coordinates', '[', '('), ']', ')')) AND
   t1.id <> t2.id;

Der Operator '&&' passt soweit.
Range Functions and Operators

Ich muss nur das ganze ein wenig formatieren, weil bei mir die Geometrie in jsonb vorliegt und ich auf das Array mit den Koordinaten per ->> zugreife und die eckigen Klammern durch runde ersetze.

Geometric Types

Die Abfrage dauert leider schon bei etwa 1600 Objekten schon etwa 3 Minuten. Leider finde ich auch keine Möglichkeit das Ergebnis so einzuschränken, dass ich nur die Polygone erhalte, wo die Fläche einen bestimmten Schwellenwert übersteigt, weil bei mir fast alle Polygone sich minimal überschneiden, ich möchte jedoch welche, die sich signifikant überlappen.

Es gibt wohl eine Art Plugin für Postgres: Postgis. Jedoch kann ich das nicht einfach auf die schnelle installieren. Die Funktionen von Postgres scheinen ja irgendwie die selben zu sein.

Mache ich da etwas grundsätzlich falsch? Unterscheiden sich die Algorithmen bei Postgres und Postgis?
 
Werbung:
Code: 
edb=# create table lapadula(j jsonb);
CREATE TABLE
edb=*# create index idx1 on lapadula using gist ((polygon(replace(replace(j ->> 'coordinates', '[', '('), ']', ')'))));
CREATE INDEX
edb=*#
 
alternativ eine generated column anlegen, mit Index:

Code: 
edb=*# create table lapadula2 (j jsonb, c polygon generated always as (polygon(replace(replace(j ->> 'coordinates', '[', '('), ']', ')'))) stored);
CREATE TABLE
edb=*# create index idx2 on lapadula2 using gist (c);
CREATE INDEX

probier es mal aus, beide Varianten, und schaue mit EXPLAIN ANALYSE was besser geht. Feedback hier wäre nett.
 
Also ich habe eine Datenbank mit etwa 18000 Polygonen und das ist das Ergebnis:

Meine Abfrage, ohne zu schauen, ob etwas überlappt, hat schon 75 Sekunden Execution Time.

Ohne Index habe ich die laufende Abfrage bei 36 Minuten abgebrochen.

So sieht meine Abfrage aus, mit der extra Spalte:

Code: 
EXPLAIN ANALYSE
SELECT
    distinct t1.id
FROM
    plan_objekt as t1, plan_objekt as t2
    left join plan_layer fpl on t2.layer_id = fpl.id
WHERE
    (t1.plan_id = 2 and t2.plan_id = 2) AND
    t1.shape ->> 'type' = 'POLYGON' AND
    fpl.ebene = true AND
    (t1.c && t2.c) AND
    (t1.id <> t2.id);

Mit dem funktionalen Index komme ich auf etwa 7 Sekunden Execution Time.

Code: 
Unique  (cost=5544.27..5547.73 rows=73 width=8) (actual time=7120.927..7128.324 rows=48 loops=1)
  ->  Sort  (cost=5544.27..5546.00 rows=692 width=8) (actual time=7120.926..7123.952 rows=72340 loops=1)
        Sort Key: t1.stelle_id
        Sort Method: quicksort  Memory: 4017kB
        ->  Nested Loop  (cost=0.57..5511.63 rows=692 width=8) (actual time=0.165..7107.440 rows=72340 loops=1)
              ->  Nested Loop  (cost=0.29..718.77 rows=1521 width=368) (actual time=0.032..9.600 rows=15904 loops=1)
                    ->  Seq Scan on plan_layer fpl  (cost=0.00..1.24 rows=2 width=8) (actual time=0.016..0.023 rows=2 loops=1)
                          Filter: ebene
                          Rows Removed by Filter: 22
                    ->  Index Scan using ix_plan_object_layer on plan_objekt t2  (cost=0.29..351.17 rows=760 width=376) (actual time=0.010..3.362 rows=7952 loops=2)
                          Index Cond: (layer_id = fpl.id)
                          Filter: (plan_id = 2)
              ->  Index Scan using idx1 on plan_objekt t1  (cost=0.29..3.14 rows=1 width=376) (actual time=0.060..0.441 rows=5 loops=15904)
"                    Index Cond: ((replace(replace((shape ->> 'coordinates'::text), '['::text, '('::text), ']'::text, ')'::text))::polygon && (replace(replace((t2.shape ->> 'coordinates'::text), '['::text, '('::text), ']'::text, ')'::text))::polygon)"
                    Rows Removed by Index Recheck: 2
                    Filter: ((plan_id = 2) AND (id <> t2.id) AND ((shape ->> 'type'::text) = 'POLYGON'::text))
                    Rows Removed by Filter: 1
Planning Time: 0.751 ms
Execution Time: 7128.794 ms

Mit der extra Spalte und dem Index darauf dauert das deutlich länger, verdächtiger Weise genauso lange wie die Abfrage ohne dem Überlappungs-Test.

Code: 
Unique  (cost=5349.56..5353.02 rows=73 width=8) (actual time=75344.294..75351.875 rows=48 loops=1)
  ->  Sort  (cost=5349.56..5351.29 rows=692 width=8) (actual time=75344.292..75347.445 rows=72340 loops=1)
        Sort Key: t1.stelle_id
        Sort Method: quicksort  Memory: 4017kB
        ->  Nested Loop  (cost=0.29..5316.92 rows=692 width=8) (actual time=0.064..75313.208 rows=72340 loops=1)
              Join Filter: ((t1.c && t2.c) AND (t1.id <> t2.id))
              Rows Removed by Join Filter: 280871820
              ->  Nested Loop  (cost=0.29..819.13 rows=1521 width=40) (actual time=0.036..40.170 rows=15904 loops=1)
                    ->  Seq Scan on plan_layer fpl  (cost=0.00..1.24 rows=2 width=8) (actual time=0.018..0.037 rows=2 loops=1)
                          Filter: ebene
                          Rows Removed by Filter: 22
                    ->  Index Scan using ix_plan_object_layer on plan_objekt t2  (cost=0.29..401.34 rows=760 width=48) (actual time=0.011..13.244 rows=7952 loops=2)
                          Index Cond: (layer_id = fpl.id)
                          Filter: (plan_id = 2)
              ->  Materialize  (cost=0.00..2075.83 rows=91 width=48) (actual time=0.002..2.113 rows=17665 loops=15904)
                    ->  Seq Scan on plan_objekt t1  (cost=0.00..2075.38 rows=91 width=48) (actual time=0.010..14.291 rows=17665 loops=1)
                          Filter: ((plan_id = 2) AND ((shape ->> 'type'::text) = 'POLYGON'::text))
                          Rows Removed by Filter: 585
Planning Time: 1.101 ms
Execution Time: 75353.001 ms

Bei der kleineren Datenbank mit etwa 1600 Polygonen war das mit der zusätzlichen Spalte schneller:

Planning Time: 0.440 ms | 0.356 ms
Execution Time: 862.879 ms | 699.860 ms

Das hilft mir schon sehr weiter, ich muss nur noch PostGIS installieren, weil ich auch die Fläche der Überlappung wissen will, um das Ergebnis weiter einzuschränken.

Vielen Dank @akretschmer
 
Werbung:
Zurück
Oben