Az els\u0151 dolog, amit fogni kell, hogy a spatial indexek nem olyan egzaktak, mint amiket eddig l\u00e1ttunk. A r\u00e9szletek mell\u0151z\u00e9s\u00e9vel a k\u00f6vetkez\u0151r\u0151l van sz\u00f3.
\nA s\u00edkot felbontj\u00e1k cell\u00e1kra, mint amikor “kock\u00e1s” pap\u00edrra rajzolunk. Az alakzatok ezekre a n\u00e9gyzetekre vannak fektetve. Minden cell\u00e1t tov\u00e1bbi cell\u00e1kra bonthatjuk, \u00e9s ott is meghat\u00e1rozhatjuk, mely al-cell\u00e1kban van m\u00e9g benne egy alakzat, \u00e9s melyben nincs. Ez a dekompoz\u00edci\u00f3t max. 4 szinten folytatj\u00e1k, \u00edgy egyre finomabb felbont\u00e1sban gy\u0171jtenek inform\u00e1ci\u00f3t az alakzatr\u00f3l. Hogy ne szabaduljonak el az adatok, vannak szab\u00e1lyok, amelyek korl\u00e1tozz\u00e1k az adatmennyis\u00e9geket.<\/p>\n
![\"A](\"http:\/\/technet.microsoft.com\/en-us\/library\/Bb964712.ad7b2688-8006-4926-a728-63a81ecc0ec5(en-us,SQL.100).gif\")
<\/p>\n
\u00c9rezhet\u0151, hogy be kell hat\u00e1rolni a “kock\u00e1s pap\u00edr” m\u00e9ret\u00e9t, hogy v\u00e9ges m\u00e9ret\u0171 legyen az index, erre az index l\u00e9trehoz\u00e1sakor van lehet\u0151s\u00e9g. Ez azonban csak a geometry t\u00edpusra vonatkozik, a geographyn\u00e1l v\u00e9ges a ter\u00fclet\u00fcnk, hisz a F\u00f6ld felsz\u00edn\u00e9r\u0151l van sz\u00f3.<\/p>\n
![\"\"](\"http:\/\/technet.microsoft.com\/en-us\/library\/Bb964712.cc805492-1e9d-49f9-aee3-b809af503d18(en-us,SQL.100).gif\")
<\/p>\n
A geography t\u00edpus ellipszoid adatin\u00e1l m\u00e9g cifr\u00e1bb a helyzet, azokat levet\u00edtik s\u00edkba, \u00e9s \u00fagy dolgoznak vele.<\/p>\n
![\"F\u00f6ldi](\"http:\/\/technet.microsoft.com\/en-us\/library\/Bb964712.57bcf264-208e-4c92-9445-d5b7b0b30d68(en-us,SQL.100).gif\")
<\/p>\n
A val\u00f3s\u00e1g persze sokkal \u00f6sszetettebb, de nem vagyunk t\u00e9rk\u00e9p\u00e9szek, \u00edgy legyen el\u00e9g ennyi. :)<\/p>\n
Mire j\u00f3 ezek ut\u00e1n egy spatial index? Megfelel\u0151 k\u00f6r\u00fclm\u00e9nyek k\u00f6z\u00f6tt<\/a> az STIntersects(), STEquals(), \u00e9s STDistance() met\u00f3dusokat meg tudja t\u00e1mogatni egy spatial index.<\/p>\n Tegy\u00fcnk vele egy pr\u00f3b\u00e1t!<\/p>\n Az el\u0151z\u0151 r\u00e9szben a Dun\u00e1hoz k\u00f6zel es\u0151 v\u00e1rosokat kerest\u00fck meg, n\u00e9zz\u00fck meg ezt index t\u00e1mogat\u00e1ssal!<\/p>\n A t\u00e1bl\u00e1ban a v\u00e1rosok multi-pontk\u00e9nt vannak felv\u00e9ve, pedig mindegyik csak 1 pontb\u00f3l \u00e1ll. Konvert\u00e1ljuk \u00e1t \u0151ket igazi pontt\u00e1, hogy minden m\u0171velet rendesen menjen rajtuk:<\/p>\n \u00cdgy az alapadataink:<\/p>\n Vegy\u00fck el\u0151 kor\u00e1bbi p\u00e9ld\u00e1nkat, a Dun\u00e1hoz 10 km-n\u00e9l k\u00f6zelebbi v\u00e1rosok list\u00e1j\u00e1t.<\/p>\n Elvileg ett\u0151l m\u00e1s lehetne a kor\u00e1bbi lek\u00e9rdez\u00e9s v\u00e9grehajt\u00e1si terve. De nem lesz az. Annyira kicsit a t\u00e1bl\u00e1nk (p\u00e1r 10 sor), hogy esze \u00e1g\u00e1ban sincs haszn\u00e1lni egy mozaikos, r\u00e1csos ide-oda vet\u00edtett indexet, a sima Filter jobban meg\u00e9ri neki.<\/p>\n Nagyobb adatmennyis\u00e9gre van sz\u00fcks\u00e9g\u00fcnk. Mivel szabad informatikai adatok ter\u00e9n (meg m\u00e1s t\u00e9ren is) Magyarorsz\u00e1g a b\u00e9ka segge alatt van, szedj\u00fcnk \u00f6ssze n\u00e9mi adatot Amerik\u00e1b\u00f3l. Itt let\u00f6lthet\u0151<\/a> sok izgalmas inf\u00f3. P\u00e9ld\u00e1ul a telep\u00fcl\u00e9sek list\u00e1ja, koordin\u00e1t\u00e1i<\/a> meg\u00e9rnek egy mis\u00e9t. Ez bet\u00f6lt\u00f6ttem a USCity t\u00e1bl\u00e1ba, 35432 sor lett.<\/p>\n Keress\u00fck meg azokat a v\u00e1rosokat, amelyek Los Angeles 10 km-es k\u00f6rzet\u00e9ben vannak:<\/p>\n Az index lehet GEOGRAPHY vagy GEOMETRY, nyilv\u00e1n az oszlop t\u00edpus\u00e1t\u00f3l f\u00fcgg\u0151en. A tessellation_scheme a mozaikoz\u00e1s m\u00f3dszer\u00e9t \u00edrja le, ez az a folyamat, amiben egyre kisebb cell\u00e1kra osztj\u00e1k fel az indexelend\u0151 tartom\u00e1nyt. A GEOGRAPHY_GRID az a piramisos, kifeketet\u0151s s\u00e9ma, ami l\u00e1that\u00f3 volt a kor\u00e1bbi rajzon. N\u00e9zz\u00fck meg a m\u00e1sik rendszer-n\u00e9zetet:<\/p>\n Ez m\u00e1r \u00e9rdekesebb. A bounding_boxok nullok, mert mint \u00edrtam, nem kell hat\u00e1rokat adni a geography indexnek, a F\u00f6ld fel\u00fclete v\u00e9ges hat\u00e1rt alkot. A level_1_grid 64 \u00e9s a level_1_grid_desc MEDIUM ugyanazt mondja, hogy 8×8-as a legdurv\u00e1bb felbont\u00e1s\u00fa r\u00e1csozat. Az\u00e9rt az el\u00e9g nagy, az eg\u00e9sz \u00e9szaki (\u00e9s d\u00e9li) f\u00e9lteke 64 r\u00e9szre van felbontva. Ok, de van m\u00e9g 3 szint. Ez azt jelenti, hogy csak sz\u00e9less\u00e9gben sz\u00e1molva 8^4-en = 4096 r\u00e9szre van osztva a F\u00f6ld. Az egyenl\u00edt\u0151 kb. 40e km hossz\u00fa, ez\u00e9rt ez az index kb. 10 km-es r\u00e9szekre v\u00e1gja fel. <\/p>\n\r\nupdate City\r\nset geom = geom.STStartPoint()\r\n\r\nselect\r\nCITY_NAME, geom.ToString()\r\nfrom City\r\n<\/pre>\n
\r\nKosice POINT (48.70000118311 21.2500004483)\r\nRijeka POINT (45.333301183109988 14.433300448300003)\r\nLodz POINT (51.778000183109988 19.4759994483)\r\nKalisz POINT (51.757999183109995 18.083000448299998)\r\nSieradz POINT (51.59600018311 18.732999448300006)\r\nPiotrkow Trybunalski POINT (51.409000183109988 19.691000448300002)\r\nRadom POINT (51.39600018311 21.158000448299987)\r\nLublin POINT (51.24200018311 22.577999448300005)\r\n...\r\n<\/pre>\n
\r\ndeclare @danube geography = geography::STPointFromText('POINT(0 0)', 4326);\r\n\r\nselect @danube = @danube.STUnion(geom)\r\nfrom River where NAME = N'Danube'\r\n\r\nselect CITY_NAME, \r\ngeom.ToString() 'A v\u00e1ros', \r\ngeom.STDistance(@danube) 'T\u00e1vols\u00e1g a foly\u00f3t\u00f3l' \r\nfrom City\r\nwhere geom.STDistance(@danube) < 10000\r\n[\/source]\r\n\r\nA v\u00e9grehajt\u00e1si terv:\r\n\r\n<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>\r\n\r\nNo, a Filternek kellene kiesni vagy legal\u00e1bbis a k\u00f6lts\u00e9g\u00e9nek cs\u00f6kkeni az index hat\u00e1s\u00e1ra. Az alap be\u00e1ll\u00edt\u00e1sokkal hozzunk l\u00e9tre egy spatial indexet:\r\n\r\n[source='sql']\r\ncreate spatial index idx_City_Spatial_1\r\non City(geom)\r\n<\/pre>\n\r\ndeclare @la geography = (select geom\r\nfrom USCity\r\nwhere name = 'Los Angeles' \r\nand County = 'Los Angeles County')\r\n\r\nselect name\r\nfrom USCity\r\nwhere geom.STDistance(@la) < 10000\r\n[\/source]\r\n\r\nNem kellene lok\u00e1lis v\u00e1ltoz\u00f3t bevezetni, de \u00edgy sz\u00e9tv\u00e1lik a v\u00e9grehajt\u00e1si terv, \u00edgy jobban l\u00e1tszik az index hat\u00e1sa.\r\n\r\nA kimenet:\r\n[source='c']\r\nLos Angeles\r\nCity Terrace\r\nEast Los Angeles\r\nVernon\r\nCommerce\r\nHuntington Park\r\nMaywood\r\nFlorence\r\nBell\r\nWalnut Park\r\n[\/source]\r\n\r\nIndex n\u00e9lk\u00fcl a v\u00e9grehajt\u00e1s \u00e1tlagban 2800 ms-ot vesz ig\u00e9nybe, ebb\u0151l kb. 2000 a CPU k\u00f6lts\u00e9g, azaz igen er\u0151sen processzor intenz\u00edv a sz\u0171r\u00e9s. A lapolvas\u00e1sok sz\u00e1ma 1850.\r\n\r\nRakjunk r\u00e1 egy spatial indexet!\r\n\r\n[source='sql']\r\ncreate spatial index idx_USCity_Spatial_1\r\non USCity(geom)\r\n[\/source]\r\n\r\nA v\u00e9grehajt\u00e1si id\u0151 leesik 160ms-ra! A lapolvas\u00e1sok sz\u00e1ma 1720 lett, azaz ebben nem lett jelent\u0151s k\u00fcl\u00f6nbs\u00e9g, de a CPU id\u0151 leesett kb. 50 ms-ra, 2000-r\u0151l. Az\u00e9rt ez igen nagy nyeres\u00e9g.\r\n\r\nAz index n\u00e9lk\u00fcli v\u00e9grehajt\u00e1si terv:\r\n\r\n<a href='http:\/\/soci.hu\/blog\/wp-content\/uploads\/2008\/02\/spatialopwithoutindex2.png' title='Spatial sz\u0171r\u00e9s index n\u00e9lk\u00fcl' target='_blank'><img src='http:\/\/soci.hu\/blog\/wp-content\/uploads\/2008\/02\/spatialopwithoutindex2.png' alt='Spatial sz\u0171r\u00e9s index n\u00e9lk\u00fcl' \/><\/a>\r\n\r\nAz el\u0151bbi index-szel:\r\n\r\n<a href='http:\/\/soci.hu\/blog\/wp-content\/uploads\/2008\/02\/spatialopwithdefaultindex2.png' title='Spatial sz\u0171r\u00e9s alap index-szel' target='_blank'><img src='http:\/\/soci.hu\/blog\/wp-content\/uploads\/2008\/02\/spatialopwithdefaultindex2.png' alt='Spatial sz\u0171r\u00e9s alap index-szel' \/><\/a>\r\n\r\nA jobb als\u00f3 Clustered Index Seek \u00e9rdekes. A Seek Predicate-je a k\u00f6vetkez\u0151:\r\n\r\n[source='c']\r\nSeek Keys[1]: Start: [AdventureWorks].[sys].[extended_index_80719340_64000].Cell_Id >= Scalar Operator([Expr1009]), \r\nEnd: [AdventureWorks].[sys].[extended_index_80719340_64000].Cell_Id <= Scalar Operator([Expr1010])\r\n[\/source]\r\n\r\nAzaz, az XML Shredinghez hasonl\u00f3an itt is fel\u00e9p\u00edtenek egy seg\u00e9dt\u00e1bl\u00e1t az index r\u00e9sz\u00e9re, \u00e9s abban keresnek. A seg\u00e9dt\u00e1bla neve: [sys].[extended_index_80719340_64000].\r\nAzonnal k\u00eds\u00e9rt\u00e9st \u00e9rz\u00fcnk pesze, hogy belen\u00e9zz\u00fcnk:\r\n\r\n[source='sql']\r\nselect * from [sys].[extended_index_80719340_64000]\r\n[\/source]\r\n\r\nMeg is kapjuk a magunk\u00e9t:\r\n\r\n[source='c']\r\nMsg 208, Level 16, State 1, Line 1\r\nInvalid object name 'sys.extended_index_80719340_64000'.\r\n[\/source]\r\n\r\nNa ne hazudjunk k\u00e9rem, menj\u00fcnk csak be a DAC kapcsolaton keresz\u00fcl (ADMIN:g\u00e9pn\u00e9v\\instance n\u00e9v):\r\n\r\n[source='c']\r\nCell_Id Cell_Attributes SRID pk0\r\n------------ --------------- ----------- -----------\r\n0x200A2A2C04 1 4326 34751\r\n0x200A2A3C04 1 4326 34756\r\n0x200A2B3404 1 4326 34762\r\n0x200A2B3704 1 4326 34763\r\n0x200A2B3804 1 4326 34764\r\n...\r\n[\/source]\r\n\r\nEbben az index t\u00e1bl\u00e1ban pont annyi sor van, mint az eredetiben, \u00e9s a pk0 oszlop teremt kapcsolatot a kett\u0151 k\u00f6z\u00f6tt, a v\u00e9grehajt\u00e1si tervben a bal oldali Merge Join illeszti a kett\u0151t \u00f6ssze, im\u00edgyen: \r\n\r\n[source='c']\r\n([AdventureWorks].[dbo].[USCity].ID) = \r\n([AdventureWorks].[sys].[extended_index_80719340_64000].pk0)\r\n[\/source]\r\n\r\nAz SRID oszlop ismer\u0151s lehet, az az adatunk SRID-je, volt m\u00e1r r\u00f3la sz\u00f3 az <a href="http:\/\/soci.hu\/blog\/index.php\/2008\/01\/21\/sql-server-2008-ujdonsagok-14-terbeli-adattipusok-1\/">els\u0151 r\u00e9szben<\/a>. Az els\u0151 k\u00e9t oszlop jelent\u00e9se egyel\u0151re ismeretlen.\r\n\r\nVess\u00fck \u00f6ssze amit a h\u00e1ts\u00f3 ny\u00edl\u00e1son \u00e1t felfedezt\u00fcnk a hivatalosan is l\u00e1that\u00f3 inf\u00f3val!\r\n\r\n[source='sql']\r\nselect name, spatial_index_type_desc, tessellation_scheme\r\nfrom sys.spatial_indexes\r\nwhere object_id = object_id('USCity')\r\n<\/pre>\n\r\nname spatial_index_type_desc tessellation_scheme\r\n-------------------------------------------------- -------------------------------------------------- --------------------------------------------------\r\nidx_USCity_Spatial_1 GEOGRAPHY GEOGRAPHY_GRID\r\n<\/pre>\n
\nNo, ezekt\u0151l az adatokt\u00f3l nem lett\u00fcnk sokkal okosabbak.<\/p>\n\r\nselect * from sys.spatial_index_tessellations\r\nwhere object_id = object_id('USCity')\r\n<\/pre>\n\r\nobject_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\r\n----------- ----------- ------------------------------ ---------------------- ---------------------- ---------------------- ---------------------- ------------ ------------------------------ ------------ ------------------------------ ------------ ------------------------------ ------------ ------------------------------ ----------------\r\n80719340 64000 GEOGRAPHY_GRID NULL NULL NULL NULL 64 MEDIUM 64 MEDIUM 64 MEDIUM 64 MEDIUM 16\r\n<\/pre>\n