6 ms·
PostgreSQL can easily store ordered key/value pairs. It’s not the only thing it can do, but it’s still very good at it.
by sfvisser 6y ago
PostgreSQL can easily store ordered key/value pairs.
It’s not the only thing it can do, but it’s still very good at it.
- 082349872349872 6y agoTFA left me clueless as to whether there's anything about an "ordered key-value store" that adding a sequence field to an unordered (more easily parallelised) store doesn't provide.
- rapsey 6y agoAwful data locality however. Random seeks while reading ordered data will give you the worst possible performance.
- j-pb 6y agoIt's all about efficient range reads and seek operations. You can compute set operations pretty efficiently using sorted indices that support a "find next or greater" operation. For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate := next(candidate) on each set, updating the candidate with the next smallest possible value, and adding it to the output set when a candidate was returned by all sets. The algorithm is worst case optimal up to a log factor, and can even be extended to perform generic constraint programming and multiway joins as a subset of that. Fascinatingly it's related to the DPLL algorithm for sat solving. http://erikdemaine.org/papers/SODA2000/ http://erikdemaine.org/papers/SODA2000/ https://arxiv.org/abs/1404.0703 https://arxiv.org/abs/1404.0703 https://arxiv.org/abs/1310.3314 https://arxiv.org/abs/1310.3314 https://arxiv.org/abs/1203.1952 https://arxiv.org/abs/1203.1952 https://arxiv.org/abs/1803.09930 https://arxiv.org/abs/1803.09930
- carterschonwald 6y agoThose join algs you link too are pretty fun. And that next key command/ Api bit is also super handy in writing performant array algorithms.
- wdb 6y agoYeah, I think PostgreSQL is a good first go to database when starting projects. I think its powerful software.