Use more efficient hashtable for tidbitmap.c to speed up bitmap scans.

Use the new simplehash.h to speed up tidbitmap.c uses. For bitmap scan
heavy queries speedups of over 100% have been measured. Both lossy and
exact scans benefit, but the wins are bigger for mostly exact scans.

The conversion is mostly trivial, except that tbm_lossify() now restarts
lossifying at the point it previously stopped. Otherwise the hash table
becomes unbalanced because the scan in done in hash-order, leaving the
end of the hashtable more densely filled then the beginning. That caused
performance issues with dynahash as well, but due to the open chaining
they were less pronounced than with the linear adressing from

Reviewed-By: Tomas Vondra
Discussion: <>



Modified Files
src/backend/nodes/tidbitmap.c | 169 ++++++++++++++++++++++++------------------
1 file changed, 97 insertions(+), 72 deletions(-)

Sent via pgsql-committers mailing list (
To make changes to your subscription:

Reply via email to