Nikolay: Hello, hello, this is PostgresFM episode 76.
My name is Nikolay and as usual, together with me is Michael.
Hi, Michael.
Michael: Hello, Nikolay.
Nikolay: So, today's topic is super interesting and very popular,
right?
Michael: Not exactly.
I chose this one.
Nikolay: Okay.
Michael: Therefore, it's boring.
Nikolay: But we will learn something new, which is good.
Michael: I hope so.
Nikolay: Even if it's useless, it's still new.
We're here to learn, right?
Michael: So Nikolay's teasing me because I've picked the topic
hash indexes, which are, well, until relatively recently, were
highly discouraged by the Postgres docs and not very sensible
to use, but-
Nikolay: until PostgreSQL 10.
Michael: Yes, but have been in Postgres for a long, long time.
I looked into the history of it and therefore some people must
think they're useful.
And I definitely think there's one or two use cases for them, but
more to the point, I think they're very interesting for people.
I think this is the kind of thing that will make you appreciate
the B-tree index as well, and also understand a little bit more
about trade-offs we make when we're choosing things within Postgres.
Nikolay: Indexes, right?
I mean, why doesn't Postgres choose indexes, index type for us?
We just want to make it fast and that's it, right?
It should choose.
Okay, a different question.
Are hash indexes more useful than the money data type?
Michael: Oh, I think so, yes.
Nikolay: Okay, this is already better.
I hope we will never have an episode about the money data type.
Michael: Yeah, me too.
Nikolay: Okay.
Michael: So yeah, should we start with what a hash index is?
Nikolay: Yeah, hash function, hash index, right?
Michael: Yeah, that's pretty much it.
Hash table.
Yeah, so in fact that's a good point.
A lot of people have come across hashing from, well, looking
at query plans for hash joins or backend engineers, very familiar
with hash tables, can be a very efficient way of taking a value,
hashing it, in this case we get a, well, Postgres behind the
scenes is calculating a 4-byte integer, storing that, and then
in the future if we want to look up the value by equality and equality
only, we can hash the value we seek and look it up in the index
in this case.
So people that like theory talk a lot about big O notation, don't
they?
So this is one of those things that I struggle to love, but it has
a low like O(1) is what people often say.
I'm not sure it's strictly true, depending on how deep down that
rabbit hole you dive.
But yeah, it can be very, very efficient for looking up things
by equality, especially in certain conditions.
So that's like, actually a couple of things on details.
I didn't realize you could...
And it makes sense, but you can use a hash index on any value,
any data type, which is quite cool.
I guess the same is true.
Nikolay: Postgres has a lot of internal hashing functions for
all data types and also for the record.
So you can say record for some table and it will give you a hash
integer 4, right?
Regular integer 32 bytes or bits.
Michael: 32 bit, 4 byte, yeah.
Nikolay: Yeah, and I actually recently rediscovered it and used
it. It was interesting.
I didn't use the hash index, but I used one of, probably, hash
text function.
Yeah, it was hash text function.
I needed to, you know, when you need to reindex a lot of indexes,
and it's a huge database.
For example, after upgrade to Postgres 13 or 14, 14 especially,
you need to re-index a lot of bit re-indexes to start benefiting
from the optimizations Peter Geoghegan and others implemented.
And obviously you need to re-index.
You will do re-index concurrently and so on, it's good, but the
question will be how to move faster.
There are parallel workers, as we discussed, and so on.
But probably you will decide to use multiple processes to issuing
the reindex concurrently command.
And in this case, if two of them try to reindex two different indexes
which belong to the same table, you will have a deadlock.
So my idea was we just need to attach each table associated with
a particular worker.
And to do it, I just took a table name, calculated hash text
from it, and then modulo number of workers.
If I have, for example, 5 workers, I just...
So we have table name, hash text function, the hash text function
produces number, like integer 4 number, and then we just modulo
of 5, like remainder of the division, it will be like 0, 1, 2,
3, 4, and that's it again, 0, 1, 2, 3, 4.
And each index associated with a particular table will always go
to a particular worker.
So there will never be a conflict, no more deadlocks.
So this is how you can redistribute work.
Maybe also check if you need to redistribute, you need to check
a lot of indexes for corruption.
You can also use many like 16 workers, for example, and you redistribute
work to avoid deadlocks.
So, hash text is useful.
I was already like CRC32 or something, I was thinking, oh, I
need to, oh, by the way, I asked my bot to advise me, and it
says, oh, there is hash text.
I never used it before, or maybe I just forgot.
And yeah, then I, if you're in psql, if you say backslash df,
then hash star, you will see more than 50 functions.
We checked it before the call.
More than 50 functions, many of them return int4, some of
them return int8.
So it's good to have a lot of already implemented functions.
You don't need to care, just use it.
Good?
Yeah, absolutely.
Yes, Small comment, slightly off topic.
Michael: Yeah, I mean related to hashing, but I guess completely
unrelated
Nikolay: to hash indexing.
Michael: Yeah, exactly.
So you mentioned already, there's a big change in the history
of hash indexes I think is worth mentioning, and that's the version
10 made hash indexes crash safe or write-ahead log.
Which is really important, like before that it meant if you had
like, it made them basically unusable or unsafe to use, especially
in a high availability setup if you had replication and then
failed over, your replica wouldn't have that index.
Nikolay: Ephemeral indexes.
Michael: Yeah, right.
Nikolay: But not anymore, so it's solved.
The same was solved with GIST a very long ago.
Originally GIST was also not write-ahead log-supported at all, but it was
implemented like 20 something years ago.
Michael: Speaking of 20 something years ago, I was looking up,
I was trying to find out when hash indexes were added, and the
git history doesn't go far enough back, I don't think, and the
docs, the online docs 7.2 is the oldest version on the online
docs and they have hash indexes.
So that's as far back as 2002 already.
So they're more than 20 years old as well.
Nikolay: Well I'm quite sure they're older because it's maybe
one of the simplest types of index you can implement.
But interesting that WAL was not implemented for so long, right?
Right. Until 2017, right?
Michael: I think you'd struggle to get...
I could be wrong, but I think if we didn't have hash indexes
in Postgres today, they wouldn't get added and they would be
encouraged to be added via an extension.
That's my guess as to how they would be implemented if they were
done today.
But I mean, I might be, or maybe via the contrib modules.
Nikolay: Well, yeah.
Michael: But we have them.
They're first class supported.
They're well logged now.
They're replicated and everything.
Crash safe, even while they're doing complex operations, it might
get to a bit later, it will recover.
So we can use them if we want to.
I guess the question then is why would we?
And you mentioned something before the call I found very interesting
and it's probably very telling.
But should I ask you, have you ever used the hash index?
Nikolay: Only in experimental environments, never on production.
I think I saw them in the wild, you know, saw them.
I don't think I ever seriously considered them.
But you need to take into account that version 10 and later,
it's already mostly my consulting practice.
Before that, I created a lot of systems, social networks and
so on.
It was before Postgres 10, so I never considered them.
My memory says stay away from them.
Michael: Yeah, that's a really good point.
So it's only since 2017 that you should even be considering using
these.
So I'd like to first cover, I know there's going to be quite
a few limitations that we need to talk about, but I'd like to
cover some of the potential benefits of hash indexes.
Like I think there's a couple that are worth mentioning.
Nikolay: Size?
Michael: Yes, So they can be, so for, imagine if you are hashing
a fairly large string or even a number, or just a piece of data
that is more than 4 bytes.
When you are indexing it with a hash index, it's only having
to store 4 bytes, or a bit more, but it's not having to store
that value in the index.
And that means for larger data types or larger values, it can
be significantly smaller than a B-tree index with some caveats.
Naturally, there are some optimizations for B-tree that we've
got in recent versions.
And yeah, this really stands out for larger values basically
and for indexes that are unique or mostly unique, like, oh sorry,
for columns that are unique or mostly unique.
So that's a big difference as well.
But there are cases like that, right?
Like I did a collaboration with Haki Benita for his blog and
he did a lot of the work.
He deserves most of the credit but he put me down as a co-author
which was kind of him and we looked at quite a few things and
for the use case that he had for hash indexes which was a URL
shortening service you get some quite large URLs can be quite
large strings in the grand scheme of things, especially for URLs.
So they actually came out quite a lot smaller when you put a
hash index on it versus a B-tree, which is pretty cool, Even
post deduplication, because these are largely going to be unique.
We didn't make them completely unique, but largely your URL shortening
thing is going to be unique strings.
So yeah, they can be significantly smaller, they can be significantly
bigger, depending on your data.
But I think size is underrated in terms of index types.
I think not only we're going to look at performance in a bit,
but base and the cache, you know, we've talked about this kind
of thing before, but I think it is worth mentioning.
Nikolay: Yeah, by the way, if we try to index in a regular way
with B-tree some large text values, there's some limitation,
I always forget.
Michael: Oh, good
Nikolay: point.
Yeah, so sometimes we just need to apply hash and use expression
B-tree on top of it, but it's not, of course, it's not a hash index,
but we use a combination, right?
In this case, we cannot order these values, but for exact matching,
this is what can work well.
Michael: Why did you, why do you hash it and then put a B-tree
index on instead of just putting a hash index on?
Nikolay: Because again, I'm an old guy.
You know, like again, my mom says stay away from hash.
By the way, with my bot and GitHub, we just checked when hash
build, the hash build function was added and it's 27 years ago,
original Postgres 95.
Michael: 27?
Nikolay: Yeah, original source code of Postgres 95.
Michael: Wow.
Nikolay: Committed by Mark Fournier.
It had already this hash build, which builds a new hash index.
So this is super old stuff.
I think maybe it even came from original Postgres.
Obviously, it came from original Postgres, maybe even from Ingres,
who knows.
So maybe it's even more than 30 years ago.
Michael: Yeah, very cool.
But yeah, that's another advantage, right?
There's no limit to the size.
Nikolay: So you think, yeah, that's great.
So you think I just can create a hash index if I have very large
text values?
Michael: You're losing the same things, right?
You can't order by them.
And you're kind of doing a self-rolled one, which maybe even proves
that we don't need them.
But I think less footprint, right, because you're having to...
Yeah, I'm not sure.
I think there might be some weird trade-offs around maintenance,
but I think you'd largely recreate them, yeah.
Nikolay: So if I say create table T something as select and then
I say repeat as column C1 and I repeat some letter a million
times, I have obviously a text value, a million letters, when I
say create index on this value, on this table, on this column,
in this case, B-tree will say index row requires 11,464 bytes, so
11k, right?
Mm-hmm.
Ah, in my case.
But maximum size is 8K, okay, like block size.
But if I say using hash, right, using hash, same column, create
index, yeah, it works.
So why do I, okay, I'm an old guy, I have old habits, I need to get
rid of it.
Actually, this is the perfect case.
Michael: Or consider it.
Nikolay: Large text values, I don't need to hash first and then
B-tree, I just use a hash index in this case.
I will need to think about it.
Thank you.
This is unexpected.
Michael: There are some reasons you might not
Nikolay: want to
Michael: do this.
Nikolay: Why?
Michael: Okay, well, let's go through the positives first.
I promised positives.
Size can be, it can be worse, but it can be a lot better.
Speed can be better, not just lookups, but also the average latency
of inserts.
I definitely had some discussions with Haki when we were reporting
these numbers that we could have done a better job, I think.
I hold my hands up, this was a couple of years ago, and I've
learned a lot since then.
But insert performance on a batch was, or when we were inserting
1 row at a time, was about 10% slower, I think, for the B-trees
than versus hash, which I was a bit surprised by, because I knew
there was some overhead around splits for hash indexes, or higher
overheads some of the time.
But lookup performance...
Nikolay: B-tree also has splits sometimes, right?
Michael: Yeah, of course.
Nikolay: So we need to compare.
In this case, we can't say hash index has this disadvantage and
that's it, right?
B-tree also has this disadvantage.
Michael: Yeah, so they're kind of bigger splits less often.
Yeah, that's a good point.
But lookup speed, I was expecting a difference and admittedly,
they're both really fast, right?
We're talking about basically key lookups.
So B-trees, we've always raved about how good they are at like
key lookups, right?
Nikolay: That's what- Yeah, just a few pages to find a proper
reference to, like it's just a few blocks to fetch from disk
or to read from page cache.
Michael: I think we only did about 100,000 lookups and it was
both of them were under a second to do 100,000 lookups.
Nikolay: So you haven't checked shared buffers at that time?
Only timing, which is quite volatile.
Michael: Yeah.
Again, I would do some things differently now.
This is a couple of years ago.
But the lookups, whilst they were both under a second, I think
it was something like 30 or 40% faster for the hash lookups,
which was, I thought, actually quite significant.
So I think there are some cases where in some extreme, if you've
got long strings and you only care about uniqueness lookups,
then I think there's a case for using them.
But that is obviously a very narrow, very specific use case.
Nikolay: I wonder in these tests if you considered the planning
time, because I guess if table is not absolutely huge, like billions
of rows.
In this case, planning time can be maybe even a bigger contributor
than index scan itself.
So we need to exclude it using maybe prepared statements and consider
only execution.
Michael: That would be a good test, but also why would the planning
time differ between index types?
Nikolay: I'm not saying it differs, I'm saying if you're comparing
these latencies, what percentage of planning time is there here?
So we need to exclude it to compare clean numbers, right?
Michael: Yeah, that'd be great.
I don't think we used prepared statements.
I'm pretty sure we didn't.
Nikolay: And honestly, I wouldn't look at timing here at the
first, like this first metric.
I would still prefer looking at shared buffers.
But okay.
Michael: But the point is they can be more efficient and that's
partly because they're, if you imagine a B-tree structure, you
might have to go through
Nikolay: a few
Michael: hops, especially once your table gets really large.
Now we've talked about partitioning so many times, right?
So you could argue that you could keep your B-trees relatively
small in the grand scheme of things.
But if we do get large enough, the hash structure is just so
much more efficient and that will show up in shared buffers as well.
So that is the argument, I think.
So you've got smaller, potentially smaller, indexes for certain,
you know, for highly unique, slightly larger data types and potential
benefits on the insert and lookup speeds.
Nikolay: Have you considered collisions?
Because if you have only integer four, obviously you might have
collisions and you need to resolve this additional hops, right?
Additional comparison and so on.
Have you considered trying to measure some edge cases?
Michael: I looked into this, I looked into the internals a bit.
Well, actually there's a couple of really good internals pages
on the PostgreSQL docs on hash indexes.
And it's only a throwaway word quite early on in one of them that
mentions that they are a lossy index type.
So it's not the only lossy index type, but it means that just
because we get a match for the hash, the 32-bit integer, doesn't
mean we do actually have a hit.
We could have a collision.
So there is a recheck, and you can get rows removed by index
recheck type things in your explain, but I haven't seen it.
Like we're talking, but you'd have to have, well, I'm not sure you'd have to have billions,
but I'm guessing you'd start, you know, in the tests I've done,
I haven't seen any.
But I guess you'd pay that overhead for every lookup, right?
Like you're having to do that recheck all the time because they're
lossy.
It's not just when there are collisions that you pay that recheck.
So those numbers I was talking about include the overhead of
rechecks.
Nikolay: Okay.
So what are the downsides?
Why shouldn't I
Michael: use- So many.
Nikolay: So many, okay.
Index only scan, as I remember, right?
Yep.
Lack of
Michael: index only scan.
Because we don't have the value in the index, it's literally
impossible to have an index only scan.
Right.
Nikolay: And that's bad.
Yeah. Right.
And that's bad.
Yeah.
Yeah, so.
But if I, in my case, if I have large text value, and I consider
B-tree versus hash expression.
Michael: You can't have an index only scan there either.
Nikolay: Yeah, because I cannot fetch the original value.
So it's not a reason that would stop me from using hash index.
Okay. Right.
Michael: In fact, if you consider collisions for that.
Nikolay: Yeah, well, yeah, yeah.
Michael: You have to implement it yourself.
Nikolay: That's true, yeah.
Michael: So I think the big one is ordering.
Obviously not in the case you're talking about where you're hashing,
but the big advantage B-trees have is they order your data and
that supports so many different things.
Nikolay: And greater than or less than comparison, obviously.
Yeah,
Michael: range scans, yeah, it feels like a limitless number
of things that that then enables.
Nikolay: Right, you can deal with collation issues, it's so cool.
They can be corrupted because of collation changes.
Michael: I mean that's a good point.
Maybe hash indexes are less likely to get corrupted.
Nikolay: Right.
Okay.
Michael: Actually, what if the hash function created a different
value instead?
Nikolay: I don't think it's a good question.
I don't know how it's implemented internally.
It should not be super difficult.
But obviously, how will it hash non-latin characters and so
on?
Michael: Yeah, exactly.
Does it depend
Nikolay: on glibc version change, for example?
It's an interesting question.
I never had this question because, again, I'm not using them
in the wild often at all.
Michael: Another huge difference, and I don't think this is a,
I don't think this is necessarily based on it's, I don't think
this is like the index only scans where it's literally impossible,
but you, in Postgres, we can't use hash indexes to enforce uniqueness.
So for unique constraints, which is a big deal.
Like, that's a really, like, for example, we can't use them for
primary keys.
Or like, there's no point because we've already got a B-tree
index on them.
Nikolay: Okay.
Good to know.
What else?
Multicolumn, right?
I remember now.
Yeah,
Michael: Exactly.
So, hash indexes don't support multicolumn.
Nikolay: You can combine values, so you can, I don't know?
Michael: But more to the point, one of the nice things about multi-column
B-tree indexes is you've also got the sorting sorted by the first
column and sorted by the second.
So we just don't have advantages like that.
And it ties into the index-only scans as well.
One of the best things about multi-column indexes is we then get
potential for index-only scans as well.
So these things, a lot of them are interplay.
One difference that isn't necessarily an issue, but I found interesting,
I thought you might as well, was that the fill factor for hash
indexes is 75 by default, whereas B-tree is 90.
Really interesting.
Nikolay: Some old decision, I guess.
Maybe not, but maybe, I don't know.
Yeah, Michael: Interesting.
Well, I guess, like, in the blog post, we looked at what does
it look like if you change the fill factor to 25, 50 or 100.
And at 100 versus 75, you just see, you see it not getting larger
as quickly, but when it does, it bounces at a faster rate.
So as the index grows, it grows less at first and then more all
at once.
So my guess is it's some trade-off between general size and performance
and the impact of splits or the cost we pay at splits.
And in fact, this is probably the biggest one you'd want to consider
on the difference between doing a B-tree index on a hash function
versus using a hash index.
And that's how insert performance would look in
terms of probably not average latency, but maybe the standard
deviation of latency.
So with hash indexes, the way they're structured, we have buckets
that values can go into, but beyond a certain size, Postgres
works it all out, and it does all this for you.
It decides, oh, we need more space.
It'd be best to have another bucket.
Let's split one of the existing buckets.
And then we pay that overhead during the insert, right?
Like that, it can slow down your insert.
So my guess is the standard deviation for inserts would be perhaps
significantly higher than B-trees but I haven't checked.
It's another thing I would like to do.
Yeah.
So on high throughput, there is a note in the internals document
about high throughput.
Let's say you've got a really high throughput table, you might
actually be better off with your B-tree index that you mentioned
than a hash one.
Nikolay: Okay.
And multi-column index, I think we can, I've just checked by
the way, hash index applied to whole table row.
It works.
Produces interferer number, it works.
I think we might probably decide to use it to, I remember I was
always using MD5 hash, converting row first to text and then
MD5, but maybe hash index is a better choice when we need to,
for example, compare the content of two snapshots, row by row,
you know, like to find which rows were changed, comparing them,
like joining by ID, by primary key, for example, and then we
compare hashes of whole row, right?
In this case, hash index is working.
I wonder if, like, if we, okay, multi-column index is not supported.
What if we just combine multiple columns and produce hash out
of them and almost the same, right?
It's strange that it's not supported.
Michael: I mean, we can still only use uniqueness lookups, right?
So I guess it's the case where you want to see if two columns when
combined are equal to the record you've stored, yeah?
But I'm not seeing the same benefits.
Nikolay: Okay, I will check a couple of things more.
Any more limitations or that's it?
Michael: I don't think so.
I might have missed one.
But those for me are substantial limitations.
And I think if you're, like when you're, imagine when you're
designing a system where you're choosing an index type for a
new feature building, and it turns out that right now, the hash
might just about come out on top.
Maybe you get slightly smaller index, maybe your lookups are
slightly faster.
I'm not sure I'd still advise using a hash index.
I think I might say, look, if your requirements change in the
future, if you ever do need to look up like a range of these
values, if there's some analytics you might need to do on it
or something, you might have been better off with a B-tree index.
You've got that extra flexibility.
You've also got, I think, probably more effort being put into
optimizations on them going forwards.
If it's a tight call between them, I might still encourage people
not to use them in general.
Nikolay: I never did it, I just did it.
I used hash record function, applied to the whole row in a table,
which has 3 columns.
And then I created an index on top of this, that hash record.
So, for the first time, I created an index not specifying columns, but
involving all columns in a table.
This is super strange.
It could be bit-free actually as well because the hash record produces
an int4, right?
So it applies to all columns.
So I said, create an index on T1 using a hash of hash record of
T1.
The whole record.
That's super strange.
I need to think Michael: about it.
What use case are you imagining for this?
Nikolay: I don't know.
I'm just exploring, you know, like, curious.
I don't know, maybe like, again, like to track which records
changed content or something.
I don't know.
It's just interesting that it works.
I thought we were required to specify columns, right?
When we like this column, that column, but here you just specify
the whole record and it works.
This shows the flexibility of Postgres as usual, right?
But I created a multi-column index hash, but it's a hash of hash.
So double hashing here.
Okay.
So I don't know.
I'm still thinking about use cases.
I still only, like, a realistic one is only this, like, really large
text values.
That's it so far for
Michael: me.
Yeah, and when you only need unique lookups of them.
Nikolay: Yeah, so yeah, interesting.
So I will keep it in mind.
Michael: Yeah, I love that we've gone, during this episode we've
gone from I never have use cases for hash indexes.
Yeah, exactly.
There we go.
Cool.
But I also think, you know, you said you've seen them in the
wild.
I think that might be a result of people overthinking it.
And I was there a couple of years ago.
I was thinking, you know, there might be some cases where that
the difference is meaningful and worthwhile, but for the flexibility,
I think.
Anyway, I've said that a few times now.
Cool.
Well, thank you, Nikolay. Thanks for indulging me.
Hopefully a few people found that interesting and useful, and
yeah, catch you next week.