On Mon, Mar 23, 2015 at 9:46 PM, Peter Geoghegan <p...@heroku.com> wrote: > On Mon, Mar 23, 2015 at 2:41 PM, Andrew Gierth > <and...@tao11.riddles.org.uk> wrote: >> Peter> As I said, I don't really consider that my patch is a rewrite, >> Peter> especially V4, which changes nothing substantive except removing >> Peter> 32-bit support. >> >> Well, that's a hell of an "except". > > > I guess you're right. I'm willing to go with whatever the consensus is > on that question.
So I changed my mind - I now think we should support 32-bit abbreviation. You might wonder why I've changed my mind so suddenly. It's not because I started caring about 32-bit systems overnight. For the record, I still think that they are almost irrelevant. But I've seen a new angle. One of the likely future uses for abbreviated keys is to guide B-Tree index scans. One technique that looks really interesting is storing an abbreviated key in internal pages. I always knew that abbreviation is as useful for index scans as it is for sorting - maybe more so. Reading "Modern B-Tree techniques" [1] again today, I realized that we can store fixed sized abbreviated keys in line items directly. If we stored a 4 byte abbreviated key, we'd pay no storage overhead on 64-bit systems that already lose that to ItemId alignment. We'd only generate abbreviated keys in internal B-Tree pages, during relatively infrequent page splits (internal pages naturally have a very wide spread of values anyway), so that would be a very low cost. Even when abbreviation doesn't work out, we have to visit the line item anyway, and an integer comparison on the same cacheline is effectively free. It would probably work out all the time anyway, owing to the natural spread of items within internal pages. Best of all, most index scans don't even need to look past the itemId array (for internal pages, which are the large majority visited by any given index scan, but a tiny minority of those actually stored), hugely cutting down on the number of cache misses. I could see this making index scans on numeric IndexTuples noticeably faster than even those on int8 IndexTuples. Of course, text is the type that this is really compelling for (perhaps int4 too - perhaps we could automatically get this for types that fit in 4 bytes naturally on 64-bit platforms). I'm not sure that we could do this with text without adopting ICU, which makes firm guarantees about binary sort key stability, so I thought that numeric could be considered a proof of concept for that. [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.219.7269&rep=rep1&type=pdf -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers