Michael: Hello and welcome to Postgres.FM, a weekly show about

all things PostgreSQL.

I am Michael, founder of pgMustard and I'm joined as usual by

Nikolay, founder of Postgres.AI.

Hello Nikolay.

Nikolay: Hi Michael, how are you?

Let's not miss the fact that we have a guest today.

Michael: We didn't miss it.

You throw things off by saying, how are you?

And I'm British, so I have to reply, and how are you?

Nikolay: Well, let's blame the US.

This is where I learned to ask.

So I'm super glad we have Peter today.

Hi, Peter.

Peter: Hi.

Good to be here.

Thanks for having me on the pod.

Michael: We are delighted to have you.

And yeah, it's Peter Geoghegan.

Hopefully everybody knows of Peter, but in case you don't, he's

a major contributor and committer to Postgres for many years.

Three or so of the last were at AWS.

So today we're going to be talking about some of Pete's recent

and upcoming work on Postgres related to skip scan implementation,

but it's far more than that.

And honestly, the more I learn about this work, the more excited

I am about it.

I thought I knew quite a lot, and I've been reading up in the

last couple of days, and it's even better.

I didn't realise, and I'm probably cheating or skipping ahead

far too much, but I want people to understand how big this is.

This could affect our indexing strategies going forwards.

We could be choosing to index Postgres differently.

I guess it's obvious in hindsight, but there are some real major

differences.

So yeah, I'm super excited about this work.

I want to thank you for having started it and continuing with

it.

I'd be interested to hear, though, what attracted you to this

work, and did you realise how powerful it would be when you first

started on it?

Peter: Actually not at first, no.

I last did a similar interview to this.

I think it was a predecessor podcast, technically, not this one.

At that time, I happened to talk about how, for whatever reason,

I kind of like finding as many different ways as possible of

looking at a thing.

At the time, I think I said something like, well, there's a bunch

of different perspectives.

There's the data structure perspective, there's the concurrency

control perspective, and on and
on down the list.

And it was that sort of general
mentality that brought me to

this work, because I realised,
hey, I'm missing something here.

My tendency to sort of collect
these different ways of looking

at the thing, The same familiar
old topic, this tendency I have.

I was for a long time missing this
extra bit, which I think is

embodied by the work I'm doing
now, and its source material,

which is a pretty obscure 1995
paper.

It happens to be called Efficient
Search of Multidimensional

Indexes.

So you haven't heard of it, but
hopefully that's not any indication

of its real-world relevance.

It has been something that I believe
has influenced a bunch of

other systems.

So it's, in that sense, I think,
pretty standard stuff.

But the implications may be, as
you were saying, Michael, are

not fully appreciated.

So maybe we'll start with a general
overview for those that don't

know what skip scan is.

It's a feature that certainly Oracle
and in recent versions MySQL

and also SQLite have.

They all call it skip scans.

I think in DB2 it's called jump
scans or something like that.

So the basic idea is to extend
the standard B-tree index access

method to support new types of
querying without changing anything

about the on-disk contents, without
fundamentally altering anything.

This is possible with multi-column
indexes, composite indexes.

The simplest case, and the one that
gets the most attention, is

where you have an omitted prefix
column in your query.

So, for example, you do a SELECT
from a table where b equals,

let's say, 5.

Here we would have a composite
index on AB, of course, A has been

omitted from the query predicate.

So traditionally, in Postgres at
least, you wouldn't be able

to really use the index.

You might do a very inefficient
full index scan where you sort

of have to grovel through the entire
leaf level of the index,

And that works, but obviously that's
not very efficient.

What SkipScan will allow you to
do here is, assuming that there

are not terribly many distinct
values in column A, as a rule

of thumb, I would say hundreds
of distinct columns total, or

perhaps thousands, is about the
upper limit, then you can effectively

use that composite index as a collection
of logical sub-indexes,

as they're sometimes called.

So, for example, the first value
might be 1 in the column A.

So we'll do 1, A equals 1, B equals
5, A equals 2, B equals 5,

A equals 3, B equals 5, and exhaustively
will do multiple small

index scans that are effectively
pretending to be one continuous

index scan.

And that will be certainly much
more efficient than a sequential

scan in most cases.

Of course, it's true that you'd
be much better off having a column

on B directly, but it's also true
that who says that that's going

to be possible?

You might just not think to do
it, or in some cases, at least,

it might not really be feasible,
which depends on the requirements

for the user.

This is particularly likely with
things like data warehousing

use cases, the facts table, where
a lot of the querying is sort

of ad hoc, and it's not really
feasible to have all the indexes

you might possibly require ahead
of time.

So here, it's making a composite
index, which is more useful

for a wider variety of queries.

If you only require adequate performance
here, sub-second performance

is attainable.

It's not going to give you sub-millisecond
performance, although

that does sometimes happen.

But it's still, for these kinds
of use cases, almost as good.

And yet it allows you to avoid
creating a bunch of quasi-redundant

indexes.

So in that sense, as you were saying,
Michael, it's kind of like...

It at least would require some
of the conventional ways that

the updated...

I wouldn't say it's a radical shift,
but there is a sense of

which, OK, in light of this new
capability, we're going to have

to rethink some of the rules of
thumb we have for indexing in

general.

I think that's likely to work out
that way.

I would say I'm excited to see
how people end up using the feature

in practice.

Many things are possible.

So that example I gave is a sort
of very traditional simple example.

But also worth noting that the
techniques that I'm working on

include similar, though slightly
different, cases where, for

example, you have a range.

So suppose the query is SELECT
* from sales, where sales date

between the 1st of August and the
10th of August.

Then it could be that you're not
enumerating every possible date

in the entire table, but just those
dates from that range.

But the same exact idea still.

So for the 1st of August, plus
whatever the actual thing that

appeared in your predicate in the
query is, let's say, again,

