|
| 1 | +$PostgreSQL: pgsql/src/backend/access/gist/README,v 1.1 2005/09/15 16:39:15 teodor Exp $ |
| 2 | + |
| 3 | +This directory contains an implementation of GiST indexing for Postgres. |
| 4 | + |
| 5 | +GiST is stands for Generalized Search Tree. It was introduced in seminal paper |
| 6 | +"Generalized Search Trees for Database Systems", 1995,Joseph M. Hellerstein, |
| 7 | +Jeffrey F. Naughton,Avi Pfeffer (http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps) and implemented by J. Hellerstein and P.Aoki in early version of |
| 8 | +PostgreSQL ( more details is available from The GiST Indexing Project at |
| 9 | +Berkeley at http://gist.cs.berkeley.edu/). As an "university" project it had a |
| 10 | +limited number of features and was in rare use. |
| 11 | + |
| 12 | +Current implementation of GiST supports: |
| 13 | + |
| 14 | + * Variable length keys |
| 15 | + * Composite keys (multi-key) |
| 16 | + * provides NULL-safe interface to GiST core |
| 17 | + * Concurrency |
| 18 | + * Recovery support via WAL logging |
| 19 | + |
| 20 | +Concurrence algoritms implemented in PostgreSQL were developed following paper |
| 21 | +"Access Methods for Next-Generation Database Systems" by Marcel Kornaker (http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz). |
| 22 | + |
| 23 | +Original algorithms were modified by following reasons: |
| 24 | + |
| 25 | +* They should be adapted to PostgreSQL conventions. For example, SEARCH |
| 26 | + algorithm was considerably changed, because in PostgreSQL function search |
| 27 | + should return one tuple (next), not all tuples at once. Also, it should |
| 28 | + release page locks between calls. |
| 29 | +* since we added support of variable length keys, it's not possible to guarantee |
| 30 | + enough free space for all keys on pages after splitting. User defined function |
| 31 | + picksplit doesn't have information about size of tuples (each tuple may |
| 32 | + contain several keys as in multicolumn index while picksplit could work with |
| 33 | + only one key ) and pages. |
| 34 | +* We modified original INSERT algorithm for perfomance reason. In particularly, |
| 35 | + it's single-pass algorithm. |
| 36 | +* Since the paper were theoretical, some details were omited and we have to find |
| 37 | + out ourself how to solve some specific problems. |
| 38 | + |
| 39 | +Because of above reasons, we have to revised interaction of GiST core and |
| 40 | +PostgreSQL WAL system. Moreover, we encountered (and solved) a problem of |
| 41 | +uncompleted insertions when recovering after crash, which was not touched in |
| 42 | +the paper. |
| 43 | + |
| 44 | +SEARCH ALGORITHM |
| 45 | +Function gettuple finds tuple, which satisfy search predicate. It store their |
| 46 | +state and returns next tuple under subsequent calls. Stack contains page, |
| 47 | +its LSN and LSN of parent page and currentposition is saved between calls. |
| 48 | + |
| 49 | +gettuple(search-pred) |
| 50 | +if ( firsttime ) |
| 51 | +push(stack, [root, 0, 0]) // page, LSN, parentLSN |
| 52 | +currentposition=0 |
| 53 | +end |
| 54 | +ptr = top of stack |
| 55 | +while(true) |
| 56 | +latch( ptr->page, S-mode ) |
| 57 | +if ( ptr->page->lsn != ptr->lsn ) |
| 58 | +ptr->lsn = ptr->page->lsn |
| 59 | +currentposition=0 |
| 60 | +if ( ptr->parentlsn < ptr->page->nsn ) |
| 61 | +add to stack rightlink |
| 62 | +else |
| 63 | +currentposition++ |
| 64 | +end |
| 65 | + |
| 66 | +while(true) |
| 67 | +currentposition = find_first_match( currentposition ) |
| 68 | +if ( currentposition is invalid ) |
| 69 | +unlatch( ptr->page ) |
| 70 | +pop stack |
| 71 | +ptr = top of stack |
| 72 | +if (ptr is NULL) |
| 73 | +return NULL |
| 74 | +break loop |
| 75 | +else if ( ptr->page is leaf ) |
| 76 | +unlatch( ptr->page ) |
| 77 | +return tuple |
| 78 | +else |
| 79 | +add to stack child page |
| 80 | +end |
| 81 | +currentposition++ |
| 82 | +end |
| 83 | +end |
| 84 | + |
| 85 | + |
| 86 | +INSERT ALGORITHM |
| 87 | + |
| 88 | +INSERT guarantees that the GiST tree remains balanced. User defined key method |
| 89 | +Penalty is used for choosing a subtree to insert; method PickSplit is used for |
| 90 | +the node splitting algorithm; method Union is used for propagating changes |
| 91 | +upward to maintain the tree properties. |
| 92 | + |
| 93 | +NOTICE: We modified original INSERT algorithm for perfomance reason. In |
| 94 | +particularly, it's single-pass algorithm. |
| 95 | + |
| 96 | +Function findLeaf is used to identify subtree for insertion. Page, in which |
| 97 | +insertion is proceeded, is locked as well as its parent page. Functions |
| 98 | +findParent and findPath are used to find parent pages, which could be changed |
| 99 | +because of concurrent access. Function pageSplit is reccurrent and could split |
| 100 | +page by more than 2 pages, which could be necessary if keys have different |
| 101 | +lengths or more than one key are inserted (in such situation, user defined |
| 102 | +function pickSplit cannot guarantee free space on page). |
| 103 | + |
| 104 | +findLeaf(new-key) |
| 105 | +push(stack, [root, 0]) //page, LSN |
| 106 | +while(true) |
| 107 | +ptr = top of stack |
| 108 | +latch( ptr->page, S-mode ) |
| 109 | +ptr->lsn = ptr->page->lsn |
| 110 | +if ( exists ptr->parent AND ptr->parent->lsn < ptr->page->nsn ) |
| 111 | +unlatch( ptr->page ) |
| 112 | +pop stack |
| 113 | +else if ( ptr->page is not leaf ) |
| 114 | +push( stack, [get_best_child(ptr->page, new-key), 0] ) |
| 115 | +unlatch( ptr->page ) |
| 116 | +else |
| 117 | +unlatch( ptr->page ) |
| 118 | +latch( ptr->page, X-mode ) |
| 119 | +if ( ptr->page is not leaf ) |
| 120 | +//the only root page can become a non-leaf |
| 121 | +unlatch( ptr->page ) |
| 122 | +else if ( ptr->parent->lsn < ptr->page->nsn ) |
| 123 | +unlatch( ptr->page ) |
| 124 | +pop stack |
| 125 | +else |
| 126 | +return stack |
| 127 | +end |
| 128 | +end |
| 129 | +end |
| 130 | + |
| 131 | +findPath( stack item ) |
| 132 | +push stack, [root, 0, 0] // page, LSN, parent |
| 133 | +while( stack ) |
| 134 | +ptr = top of stack |
| 135 | +latch( ptr->page, S-mode ) |
| 136 | +if ( ptr->parent->page->lsn < ptr->page->nsn ) |
| 137 | +push stack, [ ptr->page->rightlink, 0, ptr->parent ] |
| 138 | +end |
| 139 | +for( each tuple on page ) |
| 140 | +if ( tuple->pagepointer == item->page ) |
| 141 | +return stack |
| 142 | +else |
| 143 | +add to stack at the end [tuple->pagepointer,0, ptr] |
| 144 | +end |
| 145 | +end |
| 146 | +unlatch( ptr->page ) |
| 147 | +pop stack |
| 148 | +end |
| 149 | + |
| 150 | +findParent( stack item ) |
| 151 | +parent = item->parent |
| 152 | +latch( parent->page, X-mode ) |
| 153 | +if ( parent->page->lsn != parent->lsn ) |
| 154 | +while(true) |
| 155 | +search parent tuple on parent->page, if found the return |
| 156 | +rightlink = parent->page->rightlink |
| 157 | +unlatch( parent->page ) |
| 158 | +if ( rightlink is incorrect ) |
| 159 | +break loop |
| 160 | +end |
| 161 | +parent->page = rightlink |
| 162 | +latch( parent->page, X-mode ) |
| 163 | +end |
| 164 | +newstack = findPath( item->parent ) |
| 165 | +replace part of stack to new one |
| 166 | +return findParent( item ) |
| 167 | +end |
| 168 | + |
| 169 | +pageSplit(page, allkeys) |
| 170 | +(lkeys, rkeys) = pickSplit( allkeys ) |
| 171 | +if ( page is root ) |
| 172 | +lpage = new page |
| 173 | +else |
| 174 | +lpage = page |
| 175 | +rpage = new page |
| 176 | +if ( no space left on rpage ) |
| 177 | +newkeys = pageSplit( rpage, rkeys ) |
| 178 | +else |
| 179 | +push newkeys, union(rkeys) |
| 180 | +end |
| 181 | +if ( no space left on lpage ) |
| 182 | +push newkeys, pageSplit( lpage, lkeys ) |
| 183 | +else |
| 184 | +push newkeys, union(lkeys) |
| 185 | +end |
| 186 | +return newkeys |
| 187 | + |
| 188 | + |
| 189 | +placetopage(page, keysarray) |
| 190 | +if ( no space left on page ) |
| 191 | +keysarray = pageSplit(page, [ extract_keys(page), keysarray]) |
| 192 | +last page in chain gets old NSN, |
| 193 | +original and others - new NSN from current LSN |
| 194 | +if ( page is root ) |
| 195 | +make new root with keysarray |
| 196 | +end |
| 197 | +else |
| 198 | +put keysarray on page |
| 199 | +if ( length of keysarray > 1 ) |
| 200 | +keysarray = [ union(keysarray) ] |
| 201 | +end |
| 202 | +end |
| 203 | + |
| 204 | +insert(new-key) |
| 205 | +stack = findLeaf(new-key) |
| 206 | +keysarray = [new-key] |
| 207 | +ptr = top of stack |
| 208 | +while(true) |
| 209 | +findParent( ptr ) //findParent latches parent page |
| 210 | +keysarray = placetopage(ptr->page, keysarray) |
| 211 | +unlatch( ptr->page ) |
| 212 | +pop stack; |
| 213 | +ptr = top of stack |
| 214 | +if (length of keysarray == 1) |
| 215 | +newboundingkey = union(oldboundingkey, keysarray) |
| 216 | +if (newboundingkey == oldboundingkey) |
| 217 | +unlatch ptr->page |
| 218 | +break loop |
| 219 | +end |
| 220 | +end |
| 221 | +end |
| 222 | + |
| 223 | +Authors: |
| 224 | +Teodor Sigaev<teodor@sigaev.ru> |
| 225 | +Oleg Bartunov <oleg@sai.msu.su> |