Information ausblenden
Willkommen im Forum für alle Datenbanken! Registriere Dich kostenlos und diskutiere über DBs wie Mysql, MariaDB, Oracle, Sql-Server, Postgres, Access uvm

Abfrage über alle überlappenden Polygone ist zu langsam

Dieses Thema im Forum "PostgreSQL" wurde erstellt von lapadula, 8 September 2021.

  1. lapadula

    lapadula Aktiver Benutzer

    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?
     
  2. akretschmer

    akretschmer Datenbank-Guru

    du könntest versuchen, einen funktionalen Index auf diese polygon-Funktion zu erstellen...
     
  3. akretschmer

    akretschmer Datenbank-Guru

    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=*#
    
     
  4. akretschmer

    akretschmer Datenbank-Guru

    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.
     
    Walter gefällt das.
  5. lapadula

    lapadula Aktiver Benutzer

    Danke, ich probiere das morgen mal gründlich aus und berichte dann.
     
  6. lapadula

    lapadula Aktiver Benutzer

    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
     
    Walter und akretschmer gefällt das.
  7. akretschmer

    akretschmer Datenbank-Guru

    Du hast aber schon die Abfrage auf diese neue Spalte geändert?
     
  8. lapadula

    lapadula Aktiver Benutzer

    Ja, klar :)

    Die Abfrage, die ich gepostet habe, hat die schon benutzt. Habe einfach deinen Spaltennamen übernommen

    Code:
    (t1.c && t2.c)
     
Die Seite wird geladen...

Diese Seite empfehlen

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies.
    Information ausblenden