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

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
Cc: Stephen Frost <sfrost(at)snowman(dot)net>, Sokolov Yura <funny(dot)falcon(at)postgrespro(dot)ru>, Robert Haas <robertmhaas(at)gmail(dot)com>, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, pgsql-hackers-owner(at)postgresql(dot)org
Subject: Re: [HACKERS] Lazy hash table for XidInMVCCSnapshot (helps Zipfian a bit)
Date: 2018-03-05 15:00:41
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

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.

regards, tom lane

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2018-03-05 15:04:30 Re: PATCH: psql tab completion for SELECT
Previous Message Marko Tiikkaja 2018-03-05 14:54:53 get_actual_variable_range vs idx_scan/idx_tup_fetch, again