3 ms·

Hash indexes have other benefits than just algorithmic complexity too: traversing and updating tree structures requires a lot of pointer chasing, so in cases wh

Hash indexes have other benefits than just algorithmic complexity too: traversing and updating tree structures requires a lot of pointer chasing, so in cases where your btree index might not fit well in a reasonable level of cache (L3 etc), then this means paging stuff in and out of memory a lot, which can get very expensive very quick. And also with updates to hash tables (e.g. transactional workloads), they're very quick, versus btree updates require traversing the tree structure.

martincmartin 10y ago
Hash table updates are quick until you have to rehash. Rehashing can be done in the background, but then you had added code complexity, you'll be doing significantly more I/O during the rehashing (did you think about rehashing when sizing your machines?) and in pathological cases, you can run out of hash table space before the resize is complete. Now what?
- makmanalp 10y ago
  So this is a great point that I forgot about. Yes, it's a problem for sure, but definitely not unaddressable. The databases community has been thinking about hashing schemes that address this issue since the 80s, like linear hashing, extendible hashing and consistent hashing. The trick is often around amortizing the cost of rehashing over insertions (no background tasks needed!), or somehow minimizing the amount of remapping and rehashing that needs to be done by using clever positioning. So yeah, like anything, it's a tradeoff and not a cure-all, but it can be done quite well.
- infogulch 10y ago
  Rehashing can be incremental. 1: Allocate a new table of size at least 2X. 2: All accesses to the table hit both the old and new tables. 3: Inserts only go in new. 4: Any change (insert, update, delete) also moves 2 other elements. You can prevent a O(n) rescan at 4 by keeping a single persistent cursor that scans through the old table from top to bottom. There, still O(1) throughout (C may go up by 2-3 but that's still small). And only uses 1.5x memory. Not saying that's what postgres does here (it uses WAL, so probably not exactly).
- neilc 10y ago
  Postgres hash indexes use linear hashing, which effectively means that rehashing/expansion is done incrementally: https://en.wikipedia.org/wiki/Linear_hashing https://en.wikipedia.org/wiki/Linear_hashing

martincmartin 10y ago

Hash table updates are quick until you have to rehash. Rehashing can be done in the background, but then you had added code complexity, you'll be doing significantly more I/O during the rehashing (did you think about rehashing when sizing your machines?) and in pathological cases, you can run out of hash table space before the resize is complete. Now what?

makmanalp 10y ago
So this is a great point that I forgot about. Yes, it's a problem for sure, but definitely not unaddressable. The databases community has been thinking about hashing schemes that address this issue since the 80s, like linear hashing, extendible hashing and consistent hashing. The trick is often around amortizing the cost of rehashing over insertions (no background tasks needed!), or somehow minimizing the amount of remapping and rehashing that needs to be done by using clever positioning. So yeah, like anything, it's a tradeoff and not a cure-all, but it can be done quite well.
infogulch 10y ago
Rehashing can be incremental. 1: Allocate a new table of size at least 2X. 2: All accesses to the table hit both the old and new tables. 3: Inserts only go in new. 4: Any change (insert, update, delete) also moves 2 other elements. You can prevent a O(n) rescan at 4 by keeping a single persistent cursor that scans through the old table from top to bottom. There, still O(1) throughout (C may go up by 2-3 but that's still small). And only uses 1.5x memory. Not saying that's what postgres does here (it uses WAL, so probably not exactly).
neilc 10y ago
Postgres hash indexes use linear hashing, which effectively means that rehashing/expansion is done incrementally: https://en.wikipedia.org/wiki/Linear_hashing https://en.wikipedia.org/wiki/Linear_hashing