On 12/26/18, Robert Haas <robertmh...@gmail.com> wrote: > I wonder if we could do something really simple like a lookup based on > the first character of the scan keyword. It looks to me like there are > 440 keywords right now, and the most common starting letter is 'c', > which is the first letter of 51 keywords. So dispatching based on the > first letter clips at least 3 steps off the binary search. I don't > know whether that's enough to be worthwhile, but it's probably pretty > simple to implement.
Using radix tree structures for the top couple of node levels is a known technique to optimize tries that need to be more space-efficient at lower levels, so this has precedent. In this case there would be a space trade off of (alphabet size, rounded up) * (size of index to lower boundary + size of index to upper boundary) = 32 * (2 + 2) = 128 bytes which is pretty small compared to what we'll save by offset-based lookup. On average, there'd be 4.1 binary search steps, which is nice. I agree it'd be fairly simple to do, and might raise the bar for doing anything more complex. -John Naylor