it's b equals 5, I don't know.

That for the first of August, for
the second of August, for the

third of August.

So from the query perspective,
you haven't omitted the column.

The column appears in this between
range, but it is effectively

the same idea.

It also should be pointed out that
these are all very general

techniques.

They can be combined in all kinds
of different ways.

And that's where it becomes super
interesting.

Like, you have very, very complicated
combinations of these things.

The example query that I used in
my initial email to the hackers

and adding this to sell it to people
was taken from the original

source paper.

And in that instance, it was, I
believe...

So you have an initial omitted
prefix column, which is on a column

called Apartments.

Then you have a range.

Then you have an in, and then you
have another in.

So it's all kind of working together.

You see it's like this sort of...

And that's where I think it can
make a huge difference when you

combine all these techniques together,
which you will be able

to do freely.

So there, effectively, you have
this query that would conventionally

require a huge and inefficient index
scan, which is just kind of

a non-starter.

What you actually would have to
do is have a bunch of single-column

indexes and use some kind of bitmap
or something like that.

But then you give up the ability
to have the sort order from

the index.

You can't do a limit 5 or something
like that.

You can't use a group aggregate
directly, etc.

Whereas this way, you can pretty
well convert what you would

think of as 1 big query into what
you would think of as maybe

thousands of tiny queries that
each land on 1 if page again and

again.

And it's sort of a lot of small
queries pretending to be 1 big

one.

It's not apparent to you looking
at EXPLAIN Analyzer that's going

on, but it is.

So effectively, you're rewriting
the query as if it was just

a bunch of tiny queries in a way
that is fairly intuitively obvious.

It wouldn't be very practical to
do this, but you could do it

by procedurally generating a bunch
of these small queries yourself,

in principle, at least.

And that is the wooden core clever
idea here.

It's surprising how far this wooden
core idea will get you, because

it is a fairly simple idea in the
end.

But there's a bunch of things that
I haven't even considered

yet that the paper also contemplates.

For example, it has a part about
not-in predicates.

You would think it would be impossible
to use a not-in predicate

for an index.

But again, it's the same idea.

It's like skip-scan, except rather
than enumerating every possible

value in the index, it's enumerating
every possible value in

the index except these ones.

So it's basically the same thing
again and again.

So it just buys you an awful lot,
one core simple idea, which I

find kind of cool.

So that's the big picture.

Yeah, something that I'm expecting
to get into Postgres 18, and

something that builds on work that
started with Postgres 17.

Michael: So yeah, that's a great
explanation.

I think the multi-column thing
is the complex example you mentioned

is the part that blows my mind
and starts to make me think, you

know all this advice we've given
that's, you generally advise

people against huge multi-column
indexes because they often only

target then like a very, very niche
set of queries.

And you end up accepting that you're
going to do a large index

scan with a bunch of rows being
filtered, which we know is inefficient,

but it's currently the best solution.

You lost

Nikolay: hot updates also.

I'm going to continue advising
against too many columns in indexes.

Michael: Well, okay.

But I can see the flip side.

Once you've got fewer, once you
only need fewer indexes, you

don't have to support, like let's
say you've got 5 columns that

are important here.

Sometimes I've seen people index
all 5 in 3 different orders

to support different versions of...

And I feel like that kind of thing
will become less important

if we even need it at all anymore.

So that's mind-blowing.

But just to go back, Your thought
process is super interesting

here as well.

So did you come across this paper
as part of widening your horizons

and then think of all these implementation
ideas?

Or was it, you thought, this is
an area, this is a blind spot

for me, I should seek out papers
in this area?

Peter: Well, there's a surprisingly
little written about the topic,

actually, even though, as I say,
it's implemented in a bunch

of other systems, like Postgres.

I also think it's probably true
that they don't exploit it to

its full extent.

The actual paper was written by
people that were working on a

system called Non-Stop SQL in the
1990s, which hasn't quite completely

died yet, but it certainly has
far fewer users.

It was a very influential system,
though.

So I think that it's likely that
the full generality of it hasn't

been exploited for whatever reason
in other systems.

My hope is that my implementation
will do just that.

It's kind of weird.

The example complicated query I
gave, what I noticed about that

is, most of the time, if I changed
the order of the columns,

not always, but most of the time,
it made hardly any difference.

Wow.

Right, which is sort of like...

That wouldn't always be true, but
just given the particulars

of the query that I'm talking about,
it kind of didn't matter

if I swapped.

It made maybe a small difference
in favor or get...

But that is a bit mind-blowing,
sure, that that could ever be

true.

Again, it's going to be most compelling
in cases where you don't

know what the requirements are
ahead of time.

It's very good for ad hoc indexing.

And you can always beat it by having
a dedicated index if you

want to pay for that.

But that's perhaps impractical
for a lot of users.

And again, I think in OLTP apps,
it is still useful, but it's

more for avoiding the worst case,
for something that you maybe

should have anticipated but didn't
for whatever reason.

It's good for that more so than
something that you would ideally

plan on using.

But it is relevant to both.

As for why, I don't know.

I think it entered my awareness
about 5 or 6 years ago, but I

didn't fully understand it.

And it took me a little while to
figure out the right way of

doing it.

So having explained all that, it
should also be pointed out that

Whether or not you actually want
to rewrite your query in this

manner, it all depends, doesn't
it?

It could be, for example, that
the old way of doing it happens

to be the most efficient one, because,
yes, you could, in principle,

rewrite it into 100 different small
queries, but those small

queries would all be hitting the
same few leaf pages anyway,

so you actually would want to do
maybe not 100, maybe 1 or 2

at most small queries there.

How do you know ahead of time which
it is?

Well, you don't, right?

But you don't have to.

So I've had this intuition that
if I solve that problem first,

if I solve it for in-lists, then
after that, I would be able

to move on to this.

