Wahl der Zugriffsstrukturen Hilfe

[Haus17]

Hallo,

habe ein Problem mit dieser Aufgabe:

Gegeben ist folgende Tabelle: Punkte (x,y)
Welche Zugriffsstrukturen mit jeweils welchen Attributen unterstützen folgende SQL Anweisungen optimal? Begründen Sie jeweils Ihre Antwort. Beschreiben Sie jeweils die Vorgehensweise, wie mit dem eingesetzten Index die Anfrage effizient beantwortet werden kann.
1. Select * from Punkte where x = 6 and y>8
2. Select * from Punkte where x > 3 or y > 5
3. Select * from Punkte where y = 7
4. Select * from Punkte p1, Punkte p2 where p1.x = p2.x and p1.y = 4


Unser Dozent erklärt uns nicht, nach welchem Prinzip diese zu lösen sind. Es gibt bei uns B*, Hash, Cluster, etc.

Vielen Dank für eure Hilfe

 

[akretschmer]

1. Select * from Punkte where x = 6 and y>8
2. Select * from Punkte where x > 3 or y > 5
3. Select * from Punkte where y = 7
4. Select * from Punkte p1, Punkte p2 where p1.x = p2.x and p1.y = 4

Prinzipiell nicht eindeutig zu beantworten, weil hier keiner weiß, wie groß die Tabelle ist und wie die Daten verteilt sind. Um eine sinnvolle Basis zu haben, habe ich mal eine Tabelle mit Datentyp POINT erstellt und diese mit 10 Millionen Records gefüllt, wo x und y jeweils von 0 bis 10000 gehen:

test=# create table punkte (p point);
CREATE TABLE
test=*# insert into punkte select point((random()*10000)::int,(random()*10000)::int) from generate_series(1,10000000) s;
INSERT 0 10000000
test=*# create index index_punkte_gist on punkte using gist (p);
CREATE INDEX
test=*# create index idx_x on punkte ((p[0]));
CREATE INDEX
test=*# create index idx_y on punkte ((p[1]));
CREATE INDEX

Dazu habe ich 3 Indexe erstellt, einen GiST-Index und je einen BTREE über p[0] und p[1], was x und y entspricht.




Mal als Beispiel 1.

Wenn ich das mit (3,5) teste, so werden fast alle Punkte im Result sein, daher ein Seq-Scan:

test=*# explain analyse select * from punkte where p[0] > 3 or p[1] > 5;
  QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Seq Scan on punkte  (cost=0.00..204056.45 rows=10000096 width=16) (actual time=0.019..2181.830 rows=9999999 loops=1)
  Filter: ((p[0] > '3'::double precision) OR (p[1] > '5'::double precision))
  Rows Removed by Filter: 1
Planning time: 0.385 ms
Execution time: 2869.224 ms
(5 Zeilen)

Anders sieht das aus, wenn ich die Werte so eingrenze, daß kaum noch Records diese Bedingung erfüllen werden. Hier erkennt der Planner, daß die Indexe sinnvoller wären:

test=*# explain analyse select * from punkte where p[0] > 9990 or p[1] > 9990;
  QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on punkte  (cost=364.48..38729.10 rows=18944 width=16) (actual time=12.825..50.080 rows=19180 loops=1)
  Recheck Cond: ((p[0] > '9990'::double precision) OR (p[1] > '9990'::double precision))
  Heap Blocks: exact=16169
  ->  BitmapOr  (cost=364.48..364.48 rows=18953 width=0) (actual time=6.357..6.357 rows=0 loops=1)
  ->  Bitmap Index Scan on idx_x  (cost=0.00..179.87 rows=9525 width=0) (actual time=3.090..3.090 rows=9513 loops=1)
  Index Cond: (p[0] > '9990'::double precision)
  ->  Bitmap Index Scan on idx_y  (cost=0.00..175.14 rows=9427 width=0) (actual time=3.265..3.265 rows=9673 loops=1)
  Index Cond: (p[1] > '9990'::double precision)
Planning time: 0.289 ms
Execution time: 51.759 ms
(10 Zeilen)

Wenn ich einen Index wie folgt erstelle:

test=*# create index idx_xy on punkte ((p[0]),(p[1]));
CREATE INDEX

so könnte dieser bei folgender Abrage sehr nützlich sein:

test=*# explain analyse select * from punkte where p[0] > 9990 and p[1] > 9990;
  QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Index Scan using idx_xy on punkte  (cost=0.43..279.77 rows=9 width=16) (actual time=0.215..1.471 rows=6 loops=1)
  Index Cond: ((p[0] > '9990'::double precision) AND (p[1] > '9990'::double precision))
Planning time: 0.300 ms
Execution time: 1.503 ms
(4 Zeilen)

Allerdings wäre dieser dann bei 3. völlig wertlos, denn in kombinierten Indexen müssen die ersten Spalten auch die Where-Condition treffen.


Wozu dient der GiST-Index?

Betrachte (x,y) als Koordinaten von POI's, also Point of Interest. Meinetwegen Freßbuden. Dein Navi weiß, Du bist an an Punkt (5000,5000) und willst die nächsten 5 Freßbuden wissen:

test=*# select * from punkte order by p <-> point(5000,5000) limit 5;
  p
-------------
(4998,4998)
(4997,5000)
(5000,5004)
(4999,5004)
(5004,4999)
(5 Zeilen)

test=*# explain analyse select * from punkte order by p <-> point(5000,5000) limit 5;
  QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
Limit  (cost=0.42..0.80 rows=5 width=16) (actual time=0.212..0.322 rows=5 loops=1)
  ->  Index Only Scan using index_punkte_gist on punkte  (cost=0.42..773380.42 rows=10000000 width=16) (actual time=0.210..0.318 rows=5 loops=1)
  Order By: (p <-> '(5000,5000)'::point)
  Heap Fetches: 5
Planning time: 0.136 ms
Execution time: 0.370 ms
(6 Zeilen)

Index-basierte Umkreissuche ;-)


Die anderen Fragen kannst Du genauso nun selber ausprobieren, viel Erfolg!