Hi, On 2021-04-26 22:44:13 +0300, Yura Sokolov wrote: > Even for Robin Hood hashing 0.9 fill factor is too high. It leads to too > much movements on insertion/deletion and longer average collision chain.
That's true for modification heavy cases - but most hash tables in PG, including the smgr one, are quite read heavy. For workloads where there's a lot of smgr activity, the other overheads in relation creation/drop handling are magnitudes more expensive than the collision handling. Note that simplehash.h also grows when the distance gets too big and when there are too many elements to move, not just based on the fill factor. I kinda wish we had a chained hashtable implementation with the same interface as simplehash. It's very use-case dependent which approach is better, and right now we might be forcing some users to choose linear probing because simplehash.h is still faster than dynahash, even though chaining would actually be more appropriate. > Note that Robin Hood doesn't optimize average case. Right. > See discussion on Rust hash table fill factor when it were Robin Hood: > https://github.com/rust-lang/rust/issues/38003 The first sentence actually confirms my point above, about it being a question of read vs write heavy. Greetings, Andres Freund