That would be a useful foundation.

So Postgres 17, this has been implemented.

It'll be available, I think, in
3 weeks when we release 17, if

all goes as planned.

So that took the existing capability
for indexing in-lists and

made it so that if you have 50
integers, say, and they're contiguous

integers like 1, 2, 3, 4, 5,
through to 50, then suppose they're

all co-located on the same leaf
page, then you're going to do

1 index scan and read them all
at once.

If, on the other hand, it turns
out that they're spread out all

over the index because maybe it's
low cardinality, or maybe it's

low cardinality just in that part
of the index, there's no rule

that says it has to be 1 or the
other.

It could be at different points
in the key space.

Low cardinality, others could be
high.

So making a dynamic choice is very
useful, I think, because you

don't have to know.

That's what makes it safe to aggressively
apply these optimizations,

because if it doesn't work out,
in any case, the v3 scan code

is able to combine the would-be
accesses into 1 on the fly.

So you'll get the same behavior
as in previous versions, if

and only if that makes sense.

So that sort of flexibility, that
dynamic behavior, seemed like

an essential prerequisite.

So it's not actually true

It's conceptually the case that
you're rewriting the big query

to lots of little ones and then
combining the result, allowing

them to pretend that they are one
big index scan, even though

they're not.

But the actual degree to which
you do that, how much atomizing

actually happens, is determined
on the fly as the scan progresses.

So it's kind of indeterminate if
it's how many actual index scans

you're doing, but that doesn't
matter, if you get what I mean.

Michael: Yeah, it's so cool.

It doesn't matter to the, it's
like one of those things that as

a user, I don't have to worry about
it, think about it at all.

As somebody who's implementing
it though, it feels like it makes

it much more complex for you to
build.

Is that fair?

Peter: Yes and no.

I think there's two ways of looking
at it.

There's what you just said, which
is, in an immediate sense,

true.

It is more complicated.

But in another sense, It isn't,
because...

Complicated to who?

I mean, the optimizer has to model
all these costs, right?

And it turns out that's hard.

And it turns out that statistics
are...

Well, they're statistics.

And if you're talking about, like,
you have all these secret

hidden correlations, but these
are multiple column indexes, of

course, so we have statistics for
each column, but at least,

unless you go out of your way to,
there's no correlated statistics

for columns.

There's a generic assumption that
these are independent, even

though very often they're not.

So having the access path be very
forgiving, so the optimizer

gets things quite wrong, but it
actually doesn't matter, or it

doesn't matter very much at least,
is way easier, at least from

the point of view of the query
optimizer.

And on balance, that probably makes
it much, much easier to actually,

as a practical matter, make it
work.

I think that that will probably
turn out to be really important,

although at this point, that's
pretty speculative.

Michael: I had this on my list
of things that might come up,

but are the cost models super interesting?

It seems to me, and I haven't checked
for sure, but from looking

at some examples, you might not
have changed the cost estimations

at least in 2017.

You might consider that because
you're making a bunch of things

more efficient in a bunch of cases,
you might try and reduce

the costs for those to encourage
those scans when they make sense.

But I guess we're already doing...

Anyway, I guess my question is,
have you changed the cost model?

And if not, why not?

Peter: Yes, but I'm not surprised
that you didn't notice it because

the main change that I made to
the cost model was that now it

will saturate.

Because, a very simple observation,
the most expensive possible

index scan ought to be a full index
scan.

You know, very simple.

If you scan every single...

There's a pretty tangible maximum
cost to, in this hand, at least

in this world where this stuff
is available, as it will be in

17, where it is physically impossible
to scan the same leaf page

a second time now, no matter how
the constants have been specified

in the query itself because automatically
that just cannot happen.

It's a physical impossibility.

So we know that we can take to
the bank.

And so the cost model saturates.

There's an awful lot of uncertainty,
except when it comes to

the worst case.

We know for absolute sure that
in the very worst case we'll

scan every leaf page once.

So that's where you notice it more.

So you can have an absurdly long
in-list, and at a certain point,

it'll just stop adding additional
cost, since it is physically

impossible for the cost to keep
going up even as you continue

to add these.

So that sort of plays into what
I was saying about having some

general understanding of what the
worst possible case can be

when everything goes wrong, when
the statistics are garbage.

That assurance, in the end, makes
everything easier rather than

making it harder, I feel.

It's also just useful.

Michael: Mason I like that it seems
pessimistic but also safe.

Peter: That's exactly it, sort of.

I think statistics is being kind
of inherently just very it's

amazing that optimizers work as
well as they do, I say.

Like, people don't realise, I feel,
often, when something goes

wrong, well, it was next to a miracle
that everything was working

as well as it was.

And probably things were not technically
working optimally, but

you didn't know that because you
were happy with adequate performance.

You didn't consider that that was
technically 10 times slower

than what could have, in principle,
have been attained with the

same index and such.

So, like, I think that if we're
honest, we have to admit that

there's an awful lot of uncertainty
about the cost models, and

that doesn't necessarily matter.

We're more encouraging the idea
that it's amongst people that

are on the hackers list, that better
to have a kind of...

I wouldn't even call it insurance,
that's too strong a word,

but just have...

Account for variation at runtime
dynamically rather than doing

so statically in the query plan.

That just seems like, to me, something
that has very little downside

and potentially quite a lot of
upside.

It is a more general idea.

It doesn't just apply here.

It applies, for example, with...

I don't know.

You can do some similar things
with hash joins.

It does get more speculative if
you keep going down the line

of things that are like that.

But why would you trust an uncertain
selectivity estimate if

you didn't have to?

There's no reason why you can't
have some kind of way of recovering

from a set summation at runtime,
at least in certain cases.

I guess that it is related to that
whole way of thinking about

it.

That is the projects I'm working
on are sort of in that way,

I feel.

