Peter Geoghegan

A possibly counterintuitive case where "the key...is expensive to compute" can be when accessing the key just requires following a pointer to something not in cache. It's not the same thing syntactically, but, for example, Postgres sped up collation by packing bytes into integers:

http://pgeoghegan.blogspot.com/2015/01/abbreviated-keys-exploiting-locality-to.html

I've also seen speedups sorting strings by first sorting prefixes of them packed into uint64s (rather than sorting pointer/length references to string data), and in an application where a friend needed to sort a lot of indices into an array, it turned out to greatly speed the sort (by avoiding indirections) to copy the whole array, sort the indices and the copy of the array together, then toss out the copy.

Sorting will be a lot faster on PostgreSQL 9.5:

http://pgeoghegan.blogspot.com/2015/01/abbreviated-keys-exploiting-locality-to.html

http://pgeoghegan.blogspot.com/2015/04/abbreviated-keys-for-numeric-to.html

I wonder whether and to what extent Vitesse benefits from using this technique, which is fairly well known (e.g. it appears in a 1994 paper by Gray -- Alphasort).

As I go into in the second link there, someone reported an order of magnitude increase in sort performance in one case.

For what it's worth, I doubt that this fully accounts for why Vitesse is faster. I don't know that I'd trust my data to it, but I don't think it's snake oil, even if some of the figures shown are arguably a bit misleading.