Némi kihagyás után (dógozni is kell, meg a gyerekeknek gyógyulni) kicsit foglalkozzunk még a spatial adatokkal. Az eddigi részekben eljátszadoztunk velük, szép volt, csak arról nem volt szó, hogy működik ez az egész, ha sok adatban kell keresgélni? Alapban sok művelet piszok időigényes, mindenképpen szükség lenne valamilyen indexelési módszerre. De ezek az adatok messze nem olyan egyszerűen indexelhetők, mint mondjuk egy varchar.
A spatial index maga most is egy B* fa, csak a kihívás, hogyan lehet alakzatok adatait úgy átmasszírozni valami bináris adathalmazzá, ami aztán meggyosíthat bizonyos műveleteket, például távolságszámítást vagy metszet meghatározását.
Az index működését itt részletezik. A cikket olvasva meglehetősen bizarr dolog tárul a szemünk elé, amelyből jól látszik, hogy a spatial támogatás messze több, mint egy új CLR UDT.
Az első dolog, amit fogni kell, hogy a spatial indexek nem olyan egzaktak, mint amiket eddig láttunk. A részletek mellőzésével a következőről van szó.
A síkot felbontják cellákra, mint amikor “kockás” papírra rajzolunk. Az alakzatok ezekre a négyzetekre vannak fektetve. Minden cellát további cellákra bonthatjuk, és ott is meghatározhatjuk, mely al-cellákban van még benne egy alakzat, és melyben nincs. Ez a dekompozíciót max. 4 szinten folytatják, így egyre finomabb felbontásban gyűjtenek információt az alakzatról. Hogy ne szabaduljonak el az adatok, vannak szabályok, amelyek korlátozzák az adatmennyiségeket.
.gif)
Érezhető, hogy be kell határolni a “kockás papír” méretét, hogy véges méretű legyen az index, erre az index létrehozásakor van lehetőség. Ez azonban csak a geometry típusra vonatkozik, a geographynál véges a területünk, hisz a Föld felszínéről van szó.
.gif)
A geography típus ellipszoid adatinál még cifrább a helyzet, azokat levetítik síkba, és úgy dolgoznak vele.
.gif)
A valóság persze sokkal összetettebb, de nem vagyunk térképészek, így legyen elég ennyi. :)
Mire jó ezek után egy spatial index? Megfelelő körülmények között az STIntersects(), STEquals(), és STDistance() metódusokat meg tudja támogatni egy spatial index.
Tegyünk vele egy próbát!
Az előző részben a Dunához közel eső városokat kerestük meg, nézzük meg ezt index támogatással!
A táblában a városok multi-pontként vannak felvéve, pedig mindegyik csak 1 pontból áll. Konvertáljuk át őket igazi ponttá, hogy minden művelet rendesen menjen rajtuk:
update City set geom = geom.STStartPoint() select CITY_NAME, geom.ToString() from City
Így az alapadataink:
Kosice POINT (48.70000118311 21.2500004483) Rijeka POINT (45.333301183109988 14.433300448300003) Lodz POINT (51.778000183109988 19.4759994483) Kalisz POINT (51.757999183109995 18.083000448299998) Sieradz POINT (51.59600018311 18.732999448300006) Piotrkow Trybunalski POINT (51.409000183109988 19.691000448300002) Radom POINT (51.39600018311 21.158000448299987) Lublin POINT (51.24200018311 22.577999448300005) ...
Vegyük elő korábbi példánkat, a Dunához 10 km-nél közelebbi városok listáját.
declare @danube geography = geography::STPointFromText('POINT(0 0)', 4326);
select @danube = @danube.STUnion(geom)
from River where NAME = N'Danube'
select CITY_NAME,
geom.ToString() 'A város',
geom.STDistance(@danube) 'Távolság a folyótól'
from City
where geom.STDistance(@danube) < 10000
[/source]
A végrehajtási terv:
<a href='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithoutindex.png' title='spatialopwithoutindex.png' target='_blank'><img src='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithoutindex.png' alt='spatialopwithoutindex.png' /></a>
No, a Filternek kellene kiesni vagy legalábbis a költségének csökkeni az index hatására. Az alap beállításokkal hozzunk létre egy spatial indexet:
[source='sql']
create spatial index idx_City_Spatial_1
on City(geom)
Elvileg ettől más lehetne a korábbi lekérdezés végrehajtási terve. De nem lesz az. Annyira kicsit a táblánk (pár 10 sor), hogy esze ágában sincs használni egy mozaikos, rácsos ide-oda vetített indexet, a sima Filter jobban megéri neki.
Nagyobb adatmennyiségre van szükségünk. Mivel szabad informatikai adatok terén (meg más téren is) Magyarország a béka segge alatt van, szedjünk össze némi adatot Amerikából. Itt letölthető sok izgalmas infó. Például a települések listája, koordinátái megérnek egy misét. Ez betöltöttem a USCity táblába, 35432 sor lett.
Keressük meg azokat a városokat, amelyek Los Angeles 10 km-es körzetében vannak:
declare @la geography = (select geom
from USCity
where name = 'Los Angeles'
and County = 'Los Angeles County')
select name
from USCity
where geom.STDistance(@la) < 10000
[/source]
Nem kellene lokális változót bevezetni, de így szétválik a végrehajtási terv, így jobban látszik az index hatása.
A kimenet:
[source='c']
Los Angeles
City Terrace
East Los Angeles
Vernon
Commerce
Huntington Park
Maywood
Florence
Bell
Walnut Park
[/source]
Index nélkül a végrehajtás átlagban 2800 ms-ot vesz igénybe, ebből kb. 2000 a CPU költség, azaz igen erősen processzor intenzív a szűrés. A lapolvasások száma 1850.
Rakjunk rá egy spatial indexet!
[source='sql']
create spatial index idx_USCity_Spatial_1
on USCity(geom)
[/source]
A végrehajtási idő leesik 160ms-ra! A lapolvasások száma 1720 lett, azaz ebben nem lett jelentős különbség, de a CPU idő leesett kb. 50 ms-ra, 2000-ről. Azért ez igen nagy nyereség.
Az index nélküli végrehajtási terv:
<a href='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithoutindex2.png' title='Spatial szűrés index nélkül' target='_blank'><img src='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithoutindex2.png' alt='Spatial szűrés index nélkül' /></a>
Az előbbi index-szel:
<a href='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithdefaultindex2.png' title='Spatial szűrés alap index-szel' target='_blank'><img src='http://soci.hu/blog/wp-content/uploads/2008/02/spatialopwithdefaultindex2.png' alt='Spatial szűrés alap index-szel' /></a>
A jobb alsó Clustered Index Seek érdekes. A Seek Predicate-je a következő:
[source='c']
Seek Keys[1]: Start: [AdventureWorks].[sys].[extended_index_80719340_64000].Cell_Id >= Scalar Operator([Expr1009]),
End: [AdventureWorks].[sys].[extended_index_80719340_64000].Cell_Id <= Scalar Operator([Expr1010])
[/source]
Azaz, az XML Shredinghez hasonlóan itt is felépítenek egy segédtáblát az index részére, és abban keresnek. A segédtábla neve: [sys].[extended_index_80719340_64000].
Azonnal kísértést érzünk pesze, hogy belenézzünk:
[source='sql']
select * from [sys].[extended_index_80719340_64000]
[/source]
Meg is kapjuk a magunkét:
[source='c']
Msg 208, Level 16, State 1, Line 1
Invalid object name 'sys.extended_index_80719340_64000'.
[/source]
Na ne hazudjunk kérem, menjünk csak be a DAC kapcsolaton kereszül (ADMIN:gépnév\instance név):
[source='c']
Cell_Id Cell_Attributes SRID pk0
------------ --------------- ----------- -----------
0x200A2A2C04 1 4326 34751
0x200A2A3C04 1 4326 34756
0x200A2B3404 1 4326 34762
0x200A2B3704 1 4326 34763
0x200A2B3804 1 4326 34764
...
[/source]
Ebben az index táblában pont annyi sor van, mint az eredetiben, és a pk0 oszlop teremt kapcsolatot a kettő között, a végrehajtási tervben a bal oldali Merge Join illeszti a kettőt össze, imígyen:
[source='c']
([AdventureWorks].[dbo].[USCity].ID) =
([AdventureWorks].[sys].[extended_index_80719340_64000].pk0)
[/source]
Az SRID oszlop ismerős lehet, az az adatunk SRID-je, volt már róla szó az <a href="http://soci.hu/blog/index.php/2008/01/21/sql-server-2008-ujdonsagok-14-terbeli-adattipusok-1/">első részben</a>. Az első két oszlop jelentése egyelőre ismeretlen.
Vessük össze amit a hátsó nyíláson át felfedeztünk a hivatalosan is látható infóval!
[source='sql']
select name, spatial_index_type_desc, tessellation_scheme
from sys.spatial_indexes
where object_id = object_id('USCity')
name spatial_index_type_desc tessellation_scheme -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- idx_USCity_Spatial_1 GEOGRAPHY GEOGRAPHY_GRID
Az index lehet GEOGRAPHY vagy GEOMETRY, nyilván az oszlop típusától függően. A tessellation_scheme a mozaikozás módszerét írja le, ez az a folyamat, amiben egyre kisebb cellákra osztják fel az indexelendő tartományt. A GEOGRAPHY_GRID az a piramisos, kifeketetős séma, ami látható volt a korábbi rajzon.
No, ezektől az adatoktól nem lettünk sokkal okosabbak.
Nézzük meg a másik rendszer-nézetet:
select * from sys.spatial_index_tessellations
where object_id = object_id('USCity')
object_id index_id tessellation_scheme bounding_box_xmin bounding_box_ymin bounding_box_xmax bounding_box_ymax level_1_grid level_1_grid_desc level_2_grid level_2_grid_desc level_3_grid level_3_grid_desc level_4_grid level_4_grid_desc cells_per_object ----------- ----------- ------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ------------ ------------------------------ ------------ ------------------------------ ------------ ------------------------------ ------------ ------------------------------ ---------------- 80719340 64000 GEOGRAPHY_GRID NULL NULL NULL NULL 64 MEDIUM 64 MEDIUM 64 MEDIUM 64 MEDIUM 16
Ez már érdekesebb. A bounding_boxok nullok, mert mint írtam, nem kell határokat adni a geography indexnek, a Föld felülete véges határt alkot. A level_1_grid 64 és a level_1_grid_desc MEDIUM ugyanazt mondja, hogy 8×8-as a legdurvább felbontású rácsozat. Azért az elég nagy, az egész északi (és déli) félteke 64 részre van felbontva. Ok, de van még 3 szint. Ez azt jelenti, hogy csak szélességben számolva 8^4-en = 4096 részre van osztva a Föld. Az egyenlítő kb. 40e km hosszú, ezért ez az index kb. 10 km-es részekre vágja fel.
Update: egy MVP kolléga, Simon Sabin jelezte, hogy nem 10km a default index felbontás, hanem 2.5km. Ez azért van, mert az egyenlítőt a fenti piramisos ábra alapján a rács kerületére vetítik le, ami négyszer olyan hosszú, mint egy oldal, én pedig egy oldalra számoltam a felbontást.
Ez azért elég durva felbontás, főleg, mivel pont ebben a nagyságrendben szűrtünk a segítségével. Ennek ellenére nem lettek fals adatok a kimenetben. Miért? A végrehajtási terv bal alsó részén van egy Filter operátor. Ez arra szűr, hogy:
[AdventureWorks].[dbo].[USCity].[geom].STDistance([@la])<(1.000000000000000e+004) [/source] A bal oldali Merge Join-ból 20 sor potyog ki, valójában ennyit adott vissza az index, mivel durva a felbontása. A Filter és Nested Loop Join után már csak 10 sor maradt, ami már a helyes kimenet. Azaz igaz, hogy az index durva felbontása miatt jöttek be felesleges sorok, de nem baj, 20 sorból mégis csak könnyeb kiválasztani a jókat a lassú függvény (STDistance) tényleges végrehajtásával, mint az eredeti 34000-ből. Finomkodjunk! Hozzuk létre a maximális felbontású indexet! [source='sql'] create spatial index idx_USCity_Spatial_2 on USCity(geom) using geography_grid with ( grids = (high, high, high, high) --,cells_per_object = 64 ); [/source] Ha az előző, medium index is rajta van a táblán, akkor a szerver nem használja ezt azt indexet, mert nem éri meg neki. Ledobva az előzőt vagy index hinttel ráerőszakolva erre a végrehajtási idő 160 ms körül alakul, ami kb. azonos az előző indexelt megoldással. Azonban a lapolvasások száma az ottani 1700-ról felugrott 4800-ra, ami nem meglepő, hisz jelentősen több adat tárol az indextábla. A végrehajtási tervben az index révén 12 sor jön vissza, azaz csak 2 a potya sor, köszönhető a finom felbontású indexnek. Ellenpróbaként csináltam egy low, low, low, low durva felbontású indexet is, ebben 4x4-esek a rácsok szintenként. Ekkor az index 148 sort válogat le, ebből szűrik le a tényleges 10-et. Ennek végrehajtási teljesítménymutatói nagyon hasonlóak az első indexéhez. Valószínűleg ha sűrű elhelyezkedésű adatokról lenne szó (pl. nem városok, hanem városon belüli házak), akkor viszont egy finomabb index érné meg, a durva miatt túl sok adatot kellene lassú módon szűrni a szervernek. Összegezve látható, hogy szépen lehet játszani, hogy az adatok eloszlásának megfelelően milyen felbontású indexet hozunk létre a spatial adatainknak, így játszthatunk az IO és a CPU költség között valamiféle optimumra. Tök szép otimalizálási munka lehet ez. És ezennel a spatial adatokról szóló újdonságokat lezárom, eleget beszéltem már róluk. Látható, hogy valami teljesen új, nagyon izgalmas dolog költözött be az SQL Serverbe, amivel olyan alkalmazásokat írhatunk, amit előtte nagyon nehéz lett volna hatékonyan implementálni egy sima relációs motoron.
Could you hire me? Contact me if you like what I’ve done in this article and think I can create value for your company with my skills.
LEAVE A COMMENT
1 COMMENTS