Nikolay: Do you mind if I break
the structure a little bit as

usual?

Peter: Go ahead.

Nikolay: Honestly, I didn't read
the whole discussion.

So I'm going to ask some newbie
questions.

First of all, I see this potential
of...

There is loose index scan as well,
right?

And this is a very different thing
for distinct values.

And we have a wiki page, and we're
constantly using this technique.

And we also mentioned, like you
did, other database systems have

it implemented, Postgres doesn't.

But here we discuss skip scan and
skip scan, and this is very

different, I see.

But I just googled a little bit
and I found people use skip scan

in that context as well, right?

So if I'm right, some people reaching
this point will still not

fully understand what we'll discuss,
right?

Peter: Alex.

Nikolay: It's possible.

Right?

So we discussed the problem.

There is a problem.

We have an index on columns A, B,
but filter is only on B, the first

layer of A is not relevant, and
usually it means this index cannot

be applied

Peter: Well.

It's worth pointing out that with
what I'm talking about, it

only applies when you have at least
2 index columns, whereas

I don't believe that's true with
Skip Scan.

You can still usefully skip if
there's only 1 column.

Nikolay: Because there we need
distinct values, it's a different

task.

Here we need all values, but we
have an index, which usually we

say you have the wrong index, right?

But your optimization will make
it good, but only if a column

has not many values, right?

If it has a lot of values, maybe
it won't be good, right?

Peter: It's certainly not going
to be able to help because,

of course, technically you could
say, okay, there's a million

logically distinct subindexes,
but that degenerates to a full

index scan, so it's the same.

By the way, that might still be
the best plan, all things considered.

We can't rule that out either.

Sometimes that is actually the
best available plan.

But overall, yeah, you're probably
not going to want to use it

unless you have hundreds, perhaps
low thousands, or occasionally

maybe tens of thousands, but after
that it's unlikely.

Nikolay: Will the planner decide,
will it have some threshold

to decide when skip scan should
be applied when it already doesn't

make sense?

Peter: Not as such, because as
I sort of touched on already,

there is no special skip scan index
node.

I think that's a bad idea because
it's all dynamic, right?

It's an additive thing.

Nikolay: Yeah, now I'm catching
up.

Peter: Sometimes for all the usual
reasons, you might want to

have an index only scan that happens
to use a skip scan, or you

might want to bitmap index scan,
or you might want to parallel

index scan, etc.

It is useful, I think, to have
a distinct kind of index path.

More choices means more wrong choices
from the point of view

of the optimizer.

So I feel like that's a distinct
advantage of the approach I've

taken.

Of course, I still have to figure
out a way of making it not

matter when that's not the right
thing to do.

And that's not very easy, but I'm
almost...

I think I've got that part figured
out.

We'll see.

Michael: Do you mean to like minimize
regressions at times where...

Peter: Yeah, OK.

Because again, occasionally it's
going to be intrinsically the

best thing is to just scan the
index without trying to skip at

all.

So you don't want to waste a lot
of CPU cycles on a useless enterprise

that is skipping when you shouldn't
be skipping.

You really do want to fall back
on essentially the same behaviour

as previous releases there.

Now, mind you, overall, hopefully
the optimizer just wouldn't

pick that way of doing it, because
it would be wrong.

It wouldn't be the fastest available
plan, given the available

indexes.

So that only applies at all when
you're already doing something

that's basically pretty slow.

But overall, yeah, I think we're
going to have to make sure that

you don't notice it when it isn't
able to do what you would hope

it would.

That is sort of complicated, for
sure.

Michael: Just to make sure I've
understood, if we could do a

scan without skips, if we had the
perfect index for a very efficient,

let's say, index-only scan, that
would have been the index that

would have been chosen in the first
place because its cost estimate

would have been lowest.

So already when we are skipping,
you're doing a scan that involves

some skips.

We haven't had that available,
and therefore, yeah, okay.

That's really cool.

Peter: Yeah, in general, I think
it makes more sense to think

about these sorts of queries as
being on a continuum.

One extreme is where there's, let's
say, no more than 5 or 10 distinct.

And then the fact that you're doing
5 different descents of the

index is hardly noticeable.

It's maybe less than a millisecond
in the end anyway.

So that would be a very favourable
case for skipping.

And then you have less favourable
cases, I suppose, where cardinality

goes up.

And eventually, you get to the
point where you can't do any skipping

at all, and that's where you don't
want to pay a penalty for

being open to the possibility of
skipping, if you like.

Also, skipping, as I sort of touched
on earlier, there could

be, for example, that you have
an index that has 90% of the pages

in the index in respect of the
leading column have 3 values total,

but nevertheless, the remaining
10% are all perfectly unique.

So now you don't have...

You can't really average the two.

It's just two different things.

You can't think of it as the average
of the 2, really.

So the fact that it's kind of continuous
just makes sense.

You wouldn't want to have it be...

If the planner were to make a static
choice, then how would you

account for that variation where
you legitimately need to change

your strategy for the same index
scan in real time like that's.

Totally possible that that would
be the best thing to do so I

like not having an opinion until
you really have an opinion the

last minute you.

I do get the best of both worlds.

That's the thinking.

Anyway.

Michael: I think it's super smart.

And those distributions are quite
common.

We see them all the time.

And it's the time where statistics
most obviously falls flat

on its face because of averages.

I know it does some things to most
common values.

But anyway, I completely agree
that makes loads of sense.

Peter: Sorry, you were going to
say?

I was going to give another example
of what you're saying with

statistics.

I mentioned briefly earlier, there's
this...

I think it's called the attribute-entity-independence
assumption.

It's this generic sort of assumption
made by all cost-based optimizers

that there's no correlation between
different columns, which

is demonstrably false all the time,
but somehow mostly doesn't

break that badly.

But for something like this, you've
got to think, there could

