{"id":1526,"date":"2014-04-30T08:44:17","date_gmt":"2014-04-30T06:44:17","guid":{"rendered":"http:\/\/soci.hu\/blog\/?p=1526"},"modified":"2014-04-30T08:44:17","modified_gmt":"2014-04-30T06:44:17","slug":"sql-server-2014-ujdonsagok-4-in-memory-oltp-range-indexek-mukodese","status":"publish","type":"post","link":"https:\/\/soci.hu\/blog\/index.php\/2014\/04\/30\/sql-server-2014-ujdonsagok-4-in-memory-oltp-range-indexek-mukodese\/","title":{"rendered":"SQL Server 2014 \u00fajdons\u00e1gok – 4. In-Memory OLTP – range indexek m\u0171k\u00f6d\u00e9se"},"content":{"rendered":"

A kor\u00e1bbi r\u00e9szekb\u0151l l\u00e1ttuk, hogy a mem\u00f3ria t\u00e1bl\u00e1k sorait nem IAM page-ek vagy clustered index tartja egyben, hanem egy index, amit a primary key m\u00f6g\u00e9 kell l\u00e9trehozni. Ez lehet hash index is, de lehet egy nonclustered index is. Ezt mem\u00f3ria t\u00e1bl\u00e1kn\u00e1l range indexeknek is szokt\u00e1k h\u00edvni, mivel ezzel lehet kisebb-nagyobb oper\u00e1torokkal tartom\u00e1nyokra is keresni, a hash index csak point lookupra j\u00f3.
\nAki j\u00f3l ismeri a nonclustered indexeket diszk t\u00e1bl\u00e1kn\u00e1l, annak azonnal beugorhat, hogy a nonclu index csak kev\u00e9s sor eset\u00e9n szokott hat\u00e9kony lenni, sok sor eset\u00e9n csak akkor, ha miden adat benne van az indexben. A f\u0151 id\u0151t a nonclustered index v\u00e9g\u00e9b\u0151l a val\u00f3di adatokra \u00e1tnavig\u00e1l\u00e1s viszi el, ezt h\u00edv\u00e1k bookmark lookup vagy key lookupnak a planben.
\nMem\u00f3ria indexek eset\u00e9n NINCS ez az overhead. Minden nclu index cover indexnek tekinthet\u0151, amint el\u00e9rt\u00fcnk a lev\u00e9lszintre, azonnal “ott” van az adat. Mivel a sorok nincsenek lapokba szervezve, nincsenek page latch-ek sem.
\nHogyan vannak szervezve a mem\u00f3ria t\u00e1bl\u00e1k nonclustered indexei?
\nNyilv\u00e1n ez is egy fa, a norm\u00e1l B-Tree m\u00f3dos\u00edt\u00e1sa, Bw-Tree a neve. Aki m\u00e9lys\u00e9geiben akarja tanulm\u00e1nyozni, itt egy link<\/a> az MS Research cikkhez.
\nA c\u00e9l itt is a lock \u00e9s latch mentes kialak\u00edt\u00e1s volt. Az indexlapok nem fix m\u00e9ret\u0171ek, hanem v\u00e1ltoz\u00f3ak. Ha egyszer elk\u00e9sz\u00fclt egy lap, az t\u00f6bb\u00e9 nem m\u00f3dosul. A hash indexekn\u00e9l l\u00e1ttuk, hogy a lock free adatstrukt\u00far\u00e1k egyik implement\u00e1ci\u00f3ja, amikor nem m\u00f3dos\u00edtanak valamit, immutable az objektum, mert ahhoz szinkroniz\u00e1lni kellene a hozz\u00e1f\u00e9r\u00e9st, hanem k\u00e9sz\u00edtenek egy \u00faj p\u00e9ld\u00e1nyt, majd az eredetit egy mozdulattal kicser\u00e9lik az \u00fajra. Ezt az elvet haszn\u00e1lj\u00e1k a BwTreeben is.<\/p>\n

\"BwTree\"<\/a><\/p>\n

Az \u00e1br\u00e1ban az a tr\u00fckk, hogy az index lapok NEM egym\u00e1s c\u00edm\u00e9t tartalmazz\u00e1k, hanem a m\u00e1sik lap sorsz\u00e1m\u00e1t a bal oldalon l\u00e1that\u00f3 Page Mapping Table-ben. Azaz beraktak egy indirekci\u00f3t a fa lapjainak \u00f6sszel\u00e1ncol\u00e1s\u00e1ba. \u00cdgy m\u00e1r lehet azzal j\u00e1tszani, hogy sose m\u00f3dos\u00edtanak egy index lapot, hanem k\u00e9sz\u00edtenek egy \u00fajat, \u00e9s azt bel\u00e1ncolj\u00e1k a Page Mapping Table-be. Ez a m\u00e1r ismert CompareExchange felhaszn\u00e1l\u00e1s\u00e1val.
\nA root lap l\u00e1that\u00f3an 3 ir\u00e1nyba \u00e1gazik el. A 10 index kulcs alattiak a 3-as lapon lesznek, a 11-20 k\u00f6z\u00f6ttiek a 2-esen, \u00e9s a 21-28 k\u00f6z\u00f6ttiek a 14-esen. L\u00e1that\u00f3 teh\u00e1t, hogy minden index bejegyz\u00e9s egy kulcs \u00e9rt\u00e9ket \u00e9s egy lapsz\u00e1mot tartalmaz, ami a k\u00f6vetkez\u0151 szintre visz le.
\nA lev\u00e9lszint\u0171 lapok m\u00e1r k\u00f6zvetlen\u00fcl a sorokra mutatnak. Ha egy kulcs \u00e9rt\u00e9khez t\u00f6bb sor is tartozik, azok \u00f6ssze vannak l\u00e1ncolva a hash indexn\u00e9l l\u00e1that\u00f3 m\u00f3don. (Diszk t\u00e1bl\u00e1kn\u00e1l a clustered indexekn\u00e9l ha nem egyedi az index kulcs, akkor egy 32 bites sz\u00e1mot gener\u00e1lnak mell\u00e9, hogy egyediv\u00e9 v\u00e1ljon. Ott nincs ilyen l\u00e1ncol\u00e1s, ez\u00e9rt kell ez.)<\/p>\n

K\u00f6zbens\u0151 szinten teh\u00e1t \u00fagy m\u00f3dos\u00edtanak egy index lapot, hogy lem\u00e1solj\u00e1k, m\u00f3dos\u00edtj\u00e1k, majd kicser\u00e9lik a Page Mapping Table-ben a r\u00e9git az \u00faj verzi\u00f3ra. Ez lock-free, de el\u00e9gg\u00e9 er\u0151forr\u00e1s ig\u00e9nyes. Lev\u00e9lszinten ezt m\u00e1r nem lehet elj\u00e1tszani, mert t\u00fal nagy lenne a k\u00f6lts\u00e9ge. Ott m\u00e1s tr\u00fckk\u00f6t haszn\u00e1lnak. Amikor m\u00f3dosul egy kulcs\u00e9rt\u00e9k, akkor beraknak egy delta lapot az index lap el\u00e9. Ez a lap azt \u00edrja le, hogy az index lapon lev\u0151 inform\u00e1ci\u00f3t milyen m\u00f3dos\u00edt\u00e1sok \u00e9rtek. Az ilyen index lap picike, hisz csak egy kulcsot tartalmaz, a m\u00f3dos\u00edt\u00e1s jelleg\u00e9t (insert vagy delete), illetve mutat\u00f3t a “m\u00f3dos\u00edtott” lapra.<\/p>\n

Az al\u00e1bbi \u00e1br\u00e1n egy insert majd id\u0151ben ut\u00e1na egy delete lenyomata l\u00e1tszik. <\/p>\n

\"BwTreeUpdate\"<\/a><\/p>\n

El\u0151sz\u00f6r besz\u00fartak egy 50-es index kulcs\u00fa sort. A Page Mapping Table a m\u0171velet el\u0151tt a fekete ny\u00edl ment\u00e9n az eredeti lapra mutatott. Az insert ut\u00e1n bel\u00e1ncolj\u00e1k az index lap el\u00e9 a pirossal jelzett delta rekordot. \u00cdgy \u00f6sszerakhat\u00f3 az inf\u00f3, hogy az index lapon l\u00e1that\u00f3 inform\u00e1ci\u00f3kon k\u00edv\u00fcl m\u00e9g van egy \u00faj sorunk.
\nHa ut\u00e1na t\u00f6rlik a 48-as kulcs\u00fa sort, akkor \u00fajra bel\u00e1ncolnak egy delta rekordot, ezt mutatja a lila ny\u00fal.
\nMi a po\u00e9n ebben? A delta lapokat van id\u0151 \u00f6sszerakni, nem kell kapkodni, lockolni. Amikor k\u00e9sz, r\u00e1mutat a k\u00f6vetkez\u0151 index lapra, ami vagy egy delta page, vagy egy igazi index lap, akkor m\u00e1r csak egy CompareExchange, \u00e9s a Page Mapping Table m\u00e1ris az \u00faj lapunkra mutat, bel\u00e1ncoltuk a list\u00e1ba. Ha megel\u0151ztek, semmi gond, nekifutunk m\u00e9g egyszer. Nyilv\u00e1n ez\u00e9rt h\u00edvj\u00e1k ezt optimista megk\u00f6zel\u00edt\u00e9snek, mert arra sz\u00e1m\u00edtunk, kev\u00e9s \u00fctk\u00f6z\u00e9s lesz, \u00edgy meg\u00e9ri nekik n\u00e9ha \u00fajragener\u00e1lni adatstrukt\u00far\u00e1kat, jobban, mint \u00e1lland\u00f3an v\u00e1rni a m\u00e1sikra.<\/p>\n

Az update-et egy insert majd egy delete-k\u00e9nt val\u00f3s\u00edtanak meg, az k\u00e9t delta rekordot eredm\u00e9nyez. <\/p>\n

A sok delta rekord persze j\u00f3l belass\u00edtan\u00e1 a m\u0171veleteket, ez\u00e9rt azokat gondozni kell. Ha egy m\u0171velet eredm\u00e9nyek\u00e9ppen 16-n\u00e1l hosszabb\u00e1 v\u00e1lik a delta rekord lista, akkor a v\u00e1ltoz\u00e1sok hat\u00e1s\u00e1t az eredeti index lapra \u00f6sszepakolj\u00e1k egy \u00faj index lapra, majd kicser\u00e9lik a r\u00e9gi lapot az \u00fajra. A r\u00e9gi lapokat elviszi a Garbage Collector (err\u0151l majd k\u00e9s\u0151bbi r\u00e9szben \u00edrok, a poros sarkokkal egy\u00fctt).<\/p>\n

Ha egy lap m\u00e9rete el\u00e9ri a 8k-t a sok insert miatt, akkor azt kett\u00e9v\u00e1gj\u00e1k (lehetne nagyobb, nincs 8ks lapm\u00e9ret mint a diszkt\u00e1bl\u00e1kn\u00e1l, csak kiegyens\u00falyozatlan lenne a fa, ha t\u00fal sok sor lenne egy lapon). Ezt k\u00e9t atomi CompareExchange-dzsel val\u00f3s\u00edtj\u00e1k meg. <\/p>\n

Ha viszont a t\u00f6rl\u00e9sek miatt a lap m\u00e9rete 800 byte al\u00e1 esik, vagy m\u00e1r csak 1 sort tartalmaz, hozz\u00e1csapj\u00e1k a szomsz\u00e9dhoz a sorait, ezt is k\u00e9t atomi l\u00e9p\u00e9sben.<\/p>\n

\u00d6sszegezve, ha nagyon gyors point lookup kell, azaz egyedi vagy nagyon j\u00f3l sz\u00f3r\u00f3 kulcs ment\u00e9n kell felolvasni sorokat, akkor egy j\u00f3 bucket counttal meg\u00e1ldott hash index lehet az optim\u00e1lis megold\u00e1s, mivel a hash indexnek nincs ez a m\u00f3dos\u00edt\u00e1si overheadje.<\/p>\n

Ha viszont tartom\u00e1nyra kell keresni, vagy nem nagyon egyediek az \u00e9rt\u00e9kek, akkor a range index lesz hat\u00e9kony.<\/p>\n

A k\u00f6vetkez\u0151 r\u00e9szben a p\u00e1rhuzamos m\u00f3dos\u00edt\u00e1sok szervez\u00e9s\u00e9t n\u00e9zz\u00fck meg (optimistic concurrency).<\/p>\n","protected":false},"excerpt":{"rendered":"

A kor\u00e1bbi r\u00e9szekb\u0151l l\u00e1ttuk, hogy a mem\u00f3ria t\u00e1bl\u00e1k sorait nem IAM page-ek vagy clustered index tartja egyben, hanem egy index, amit a…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,4,30,87],"tags":[],"class_list":["post-1526","post","type-post","status-publish","format-standard","hentry","category-adatbazisok","category-szakmai-elet","category-sql-server","category-sql-server-2014"],"_links":{"self":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1526","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1526"}],"version-history":[{"count":6,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1526\/revisions"}],"predecessor-version":[{"id":1588,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1526\/revisions\/1588"}],"wp:attachment":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1526"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1526"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1526"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}