Why databases use ordered indexes but programming uses hash tables • Hacker News Board

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

#131

Post by HelloNurse » Tue, Dec 10, 2019, 8:39 AM UTC

loeg wrote: post #87

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…

Growing hash tables only takes amortized O(1); you just do two operations per logical operation, which is still O(1). One search term is "incremental resizing." https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing

In practical applications, costs are often not amortized.

If lucky transactions are more than fast enough but unlucky transactions time out because they perform a rebuild it's a defect that cannot be accepted because average performance is good.

Most databases need to take care of worst case performance with techniques that increase complexity and degrade best-case and aggregate performance (e.g. maintaining two hash tables, with lookup accessing both, insertions into the preferred one, and background threads that move records from the old table to the new table).

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

#132

Post by alecco » Tue, Dec 10, 2019, 8:44 AM UTC

geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Relational databases do mostly range queries. (e.g. SELECT a WHERE b > ?). Hash tables suck for that since in general they reshuffle (hash) keys. In tree structures 1m key range access is 1 random lookup and 1m sequential (cache-friendly). In hash tables that becomes 1m random lookups and not cache friendly.

See section IV 4 E, "range queries" in "A comparison of adaptive radix trees and hash tables" (2015)

https://15721.courses.cs.cmu.edu/spring2019/papers/08-oltpin...

Even for the best hash table-based indexing B+Trees win. And combining this with the big cost of resizing (growing) or rehashing a table (rebalancing, i.e. Cuckoo) they are not useful.

Perhaps some adaptive hashing method could take care of this in the future.

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

#133

Post by Thorrez » Tue, Dec 10, 2019, 9:14 AM UTC

LessDmesg wrote: post #105

Thorrez wrote: post #100

Earlier quoted context omitted.

It's amortized O(1) even without any special incremental resizing. I think the goal of incremental resizing is to get closer to actual O(1). But I'm not sure incremental resizing can get to actual O(1). Is the malloc() call for the new memory O(1)? And then after malloc() wouldn't the memory have to be initialized somehow (maybe just 0-initialized)?

malloc() isn't O(1), but allocations in a normal GC are O(1).

Is there some reason that malloc() would be slower asymptotically than a GC? Why couldn't whatever technique is used for the fast GC be used for malloc() as well?

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

#134

Post by senderista » Tue, Dec 10, 2019, 9:22 AM UTC

rklaehn wrote: post #124

kccqzy wrote: post #120

Earlier quoted context omitted.

I agree, but instead I would use the term "path-dependent" for hash tables rather than "non-deterministic" because, after all, unless you salt your hash functions, there is really no randomness anywhere. What you think of as non-deterministic really is deterministic but it is determined by the precise order of insertion. This is sometimes also called memorylessness. Even though tree-based data structures give you an…

> I agree, but instead I would use the term "path-dependent" for hash tables rather than "non-deterministic" because, after all, unless you salt your hash functions, there is really no randomness anywhere. What you think of as non-deterministic really is deterministic but it is determined by the precise order of insertion. This is sometimes also called memorylessness. You are right that non-deterministic is not stric…

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 bidirectional linear probing: https://github.com/senderista/hashtable-benchmarks/blob/mast....

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

#135

Post by notduncansmith » Tue, Dec 10, 2019, 9:32 AM UTC

cperciva wrote: post #37

geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

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.

And that’s assuming you’ve missed several layers of cache between the CPU and main (virtual) memory!

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

#136

Post by senderista » Tue, Dec 10, 2019, 9:35 AM UTC

mercutio2 wrote: post #42

School-Cotton wrote: post #28

Earlier quoted context omitted.

> Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running tim…

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

In colloquial usage among programmers "Big-O" almost always really means Big-Theta.

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

#137

Post by johncolanduoni » Tue, Dec 10, 2019, 9:40 AM UTC

jhanschoo wrote: post #115

dmurray wrote: post #21

Earlier quoted context omitted.

Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation uses 32 bits for the hash function, and can only scale to 4 billion slots. Maybe your implementation of a vector has the same limitation. In general, the reason you'll have trouble trying to store 2^trillion items is not because you chose a data structure with wo…

Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model. I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.

A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.

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

#138

Post by rklaehn » Tue, Dec 10, 2019, 9:43 AM UTC

senderista wrote: post #134

rklaehn wrote: post #124

Earlier quoted context omitted.

> I agree, but instead I would use the term "path-dependent" for hash tables rather than "non-deterministic" because, after all, unless you salt your hash functions, there is really no randomness anywhere. What you think of as non-deterministic really is deterministic but it is determined by the precise order of insertion. This is sometimes also called memorylessness. You are right that non-deterministic is not stric…

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 some unsafe stuff to allow in place updates to prevent allocations.

Not quite ready for prime time yet, but you can see the basic ideas being used in this data structure:

https://docs.rs/range-collections/0.1.0/range_collections/ra...

You could do a deterministic hash table by using a cryptographic hash function like sha256 and then use a binary trie of the hashes. No need to deal with collisions as far as we know. The hash is expensive, but if you need the hash for something else anyway, this is pretty neat...

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

#139

Post by AstralStorm » Tue, Dec 10, 2019, 9:48 AM UTC

cperciva wrote: post #37

geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

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.

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

#140

Post by senderista » Tue, Dec 10, 2019, 9:54 AM UTC

adrianmonk wrote: post #128

I was going to guess that a reason databases prefer ordered tables is that, for two large tables (lots bigger than RAM), equijoins are easy to do efficiently: just do a merge. I wasn't aware of any obvious way to do the same with two on-disk hash tables. But it appears some databases (MySQL?) do this. So now my question is how. Use the same hash function for the two tables to be joined, then loop over buckets, matchi…

There are a couple of common hash join algorithms that databases use: symmetric hash join and asymmetric hash join. The latter is actually simpler. Take the first (smaller) table and read it into a hash table (assuming it can fit in memory for simplicity's sake). Then stream all rows from the second table, looking up the join key for each input row in the hash table containing the first table. If you get a match, emit an output row. For symmetric hash join, you stream both input tables simultaneously: for each input row, you first check the other input table's hash table for a match (emitting an output row for each match), and then add the input row to that input table's hash table. (When you've exhausted one of the input tables, you can actually delete the other input table's hash table from memory, since you won't produce any more matches from it.) Again I've oversimplified in assuming that the input tables fit in memory, but the algorithms for spilling to disk are pretty simple (basically hash the inputs on the join key into disk partitions which do fit into memory and build hash tables from each partition).

Parallel databases also use hash join for performing distributed joins: each node hashes its inputs on the join key to distribute onto the other nodes, so that all inputs with the same join key end up on the same node. Then you can apply one of the hash join algorithms above.