Nik and Michael are joined by Salma El-Sayed and Kirk Wolak to discuss their in-progress and very ambitious Google Summer of Code project around adding Btree Merge support to Postgres. Here are some links to things they mentioned: Salma El-Sayed https://postgres.fm/people/salma-el-sayed Kirk Wolak https://postgres.fm/people/kirk-wolak Google Summer of Code https://summerofcode.withgoogle.com PostgreSQL GSoC 2026 project ideas https://wiki.postgresql.org/wiki/GSoC_2026 CMU Intro to Database Systems https://www.youtube.com/playlist?list=PLSE8ODhjZXjYMAgsGH-GtY5rJYZ6zjsd5 Kirk, NIK, and Andrey’s Hacking Postgres sessions on YouTube https://www.youtube.com/playlist?list=PLH8y1BNPAKjKDdJA7sDmFWUkbbYux3TRz B-tree Index Bloat Reduction - Approach & Questions (Hackers thread, with patches) https://www.postgresql.org/message-id/flat/CANBEAPFq3YAOydjUS3xwcUG9L6e3WE5Z4nGPk_Q3RsjSFWTJNA%40mail.gmail.com B-tree merge visualizer https://kirkw.github.io/explainers/btree-merge-explainer.html ~~~ What did you like or not like? What should we discuss next time? Let us know via a YouTube comment, on social media, or by commenting on our Google doc! ~~~ Postgres FM is produced by: Michael Christofides, founder of pgMustard Nikolay Samokhvalov, founder of Postgres.ai With credit to: Jessie Draws for the elephant artwork
Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.
Transcript
From the show. Tap a time to play from there.
Michael: Hello and welcome to Postgres.FM, a weekly show about all things PostgreSQL. I am Michael, founder of pgMustard, and I am joined by 2 special guests. Firstly, Salma El-Sayed, recently graduated from the Mansoura University in a computer and control engineering degree and Google Summer of Code participant working on B-tree merge for Postgres. Welcome Salma. Salma: Hi. Michael: Thank you so much. Yeah, great to have you. And also Kirk Wolak, who is a software architect at KiraSoft,
Google Summer of Code mentor, and a co-host with Nik on the YouTube Hacking Postgres series. Hi, Kirk, nice to have you too. Kirk: Michael, it's good to finally be able to be in 1 of these with you. Thank you. Michael: Yeah, I've watched many of your sessions as well, so this feels like a collab maybe. Kirk: Kind of. Michael: I wondered actually if we could start with you, Kirk. I wonder if you could give us a little bit of background on being a Google Summer of Code mentor. From your perspective, how does that work? For people that aren't familiar with it? What does it mean?
Kirk: Sure. In fact, I just did a lightning round as a mentor because of how we integrated AI, because they're really curious about moving forward. So 1st off, Google Summer of Code is an initiative to help bring new people into the open source world. And the ultimate goal is to create new contributors. And I'm taking that completely to heart. So my goal for Salma is to make sure she not only does something big, but we also make it so that she contributes in the future.
So much so that we're arranging for other companies to support her in these efforts. So that long-term we absolutely have a contributor. My position, it's my 1st time mentoring and I'm getting help from Andreas Karlsson, Andrey Borodin from the hackers thing, and there's a couple other people, Andrei Lepikhov, I believe saying all these names is hard. I call them together, the Andres. All 3 people I work with are called Andre Great. Anyways, but yeah, so the Google Summer of Code Initiative is
for that purpose. And we actually, with Nik, because of all the hacking, we actually had 5 or 6 projects. And this was by far the hardest project. This was fixing a 30-year-old Postgres problem that was too hard for the original PhDs who wrote the paper, Yao et al. And Shasha later on how we actually handle our B-tree stuff. So it left behind a gaping hole and I'm 1 of these people I have not as much programming in Postgres world but I've been chief
architect of software and doing software since I was a teenager professionally so for me once I got access to AI's and then a good programmer like Salma I'm like the world is my oyster and then of course you learn their lessons from there. Michael: Yeah, calling this a big project I think might still be understating it. This is a huge ambitious undertaking But let's come back to that because I wanted to hear from Salma as well. Just from the basics, what made you interested in doing Google
Summer of Code? Why Postgres? Were you looking for a project this big? From your perspective, what's it been like? Salma: I was interested in databases. I was studying the CMU course, it's Database Introduction to Database. It's from the University of CMU, but it's online. And I was working on a project implementing B+ tree for the BusTub project. It's the database management system they have project.
We implement it for it. And also I know some people from my university who got accepted to Google Summer of Code last year. So I wanted to check what's going on in GSoC and check the organizations. And then when I found Postgres, I found a project about the B+ tree and I found it interesting. Then I didn't know anything about the internals of the Postgres
at that set point, but I sent Kirk an email asking about what should I do 1st, how should I prepare, if my knowledge and my level is good for this project? And he responded with the hacking sessions he, Andrey and Nik had. And I watched the sessions and asked him again and sent another email asking questions about B-trees and the bloat problems, the ideas they discussed in the videos.
And that's when everything started. We kept talking back and forth until GSoC started in May. Michael: Yeah, so it sounds like a match made in heaven. Kirk's crazy enough to suggest a project this huge and ambitious and you're crazy enough to be interested in it. Okay I'll start and see how this is working. Kirk: So there's a magic truth into that. I've been running and managing developers for the last 30 years. And 1 of the secrets I've learned in managing developers is you
only give them enough information that helps their confidence, and you hide the things they're going to run into into the future until they get there. Otherwise you overwhelm them and they give up and and having such a let's say naive student was so helpful in the beginning as she just learned last week. So yes. Michael: There is definitely, I can definitely see that that there are benefits to that side of things but it reminds me of
that if it's a meme or something or maybe just a post that was just funny it said something like we don't do this because it's easy we do this because we thought it would be easy something like that Kirk: yes exactly and and if you want I can give you the this is the cool part and this is my kind of metaphor for helping everyone understand what's going on. All right, fixing a B-tree and doing B-tree merge and page merging and keeping it perfectly clean is absolutely well studied and
it's easy in a single user environment with only 1 thread that does the reading and writing. Okay, the only thing that makes this complicated is that you have potentially 10, 000 other people reading the same structure while you're changing it. And the magic, and this is the part that we had to understand, the magic is simply 1st we are limited in how big of changes we can make at every step so that anybody who notices the change
can self-correct. And then next is to turn it into the small number of steps into the future until eventually all the changes are made and the B-tree is back to normal and you didn't break anybody who's out there running. Because you can't break a search, you can't break an insert, you can't break a delete. If you break these things, obviously you're breaking them in other threads. So that's the only thing that makes it hard. If we could just do it and do it all on our own, For example,
if we could actually send a message to everyone scanning an index right now and say stop, restart after I'm done, and then we make the changes and push them, that would be easy. All right? But imagine having a 30-minute query get stopped and have to restart. That would be horrible implementation. Hey, Nik. Nik: Hello. Hello. Yeah, apologies for being late. This is 1st time so far. Michael: Good to have you here. I think we should even, maybe we could go back a step and look at Why even bother now?
Like Postgres has got this far without B-tree merge. Kirk: Good question. Michael: It could conceivably continue for quite some time without it. Like what problems is it causing and why are the existing ways of handling that maybe not sufficient? Or why, if this is such a big undertaking on such a difficult thing, the payoff must be big too, right? Like what's the benefit? Kirk: Yeah, so to say the payoff must be big too isn't necessarily the same thing.
The people who need it the most are the people who can afford it the least. So for example, this started because Andrey Borodin mentioned they have a table that's so large at his company that if they do reindex concurrently, 1 index takes over 72 hours to reindex concurrently to get rid of this bloat. So the thing is, and then there's also times where there's no getting rid of the bloat if it was a one-time set of deletes and you're not doing a bunch of inserts back in the beginning
part of the index you're not cleaning that up it's just gonna stay there forever so part of the problem is bloat impacts space usage but that every time you make space bigger you also start impacting time, especially if it's empty space. So now your search is taking, you're reading more buffers, you're doing more work than you have to do to get and collect these things. So the 1st thing is, it was hard in the past, Very few people understood all of the complexity and therefore they weren't willing to make the change. AI is available now that can explain all of this complexity better.
And even a guy like me, who's got 40 years experience elsewhere, I can now come in and point that experience at a problem with the help of AI and wrap my arms around it and go, oh I see what the problem is. Everyone's trying to do it quickly. We need to do it slowly and if we make the change slowly then it's possible to do. What's the benefit? Postgres ends up with self-healing indexes. That's how I refer to them. As you naturally, in fact, where does this cleanup belong?
It belongs in vacuum and the delete code. When you delete records, it just marks them as deleted. When you actually remove them from there and you leave a page mostly empty, that's the logic we're writing and they're going to be able to put that right back in the vacuum and say, oh, let's push these tuples over here onto this very empty page already and let's start the unlink process so the vacuum process which already does a lot of work that Postgres counts on can now pick this stuff up and then let's we don't need the reindex go ahead
Nik: let me explain my perspective When I was studying B-tree in school, 20 plus years ago, they told us, books like Chris Date, Aho Ullman, other books, they told us that B-tree is almost balanced tree with a lot of children in each node, right? Almost balanced means that from root to leaf it's always n or n plus 1. And there are algorithms that rebalance it when we insert data
or remove data from leaves. So it means that when you insert and usually when we have integer 4, int8, always on the right side, right? And when you insert and the right side leaf becomes already almost full, it's split, right? And then rebalancing happens. And vice versa, when we delete everything, some leaves are empty, the balance happens when leaves are being deleted.
But for me, some time ago, it was a big surprise that only the 1st part is implemented in Postgres. And only then realization came how actual index bloat is happening. And we know that there are optimizations in Postgres 13 and 14 for deduplication, but it's not solving that. As you mentioned, Kirk, if you update or delete, especially if you delete, updates also like kind of deletes plus inserts,
right? If you delete entries in leaves, which are in the middle of the whole range, It creates basically empty space, right? And it stays there. A fun correction. In the heap, if whole page is empty, it will be truncated if it's at the end. In B-tree, it will be truncated even if it's in the middle, right? But it should be fully empty and this is rare. Kirk: So- That's the magic. Current Postgres only deletes a page from a leaf page if it's
100 percent empty. If it's 99.999, meaning there's just 1 record out of 8, 000, it's going to hold that page open, okay? And they don't want to go through the trouble of moving that 1 record. Yeah. Nik: How many references can be in a page? 8, 000 is a page. Kirk: Yeah, that's a page size. Yeah, but. Nik: Yeah, yeah. And yeah, anyway, but so this is how bloat and it cannot be removed by vacuum. It's just empty space, right? And this means that UUID version 4 has advantage over UUID version
7. Kirk: No, hold it. UUID 7 had the advantage. It went to the right. Oh, I get what you're saying. Yes. Nik: Our normal way of thinking, UUID version 7 has advantage because data locality, all fresh data stays in fewer pages. But this also means that if you have int4 or int8 primary keys, delete the data in the middle, it leads to bloat and that's it. Without merge algorithm, right? And the UUID version 4, you have some chances to have a new insert
happening to the same leaf, maybe. Anyway, this is my understanding. It was a big surprise for me that Postgres doesn't have split, not split, merge, right? Kirk: Merge. And their argument... The other key point I want to make is because of the research I did and listening to Hacker's comment before. So you understand sometimes programmers justify their decisions after the fact, okay? I'm a software developer, I confess, I've done this myself. Anyway, so 1 of the pieces of feedback I got from Bruce
was, oh, they tested theoretically that merging at 50% empty just causes more page splits. And I'm thinking to myself, what a straw man argument. Okay, nobody in their right mind should take 2 50% empty pages and merge them and create 100% full page. That's why we have things like fillfactor. Of course that page is just gonna split on the next insert. So, but yes this gets back to the arguments against bothering
to solve this problem. I think the problem has become easier to solve in today's world. Michael: Just to put the other perspective across a little bit, I think I agree that it's good to, we should definitely approach new hard problems, like if we, someone's got to at some point, right, it makes sense. But, This is like incredibly difficult part of the code. It's B-tree indexes. It affects every Postgres installation out there. The risk of making mistakes is like really bad, right? We're moving things around in a B-tree.
That means ordering matters. And like we can have corruption. We could miss entries in a scan and think there isn't data, or we could see an entry twice and get duplicated data. So the like risk of it going wrong is so high that like it has to be perfect and it is it has to be like foolproof like real solid. So then you have to say then what's the like if we're going to risk doing any solution to this It like what's the benefit? So I think then we do have to come back to like how do we solve this currently and I think Andrey's 72 hour reindexing this concurrently
must be such a big table and like put on a big index as well right that it must be like an absolute outlier and most big indexes still should be like in the order of tens of minutes or hours like like single-digit hours I would have thought Kirk: but and why have to Michael: okay so the downsides there are downsides right like it you can only run 1 at a time, you need the space again, but like that's only disk space, right? Nik: Are you talking about reindexing? Kirk: Yeah, yeah, it's reindexing concurrently.
Nik: It's been horizon pinned, this is a key problem. Yeah. So you fight bloat in 1 index and cause bloat everywhere in that database. Michael: But there's like, we've talked, Nik, we've talked many times about, like, this is a reason to partition or keep your tables smaller. Like, there are other design solutions around this area. So I think I've also personally seen indexes that were 99% bloat because of, like, access patterns. So you can get these extreme cases that you're talking about.
I've seen it in real world workplace. Nik: Simple. Yeah, simplest example is when we have like a long history of something like orders in e-commerce and then they decide to clean up, they don't need orders exceeding 1 year or 2 years, they delete all that data. But since int8 or UUID version 7 primary key, bloat stays in index and the only way is to rebuild it. Yeah. So the simplest example. Maybe I'm not right, because if you delete whole data from the past.
Michael: Imagine if customers on like a software as a service application, you delete all of their data because they leave the service and that removes Nik: like Michael: 80% of, like maybe they're a big customer leaves and 80% of every page goes like that's a very easy way of Removing it moving a lot of every page, but not 100 percent of every anyone page I get that this problem. I do get that this problem exists, But I'm just pushing back to say is it as bad a by the way to add to your to add to your case It also pollutes the cache. I think that's a big deal, especially in the days of memory getting
more expensive There are other knock-on impacts of carrying all of this wasted space around but I'm still of the opinion that the bar should be extremely high for attacking this. Kirk: Well, okay, I'll give you your argument temporarily. Let me give you the opposite side of our argument for how hard it turned out not to be. Now, granted, our patch isn't complete, but we had a working prototype in the 1st 0.5 of the Google Summer of Code project timeline.
Michael: Okay, let's wait. So should we switch to solution then? And Salma, do you want to talk us through what was your approach? Like how did you go about designing this and why did you make certain design decisions? Salma: Okay, we had a lot of discussions. 1st we had a lot of prototype and a lot of 1st ideas. Our 1st design idea was to merge 2 pages together. So we have a left page and a right page and we move all data
from the left page to the right 1. And we use the left page as a direction, leaves the data in it as a direction for backward scans. So when a scanner, when a scan read the right page, then it was waiting between the 2 pages, and we merged these 2 pages together. Then after the merge happened, it landed on the left page, which
we removed its data. So our 1st idea was to keep the data in the left page so this backward scan can read it and go on. No need to recover, no need to do any extra work. But When we proposed this to the hackers, they said that this is a corruption to the index because we have repeated data and it will cause a lot of problems. Also, when vacuum cleans the index, So if it's going to clean
these 2 or only clean the data or the right page. So MUSECUR try to find another solution. So the solution we are working on, and we sent the 1st concept about hackers, was instead of keeping the left page as as hidden data, we only keep it only to route the scans, the forward and backward scan to how to recover.
When a scanner read the right page, it's about to read the left page, which is now a tombstone, it doesn't contain any data. Actually, the scan in this position have a scan opaque data saved and not overridden yet. So this scan opaque contains the TID, a list of TIDs from the
right page read before the merger actually happened. So we are using this to save these TIDs in another list. So when we read the right page, we know which TIDs we read and which values we read and which we haven't yet read. So we go back, read the page again and eliminate all the values
we haven't seen before, which are saved. So anything except the ones we saved in the list we have. Kirk: So again, what we called the original merged away page, we called those ghost records. They were ghost copies of the original records. And let's understand 1 thing. If I have 100 scans going on and I merge 2 leaf pages together and nobody notices because they were in different parts of the tree? Does anyone care?
No, because by the time they get to those pages, they'll be correct. There's just a tiny amount of time where we could actually do the merge while people are currently have these things read in memory and they're processing them waiting to read either the next or the previous page and that's what Salma was talking about. So if we have scans that are touching the points that we're doing this to, those are the only ones we care about. If they're 1 before it or 1 on the other side of it, we don't
care about those scans because they'll be correct by the time our lock lets go. Unfortunately for the guys who read in the page that we're going to merge away, they read in and they processed 4 records off of that page. Then they read the next page and now those 4 records have already been added to that page. That would cause the error of duplicate records. We can't allow that. So Salma explained, all we did was we kept in memory the records that we read from the previous page, the 4 that we accepted.
And then on this page, right as we go to process this, we know to save this because we detect the flag. And then when we read all these new records plus these 4, we subtract these 4 off and only add the new records to our scan. And so the forward scan continues and it didn't miss a beat. And we do effectively the exact same thing in reverse for a backwards scan. That's the only special cases we have to worry about. Right at that edge case and it's only when they're reading.
So what did we do to reduce the risks? 1, we'll only merge 2 leaf pages together. If you try to merge more than 2, you introduce undetectable errors. Everything we do, we should make detectable and then we should handle. So by merging only 2 pages together, we limit how much we can actually fix, but at the same time, we limit what we can break to a known set and that's then what we implement for the code. Next we make sure that these 2 leaf nodes are only pointed at
from the same parent so this way we don't have to repair the upper structure of the tree. This is another 90, 80, 20, 90, 10 hack. Why are we doing it that way? Because again, I don't want to repair anything more. I just want to work on these 3 nodes so that this way the 2 leaf pages can be turned into 1. Everyone who used to point at this 1 will now point to this 1 and slowly this page will become empty and disappear just like a deleted page but very slowly through the process.
So by minimizing how much we do in any 1 amount of workload and focusing it correctly, what we do is we expose the surface area of the problems. And then our job is Hansel and Gretel. We got to drop enough candy or bits on these leaf nodes so that the scans can detect that oh this changed while I was standing on it if it changed while I wasn't standing on it I don't care and then I can't fix I can do that small change by the way the
next change it has to happen I have to wait to the transaction ID of all transactions passes in time. The same way deleting a page goes from half-dead to deleted and then from deleted to free space. It has to wait that transaction ID passing in order for the next pass to work. And these are the baby steps. And that's when I compare it to trying to do road work and put up a detour. If you want to put a detour on a road that's currently active
without jamming the traffic, you have to let traffic still go through that's already on the road. You start backwards and put the detour flags, the furthest ones out 1st, and bring them in, and then you slowly start putting cones out there to force the traffic to take the new path. Anybody who's caught in front of you, it's only those cars that you're dropping cones on in front of that have to react to this merge. Everyone else who comes after everything's in place, they'll end up on the detour.
And then once you lift the detour away, and that's vacuum's job, vacuum's job lifts all the cones away and it goes and picks up all the detour flags. And now whoever was on the detour flag finishes and the rest of the people finish on the normal highway, and from that point forward, nobody notices. Nik: So I know major hackers participated, like Peter Geoghegan and Robert Haas, others. And there was a big question, as I understand, how can you prove
reliably some guarantees that everything will be correct always, even on all edge and corner cases? Was this answered or not? Kirk: We're still answering it, right? The answer is to keep the changes small and to make sure all the different code detects those changes they just identified a bug where in the middle of a B-tree merge somebody did an extra delete and the code coming in didn't detect the flag on the page
that it was merged away. So it tried to process the page. But yes, there's pieces there we're still going to have to solve. Nik: What bothers me a lot is my AI is finding bugs in Postgres 19 every day right now. And that's much easier. It's easier to find a bug than to prove reliably that there are no bugs. Kirk: Isn't it fundamentally impossible to prove a negative? Nik: Well, that's why those theoretical foundations exist.
It's proving something like mathematics. This is the question they ask, like Peter Geoghegan, right? So some, like, ideally it would be, okay, Postgres follows just those articles from 80s, right? Let's, let's, Let's just, based on that, we know everything is fine. But there are nuances in current implementation, it's impossible to, there is no full match, obviously. There's, Kirk: we already just found a new limitation of our approach.
It turns out there's 2 B-tree versions for file versioning. There's an older version that doesn't support the flags we're using and we can't do the merge on those B-trees, clearly. So that's going to be 1 of the flags that we have. The real question becomes simply, is the process sound? Does it set up the right locks and the pins in the right order? We've already got the logging working, where it's pushing out the WAL log and we can crash the server and recover it in the middle of the merge process and then the vacuum on the other
end can finish cleaning it up. It's coming together and we're just past the halfway mark of Google Summer of Code. Now, that said, I'm not expecting this to get published by the time November rolls around and Google Summer of Code is done, okay? We know that this is gonna take longer, and part of it is, is Nik, I'm expecting you to tell your AI super agents to go out there and crush this code looking for the edge cases, right? And the other side of this equation is, we'll never know it's
perfect, right? At some point we know it'll be well tested. Nik: Some proof is needed as I understand this is, this would be, I wanted to ask Salma, this is probably 1 of the hardest projects of Google Summer of Code. I participated in Google Summer of Code in 2006, exactly 20 years ago. And since then I kept an eye on it. And this looks like the most challenging in terms of how fundamental it is. How does it feel from your side? I know guys like Robert Haas and Peter Geoghegan proposed to
change the project, right? Because of complexity. How does it look? Isn't that scary? Salma: Yes, but from the start Kirk told me this is already the problem and we will not have it done with the end of the Summer of Code. I mean it's it's hard but I truly I'm loving from doing it with Kirk. I want to see it make progress and hackers have their insights on it and their views.
We do a lot of work on it. It's a little bit, yes, hard, not a little bit, but it's not that hard, like I'm scared of it. Kirk: Also, understand, I think I mentioned this with you, Nik, and Salma knows this. What's our definition of success when it comes to Google's Summer of Code being done? Is it that this gets published, accepted, and there's confetti in the streets? No. My definition of success is we've defined a language by which
we can now talk about making this happen in the future. Meaning we've identified the core issues, we can talk about it. Next, we started quantifying the impact on performance from the standpoint of how much is it really slowing down every B-tree search? Look, if it's gonna cost every B-tree search 20% efficiency, like no, let's not do this to answer Michael's question, right? If this isn't a very small delta hit on searching, then it's
not worth it. But on the other hand, if we don't develop the language, we don't develop the protocols for testing it for performance, We don't develop the process by which people can discuss it and review it. If we get all that done, I think this is a huge successful Google Summer of Code project in my opinion. And if we have that plus a rough working prototype, Hallelujah. That's something we can carry forward and maybe it falls on to much more experienced people than us, just to make sure of the
correctness. But I'll be honest, that was the limited version that kept me motivated. As we've made the progress we've made, my understanding of these B-trees and why they made the decisions they made has skyrocketed. And I'm becoming more and more confident in our approach because I'm starting to really understand what it is we have to do, what those breadcrumbs are. Now, is there a lot of testing involved?
Absolutely. Could this affect third-party tools that work on indexes? Absolutely. If they don't know what a merged away page is or a merged page, and they're not looking for that stuff, they could make mistakes. Absolutely. We don't want that to happen either. But on the flip side, Core never worries about the extensions per se. It's the extensions job when that version comes out to be up to date. I don't want to worry too much about it, but I honestly think we're close. We have the core concepts in place.
That's the part I'm impressed with. Also, Salma: at the very beginning, Andreas turned to me in our 1st meeting that it's not only about completing this project, it's about getting new people to contribute to Postgres. So I will just take care of Postgres, so they contribute to new steppasses. Nik: Yeah that's great, that's great. So how many months left? You mentioned November, right?
Salma: I think it's the beginning of November. Nik: Since it's already not much time left, what should we expect in terms of prototyping this thing? Kirk: So the way that we did this to get it working was, as we read the next page, if we detected we were stepping in the middle of a quagmire, meaning the change happened under our feet, we could just reach back in memory, look at the records we just added, and apply a fix up algorithm. That was completely working. And we had the stuff working inside a vacuum.
So that was good. What we found is parallel scans would not work this way because you'd have to pass all of the TIDs from the previous read to a different thread. And all of that messaging would just destroy the parallel thread. So what we've done is we backed up the truck and we reanalyzed the situation and we realized all we really need is the 1 pivot tuple. So on a forward scan we need the last tuple on the page that we're going to merge away and on the backward scan we need the
1st tuple of that page so we know what to pre-process if we reread that page. So let's do backwards scan. I just did this page, our right page, before the merge happened and I know the 1st tuple and even in a parallel scan this is great. I go and I read the next page backwards and it was merged away. That flag tells me I have to go back and reread the merged page into but I only process the records that are less than that current
record that we saved from the previous page. Those are all the ones that were inserted because we only move the keys to the right in the tree. And they're sorted, which is beautiful. And they're sorted uniquely because the last sort key is the TID, the row ID in the table. So now we pull that up, we reread that page, we strip off everything we don't want to read again that we already read and we just add the remaining records in. So now with this change we have to go back and rewrite our existing routine but now that means we now have parallel scan will be
working shortly and I'm thinking within a week or so parallel scan will be working and the normal scan will be working using this new logic, which means at this point we have the WAL logging, parallel scan, regular scan, and the core handling. Now we have to find the nuanced places, the delete records, update records, things like this that touch these pages and we have to find the other touch points to make sure that they're honoring the new flags we've created in these things.
Once we're done with that it's looking good but in the next week or 2, I believe Salma, and I'm speaking for you, Salma, you can chime in. How long do you think it's going to take you to rewrite all of that code you spent months on? I'm giving you 2 weeks so far. Go ahead, tell me how wrong I am. Salma: I have done before 2 weeks, but yes. Kirk: Now you know why I love her Nik: so you mentioned with WAL logging what's left then WAL is very difficult
Kirk: It's it's it was only difficult correct me if I'm wrong the difficult part of WAL was 1st off It's a complete mind change in the problem You're solving because now you're working on playback and in capturing stuff and then the testing required that Salma had to learn how to set up a WAL transfer and a recovery process and do all that. Other than that, what do you think on the WAL logging stuff in making sure that it worked? Salma, what was hard? Salma: Nothing in particular, but we had to add a new nbtree
resource manager, because the nbtree only had 1 slot left, the left slot, and we needed 3 slots for logging, 1 slot for logging the merge, and 2 for when vacuum cleaning the merged away page and when cleaning the merged page. So we needed 3. 1st, we did it like with multiplexing this only slot, but it wasn't clean.
So we asked on Discord that I can do another, a new resource manager. And we did a new nbtree2, like following heap2, which is already introduced. Kirk: And for those who are not up on that new resource manager, effectively, WAL is blocks of data. When you read in a WAL block, there's a bunch of flags that tell you how to interpret that data. That's the resource manager layer of it, is it looks and says, oh, this is a B-tree WAL.
In this case, it's a B-tree merged away WAL record right so it has to know how to read this in and process it and we had to teach it that by adding our new types in. Nik: I somehow haven't followed the project recently and miss that WAL is already being in work. Yeah. I'm impressed. So if everything goes well, what will be left? Besides a theoretical question that everything is reliable, which
is a tiny question. Michael: Quite a big deal. Nik: Yeah. Yeah. What will be left? Kirk: Besides the question of, is it correct? What will Nik: be left? Kirk: Honestly, it's the things we just talked about, right? It is literally the parallel scan and getting that in there, plus finding other touch points or edge points. And then in my book, the next layer is performance testing and having you send your guys at it? Nik: Actually, now, just once we talk through all this, I have
a great idea to point my new harness to find those bugs. Like, I'm pretty sure we will find some. But it won't prove the theoretical correctness of everything, but it may be to help a little bit. My question is what will be left to feel the prototype complete? If all is there, what's what else left? Nothing? Kirk: Well, this last 2 week cycle is going to be most of it. And then getting people to give us feedback and testing. That's what I want this broadcast to talk about.
Because this is, I think this is the UUIDv7 of Google Summer of Code. In PG18, that was the 1 feature everyone understood. It's all. Nik: That feature was simple. Kirk: It was. Nik: That feature was simple, and you need to make efforts to use it. Unlike this feature, which is hard and everyone is supposed to benefit from it by default. So I understand why you say this, but this is for me, it's quite opposite. And this podcast I wanted to do because this is the most impressive
Google Summer of Code I saw in 20 years, as I feel it. It's like taking articles from 80s, using AI, attacking a hard problem. And it definitely deserves attention. I definitely will point my harness to find bugs. Kirk: We need people to actually be looking at this and giving us feedback. Michael: Yeah, I actually wanted to commend you for the amount of interest you'd already got. The level of detail that people have given comments and Advice
already from senior people and people that have worked on B-tree deletion in the past as well It's been incredible, but I think I'm a bit confused because I think some of their feedback I can't tell if it's been addressed yet So I saw 1 comment from Peter saying what it boils down to is the same TID must never exist in any 2 index tuples that Kirk: was the ghost record That was the issue with ghost records. Michael: Yeah, so that's no longer true. Kirk: Yeah, we don't do it that way anymore. We fixed that
Michael: Yes, Kirk: it became an invariant and they didn't even appreciate the fact that nobody's supposed to look at those records except the people that are getting their toes stepped on in the scan. Everyone else further from the scan would never look at them. And they blasted it, which is okay, because the technique that Salma came up with is actually more efficient. So I appreciate the feedback, but keep going. If there's other feedback you'd like to hear, but for the most part, most of these things have been answered.
Michael: Yeah I think that's the kind of thing though that does help not prove that an issue can't exist but as soon as you allow for 2 TIDs to point to this like as soon as you allow for 2 records to point to the same TID you introduce the possibility of corruption. So I do think that's the kind of design decision that helps avoid whole categories of bug, which is quite nice. Kirk: Salma, did you have to modify amcheck? Salma: Yes. Yeah, we have to let it know about the Merged Away page And most
of a lot of a lot for a lot of parts of the code it was part of Nik: the core Salma: read the high key from pages and the few and Kirk: We don't have any tension Salma: Yeah, we don't pay attention to the rest of a page So we have to tell a lot of parts of the code that they just skip the merged away page the same way it does with the deleted page. Kirk: Or half-dead. Yep. Yes. Perfect. But no, back to your point. So not, not only did we get feedback, we had to fix amcheck.
But then after she fixed it, by teaching it how to recognize our pages But then it came back and said no you cheated You didn't teach it how to inspect your pages to make sure they're actually correct. And so Salma went and worked on that. And so let's be clear. We are standing on the shoulders of everybody in the Postgres community. And this kind of feedback is helpful for us. Yeah, we bit off way more than we could chew by ourself. And if we were alone on a stranded on a desert island with a
Cray supercomputer and an AI, I don't think we're gonna get near the best result we get by interfacing and working with the community. Michael: Nice, yeah, agreed. Salma: We just got an email, someone reviewed and pointed out a bug we need to fix. And this is the kind, also the kind of review we need because It pointed out to some part of the vacuum that I didn't know it existed. So yeah, it helps a lot to point out to this.
Nik: I would also check maybe pgstattuple extension and some other extensions. Yeah, I'm definitely pointing my harness after I'm done with my bugs. If I'm done with bugs, because they keep... Kirk: Squeeze this in between the big runs and the bugs. Nik: Sounds good. Yeah, Sounds good. Great. I'm very impressed with progress. I was expecting like attacking only part of it, but it's obviously attack of the whole thing.
It's impressive, especially. Kirk: So Michael, with all that, are you as nervous now as you were at the beginning? Michael: I think the closer you 2 get to something committable, the more nervous I'll be. So don't treat my nervousness as any kind of sign of your progress. But I would agree that this is a really impressively ambitious project, and if it's about learning and inspiring people to become committers or contributors in the future, I think you've succeeded.
And we wanted to talk about it, right? It's an interesting enough piece that we wanted to talk about it here so I'm really pleased that you're attacking this I think you've set expectations well on the chance of getting anything committed here but it sounds like you 2 are getting dangerously close so I should be worried but that that's a compliment right the fact that I I was worried when senior hackers were making changes to B-tree code in 13, 14. Turned out some of it was like the best work I've ever seen.
Nik: 14.0, you remember this? Michael: I remember the, yeah, but that was slightly different code, right? Like the reindex concurrently stuff, yeah. But the bottom-up deletion, that was Peter Geoghegan as well, that is another attempt at trying to avoid the problem in the 1st place of B-tree bloat but without having to worry about merging so it was trying to avoid splitting it's the from the other side of it I was so impressed by that work I'm really impressed that there weren't major issues with it So it's this kind of super
scary stuff that touches everything. They're the changes I like the most because everybody benefits without having to do anything. But they're the changes I find most scary because everybody's affected without having to do anything. So yeah, it's impressive that you've even taken this on, and I'm really impressed with your progress and the feedback you've got. And hopefully, Salma, the whole point was to get you interested in contributing to Postgres, and it sounds like you are. Thanks. Nik: I know about other plans, right? Not only about this complex project, but maybe smaller features
and fixes and so on. That's great. Kirk: Salma's kind of found a sponsor and she's in the background also picking up some of our LSN drop table logging and some of the other hacker stuff that Andrey and Nik and I are doing on the side. And she's gonna help push some of those through because we just keep coming up with new ideas and we don't babysit the old ones through all the commitfest, right? And there's a lot of work there. So she's picking up some extra work and skills doing that as well. Nik: It's time to start joining our sessions on hacking sessions
on YouTube. Kirk: Oh, look at that. Nik: Yeah. So to wrap up, let's maybe repeat what people can do to help. Just review the patch, test it, find bugs and so on, right? And spread the word. Also, we have a playground in terms of visualization. To play with it a little bit, yeah. Kirk: So yeah, check out the visualizations. They're still accurate for now. I'll update them in 2 weeks when we get the patch. But at least go through and do a plus 1 if you like the idea that we're working on it, Michael.
Anybody else? Okay, plus 1 these because the more replies people get and see in the hackers email chain, the more likely they're going to crack it open and take a look at what's going on. And we want that attention. Again, we admit it may not get committed, but the flip side is that the more people that look at it and realize that this is not crazy, the more it helps us. So those are the key things we need. We just need that extra attention, whatever anyone else there can do.
And again, I want to say kudos to Google Summer of Code, because This wouldn't have happened if it wasn't for that. It's my 1st time mentoring. I feel bad for Salma, but I did my best. Salma: No, you are a great mentor. Nik: Great. Thank you for coming. It was interesting. It's a very challenging and super interesting project. I'm rooting for it. And I'm going to help when I can. Thank you. Kirk: Awesome, thank you guys. Have a good day. Salma: Thank you. Michael: Likewise, congrats. Good to meet you both.
Tip: watch on YouTube. Since episode 193, the video shows charts and illustrations as we talk. https://youtu.be/VcDU-NRE3hI Michael, Nik, and Kirk discuss Postgres 19: why the release came in November and not in...
Tip: watch on YouTube. Since episode 193, the video shows charts and illustrations as we talk. https://www.youtube.com/watch?v=gAdhpYewLZ8 Nik and Kirk discuss the hidden costs of CREATE TEMP TABLE: dead tuples and...
Tip: watch on YouTube. Since episode 193, the video shows charts and illustrations as we talk. https://www.youtube.com/watch?v=7oeAAqU00zk Nik and Kirk are joined by Álvaro Hernández to discuss how Postgres in...
Tip: watch on YouTube. Since episode 193, the video shows charts and illustrations as we talk. https://www.youtube.com/watch?v=gf8e3JkQ_8M Nik is joined by Kirk Wolak to discuss what a random UUIDv4 primary key really...
Nik is joined by Kirk Wolak, Software Architect at KiraSoft, to discuss what a database still needs after pg_restore finishes and before it takes production traffic - what pg_dump and pg_restore leave behind, why...