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

91–100 of 205 posts

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

#91

Post by batoure »

romwell wrote: post #45

Sometimes databases use hash tables for indexing. This is a natural match for a key-value store. In particular, the following KV stores offer hash table-based indexing: -Berkeley DB [1] -Tokyo Cabinet (and its successor, Kyoto Cabinet) [2] -Bitcask (used in Riak) [3] In many benchmarks, the hash-based systems perform better than tree-based ones. The real advantage of trees, as Berkeley DB manual says: > Btrees are be…

Came here basically to say this you will also find that well architected HBase/Big Table often work this way as well

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

#92

Post by dodobirdlord »

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…

Isn't this problem solved entirely by consistent hashing? Even for a non-distributed hash table, you can "distribute" your table over a collection of fixed-size blocks in memory or on disk. Maximum cost of rehashing is the cost of splitting a block, which can be made arbitrarily small. The cost can even be paid in parallel in non-pathological scenarios with a push-down/write-through splitting mechanism.

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

#93

Post by taneq »

adrianN wrote: post #71
taneq wrote: post #53

Earlier quoted context omitted.

std::unordered_map was only added in C++11, which explains why it's not used in legacy code. Habit, inertia and a desire to keep codebases internally consistent explains why it's less common now.

Also std::unordered_map suffers from a design flaw that forces a poor implementation.

Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.

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

#94

Post by tsimionescu »

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…

> you can't really have a data structure that mains O(1) as it's size increases to infinity.

At the level of abstraction that comexity analysis is usually done, you can. For example, a lookup in an array (a[X]) has O(1) worse-case complexity no matter how large the array is.

Of course, this relies on a few abstractions - that random memory access has uniform cost; and that basic numeric operations have uniform cost regardless of the size of the operands. Of course, in real computers, both of these assumptions are wrong (adding terabyte-size numbers is not as fast as adding byte-sized numbers, large amounts of memory can't usually be stored on random-access hardware etc.), but that does not necessarily impact the usefulness of complexity analysis.

For hash-tables in particular, the worse-case complexity for key lookup depends on some guarantees from the hash algorithm. If you had a magical hash that is unique for any key in your domain, than lookup would be O(1) for a hash table of n elements, as n approaches infinity. Since that is not a good abstraction, we need to model the table using hash functions that can create collisions, and the worse case becomes that O(n) elements collide and get put into the same bucket, giving worse-case complexity of O(n). Adding elements to the hash table is a different operation, same as for the array.

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

#95

Post by abhishekjha »

cellar_door wrote: post #32
gruez wrote: post #29

Earlier quoted context omitted.

Another question: doesn't the O(1) property of hashtables require that there's no collisions? Because of the birthday paradox, you'll need an insanely large hashtable to avoid collisions, and if you don't (or get unlucky), the performance approaches O(n) as the hashtable gets fuller. If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".

Collisions are expected (fill factors are typically typically 2/3 to 3/4). You make every bucket in the table a linked list. And check each value in the list against that for which you are searching.

Java switches to Red-Black after a bucket's linked list's length has grown upto some constant number(8?).

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

#96

Post by mantap »

ummonk wrote: post #81
kodablah wrote: post #54

Earlier quoted context omitted.

You should reach for the best tool for the job instead of giving job-specific reasons for your general choice. Without going into detail explaining how your bullets either don't apply to most uses, prematurely code for a future case that may not exist, dismiss performance, reference other languages as if language implementation is not a factor in the choice, etc... suffice to say they both have their place and in gen…

An ordered map is much better as a default simply because it can do everything that an unordered map can. Choosing to use an unordered map instead is a premature optimization that is nearly always unnecessary.

IMO, premature optimization doesn't apply to cases where you are making general decisions about policy or defaults, otherwise you can get into a "death by a thousand cuts" situation where none of your functions are slow individually but the whole program is slow (i.e. big overheads). To me, premature optimization means don't optimize a specific function unless you know it is slow. I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write.

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

#97

Post by microtonal »

loeg wrote: post #83
dexen wrote: post #36

Earlier quoted context omitted.

Your both points (very valid) could perhaps be wrapped up as: Indexes have lower computational complexity for certain tasks (in particular range queries & sort), but higher constants than typical hashing. Thus indexes make more sense with two-tiered memory; to cache in RAM metadata about data kept in block storage. How that could be put to good use with the L1 cache being much faster than RAM is anyone's guess[1]. --…

Rust's default (edit: ordered) map structure is a memory Btree, fwiw.

What do you mean by this? There is no default map type. The standard library has types such as BTreeMap and HashMap, that pretty much are what it says on the tin.

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

#98

Post by abhishekjha »

taneq wrote: post #93
adrianN wrote: post #71

Earlier quoted context omitted.

Also std::unordered_map suffers from a design flaw that forces a poor implementation.

Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.

Apparently the standard imposes a set of requirements that the implementation must abide by thus making it a lot slower.

[0] : https://www.reddit.com/r/programming/comments/5pwgtn/hash_ma...

[1] : https://stackoverflow.com/questions/42588264/why-is-stdunord...

[2] : https://www.youtube.com/watch?v=ncHmEUmJZf4

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

#99

Post by adrianN »

taneq wrote: post #93
adrianN wrote: post #71

Earlier quoted context omitted.

Also std::unordered_map suffers from a design flaw that forces a poor implementation.

Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.

The interface forces an implementation as a map with linked-list buckets which is suboptimal for many use cases. So people who care about performance usually just implement their own hash map or use a library.

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

#100

Post by Thorrez »

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

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)?

Post reply on HN