be a very strong correlation between
columns, or there could

be a totally different, completely
independent relationship between

the 2.

And it's really hard to model that.

So if you can just not do that
to much of an extent at all and

still get useful query plans, that
seems ideal.

You know, there's just different
types of indexes.

So you have, for example, in the
paper that I talk about, it's

data warehousing, So you explicitly
have different dimensions

of a business that are obviously
quite independent.

But then you could also have something
like, I don't know, supplier

ID, first column, second column,
discount code.

So it might be that different suppliers
use the same discount

code, coincidentally, But even
then, those 2 discount codes are

completely distinct entities.

So it just doesn't make sense to
think of them as being the same

at all.

You wouldn't expect a query to
just supply a predicate that doesn't

have a supplier ID.

You would expect either to have
a display ID or have both.

You wouldn't expect it to be omitted,
because it just wouldn't

make sense.

So it's impossible or very difficult,
in any case, for the optimizer

to understand those kinds of distinctions,
even though they're

obviously very, very common.

So again, ideally, it wouldn't
have to.

Ideally, it would just be able
to fall back on this sort of idea

of, hey, we'll try to work it out
at runtime to the best of our

ability.

As long as we get the fastest query
plan, everyone's happy.

It doesn't necessarily have to
be that exact and cost model.

In fact, usually isn't.

So that's kind of the, the overarching
philosophy of the thing.

And.

Michael: Yeah, as usual with your
work, it's so simple once it

makes like, once you understand
it, but to like, I'm super impressed

with the thought process to have
got there.

It feels like yet another feature
where, as users, we don't have

to think about how it's working,
why it's working that much.

Maybe with strategies later in
terms of indexing, we can take

advantage of that.

But we could carry on indexing
exactly the way we are, and we'll

only benefit as a result still.

Peter: Unless I mess up, of course,
but hopefully I won't do that.

Yeah.

I'm not exactly playing to my strengths
when I'm talking about

the optimizer, you understand,
but nevertheless, that is kind

of part of the philosophy.

I'm not really an optimizer person.

I like being successful, that's
probably why.

But here, I think that undeniably,
there is some thought given

to those aspects, because it kind
of has to be.

Michael: What do you mean successful?

Peter: Well, it's just really hard
to do anything in the optimizer.

That's why some people will do.

And thank goodness someone is willing
to do it.

But it's a very difficult area
to work in, I feel, which does

seem to put people off more than
perhaps it should.

Perhaps that will change at some
point in the future, but you

have to ask somebody else about
that.

Michael: Al-Khalili Yes.

That somebody else, I believe,
is going on another podcast, which

I'm excited to… Al-Khalili

Peter: Oh, great.

I think I know what you're talking
about.

Michael: Yes, for everybody else,
this is Tom Lane going on the

Talking Postgres podcast, which
is scheduled to be live, I think,

next month.

So I'll share a link to that.

Exciting times.

So we've talked about it briefly
already, But another cool thing

you've done here is split this
work into some useful stuff on

its own for version 17 coming out
soon.

I'll be interested to hear how
and when did you realize you could

split it up into the in-list optimizations
that I think are going

to be very useful for a bunch of
often-generated queries that

people don't have that much control
over, like long, like relatively

long in-lists seem to pop up, at
least from what I've seen from

like ORMs normally.

How did you work that out?

Peter: I'm not sure exactly when.

I think it probably wasn't any
1 moment where I realised that

those were… I remember talking
about another patch, actually

1 for LucidNextScan, and just being
very confused about that

whole area myself, being very confused
about what the difference

is, where to draw the boundaries
architecturally.

And I recall asking to nobody in
particular at the time, how

does this relate to in-lists or
what we would call internally,

ScalarArrayOpExprs equals
any array expressions?

There must be some relationship
here.

At that time, I was aware of the
paper, the source material,

and that strongly suggested as
much.

But I just didn't...

I kind of thought, you can't really
have an opinion about 1 without

having an opinion about the other.

You want to be able to combine
these things arbitrarily.

So that was when the initial awareness
sort of sunk in.

Then I had some work on Vacuum
over a couple of releases, and

then I came back to B-tree again.

And I think at that point I realised,
OK, this is probably the

most useful thing I could do.

And then I got a little bit lucky
as well with the project for

17.

I worked out a couple of things
on the optimizer side that I

wasn't necessarily counting on.

That's more subtle.

It's stuff that's related to whether
or not we know that the

scan will return ordered results.

So I realized the relationship
between that question...

So in previous versions, you would
do a query like SELECT FROM

TABLE where a equals 5 and b in
a long list, ordered by AB limit

something, and it wouldn't be able
to terminate the scan early

because, for reasons that are complicated
and not that interesting,

the implementation could trust
the B-tree code to correctly return

things in the ordered results.

So I kind of had this idea that
that was important, but I didn't

know how important it was to everything
else.

So I kind of got a bit lucky in
figuring that out in about 2023.

Before I even realized that I was
pretty sure that I would do

the skip scan thing, but there
was some serendipity with, there

was actually a user complaint,
I think it was on Slack.

Michael: Oh, yeah, Benoit.

I'll link that up as well.

Peter: Yeah, Benoit had a complaint.

Basically, because of the limitation
I just mentioned, the query

plan, which was for such a query
with an emit, it couldn't do

it without creating a way of filtering
the non-matching rows

that required heap access.

So for reasons that are not really
fundamental and worth explaining,

it did way more heap accesses just
to exclude non-matching rows,

when in principle it could have
done that at the index level

before accessing the heap at all.

So for very roundabout, hard to
explain, and actually not that

relevant reasons, that made a huge
difference for his use case.

I wasn't even thinking about it,
because I'm a B-tree fellow.

I wasn't really thinking about
avoiding heap accesses.

But then I found, actually, that's
by far the main reason to

do that.

