Re: pgsql: Use perfect hashing, instead of binary search, for keyword looku - Mailing list pgsql-hackers

From Robert Haas
Subject Re: pgsql: Use perfect hashing, instead of binary search, for keyword looku
Date
Msg-id CA+TgmoaSku2c9JQf2fLMJEcFwQb+FnR+NkNaSu=fR4kqHohwqg@mail.gmail.com
Whole thread Raw
List pgsql-hackers
On Wed, Jan 9, 2019 at 7:48 PM Tom Lane <tgl@sss.pgh.pa.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


pgsql-hackers by date:

Previous
From: Michael Paquier
Date:
Subject: Re: BTW, have we got a commitfest manager for the January CF?
Next
From: Thomas Munro
Date:
Subject: Re: Early WIP/PoC for inlining CTEs