postgres/postgres

Less hashing, same performance: Building a better Bloom filter

Abstract A standard technique from the hashing literature is to use two hash functions h 1 ( x ) and h 2 ( x ) to simulate additional hash functions of the form g i ( x ) = h 1 ( x ) + i h 2 ( x ). We demonstrate that this technique can be usefully applied to Bloom filters and related data structure...

An Adaptive Hash Join Algorithm for Multiuser Environments.

Serializable isolation for snapshot databases

Many popular database management systems implement a multiversion concurrency control algorithm called snapshot isolation rather than providing full serializability based on locking. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by int...

Novel Table Lookup-Based Algorithms for High-Performance CRC Generation

A framework for designing a family of novel fast cyclic redundancy code (CRC) generation algorithms is presented. Our algorithms can ideally read arbitrarily large amounts of data at a time, while optimizing their memory requirement to meet the constraints of specific computer architectures. In addi...