On Wed, Jul 1, 2026 at 2:04 AM Matthias van de Meent <[email protected]> wrote: > > On Tue, 30 Jun 2026 at 19:37, Salma El-Sayed <[email protected]> > wrote: > >
> What happens when MERGED_AWAY's only MERGED sibling is deleted? > Presumably MERGED_AWAY can be cleaned up then, too, because its tuples For this we have to keep track of the MERGED_AWAY blkno in each MERGED page, and VACUUM has to be aware of all MERGED pages to know it has deleted all of them. > This can be unsafe if you don't check that L is still the left-link of > R: If L got deleted (its fxid horizon expired and R got a new left > sibling) and the new left sibling got merged into R before we scan it, > then the data on L could contain items that we'd already scanned when > we accessed the now newly minted MERGED_AWAY page that's now R's left > sibling. > > This can be detected by detecting that L is no longer the left sibling > (and "merge group separator") of R. Note that R (in this specific case > of R being the immediate sibling of L) cannot get a new left sibling > other than through concurrent deletion of L, which can allow the > former sibling of L to be merged into R. Yes, it is easy to detect this. The last page we read is X, so recovering is straightforward. Moreover, if an active scan is waiting between L and R, the safexid for L to be deleted will be newer than the scan's horizon, so L will not be unlinked from its siblings. > > b) If false: > > - currPos.items still holds the tuples read from L. We save > > these items into savedMergeTids (we only do this step for the first M > > page in the merge group). > > How do you detect it is the first page in the merge group? What if you > land on an M page after descending the tree?. We can detect that we landed on an M page in _bt_readfirstpage, and then set skipMergeRecovery = true. > > - Read R by calling _bt_readpage. > > - Loop through currPos.items for R and remove any item that > > exists in savedMergeTids. > > - Return tuples to the caller if any remain after filtering. > > Otherwise, continue to the next M page in the group. > > > > 3) The scan steps into B (MA) and does the same as L. > > 4) The scan steps into C (HD) and skips it. > > Shouldn't this page C be HD+M, given that it is a merged page in the > process of being deleted? Or did I miss something? Yes, C is HD+M. > > *BACKWARD SCAN* > > > > Scenario: L(MA) <--> R(M) <--> A(M) <--> B(M) <--> C(normal page) > > > > Definitions: > > - skipMergeRecovery: The scan read a M page after a merge occurred, > > requiring no recovery. > > - needMergeRecovery: The scan read a M page before the merge, then > > stepped into an MA page. The flag is set to true to start recovery. > > Stepping into an MA page again while true means recovery is finished. > > > > 1) The scan steps into L: > > a) If skipMergeRecovery OR needMergeRecovery is true: The scan read > > merged pages and will skip this MA page. Reset both booleans to be > > ready for the next merged group. > > What if L and R were M pages when the scan accessed R, but > subsequently their MA page (left of L) was deleted and L got merged > into R? > Then we'd skip the keyspace that was merged from L into R, right? I > think it's the same (but inverse) issue as I'd mentioned above, but > more difficult to correctly detect because the siblings pointers of R > don't change, nor do L's. > If we can save the MA blkno in every M page, then when the scan reads any M page it saves this blkno in a new field in BTScanOpaqueData. When we reach the MA page, we check the saved blkno against the MA page's own blkno. If we find a way to save this blkno, I believe the problem will be solved. Another way to solve this is to backtrack every time we encounter an MA page, but this creates overhead we would prefer to avoid. It is also worth noting that it is very rare for a page to be merged, then split, then merged again, since the threshold we use for triggering a merge is very low. > > b) If neither is true: The scan read R before the merge, and > > currPos.items still has the data read from it. > > - Save these items into savedMergeTids. > > - Walk forward until reaching C (the first page with no M flag). > > - Set blkno = B, and lastcurrblkno = C (needed to recover from > > splits in the backward scan). > > - The scan continues walking backward from B. > > This (b) confused me a bit. > > IIUC, the order of operations for this condition to be hit is: > > 1. R was scanned; > 2. L got merged into R; [L=MA, R=M] > 3. R split into R, A, and B; [R=M, A=M, B=M] > 4. the scan accesses L (and condition B is met, and the described > branch is executed). > > Is that right? Yes, that is exactly right. > > 2) The scan steps into B, A, or R: > > a) If needMergeRecovery is false: The simplest case. Read the page > > normally and set skipMergeRecovery = true, so that when the scan steps > > left onto the MA tombstone, it knows to skip it cleanly. > > b) If needMergeRecovery is true: The scan is in merge recovery. > > - Call _bt_readpage to read the page. > > - Loop through currPos.items and remove any item that exists in > > savedMergeTids. > > - Return tuples to the caller if any remain after filtering. > > Otherwise, continue to the next M page in the group. > > ... and this is safe, because all M pages must be split _after_ the > merge happened, so they all contain the keyspace of [L+R], and the > tuples of R we'd already scanned are excluded. Am I understanding this > correctly? Yes. We have R's data in savedMergeTids. B, A, and R now contain the combined keyspace of (L+R), and we want to read only L's tuples from them. > For backward concurrent-merge-recovery, we would keep a copy of the > old tuples around on the MERGED_AWAY page; whilst allowing VACUUM to > reclaim those tuples. These tuples will be accessed only by backward > scans who were stepping from R to L whilst the merge was going on. But isn't this the same index corruption problem we faced in the previous design? As Peter noted: > What it boils down to is that the same TID must never exist in any 2 > index tuples in the same index simultaneously. > Overall, it's really great to see work being done on this hard > problem. Good job so far! Thanks! Kind regards, Salma El-Sayed
