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

121–130 of 205 posts

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

#121

Post by misterman0 »

geophile wrote: post #68
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…

No. This discussion is about algorithmic complexity, typically counting comparisons. And of course, it ignores constants. If we're counting page accesses, we care very much about the constants. And furthermore, a "multi-level hash table" is a tree, except an unordered one. What a useless beast!

>> What a useless beast!

Mostly but not entirely. There are cases where you need a tree but you don't care about order, e.g. when order depends on a state that is unknown at time of writing or when all you want to encode are relationships.

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

#122

Post by kccqzy »

loeg wrote: post #88
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…

Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.

Cache locality issues can be fixed by using a good allocator (or a good compacting GC).

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

#123

Post by adrianN »

yuushi wrote: post #107
adrianN wrote: post #71

Earlier quoted context omitted.

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

Depending on what you required, it can still be significantly faster than std::map. Any tree-based data structure is going to play havoc with cache. Also, it will perform an allocation for every single node inserted, which can become rather expensive (unless you're using some customized allocator for this). Honestly, sorted vectors can often be a good replacement, depending on the workload, if you must have ordered d…

Unfortunately unordered_map also requires lots and lots of allocations, because it's forced to use linked-list buckets.

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

#124

Post by rklaehn »

kccqzy wrote: post #120
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…

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 strictly correct for non-salted hash functions. That makes it even more annoying, since it is deterministic enough that you might accidentally rely on the order. It is close enough to nondeterministic since iteration order can change when the hash function changes, but also when some minor internal parameter of the hashtable changes.

> Even though tree-based data structures give you an iteration order that is predictable and useful, the structure itself is still not fully memoryless. For example in a red-black tree if you insert an element smaller than all preexisting elements and then immediately delete the minimum, the tree could be different.

Yes, I am aware and a very big fan of data structures that are actually fully memoryless, such as all kinds of binary tries, radix trees, or just wrapped sorted arrays. The latter are totally underrated, since they have very compact in memory representation (just the elements, single piece of heap) and have very competitive lookup performance.

They of course totally suck when you want to do random single element updates, but then just use something else...

I am going to release an entire collections library based on sorted arrays for rust over Christmas...

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

#125

Post by rocqua »

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…

Big O can b the upper bound can be for the amortized worst case though.

The other notations (small o and omega) are about scaling (small o doesn't allow constant factors) and pinching (omega means there are two constant factors, one of which forms a lower bound, and the other an upper bound.

True, the word amortized (i.e. average) is left out here, which still makes people's usage imprecise. But there is a decent argument that amortized is more meaningful than worst-case. Because amortized gives expected throughput and latency, whereas worst-case says very little about throughput and only informs you on the 99th percentile of latency.

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

#126

Post by darawk »

School-Cotton wrote: post #86
darawk wrote: post #62

Earlier quoted context omitted.

When referring to the O() of a particular algorithm without further specification, upper bound is what is meant. When discussing the asymptotics of quicksort you say that it is O(n log(n)) in the average case, not that it is O(n log(n)) in general.

> upper bound is what is meant I tried to make this clear in my comment - (asymptotic) "upper bound" is a concept applicable to any function from N to R. So do you mean the upper bound of the worst case, the upper bound of the average case, the upper bound of the best case, the upper bound of the worst case memory usage, the upper bound of the median price of eggs in China on the n th day since 1970, or something els…

Ya, I just mean that without further qualification, it's the upper bound of the whole function that's being referred to, which is equivalent to the upper bound of the worst case.

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

#128

Post by adrianmonk »

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, matching corresponding buckets between tables? And then what, treat those subsets similar to a join of two unsorted tables? I guess that's okay as long as each of your hash buckets only has very few things in it. Is there a better way?

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

#129

Post by CoolGuySteve »

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.

But the point remains, walking the cache hierarchy once for a hash table is faster than walking it log times for a Btree.

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

#130

Post by kodablah »

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.

Premature optimization concerns effort. We do a lot of things when writing code that could be considered premature optimization by your vague definition. By this definition too, staying in Java land, I should probably not instantiate my ArrayList or HashMap with a capacity even if I know it...technically premature optimization.

All else equal wrt simplicity, choose the highest performing option that contains the features you need. Dogmatic premature optimization rules are unhelpful. We can apply reasonable thinking, and we should.

Post reply on HN