On Thu, Aug 30, 2018 at 2:40 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> A related topic is the cache-unfriendliness of traditional binary
> searches of sorted data. Check out "Array Layouts for
> Comparison-Based Searching"[1] if you haven't already. It says that
> if your array fits in L2 cache, as our btree pages do, then binary
> search still wins against Eytzinger et al, which I was a bit
> disappointed about when I was (casually) investigating new layouts
> based on some comments from a fellow hacker (I can't remember if it
> was Andres or Peter G who mentioned this topic to me).
It might have been both of us, at different times.
> However, the
> paper is talking about "branch-free binary search with explicit
> prefetch", which apparently eats plain old branchy binary search for
> breakfast, and I gather they tested on a lot of hardware. That sounds
> interesting to look into.
I think that the main win will come from stacking a bunch of different
optimizations on top of each other, including key normalization,
automatic prefix compression on internal pages (something that's a lot
easier than on leaf pages [1]), and abbreviated keys in the ItemId
array of nbtree pages [2] (even 15-bit abbreviated keys can have a lot
of entropy when combined with these other techniques). Once we have
all that in place, I expect drastically fewer iCache misses, making
other optimizations interesting.
I'm bullish on the idea of using something like an unrolled binary
search, or an interpolation search in the long term. In the meantime,
we have too many iCache misses. As a datapoint, iCache misses
reportedly dominate the overhead of TPC-C and TPC-E [3]. Nestloop
joins with inner index scans are dominant within those benchmarks.
[1] https://wiki.postgresql.org/wiki/Key_normalization#Using_existing_.22minus_infinity.22_index_tuple_as_a_low_key
[2] https://www.postgresql.org/message-id/CAH2-Wz=mV4dmOaPFicRSyNtv2KinxEOtBwUY5R7fXXOC-OearA@mail.gmail.com
[3] https://openproceedings.org/2013/conf/edbt/TozunPKJA13.pdf --
"6.1.2 Core stalls"
--
Peter Geoghegan