I was thinking initially about
just the simple fact that, hey,

do you want to do the index descent
1 time or a hundred times?

Obviously, you want to do it 1
time if that's feasible.

That's where I started, but then
I realized not much later, but

somewhat later with some help from
Edoard, oh, actually, yeah,

you can in some cases at least
completely...

Only to all this right about nonsense
with restrictions in the

planner, you can completely...

In some cases, like the one he showed,
you can completely eliminate

a huge number.

And that was by far the best, the
most flattering case for the

B-tree work, where I think it was
like 8, 20 times faster, something

like that.

It doesn't really matter what the
number is, it's way, way faster,

because you're fundamentally doing
way less I/O.

So I didn't necessarily count on
that happening at all.

And then it kind of did without
my initially realizing it, which

was nice.

Serendipity did play a role, as
it often does.

Michael: Very cool.

Nikolay, do you have any questions?

Nikolay: Of course, I have comments
and questions.

All of them are silly, maybe.

Once again, we should avoid this
confusion.

Loose index scan is not skip scan.

Because I saw posts mixing these
names, but I double-checked

Oracle and SQLite, and they have
both skip scan, the same meaning,

so we should stick to this.

Peter: I guess so, yeah.

I mean, I wouldn't mind calling
it something else entirely, but

I certainly do think the distinction
between loose index scan

and skip scan.

I was confused on that point myself.

I mentioned this already.

The important distinction between
the 2 is...

So loose index scan involves an
Index scan that knows specifically

that it's feeding into a group
Aggregate.

So it's only correct because you
don't actually logically need

to return all of the rows from
the Index, or indeed from the

Heap at all.

It's only correct because of that
high-level context that you're

applying in the slow-level code.

Whereas, in contrast, SkipScan
isn't like that.

SkipScan is just exploiting information
that's readily available

to the scan.

It's doing Index scan things in
a more clever way without really

understanding how that information
is being consumed 1 level

up or 2 levels up.

So that's how I think of it.

Nikolay: Yeah, you mentioned work
on LucentXScan also happening.

What do you think about the future
of that work?

Peter: I think it's a perfectly
fine idea.

There's nothing wrong with it.

I did briefly look at that some
years back.

My recollection of exactly how
it was at the time is a little

bit vague.

I remember noticing that it had
lots of bloat which was

probably a little bit of something
that discouraged my involvement,

because, again, I like being successful.

Right, yeah.

But fundamentally, it's a perfectly
sound idea.

It's obviously a good idea that
could be implemented with enough

effort.

And I think that the patch didn't
have any major problems, or

at least didn't have any major
problems that could not be addressed

in the fullness of time.

I recall Tom, at the time, who
was sort of asked to take a look

at it by me, saying it was maybe
doing things the wrong way on

the Planner, but that's kind of
above my pay grade.

But from an indexing point of view,
obviously it makes sense.

It's like, just thinking about
it very sensibly, it's doing potentially

an enormous amount of extra I/O
you don't need to do logically.

It's just not...

Yeah, I mean, it's inarguable that
that's a perfectly good idea.

If I haven't started there or I
haven't paid too much attention

to it, it's only because of competing
priorities.

I think it's totally reasonable.

Nikolay: Yeah, we write with recursive
all the time to implement

this, basically at the application
level.

I'm curious if there are any specific
benchmarks which could

be helpful for these both patches
to check, like, kind of workloads?

Peter: Well, not really, because
as often is the case with things

that have some compiler component
to them, it's sort of like,

It's perfectly obvious that it's
not a quantitative improvement,

it's a qualitative improvement.

So you name a number, and I'll
give you a test case that is faster

by that amount.

It doesn't make up a number.

It's no problem.

I'll get you a test case that will
do that.

I just have to come up with something
that has sufficiently large

amounts of things that you will
be skipping now.

Coming up with a number, it's not
really very meaningful.

You're doing it in the efficient
way, the obvious, sensible way,

having not done that, so there's
really no practical limit on

how much faster it could be.

And it's hard to make generalizations
in the real world.

That's the annoying answer to your
question.

Nikolay: By the way, I wanted to
ask you about propagation of

this idea from B-tree to other
types of indexes, GIN first of

all.

Is it a valid idea at all?

Maybe with combination with the
btree_gin?

Peter: It definitely could be,
but then the way the GIN in particular

does multicolumn indexes is kind
of weird.

The way that actually works is,
it essentially, rather than having

a B-tree that has A and B stored
together, let's say it has a

B-tree, if and only if you have
a multi-column index, It has

a B-tree where attribute 1 is stored
with 1, whatever the value

for A is, and attribute 2 is stored
with 2, whatever the value

for A is.

So the column number is, in the
B-tree itself, where the entries

live, is the most significant key,
which is very different.

Now, if you said to me, what about
GIST, then that's very different,

because GIST is much more like
B-tree, particularly here.

I think with GIST it's totally
possible.

The way that GIST works, so the
source paper I mentioned, Efficient

Search of Multidimensional Indexes,
it might be confused.

You might think, well, multidimensional
like GIST?

And the answer is, yes, sort of.

I'm doing work that's purely enhancing
B-trees, but some of the

ideas with dimensionality are at
least at a high level related

to things like multidimensional
indexing using GIST.

So I think it's entirely possible
to do that.

GIST is loosely ordered, so it's
kind of inherently doing something

a bit like that anyway, where it's
not so much finding the exact

match and the exact place where
it must be, but rather looking

in all the places it could be exhaustively,
which is usually

only a fairly small number of pages.

It doesn't have the same propensity
of B-tree to go to exactly

the right...

The only right place for that value
that you're looking for directly.

It's more because of the loose
ordering of the index, it's not

quite doing it that way.

There's a bounding box in the internal
pages which describes

what the leaf pages contain.

So you might have to do 2 or 3,
even for a point lookup, you

