From: | John Naylor <jcnaylor(at)gmail(dot)com> |
---|---|
To: | Robert Haas <robertmhaas(at)gmail(dot)com> |
Cc: | Andres Freund <andres(at)anarazel(dot)de>, Andrew Gierth <andrew(at)tao11(dot)riddles(dot)org(dot)uk>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: reducing the footprint of ScanKeyword (was Re: Large writable variables) |
Date: | 2018-12-26 19:45:47 |
Message-ID: | CAJVSVGXrbjGtqTO5L-YvwYALkgdnZVzaaoWedadCAfrAWsoS=g@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On 12/26/18, Robert Haas <robertmhaas(at)gmail(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Peter Geoghegan | 2018-12-26 19:46:47 | Re: random() (was Re: New GUC to sample log queries) |
Previous Message | Tom Lane | 2018-12-26 19:31:06 | Re: random() (was Re: New GUC to sample log queries) |