Greetings,
* Peter J. Holzer (hjp-pgsql@hjp.at) wrote:
> On 2019-05-18 19:16:19 -0500, Ron wrote:
> > > If the the table fills up, you increase nr_buckets, reallocate and
> > > rehash all entries.
> >
> > Ouch. Response time on a big table would take a serious hit if that rehash
> > happened in the middle of the day on a big OLTP system.
As noted below, that isn't actually how it works with PG's hash indexes.
> So that might be a reason not to use hash indexes tables where the worst
> case insert time is a concern (the average insert time is still O(1)).
The worst-case insert time is certainly worse than the average but it's
not nearly as bad as being imagined here.
> You can split buckets lazily, and in fact PostgreSQL does this. I just
> looked at the code briefly, but I don't really understand how it works.
> Guess I would have to read Margo Seltzer's paper paper for that.
>
> Still, even with that optimization (or tradeoff - it may make the lookup
> slower) the README notes that splits are expensive.
There's multiple different levels, really, from "best case" where the
new item can just be placed directly on to a page that has free space,
to "slightly worse case" where an overflow page has to be added, to
"even worse case" where a prior page split has to be finished, to
"probably worst case" where a full page split has to happen. There
might even be some pathological cases where a prior page split has to be
finished and then an overflow page has to be added and then another page
split has to be done, or some such. Even so, for equality-based
lookups (where the data set has few or zero duplicates), hash indexes
can work quite well, but it's of course good to understand that inserts
aren't always going to be exactly the same speed every time.
Thanks,
Stephen
