| 1 |
src/backend/access/hash/README |
| 2 |
|
| 3 |
Hash Indexing |
| 4 |
============= |
| 5 |
|
| 6 |
This directory contains an implementation of hash indexing for Postgres. |
| 7 |
Most of the core ideas are taken from Margo Seltzer and Ozan Yigit, |
| 8 |
A New Hashing Package for UNIX, Proceedings of the Winter USENIX Conference, |
| 9 |
January 1991. (Our in-memory hashtable implementation, |
| 10 |
src/backend/utils/hash/dynahash.c, also relies on some of the same concepts; |
| 11 |
it is derived from code written by Esmond Pitt and later improved by Margo |
| 12 |
among others.) |
| 13 |
|
| 14 |
A hash index consists of two or more "buckets", into which tuples are |
| 15 |
placed whenever their hash key maps to the bucket number. The |
| 16 |
key-to-bucket-number mapping is chosen so that the index can be |
| 17 |
incrementally expanded. When a new bucket is to be added to the index, |
| 18 |
exactly one existing bucket will need to be "split", with some of its |
| 19 |
tuples being transferred to the new bucket according to the updated |
| 20 |
key-to-bucket-number mapping. This is essentially the same hash table |
| 21 |
management technique embodied in src/backend/utils/hash/dynahash.c for |
| 22 |
in-memory hash tables. |
| 23 |
|
| 24 |
Each bucket in the hash index comprises one or more index pages. The |
| 25 |
bucket's first page is permanently assigned to it when the bucket is |
| 26 |
created. Additional pages, called "overflow pages", are added if the |
| 27 |
bucket receives too many tuples to fit in the primary bucket page. |
| 28 |
The pages of a bucket are chained together in a doubly-linked list |
| 29 |
using fields in the index page special space. |
| 30 |
|
| 31 |
There is currently no provision to shrink a hash index, other than by |
| 32 |
rebuilding it with REINDEX. Overflow pages can be recycled for reuse |
| 33 |
in other buckets, but we never give them back to the operating system. |
| 34 |
There is no provision for reducing the number of buckets, either. |
| 35 |
|
| 36 |
As of PostgreSQL 8.4, hash index entries store only the hash code, not the |
| 37 |
actual data value, for each indexed item. This makes the index entries |
| 38 |
smaller (perhaps very substantially so) and speeds up various operations. |
| 39 |
In particular, we can speed searches by keeping the index entries in any |
| 40 |
one index page sorted by hash code, thus allowing binary search to be used |
| 41 |
within an index page. Note however that there is *no* assumption about the |
| 42 |
relative ordering of hash codes across different index pages of a bucket. |
| 43 |
|
| 44 |
|
| 45 |
Page Addressing |
| 46 |
--------------- |
| 47 |
|
| 48 |
There are four kinds of pages in a hash index: the meta page (page zero), |
| 49 |
which contains statically allocated control information; primary bucket |
| 50 |
pages; overflow pages; and bitmap pages, which keep track of overflow |
| 51 |
pages that have been freed and are available for re-use. For addressing |
| 52 |
purposes, bitmap pages are regarded as a subset of the overflow pages. |
| 53 |
|
| 54 |
Primary bucket pages and overflow pages are allocated independently (since |
| 55 |
any given index might need more or fewer overflow pages relative to its |
| 56 |
number of buckets). The hash code uses an interesting set of addressing |
| 57 |
rules to support a variable number of overflow pages while not having to |
| 58 |
move primary bucket pages around after they are created. |
| 59 |
|
| 60 |
Primary bucket pages (henceforth just "bucket pages") are allocated in |
| 61 |
power-of-2 groups, called "split points" in the code. That means at every new |
| 62 |
splitpoint we double the existing number of buckets. Allocating huge chunks |
| 63 |
of bucket pages all at once isn't optimal and we will take ages to consume |
| 64 |
those. To avoid this exponential growth of index size, we did use a trick to |
| 65 |
break up allocation of buckets at the splitpoint into 4 equal phases. If |
| 66 |
(2 ^ x) are the total buckets need to be allocated at a splitpoint (from now on |
| 67 |
we shall call this as a splitpoint group), then we allocate 1/4th (2 ^ (x - 2)) |
| 68 |
of total buckets at each phase of splitpoint group. Next quarter of allocation |
| 69 |
will only happen if buckets of the previous phase have been already consumed. |
| 70 |
For the initial splitpoint groups < 10 we will allocate all of their buckets in |
| 71 |
single phase only, as number of buckets allocated at initial groups are small |
| 72 |
in numbers. And for the groups >= 10 the allocation process is distributed |
| 73 |
among four equal phases. At group 10 we allocate (2 ^ 9) buckets in 4 |
| 74 |
different phases {2 ^ 7, 2 ^ 7, 2 ^ 7, 2 ^ 7}, the numbers in curly braces |
| 75 |
indicate the number of buckets allocated within each phase of splitpoint group |
| 76 |
10. And, for splitpoint group 11 and 12 allocation phases will be |
| 77 |
{2 ^ 8, 2 ^ 8, 2 ^ 8, 2 ^ 8} and {2 ^ 9, 2 ^ 9, 2 ^ 9, 2 ^ 9} respectively. We |
| 78 |
can see that at each splitpoint group we double the total number of buckets |
| 79 |
from the previous group but in an incremental phase. The bucket pages |
| 80 |
allocated within one phase of a splitpoint group will appear consecutively in |
| 81 |
the index. This addressing scheme allows the physical location of a bucket |
| 82 |
page to be computed from the bucket number relatively easily, using only a |
| 83 |
small amount of control information. If we look at the function |
| 84 |
_hash_spareindex for a given bucket number we first compute the |
| 85 |
splitpoint group it belongs to and then the phase to which the bucket belongs |
| 86 |
to. Adding them we get the global splitpoint phase number S to which the |
| 87 |
bucket belongs and then simply add "hashm_spares[S] + 1" (where hashm_spares[] |
| 88 |
is an array stored in the metapage) with given bucket number to compute its |
| 89 |
physical address. The hashm_spares[S] can be interpreted as the total number |
| 90 |
of overflow pages that have been allocated before the bucket pages of |
| 91 |
splitpoint phase S. The hashm_spares[0] is always 0, so that buckets 0 and 1 |
| 92 |
always appear at block numbers 1 and 2, just after the meta page. We always |
| 93 |
have hashm_spares[N] <= hashm_spares[N+1], since the latter count includes the |
| 94 |
former. The difference between the two represents the number of overflow pages |
| 95 |
appearing between the bucket page groups of splitpoints phase N and N+1. |
| 96 |
(Note: the above describes what happens when filling an initially minimally |
| 97 |
sized hash index. In practice, we try to estimate the required index size and |
| 98 |
allocate a suitable number of splitpoints phases immediately, to avoid |
| 99 |
expensive re-splitting during initial index build.) |
| 100 |
|
| 101 |
When S splitpoints exist altogether, the array entries hashm_spares[0] |
| 102 |
through hashm_spares[S] are valid; hashm_spares[S] records the current |
| 103 |
total number of overflow pages. New overflow pages are created as needed |
| 104 |
at the end of the index, and recorded by incrementing hashm_spares[S]. |
| 105 |
When it is time to create a new splitpoint phase's worth of bucket pages, we |
| 106 |
copy hashm_spares[S] into hashm_spares[S+1] and increment S (which is |
| 107 |
stored in the hashm_ovflpoint field of the meta page). This has the |
| 108 |
effect of reserving the correct number of bucket pages at the end of the |
| 109 |
index, and preparing to allocate additional overflow pages after those |
| 110 |
bucket pages. hashm_spares[] entries before S cannot change anymore, |
| 111 |
since that would require moving already-created bucket pages. |
| 112 |
|
| 113 |
The last page nominally used by the index is always determinable from |
| 114 |
hashm_spares[S]. To avoid complaints from smgr, the logical EOF as seen by |
| 115 |
the filesystem and smgr must always be greater than or equal to this page. |
| 116 |
We have to allow the case "greater than" because it's possible that during |
| 117 |
an index extension we crash after allocating filesystem space and before |
| 118 |
updating the metapage. Note that on filesystems that allow "holes" in |
| 119 |
files, it's entirely likely that pages before the logical EOF are not yet |
| 120 |
allocated: when we allocate a new splitpoint phase's worth of bucket pages, we |
| 121 |
physically zero the last such page to force the EOF up, and the first such |
| 122 |
page will be used immediately, but the intervening pages are not written |
| 123 |
until needed. |
| 124 |
|
| 125 |
Since overflow pages may be recycled if enough tuples are deleted from |
| 126 |
their bucket, we need a way to keep track of currently-free overflow |
| 127 |
pages. The state of each overflow page (0 = available, 1 = not available) |
| 128 |
is recorded in "bitmap" pages dedicated to this purpose. The entries in |
| 129 |
the bitmap are indexed by "bit number", a zero-based count in which every |
| 130 |
overflow page has a unique entry. We can convert between an overflow |
| 131 |
page's physical block number and its bit number using the information in |
| 132 |
hashm_spares[] (see hashovfl.c for details). The bit number sequence |
| 133 |
includes the bitmap pages, which is the reason for saying that bitmap |
| 134 |
pages are a subset of the overflow pages. It turns out in fact that each |
| 135 |
bitmap page's first bit represents itself --- this is not an essential |
| 136 |
property, but falls out of the fact that we only allocate another bitmap |
| 137 |
page when we really need one. Bit number zero always corresponds to the |
| 138 |
first bitmap page, which is allocated during index creation just after all |
| 139 |
the initially created buckets. |
| 140 |
|
| 141 |
|
| 142 |
Lock Definitions |
| 143 |
---------------- |
| 144 |
|
| 145 |
Concurrency control for hash indexes is provided using buffer content |
| 146 |
locks, buffer pins, and cleanup locks. Here as elsewhere in PostgreSQL, |
| 147 |
cleanup lock means that we hold an exclusive lock on the buffer and have |
| 148 |
observed at some point after acquiring the lock that we hold the only pin |
| 149 |
on that buffer. For hash indexes, a cleanup lock on a primary bucket page |
| 150 |
represents the right to perform an arbitrary reorganization of the entire |
| 151 |
bucket. Therefore, scans retain a pin on the primary bucket page for the |
| 152 |
bucket they are currently scanning. Splitting a bucket requires a cleanup |
| 153 |
lock on both the old and new primary bucket pages. VACUUM therefore takes |
| 154 |
a cleanup lock on every bucket page in order to remove tuples. It can also |
| 155 |
remove tuples copied to a new bucket by any previous split operation, because |
| 156 |
the cleanup lock taken on the primary bucket page guarantees that no scans |
| 157 |
which started prior to the most recent split can still be in progress. After |
| 158 |
cleaning each page individually, it attempts to take a cleanup lock on the |
| 159 |
primary bucket page in order to "squeeze" the bucket down to the minimum |
| 160 |
possible number of pages. |
| 161 |
|
| 162 |
To avoid deadlocks, we must be consistent about the lock order in which we |
| 163 |
lock the buckets for operations that requires locks on two different buckets. |
| 164 |
We choose to always lock the lower-numbered bucket first. The metapage is |
| 165 |
only ever locked after all bucket locks have been taken. |
| 166 |
|
| 167 |
|
| 168 |
Metapage Caching |
| 169 |
---------------- |
| 170 |
|
| 171 |
Both scanning the index and inserting tuples require locating the bucket |
| 172 |
where a given tuple ought to be located. To do this, we need the bucket |
| 173 |
count, highmask, and lowmask from the metapage; however, it's undesirable |
| 174 |
for performance reasons to have to lock and pin the metapage for every such |
| 175 |
operation. Instead, we retain a cached copy of the metapage in each backend's |
| 176 |
relcache entry. This will produce the correct bucket mapping as long as the |
| 177 |
target bucket hasn't been split since the last cache refresh. |
| 178 |
|
| 179 |
To guard against the possibility that such a split has occurred, the |
| 180 |
primary page of each bucket chain stores the number of buckets that |
| 181 |
existed as of the time the bucket was last split, or if never split as |
| 182 |
of the time it was created, in the space normally used for the |
| 183 |
previous block number (that is, hasho_prevblkno). This doesn't cost |
| 184 |
anything because the primary bucket page is always the first page in |
| 185 |
the chain, and the previous block number is therefore always, in |
| 186 |
reality, InvalidBlockNumber. |
| 187 |
|
| 188 |
After computing the ostensibly-correct bucket number based on our cached |
| 189 |
copy of the metapage, we lock the corresponding primary bucket page and |
| 190 |
check whether the bucket count stored in hasho_prevblkno is greater than |
| 191 |
the number of buckets stored in our cached copy of the metapage. If |
| 192 |
so, the bucket has certainly been split, because the count must originally |
| 193 |
have been less than the number of buckets that existed at that time and |
| 194 |
can't have increased except due to a split. If not, the bucket can't have |
| 195 |
been split, because a split would have created a new bucket with a higher |
| 196 |
bucket number than any we'd seen previously. In the latter case, we've |
| 197 |
locked the correct bucket and can proceed; in the former case, we must |
| 198 |
release the lock on this bucket, lock the metapage, update our cache, |
| 199 |
unlock the metapage, and retry. |
| 200 |
|
| 201 |
Needing to retry occasionally might seem expensive, but the number of times |
| 202 |
any given bucket can be split is limited to a few dozen no matter how |
| 203 |
many times the hash index is accessed, because the total number of |
| 204 |
buckets is limited to less than 2^32. On the other hand, the number of |
| 205 |
times we access a bucket is unbounded and will be several orders of |
| 206 |
magnitude larger even in unsympathetic cases. |
| 207 |
|
| 208 |
(The metapage cache is new in v10. Older hash indexes had the primary |
| 209 |
bucket page's hasho_prevblkno initialized to InvalidBuffer.) |
| 210 |
|
| 211 |
Pseudocode Algorithms |
| 212 |
--------------------- |
| 213 |
|
| 214 |
Various flags that are used in hash index operations are described as below: |
| 215 |
|
| 216 |
The bucket-being-split and bucket-being-populated flags indicate that split |
| 217 |
operation is in progress for a bucket. During split operation, a |
| 218 |
bucket-being-split flag is set on the old bucket and bucket-being-populated |
| 219 |
flag is set on new bucket. These flags are cleared once the split operation |
| 220 |
is finished. |
| 221 |
|
| 222 |
The split-cleanup flag indicates that a bucket which has been recently split |
| 223 |
still contains tuples that were also copied to the new bucket; it essentially |
| 224 |
marks the split as incomplete. Once we're certain that no scans which |
| 225 |
started before the new bucket was fully populated are still in progress, we |
| 226 |
can remove the copies from the old bucket and clear the flag. We insist that |
| 227 |
this flag must be clear before splitting a bucket; thus, a bucket can't be |
| 228 |
split again until the previous split is totally complete. |
| 229 |
|
| 230 |
The moved-by-split flag on a tuple indicates that tuple is moved from old to |
| 231 |
new bucket. Concurrent scans will skip such tuples until the split operation |
| 232 |
is finished. Once the tuple is marked as moved-by-split, it will remain so |
| 233 |
forever but that does no harm. We have intentionally not cleared it as that |
| 234 |
can generate an additional I/O which is not necessary. |
| 235 |
|
| 236 |
The operations we need to support are: readers scanning the index for |
| 237 |
entries of a particular hash code (which by definition are all in the same |
| 238 |
bucket); insertion of a new tuple into the correct bucket; enlarging the |
| 239 |
hash table by splitting an existing bucket; and garbage collection |
| 240 |
(deletion of dead tuples and compaction of buckets). Bucket splitting is |
| 241 |
done at conclusion of any insertion that leaves the hash table more full |
| 242 |
than the target load factor, but it is convenient to consider it as an |
| 243 |
independent operation. Note that we do not have a bucket-merge operation |
| 244 |
--- the number of buckets never shrinks. Insertion, splitting, and |
| 245 |
garbage collection may all need access to freelist management, which keeps |
| 246 |
track of available overflow pages. |
| 247 |
|
| 248 |
The reader algorithm is: |
| 249 |
|
| 250 |
lock the primary bucket page of the target bucket |
| 251 |
if the target bucket is still being populated by a split: |
| 252 |
release the buffer content lock on current bucket page |
| 253 |
pin and acquire the buffer content lock on old bucket in shared mode |
| 254 |
release the buffer content lock on old bucket, but not pin |
| 255 |
retake the buffer content lock on new bucket |
| 256 |
arrange to scan the old bucket normally and the new bucket for |
| 257 |
tuples which are not moved-by-split |
| 258 |
-- then, per read request: |
| 259 |
reacquire content lock on current page |
| 260 |
step to next page if necessary (no chaining of content locks, but keep |
| 261 |
the pin on the primary bucket throughout the scan) |
| 262 |
save all the matching tuples from current index page into an items array |
| 263 |
release pin and content lock (but if it is primary bucket page retain |
| 264 |
its pin till the end of the scan) |
| 265 |
get tuple from an item array |
| 266 |
-- at scan shutdown: |
| 267 |
release all pins still held |
| 268 |
|
| 269 |
Holding the buffer pin on the primary bucket page for the whole scan prevents |
| 270 |
the reader's current-tuple pointer from being invalidated by splits or |
| 271 |
compactions. (Of course, other buckets can still be split or compacted.) |
| 272 |
|
| 273 |
To minimize lock/unlock traffic, hash index scan always searches the entire |
| 274 |
hash page to identify all the matching items at once, copying their heap tuple |
| 275 |
IDs into backend-local storage. The heap tuple IDs are then processed while not |
| 276 |
holding any page lock within the index thereby, allowing concurrent insertion |
| 277 |
to happen on the same index page without any requirement of re-finding the |
| 278 |
current scan position for the reader. We do continue to hold a pin on the |
| 279 |
bucket page, to protect against concurrent deletions and bucket split. |
| 280 |
|
| 281 |
To allow for scans during a bucket split, if at the start of the scan, the |
| 282 |
bucket is marked as bucket-being-populated, it scan all the tuples in that |
| 283 |
bucket except for those that are marked as moved-by-split. Once it finishes |
| 284 |
the scan of all the tuples in the current bucket, it scans the old bucket from |
| 285 |
which this bucket is formed by split. |
| 286 |
|
| 287 |
The insertion algorithm is rather similar: |
| 288 |
|
| 289 |
lock the primary bucket page of the target bucket |
| 290 |
-- (so far same as reader, except for acquisition of buffer content lock in |
| 291 |
exclusive mode on primary bucket page) |
| 292 |
if the bucket-being-split flag is set for a bucket and pin count on it is |
| 293 |
one, then finish the split |
| 294 |
release the buffer content lock on current bucket |
| 295 |
get the "new" bucket which was being populated by the split |
| 296 |
scan the new bucket and form the hash table of TIDs |
| 297 |
conditionally get the cleanup lock on old and new buckets |
| 298 |
if we get the lock on both the buckets |
| 299 |
finish the split using algorithm mentioned below for split |
| 300 |
release the pin on old bucket and restart the insert from beginning. |
| 301 |
if current page is full, first check if this page contains any dead tuples. |
| 302 |
if yes, remove dead tuples from the current page and again check for the |
| 303 |
availability of the space. If enough space found, insert the tuple else |
| 304 |
release lock but not pin, read/exclusive-lock |
| 305 |
next page; repeat as needed |
| 306 |
>> see below if no space in any page of bucket |
| 307 |
take buffer content lock in exclusive mode on metapage |
| 308 |
insert tuple at appropriate place in page |
| 309 |
mark current page dirty |
| 310 |
increment tuple count, decide if split needed |
| 311 |
mark meta page dirty |
| 312 |
write WAL for insertion of tuple |
| 313 |
release the buffer content lock on metapage |
| 314 |
release buffer content lock on current page |
| 315 |
if current page is not a bucket page, release the pin on bucket page |
| 316 |
if split is needed, enter Split algorithm below |
| 317 |
release the pin on metapage |
| 318 |
|
| 319 |
To speed searches, the index entries within any individual index page are |
| 320 |
kept sorted by hash code; the insertion code must take care to insert new |
| 321 |
entries in the right place. It is okay for an insertion to take place in a |
| 322 |
bucket that is being actively scanned, because readers can cope with this |
| 323 |
as explained above. We only need the short-term buffer locks to ensure |
| 324 |
that readers do not see a partially-updated page. |
| 325 |
|
| 326 |
To avoid deadlock between readers and inserters, whenever there is a need |
| 327 |
to lock multiple buckets, we always take in the order suggested in Lock |
| 328 |
Definitions above. This algorithm allows them a very high degree of |
| 329 |
concurrency. (The exclusive metapage lock taken to update the tuple count |
| 330 |
is stronger than necessary, since readers do not care about the tuple count, |
| 331 |
but the lock is held for such a short time that this is probably not an |
| 332 |
issue.) |
| 333 |
|
| 334 |
When an inserter cannot find space in any existing page of a bucket, it |
| 335 |
must obtain an overflow page and add that page to the bucket's chain. |
| 336 |
Details of that part of the algorithm appear later. |
| 337 |
|
| 338 |
The page split algorithm is entered whenever an inserter observes that the |
| 339 |
index is overfull (has a higher-than-wanted ratio of tuples to buckets). |
| 340 |
The algorithm attempts, but does not necessarily succeed, to split one |
| 341 |
existing bucket in two, thereby lowering the fill ratio: |
| 342 |
|
| 343 |
pin meta page and take buffer content lock in exclusive mode |
| 344 |
check split still needed |
| 345 |
if split not needed anymore, drop buffer content lock and pin and exit |
| 346 |
decide which bucket to split |
| 347 |
try to take a cleanup lock on that bucket; if fail, give up |
| 348 |
if that bucket is still being split or has split-cleanup work: |
| 349 |
try to finish the split and the cleanup work |
| 350 |
if that succeeds, start over; if it fails, give up |
| 351 |
mark the old and new buckets indicating split is in progress |
| 352 |
mark both old and new buckets as dirty |
| 353 |
write WAL for allocation of new page for split |
| 354 |
copy the tuples that belongs to new bucket from old bucket, marking |
| 355 |
them as moved-by-split |
| 356 |
write WAL record for moving tuples to new page once the new page is full |
| 357 |
or all the pages of old bucket are finished |
| 358 |
release lock but not pin for primary bucket page of old bucket, |
| 359 |
read/shared-lock next page; repeat as needed |
| 360 |
clear the bucket-being-split and bucket-being-populated flags |
| 361 |
mark the old bucket indicating split-cleanup |
| 362 |
write WAL for changing the flags on both old and new buckets |
| 363 |
|
| 364 |
The split operation's attempt to acquire cleanup-lock on the old bucket number |
| 365 |
could fail if another process holds any lock or pin on it. We do not want to |
| 366 |
wait if that happens, because we don't want to wait while holding the metapage |
| 367 |
exclusive-lock. So, this is a conditional LWLockAcquire operation, and if |
| 368 |
it fails we just abandon the attempt to split. This is all right since the |
| 369 |
index is overfull but perfectly functional. Every subsequent inserter will |
| 370 |
try to split, and eventually one will succeed. If multiple inserters failed |
| 371 |
to split, the index might still be overfull, but eventually, the index will |
| 372 |
not be overfull and split attempts will stop. (We could make a successful |
| 373 |
splitter loop to see if the index is still overfull, but it seems better to |
| 374 |
distribute the split overhead across successive insertions.) |
| 375 |
|
| 376 |
If a split fails partway through (e.g. due to insufficient disk space or an |
| 377 |
interrupt), the index will not be corrupted. Instead, we'll retry the split |
| 378 |
every time a tuple is inserted into the old bucket prior to inserting the new |
| 379 |
tuple; eventually, we should succeed. The fact that a split is left |
| 380 |
unfinished doesn't prevent subsequent buckets from being split, but we won't |
| 381 |
try to split the bucket again until the prior split is finished. In other |
| 382 |
words, a bucket can be in the middle of being split for some time, but it can't |
| 383 |
be in the middle of two splits at the same time. |
| 384 |
|
| 385 |
The fourth operation is garbage collection (bulk deletion): |
| 386 |
|
| 387 |
next bucket := 0 |
| 388 |
pin metapage and take buffer content lock in exclusive mode |
| 389 |
fetch current max bucket number |
| 390 |
release meta page buffer content lock and pin |
| 391 |
while next bucket <= max bucket do |
| 392 |
acquire cleanup lock on primary bucket page |
| 393 |
loop: |
| 394 |
scan and remove tuples |
| 395 |
mark the target page dirty |
| 396 |
write WAL for deleting tuples from target page |
| 397 |
if this is the last bucket page, break out of loop |
| 398 |
pin and x-lock next page |
| 399 |
release prior lock and pin (except keep pin on primary bucket page) |
| 400 |
if the page we have locked is not the primary bucket page: |
| 401 |
release lock and take exclusive lock on primary bucket page |
| 402 |
if there are no other pins on the primary bucket page: |
| 403 |
squeeze the bucket to remove free space |
| 404 |
release the pin on primary bucket page |
| 405 |
next bucket ++ |
| 406 |
end loop |
| 407 |
pin metapage and take buffer content lock in exclusive mode |
| 408 |
check if number of buckets changed |
| 409 |
if so, release content lock and pin and return to for-each-bucket loop |
| 410 |
else update metapage tuple count |
| 411 |
mark meta page dirty and write WAL for update of metapage |
| 412 |
release buffer content lock and pin |
| 413 |
|
| 414 |
Note that this is designed to allow concurrent splits and scans. If a split |
| 415 |
occurs, tuples relocated into the new bucket will be visited twice by the |
| 416 |
scan, but that does no harm. See also "Interlocking Between Scans and |
| 417 |
VACUUM", below. |
| 418 |
|
| 419 |
We must be careful about the statistics reported by the VACUUM operation. |
| 420 |
What we can do is count the number of tuples scanned, and believe this in |
| 421 |
preference to the stored tuple count if the stored tuple count and number of |
| 422 |
buckets did *not* change at any time during the scan. This provides a way of |
| 423 |
correcting the stored tuple count if it gets out of sync for some reason. But |
| 424 |
if a split or insertion does occur concurrently, the scan count is |
| 425 |
untrustworthy; instead, subtract the number of tuples deleted from the stored |
| 426 |
tuple count and use that. |
| 427 |
|
| 428 |
Interlocking Between Scans and VACUUM |
| 429 |
------------------------------------- |
| 430 |
|
| 431 |
Since we release the lock on bucket page during a cleanup scan of a bucket, a |
| 432 |
concurrent scan could start in that bucket before we've finished vacuuming it. |
| 433 |
If a scan gets ahead of cleanup, we could have the following problem: (1) the |
| 434 |
scan sees heap TIDs that are about to be removed before they are processed by |
| 435 |
VACUUM, (2) the scan decides that one or more of those TIDs are dead, (3) |
| 436 |
VACUUM completes, (4) one or more of the TIDs the scan decided were dead are |
| 437 |
reused for an unrelated tuple, and finally (5) the scan wakes up and |
| 438 |
erroneously kills the new tuple. |
| 439 |
|
| 440 |
Note that this requires VACUUM and a scan to be active in the same bucket at |
| 441 |
the same time. If VACUUM completes before the scan starts, the scan never has |
| 442 |
a chance to see the dead tuples; if the scan completes before the VACUUM |
| 443 |
starts, the heap TIDs can't have been reused meanwhile. Furthermore, VACUUM |
| 444 |
can't start on a bucket that has an active scan, because the scan holds a pin |
| 445 |
on the primary bucket page, and VACUUM must take a cleanup lock on that page |
| 446 |
in order to begin cleanup. Therefore, the only way this problem can occur is |
| 447 |
for a scan to start after VACUUM has released the cleanup lock on the bucket |
| 448 |
but before it has processed the entire bucket and then overtake the cleanup |
| 449 |
operation. |
| 450 |
|
| 451 |
Currently, we prevent this using lock chaining: cleanup locks the next page |
| 452 |
in the chain before releasing the lock and pin on the page just processed. |
| 453 |
|
| 454 |
Free Space Management |
| 455 |
--------------------- |
| 456 |
|
| 457 |
(Question: why is this so complicated? Why not just have a linked list |
| 458 |
of free pages with the list head in the metapage? It's not like we |
| 459 |
avoid needing to modify the metapage with all this.) |
| 460 |
|
| 461 |
Free space management consists of two sub-algorithms, one for reserving |
| 462 |
an overflow page to add to a bucket chain, and one for returning an empty |
| 463 |
overflow page to the free pool. |
| 464 |
|
| 465 |
Obtaining an overflow page: |
| 466 |
|
| 467 |
take metapage content lock in exclusive mode |
| 468 |
determine next bitmap page number; if none, exit loop |
| 469 |
release meta page content lock |
| 470 |
pin bitmap page and take content lock in exclusive mode |
| 471 |
search for a free page (zero bit in bitmap) |
| 472 |
if found: |
| 473 |
set bit in bitmap |
| 474 |
mark bitmap page dirty |
| 475 |
take metapage buffer content lock in exclusive mode |
| 476 |
if first-free-bit value did not change, |
| 477 |
update it and mark meta page dirty |
| 478 |
else (not found): |
| 479 |
release bitmap page buffer content lock |
| 480 |
loop back to try next bitmap page, if any |
| 481 |
-- here when we have checked all bitmap pages; we hold meta excl. lock |
| 482 |
extend index to add another overflow page; update meta information |
| 483 |
mark meta page dirty |
| 484 |
return page number |
| 485 |
|
| 486 |
It is slightly annoying to release and reacquire the metapage lock |
| 487 |
multiple times, but it seems best to do it that way to minimize loss of |
| 488 |
concurrency against processes just entering the index. We don't want |
| 489 |
to hold the metapage exclusive lock while reading in a bitmap page. |
| 490 |
(We can at least avoid repeated buffer pin/unpin here.) |
| 491 |
|
| 492 |
The normal path for extending the index does not require doing I/O while |
| 493 |
holding the metapage lock. We do have to do I/O when the extension |
| 494 |
requires adding a new bitmap page as well as the required overflow page |
| 495 |
... but that is an infrequent case, so the loss of concurrency seems |
| 496 |
acceptable. |
| 497 |
|
| 498 |
The portion of tuple insertion that calls the above subroutine looks |
| 499 |
like this: |
| 500 |
|
| 501 |
-- having determined that no space is free in the target bucket: |
| 502 |
remember last page of bucket, drop write lock on it |
| 503 |
re-write-lock last page of bucket |
| 504 |
if it is not last anymore, step to the last page |
| 505 |
execute free-page-acquire (obtaining an overflow page) mechanism |
| 506 |
described above |
| 507 |
update (former) last page to point to the new page and mark buffer dirty |
| 508 |
write-lock and initialize new page, with back link to former last page |
| 509 |
write WAL for addition of overflow page |
| 510 |
release the locks on meta page and bitmap page acquired in |
| 511 |
free-page-acquire algorithm |
| 512 |
release the lock on former last page |
| 513 |
release the lock on new overflow page |
| 514 |
insert tuple into new page |
| 515 |
-- etc. |
| 516 |
|
| 517 |
Notice this handles the case where two concurrent inserters try to extend |
| 518 |
the same bucket. They will end up with a valid, though perhaps |
| 519 |
space-inefficient, configuration: two overflow pages will be added to the |
| 520 |
bucket, each containing one tuple. |
| 521 |
|
| 522 |
The last part of this violates the rule about holding write lock on two |
| 523 |
pages concurrently, but it should be okay to write-lock the previously |
| 524 |
free page; there can be no other process holding lock on it. |
| 525 |
|
| 526 |
Bucket splitting uses a similar algorithm if it has to extend the new |
| 527 |
bucket, but it need not worry about concurrent extension since it has |
| 528 |
buffer content lock in exclusive mode on the new bucket. |
| 529 |
|
| 530 |
Freeing an overflow page requires the process to hold buffer content lock in |
| 531 |
exclusive mode on the containing bucket, so need not worry about other |
| 532 |
accessors of pages in the bucket. The algorithm is: |
| 533 |
|
| 534 |
delink overflow page from bucket chain |
| 535 |
(this requires read/update/write/release of fore and aft siblings) |
| 536 |
pin meta page and take buffer content lock in shared mode |
| 537 |
determine which bitmap page contains the free space bit for page |
| 538 |
release meta page buffer content lock |
| 539 |
pin bitmap page and take buffer content lock in exclusive mode |
| 540 |
retake meta page buffer content lock in exclusive mode |
| 541 |
move (insert) tuples that belong to the overflow page being freed |
| 542 |
update bitmap bit |
| 543 |
mark bitmap page dirty |
| 544 |
if page number is still less than first-free-bit, |
| 545 |
update first-free-bit field and mark meta page dirty |
| 546 |
write WAL for delinking overflow page operation |
| 547 |
release buffer content lock and pin |
| 548 |
release meta page buffer content lock and pin |
| 549 |
|
| 550 |
We have to do it this way because we must clear the bitmap bit before |
| 551 |
changing the first-free-bit field (hashm_firstfree). It is possible that |
| 552 |
we set first-free-bit too small (because someone has already reused the |
| 553 |
page we just freed), but that is okay; the only cost is the next overflow |
| 554 |
page acquirer will scan more bitmap bits than he needs to. What must be |
| 555 |
avoided is having first-free-bit greater than the actual first free bit, |
| 556 |
because then that free page would never be found by searchers. |
| 557 |
|
| 558 |
The reason of moving tuples from overflow page while delinking the later is |
| 559 |
to make that as an atomic operation. Not doing so could lead to spurious reads |
| 560 |
on standby. Basically, the user might see the same tuple twice. |
| 561 |
|
| 562 |
|
| 563 |
WAL Considerations |
| 564 |
------------------ |
| 565 |
|
| 566 |
The hash index operations like create index, insert, delete, bucket split, |
| 567 |
allocate overflow page, and squeeze in themselves don't guarantee hash index |
| 568 |
consistency after a crash. To provide robustness, we write WAL for each of |
| 569 |
these operations. |
| 570 |
|
| 571 |
CREATE INDEX writes multiple WAL records. First, we write a record to cover |
| 572 |
the initialization of the metapage, followed by one for each new bucket |
| 573 |
created, followed by one for the initial bitmap page. It's not important for |
| 574 |
index creation to appear atomic, because the index isn't yet visible to any |
| 575 |
other transaction, and the creating transaction will roll back in the event of |
| 576 |
a crash. It would be difficult to cover the whole operation with a single |
| 577 |
write-ahead log record anyway, because we can log only a fixed number of |
| 578 |
pages, as given by XLR_MAX_BLOCK_ID (32), with current XLog machinery. |
| 579 |
|
| 580 |
Ordinary item insertions (that don't force a page split or need a new overflow |
| 581 |
page) are single WAL entries. They touch a single bucket page and the |
| 582 |
metapage. The metapage is updated during replay as it is updated during |
| 583 |
original operation. |
| 584 |
|
| 585 |
If an insertion causes the addition of an overflow page, there will be one |
| 586 |
WAL entry for the new overflow page and second entry for insert itself. |
| 587 |
|
| 588 |
If an insertion causes a bucket split, there will be one WAL entry for insert |
| 589 |
itself, followed by a WAL entry for allocating a new bucket, followed by a WAL |
| 590 |
entry for each overflow bucket page in the new bucket to which the tuples are |
| 591 |
moved from old bucket, followed by a WAL entry to indicate that split is |
| 592 |
complete for both old and new buckets. A split operation which requires |
| 593 |
overflow pages to complete the operation will need to write a WAL record for |
| 594 |
each new allocation of an overflow page. |
| 595 |
|
| 596 |
As splitting involves multiple atomic actions, it's possible that the system |
| 597 |
crashes between moving tuples from bucket pages of the old bucket to new |
| 598 |
bucket. In such a case, after recovery, the old and new buckets will be |
| 599 |
marked with bucket-being-split and bucket-being-populated flags respectively |
| 600 |
which indicates that split is in progress for those buckets. The reader |
| 601 |
algorithm works correctly, as it will scan both the old and new buckets when |
| 602 |
the split is in progress as explained in the reader algorithm section above. |
| 603 |
|
| 604 |
We finish the split at next insert or split operation on the old bucket as |
| 605 |
explained in insert and split algorithm above. It could be done during |
| 606 |
searches, too, but it seems best not to put any extra updates in what would |
| 607 |
otherwise be a read-only operation (updating is not possible in hot standby |
| 608 |
mode anyway). It would seem natural to complete the split in VACUUM, but since |
| 609 |
splitting a bucket might require allocating a new page, it might fail if you |
| 610 |
run out of disk space. That would be bad during VACUUM - the reason for |
| 611 |
running VACUUM in the first place might be that you run out of disk space, |
| 612 |
and now VACUUM won't finish because you're out of disk space. In contrast, |
| 613 |
an insertion can require enlarging the physical file anyway. |
| 614 |
|
| 615 |
Deletion of tuples from a bucket is performed for two reasons: to remove dead |
| 616 |
tuples, and to remove tuples that were moved by a bucket split. A WAL entry |
| 617 |
is made for each bucket page from which tuples are removed, and then another |
| 618 |
WAL entry is made when we clear the needs-split-cleanup flag. If dead tuples |
| 619 |
are removed, a separate WAL entry is made to update the metapage. |
| 620 |
|
| 621 |
As deletion involves multiple atomic operations, it is quite possible that |
| 622 |
system crashes after (a) removing tuples from some of the bucket pages, (b) |
| 623 |
before clearing the garbage flag, or (c) before updating the metapage. If the |
| 624 |
system crashes before completing (b), it will again try to clean the bucket |
| 625 |
during next vacuum or insert after recovery which can have some performance |
| 626 |
impact, but it will work fine. If the system crashes before completing (c), |
| 627 |
after recovery there could be some additional splits until the next vacuum |
| 628 |
updates the metapage, but the other operations like insert, delete and scan |
| 629 |
will work correctly. We can fix this problem by actually updating the |
| 630 |
metapage based on delete operation during replay, but it's not clear whether |
| 631 |
it's worth the complication. |
| 632 |
|
| 633 |
A squeeze operation moves tuples from one of the buckets later in the chain to |
| 634 |
one of the bucket earlier in chain and writes WAL record when either the |
| 635 |
bucket to which it is writing tuples is filled or bucket from which it |
| 636 |
is removing the tuples becomes empty. |
| 637 |
|
| 638 |
As a squeeze operation involves writing multiple atomic operations, it is |
| 639 |
quite possible that the system crashes before completing the operation on |
| 640 |
entire bucket. After recovery, the operations will work correctly, but |
| 641 |
the index will remain bloated and this can impact performance of read and |
| 642 |
insert operations until the next vacuum squeeze the bucket completely. |
| 643 |
|
| 644 |
|
| 645 |
Other Notes |
| 646 |
----------- |
| 647 |
|
| 648 |
Clean up locks prevent a split from occurring while *another* process is stopped |
| 649 |
in a given bucket. It also ensures that one of our *own* backend's scans is not |
| 650 |
stopped in the bucket. |