Re: pgsql: Use perfect hashing, instead of binary search, for keyword looku

On Wed, Jan 9, 2019 at 7:48 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Use perfect hashing, instead of binary search, for keyword lookup.
>
> We've been speculating for a long time that hash-based keyword lookup
> ought to be faster than binary search, but up to now we hadn't found
> a suitable tool for generating the hash function. Joerg Sonnenberger
> provided the inspiration, and sample code, to show us that rolling our
> own generator wasn't a ridiculous idea. Hence, do that.
>
> The method used here requires a lookup table of approximately 4 bytes
> per keyword, but that's less than what we saved in the predecessor commit
> afb0d0712, so it's not a big problem. The time savings is indeed
> significant: preliminary testing suggests that the total time for raw
> parsing (flex + bison phases) drops by ~20%.
>
> Patch by me, but it owes its existence to Joerg Sonnenberger;
> thanks also to John Naylor for review.

Wow. That is a VERY significant improvement.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company