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

21–30 of 205 posts

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

#21

Post by dmurray »

Darmani wrote: post #17
amelius wrote: post #12

Earlier quoted context omitted.

Also, most hash tables are not really O(1). The worst case scenario is more like O(n).

In some senses, no hash tables are O(1). Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason. You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where yo…

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 worse asymptotic performance than you expected, it's because you run out of space in the universe in which to store them.

So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.

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

#22

Post by [deleted] »

michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

[deleted]

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

#23

Post by fyp »

Even if you need range queries when programming, it's rare that you need it for a dynamic dataset. This means you can get better constant factors just by sorting your data and binary searching. You only need trees if you need to insert/delete/update items in the middle.

Most programming tasks work with static datasets because memory is volatile. We are always loading the data from somewhere else and usually just once because reactively updating the in-memory collection is nontrivial to hook up. On the other hand, this is the default for databases.

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

#24

Post by twotwotwo »

Indexes on things that’re correlated with time (ID, timestamp) tend to concentrate recently added data towards the “end” of the table/index, which is a big help when you have years of data but mostly people are asking about the last few weeks.

It gets a couple sentences in the post, but prefix searches are key (ha!): a sorted index on (foo, bar, baz) helps not only searches on all three attributes but also foo=x and bar=y or just foo=x. It can also be useful when you want to look things up by a prefix of an individual column: filter to a given day or month using a timestamp index, or filter to errors reported from client version 3.2.x. As a “covering index” it can somewhat help with queries that limit to foo=x and do something with bar (filter on it, return it, sum it, etc.). Finally, it helps with multiple scenarios for aggregation, not only searching: a timestamp index can let you get a count of orders by day, hour, or second without needing to make another temporary table/index.

Often the crucial thing for keeping a DB humming is not getting the last couple percent out of already-fast operations but making sure you don’t have any disastrous queries, so an index being versatile for many kinds of search is especially valuable.

Related to that last point, databases are trying to prepare for queries that haven’t even been written yet, while when you’re coding some algorithm that involves a hashtable, you already know exactly what lookup you’re going to do a few lines later. That on its own is going to push you towards more flexible types of indexing.

(Crossposted from https://lobste.rs/s/68dgox/, where other folks have some good comments.)

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

#26

Post by travisjungroth »

whack wrote: post #15
michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

> Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are. Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch…

This is why benchmarking can be useful. I’m not sure why in a field where the materials cost of testing an idea is zero it’s done so much less frequently than theorizing.

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

#27

Post by blaisio »

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 this), but this is also not ideal for databases because the associated disk accesses are so expensive, and it requires significantly more disk space.

Many real world implementations just don't rehash unless you ask, which makes them pretty inefficient for most use cases.

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

#28

Post by School-Cotton »

darawk wrote: post #16
michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

Also of note, hash tables (unless they are using perfect hashing) are not O(1). Big O notation refers to the worst case time, and the worst case time for a hash table is when the hash key is non-unique and the desired element needs to be looked up in a table. The relation between N and the complexity of this operation is somewhat implementation / data distribution dependent, but in the true worst case it is O(N) (all…

> 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 times.

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

#29

Post by gruez »

michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

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".

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

#30

Post by fyp »

michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

Looking at the performance graphs of different hash table implementations is the best way to invalidate the idea of "constant time":

https://probablydance.com/2018/05/28/a-new-fast-hash-table-i...

HN submission with related comments: https://news.ycombinator.com/item?id=17177798

Post reply on HN