Re: [HACKERS] Lazy hash table for XidInMVCCSnapshot (helps Zipfian a bit)

05.03.2018 18:00, Tom Lane пишет:
> Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> writes:
>> Snapshots are static (we don't really add new XIDs into existing ones,
>> right?), so why don't we simply sort the XIDs and then use bsearch to
>> lookup values? That should fix the linear search, without need for any
>> local hash table.
>
> +1 for looking into that, since it would avoid adding any complication
> to snapshot copying. In principle, with enough XIDs in the snap, an
> O(1) hash probe would be quicker than an O(log N) bsearch ... but I'm
> dubious that we are often in the range where that would matter.
> We do need to worry about the cost of snapshot copying, too.

Sorting - is the first thing I've tried. Unfortunately, sorting itself
eats too much cpu. Filling hash table is much faster.

Can I rely on snapshots being static? May be then there is no need in
separate raw representation and hash table. I may try to fill hash table
directly in GetSnapshotData instead of lazy filling. Though it will
increase time under lock, so it is debatable and should be carefully
measured.

I'll look at a bug in CopySnapshot soon. Excuse me for delaying.

With regards,
Sokolov Yura