might have to do 2 or 3 leaf page
accesses, as opposed to just

1, which would be very often the
case with B-tree.

So it's almost kind of doing that
anyway.

So it seems entirely plausible
that with GiST you could do something

similar.

I don't think that's probably possible
in the case of GIN, though,

because what does that even mean
in light of the scheme with

GIN storing two different attributes
in completely different places?

And the tree doesn't really seem
compatible with that.

I don't know, though.

I mean, anything's possible

Nikolay: what if it's a bit region
when first called on this.

Scalar like organization ID
or category or something and

second column is like JSONB or
something?

Peter: Maybe.

I mean, I think it's probably more
proveable to talk about it

in the context of a use case.

So there, I guess, intrinsically,
you have a kind of nested structure

to JSON.

And so having that capability could
be useful if you had some

kind of partitioning scheme or
something like that, I suppose.

Nikolay: I mean, JSON nested structure
doesn't matter.

It's a second column.

I

Peter: know, I know.

Nikolay: Right?

We put a scalar value, like some
number or timestamp on the first

place.

Peter: Yeah, I mean, I think that
could be possible.

I haven't thought about it too
much, though.

You have to talk about it in two
levels as well, though.

It's like, what would be practically
achievable within a year?

Nikolay: Let me tell you.

Why I care so much about this.

Because I started to reflect on
one problem recently related to

full-text search in Postgres and
why people move to Elastic.

Why I did?

Because I saw a similar situation
happening with pgvector.

The most popular issue in pgvector
repository right now on GitHub

is additional filtering.

So people need like global index
with vectors, but they also

need to be able to sometimes search
locally for a particular project,

organization, I don't know, anything.

And this usually is done, what
Elastic and others, they call

it metadata search.

Basically, it's additional filters,
usually these colors, like

numbers or timestamps, something.

And for vector search, it's not
solved yet.

That's why people still can say,
like, they say PostgreSQL vector

search with pgvector is not well
for us.

Because the usual solution is,
let's just create partial indexes.

But if you have hundreds or thousands
of categories, it doesn't

work well.

Then I realized that for full-text
search, we had a similar problem

for years.

Usually it's solved by extension
bit region.

Then you are able to create a multi-column
index, but this is

a barrier for many people.

Although this is a contrib module,
it's present everywhere, it's

some kind of a barrier.

And I saw cases when people even
created this extension, but

somehow still not using it well.

They still have this problem, B-tree
vs. GIN dilemma for planner,

right?

So I'm thinking, for example, if
we use BRIN more often, we

usually will put scalar value on
first position, because it's

more selective, by default, maybe.

We don't know.

And if it has a low number of distinct
values, this skip-scan

approach would make total sense
there as well.

Right?

Peter: Maybe.

I don't have a lot of domain expertise
here, so forgive me, I

need to ask questions to clarify
what you meant.

Are you talking about pushing down
a limit for each grouping

or something like that?

Nikolay: Limit is like...

I'm not sure about limit and ordering,
I'm just thinking...

Peter: But not a limit for the
entire query, but rather for each

individual grouping or whatever.

Where you want to...

Is that what you mean to the question?

Nikolay: Imagine we have full-text
search, TSVector, GIN index,

and then we have additional things,
like, for example, creation

time.

And when we want to search within
some window only, By default,

full-text search in Postgres doesn't
support it itself.

It will be a different B-tree index
on timestamp, like created at

timestamp, and we have a global
whole table GIN.

And then the planner decides what
is cheaper.

Bit by bit and then filter on the fly,
or use full text search and

then filter or order by on timestamp.

And the pg_trgm extension gives
you the opportunity to combine,

have 2 column index.

And then the goal is to find everything,
no limits, right?

But if we put scalar value on first
position, queries which don't

have this filter will be not good
with this index.

So we put a timestamp as our column
A and the TS vector as our

column B, use B-tree for that
to have 2-column index.

And then I would like to have skip
scan for this, because if

my query doesn't have additional
filtering and we have a low

number of distinct values for column
A, maybe timestamp was not

good because it will be a lot of
distinct values.

Let's say it's some category ID
or, I don't know, like group

ID or something.

In this case, probably skip scan
will help there as well for

such queries.

Or I'm forced to put this column
to second position and keep

full-text vector on the first position?

Okay, this is something to think
about additionally.

I'm just very curious.

Peter: I don't know is the simple
answer.

In principle, you could...

I mean, after all, what I've described
is, in the end, there's

a bunch of details, but it is basically
quite simple.

You have to be willing to do, at
least in the simple case where

you omitted, fully omitted a prefix
column, you have to be willing

to look at every single individual
partition, every distinct

value, which adds up quite quickly
if it's something like a timestamp.

Whereas if you had some kind of
bucket by day or something like

that, then it would be more feasible,
because then you would

have relatively few buckets, and
especially if you had not completely

omitted the date column, if you
had a range in between, then

it would be, I think, feasible
from a data structure point of

view, not necessarily in GIN, but
in something, to do something

like that.

I mean, I don't know what the basis
of comparison here, what

is Elastic doing?

I just don't know.

I can't speak to that.

I don't know
Nikolay: as well, internals.

They just claim if you have additional
filtering, it's not slower

at all, and usually it's faster.

This is what their documentation
says.

I'm very curious about internals
as well, because I just feel

this, even from a user perspective,
even the need to create btree_gin

extension, it's already a
barrier.

Some people don't do it, and they
think, okay, full-text search

is weak, And they are going to
have the same impression about

vector search.

And this whole topic about combination
of these powerful indexes

with B-tree indexes, It's interesting.

Direction, I think, can be improved
as well.

And with SkipScan, maybe it can
be improved further.

This is my basic idea.

It's quite maybe not well thought.

I promised to have silly questions.

So

Peter: It's okay.

There are no silly questions.

