diff options
Diffstat (limited to 'src/backend/access/gin/README')
| -rw-r--r-- | src/backend/access/gin/README | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/src/backend/access/gin/README b/src/backend/access/gin/README index 434d398bf78..1c1c7b64336 100644 --- a/src/backend/access/gin/README +++ b/src/backend/access/gin/README @@ -210,6 +210,56 @@ fit on one pending-list page must have those pages to itself, even if this results in wasting much of the space on the preceding page and the last page for the tuple.) +Concurrency +----------- + +The entry tree and each posting tree is a B-tree, with right-links connecting +sibling pages at the same level. This is the same structure that is used in +the regular B-tree indexam (invented by Lehman & Yao), but we don't support +scanning a GIN trees backwards, so we don't need left-links. + +To avoid deadlocks, B-tree pages must always be locked in the same order: +left to right, and bottom to top. When searching, the tree is traversed from +top to bottom, so the lock on the parent page must be released before +descending to the next level. Concurrent page splits move the keyspace to +right, so after following a downlink, the page actually containing the key +we're looking for might be somewhere to the right of the page we landed on. +In that case, we follow the right-links until we find the page we're looking +for. + +To delete a page, the page's left sibling, the target page, and its parent, +are locked in that order, and the page is marked as deleted. However, a +concurrent search might already have read a pointer to the page, and might be +just about to follow it. A page can be reached via the right-link of its left +sibling, or via its downlink in the parent. + +To prevent a backend from reaching a deleted page via a right-link, when +following a right-link the lock on the previous page is not released until +the lock on next page has been acquired. + +The downlink is more tricky. A search descending the tree must release the +lock on the parent page before locking the child, or it could deadlock with +a concurrent split of the child page; a page split locks the parent, while +already holding a lock on the child page. However, posting trees are only +fully searched from left to right, starting from the leftmost leaf. (The +tree-structure is only needed by insertions, to quickly find the correct +insert location). So as long as we don't delete the leftmost page on each +level, a search can never follow a downlink to page that's about to be +deleted. + +The previous paragraph's reasoning only applies to searches, and only to +posting trees. To protect from inserters following a downlink to a deleted +page, vacuum simply locks out all concurrent insertions to the posting tree, +by holding a super-exclusive lock on the posting tree root. Inserters hold a +pin on the root page, but searches do not, so while new searches cannot begin +while root page is locked, any already-in-progress scans can continue +concurrently with vacuum. In the entry tree, we never delete pages. + +(This is quite different from the mechanism the btree indexam uses to make +page-deletions safe; it stamps the deleted pages with an XID and keeps the +deleted pages around with the right-link intact until all concurrent scans +have finished.) + Limitations ----------- |