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

Tomas Vondra <tomas.vondra@2ndquadrant.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.

            regards, tom lane