Well, I've got an even sillier
idea because I don't have I think

a very very Fisher Price level
understanding of how pgvector

works, which is not going to do
much good here So, you know,

I'm not going to say something
about I think I know so little

about it's something that.

Maybe I'll talk to Jonathan Katz
better next time I see him he's

my go to expert on these things.

Yeah

Nikolay: I'm sure he knows already
this problem very well, because

as I said, this is the most active
discussion among issues on

GitHub repository, and basically all people
need this.

They need a combination of B-tree
and vector search somehow.

Maybe not only just one B-tree, not
only this color, but a bunch

of them, because they need to filter
additionally.

This is a challenge.

I also know one project which they
built some kind of quite universal

solution for the others.

When they first came to us, they
said, we are forced to index

every column for flexibility.

We know this is anti-pattern, but
we are forced.

I'm sure they will be happy when
Postgres 18 is out with this

optimization.

This is super relief for them,
because they are struggling with

this problem.

It's good to have only, as Michael
said, only one index on multiple

columns and don't think too much
about order.

Peter: Yeah.

Especially if, as I say, the important
distinction is between

getting a very slow, totally unacceptable
performance, typically

if sequentials can have a very
large table, versus adequate,

sub-second but not sub-millisecond.

Like, a lot of people are in that
zone, and if they have a lot

of ad hoc queries, they can't really
predict the indexing needs

ahead of time.

I think it makes the biggest difference
there.

Much less so in OLTP apps, but
still to some degree, it's going

to get you acceptable performance
where you didn't know that

you really ought to have had a
certain kind of index, and then

you get adequate-ish performance
there too, which could make

all the difference in a pinch.

Nikolay: Yeah, well, actually,
interesting additional question

I have.

With loose index scan, we have
this wiki page describing this

technique.

We apply this technique using recursive
CTE, and there is an

Expectation in the future we will
stop doing this, it will be

fully automated.

It doesn't make any sense to think
about implementing while we

are still not there and not on
Postgres 18, it's not even committed.

It doesn't make sense to try to
implement a similar approach

at a higher level ourselves, somehow,
splitting query to pieces

like different index scans.

Peter: It might.

I would just say, in the case of...

If you're able to upgrade to Postgres
17,

Nikolay: and

Peter: having done that, you're
able to also...

Suppose you have 10 distinct values
in your leading column.

If you can write an inlist that
has those 10 distinct columns

and are satisfied that that will
work for you, that will give

you the correct answer, not only
when you write the query, but

going forward, if it's sort of
static, then you can totally do

that.

And in fact, I would expect the
actual access patterns to be

identical to what you would have
gotten had you had the skip

scan feature.

It is basically doing the same
thing.

It's just rather than having an
array with these constants that

come from a query, you will instead
have a magical sort of an

array that the B-tree scan code
uses almost the same way.

It's just that it generates its
array elements procedurally and

on demand, but it is essentially
the same thing at quite a low

level.

So it would be not just similar,
but identical, if you could

make it work within those constraints.

And in particular, there'd be no
possible downside in terms of

whether or not it made sense to
do a full index scan.

Depending on the distribution of
values, it's going to be adaptive

in that same way I described.

With a big caveat, of course, you
kind of need to know that,

at least for those leading values,
that it's static and predictable,

and it won't change and break your
query.

Nikolay: So I guess our approaches
will change with this.

Usually we, like, analyze workload
and decide on indexes, we

decide what to put on the first
position, second position.

Here it seems like Sometimes we
will decide to put columns with

lower cardinality of distinct values
or something.

Peter: That'll start to make way
more sense than it did.

I don't want to overstate it.

It's not like a revolution by any
means, but there are specific

rules of thumb that will be we
can buy it for sure Would that

you already said yourself Nikolai
was Oh put the most Just put

the highest cardinality column first
That's already kind

of suspect actually, but it's actually
is in this world with

this capability.

Nikolay: Interesting.

Peter: I think it's mostly confined.

That'll be most true by far with
more your data warehousing use

cases, where there is a built-in
requirement for a lot of ad

hoc querying that you can't really
exactly predict ahead of time,

looking at the details of something
rather than just a summary,

really matters, then yes, absolutely,
that will be true.

Well, with all the CPUs, less
so.

Nikolay: Cool.

Yeah, this is an interesting direction
to explore, even if the patch

is not yet committed.

Yeah, thank you.

Go and have something in the to-do
list.

Michael: Yeah.

Is there anything else you wanted
to make sure you mentioned,

Peter, or anything anyone can help
you with?

Peter: Well, I always welcome input
into the work I'm doing.

It would be kind of nice if I could
get some feedback on the

stuff we were just discussing about,
hey, how as a practical

matter does this alter the general
advice that we give to you

about how to index things?

I'm not entirely sure how, in practice,
that will tend to work

out anyway.

It is nice that this is a very
general thing.

I think that will tend to make
it possible to use it more often,

because in a certain sense, the
optimizer only has to have the

right rough idea, because if it
has that, then it will pick an

index scan, and then the index
scan itself will figure out what

to do.

So I think that's probably going
to make it more compelling than

it appears to be in other systems,
where, as far as I can tell,

I might be mistaken, they require
the optimizer to generate a

distinct index node type.

So it's kind of either-or, which
seems to me anyway, could be

something that limited the applicability
of the optimizations.

So I feel like it would be nice
if I had a better idea of how,

practically speaking, this will
change things and where.

I don't think I've got a complete
understanding of that myself.

Like, what kind of applications,
what kind of usage patterns.

That would be nice to have more
detail on.

So if anyone wants to help me,
that would be an obvious place

to start, I would say.

Michael: Nice, thanks so much,
Peter.

It's been an honor having you on.

Great chat.

Peter: Thank you both.

Thanks, Michael.

I really enjoyed it.

Nikolay: Thank you.