Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why databases use ordered indexes but programming uses hash tables

evanjones.ca

Post reply on HN
Print view View original

141–150 of 205 posts

Re: Why databases use ordered indexes but programming uses hash tables

#141

Post by senderista »

blaisio wrote: post #27

One major issue with disk based hash tables is rehashing. Actually, in-memory hash tables have the same problem, but most people don't notice it. Imagine your database suddenly duplicating itself because you inserted one row and suddenly overloaded a bucket. Some hash tables that are designed to minimize the potential for DDOS attacks and improve the amortization of work use gradual rehashing (Go's hash table does th…

That doesn't happen in databases. The standard incremental hashing algorithms (linear and extendible hashing) were devised for databases. Both of these algorithms split only one bucket at a time and thus avoid large allocations.

Re: Why databases use ordered indexes but programming uses hash tables

#142

Post by senderista »

halayli wrote: post #43

I believe it's more due to the fact that sorting, and less/greater than operators come up way more often in databases and using an ordered index makes a much better use case. And the other reason is MVCC. It's easy to maintain multiple snapshots of a b-tree index and swap a root's ptr to point to a new sub-tree.

Sorting in a database makes sense even when you never use ORDER BY. You can do streaming joins/unions, and implement streaming, non-blocking aggregation operators (because you know when you've seen the last row for a grouping key, so you can output the result for that group immediately and evict its state from memory). Query plans will sometimes sort inputs (or intermediate results) for these reasons even when the final output is unordered; this is known as "interesting orders".

Re: Why databases use ordered indexes but programming uses hash tables

#143

Post by lichtenberger »

For densely packed IDs (32 or 64 bit integers...) I think it's even faster to use a keyed trie structure, as it can use fast bit-shifting operations in contrast to using standard B+-trees.

Also, this can be used as a persistent, on-disk / flash drive data structure or as a hash array mapped trie for HashMap implementations in-memory (Scala or Closure for instance).

For a persistent (both in the sense of functional programming as well as storing on non-volatile disk), this is for instance implemented in SirixDB (https://sirix.io), a temporal data store prototype I'm maintaining and developing :-)

Re: Why databases use ordered indexes but programming uses hash tables

#144

Post by garmaine »

yuushi wrote: post #102
garmaine wrote: post #80

Earlier quoted context omitted.

std::map in C++ is way easier to work with than std::unordered_map (which didn't even exist until C++11).

Define "way easier". The interface, at least for day to day operations, is basically identical.

Supports more features like ordered traversal, generally faster in most cases (yup!), consistent api cost, doesn’t invalidate iterators on certain operations like moving between maps. That’s just off the top of my head.

Re: Why databases use ordered indexes but programming uses hash tables

#145

Post by lichtenberger »

rklaehn wrote: post #117

Databases use hashes all the time, also ordered indexes are very frequently used in programming (e.g. C++ stl). I think ordered indexes are a good default for use in programming languages. They are deterministic and do not have strange corner cases that can be exploited. E.g. the order when iterating over elements in a hashtable is pretty much random, whereas the order of elements in an ordered tree based data struct…

You can also implement a hash map as a tree ;-)

Re: Why databases use ordered indexes but programming uses hash tables

#146

Post by senderista »

rklaehn wrote: post #138
senderista wrote: post #134

Earlier quoted context omitted.

If you like sorted arrays and Rust, you might want to take a look at my sorted-vec crate, which has O(sqrt(N)) insertions and deletions: https://github.com/senderista/sorted-vec . In my tests it takes less than half the memory of BTreeSet. PS: It isn't difficult to devise hash tables with path-independent iteration order. You can simply order the keys by their hash code values. See e.g., my implementation of bidirect…

Yes, saw that one. Neat. My stuff is even simpler. It is just a flat array in memory and should just not be used when you want random single element inserts or deletions. But I find that rather uncommon anyway in many use cases. I made sure that building a new collection from an iterator is fast. What I do use is a minimum comparison sort that makes very common cases very fast in terms of number of comparisons, and s…

I have played with hash tries in the past for determinism/dynamism compared to hash tables. I think they're an excellent choice for integer sets, where you can use a reversible hash function to losslessly randomize the elements (I use the same idea in the integer hash table I linked above). If I didn't need graceful resizing, though, I would use either Cleary hash tables or bucketized cuckoo tables for this application.

Re: Why databases use ordered indexes but programming uses hash tables

#147

Post by ajuc »

joe_the_user wrote: post #47
cwalv wrote: post #34

Earlier quoted context omitted.

Didn't the article address 1) with this?: > Another difference is that hash tables only provide average constant time accesses. Bad behaviour can be caused by hash collisions, either unintentional or malicious, but a bigger issue is rehashing. Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table. The impact of this can be reduced by using multi-le…

"Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table." This my impression and it seems like it implies that the "hash table has O(1) access" is bullshit taken as a general formulation. The situation is essentially, hash tables can have "O(1) access" time at a certain size and if tuned for that size. BUT that seems an abuse of big-O notation, whic…

> that seems an abuse of big-O notation

Formally it's amortized O(1) time and pessimistic O(n) time.

It's not abuse - many algorithms and data structures have different performance in average and worst case - for example quicksort is O(n log n) but in worst case it's O(n^2). People just ignore the worst case unless worst-case guarantees are especially important for their system.

Re: Why databases use ordered indexes but programming uses hash tables

#149

Post by rklaehn »

senderista wrote: post #146
rklaehn wrote: post #138

Earlier quoted context omitted.

Yes, saw that one. Neat. My stuff is even simpler. It is just a flat array in memory and should just not be used when you want random single element inserts or deletions. But I find that rather uncommon anyway in many use cases. I made sure that building a new collection from an iterator is fast. What I do use is a minimum comparison sort that makes very common cases very fast in terms of number of comparisons, and s…

I have played with hash tries in the past for determinism/dynamism compared to hash tables. I think they're an excellent choice for integer sets, where you can use a reversible hash function to losslessly randomize the elements (I use the same idea in the integer hash table I linked above). If I didn't need graceful resizing, though, I would use either Cleary hash tables or bucketized cuckoo tables for this applicati…

The hash set and hash map for scala are actually based on hash tries, but with a non-cryptographic hash, so collisions still need to be handled.

I wrote efficient set operations for scala.collection.immutable.HashSet once. Lots of bit-twiddling, which is not as fun on the JVM compared to rust...

Re: Why databases use ordered indexes but programming uses hash tables

#150

Post by cperciva »

AstralStorm wrote: post #139
cperciva wrote: post #37

Earlier quoted context omitted.

On modern hardware a key lookup in a hash table isn't necessarily a single page read! Sure, it's a single virtual memory access, but if that page isn't in your TLB you need to read the page table... and if the page containing that part of the page table isn't in the TLB you need to read that page... On modern hardware, every memory access looks very much like a B-tree lookup.

TLB hierarchy is not a B-tree, it is a trie in all of the CPUs. Very different layout (not balanced and also hard sized), much faster on happy path. Making a 48-bit B-tree would have a bit of a memory problem making TLB huge. And then CPU cache is an array. Single virtual memory access is bound to be a single physical as well, with minor exceptions for NUMA nodes being crossed.

There's a reason I said "looks very much like" rather than "is". ;-)
Post reply on HN