Debian Codegraph @

src/backend/access/hash/README

raw
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.