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.