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

191–200 of 205 posts

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

#191

Post by adrianmonk »

senderista wrote: post #140
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, emi…

Since the case where the smaller table fits in RAM is easy and obvious, it's the other case that I'm interested in.

It sounds like you might be saying when two large hash-based tables need to be joined, you're basically starting from scratch in that you're not taking advantage of the existing hash data structure. (At least that's how I interpret "build hash tables", in contrast to somehow using what already exists on disk.)

This sounds pretty slow to me compared to a merge join of ordered lists. There seems to be a lot of I/O (including writes, temp files, and a few passes) whereas with a merge join it's just reads and they're more or less sequential I/O.

So this would be a reason for databases to lean toward ordered storage. But only if disk-based hash joins are as slow as I think they are, which is the part I'm not sure about.

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

#192

Post by halayli »

senderista wrote: post #142
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 fi…

correct. There are many parts of the db planner that checks if the output is sorted to take a more optimal path.

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

#193

Post by jdsully »

cperciva wrote: post #116
davedx wrote: post #109

Earlier quoted context omitted.

> If you're ping-ponging processes on a single CPU, you won't necessarily have what you need in the TLB. Is that really likely on a production database server?

Depends on the design. At a minimum you're ping-ponging between userland and kernel; but you might also be bouncing between a transport layer unwrapper, an authentication front-end, the database core, and a storage back-end.

Spectre may have changed things, but for a long time a user->kernel switch didn't imply a full TLB flush.

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

#194

Post by senderista »

adrianmonk wrote: post #191
senderista wrote: post #140

Earlier quoted context omitted.

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, emi…

Since the case where the smaller table fits in RAM is easy and obvious, it's the other case that I'm interested in. It sounds like you might be saying when two large hash-based tables need to be joined, you're basically starting from scratch in that you're not taking advantage of the existing hash data structure. (At least that's how I interpret "build hash tables", in contrast to somehow using what already exists on…

It might not be clear that symmetric hash join is a streaming, non-blocking operator (i.e., it can start producing results immediately without waiting for a hash table to be built). Unlike merge join, though, it requires all input rows to be kept in memory (at least until the other table is exhausted).

I suspect query optimizers haven’t taken hash indexes into account for joins because they’re so rare in practice, but it’s probably worth considering.

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

#195

Post by geophile »

mrfusion wrote: post #163
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…

Why can’t hash tables shrink and grow gracefully?

They can. See linear hashing and extensible hashing.

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

#196

Post by geophile »

jameshart wrote: post #165
mrfusion wrote: post #163

Earlier quoted context omitted.

Why can’t hash tables shrink and grow gracefully?

Because items are placed into buckets based on their hash, and as you add or remove buckets you need to redistribute items. I guess it depends what your definition is of ‘graceful’.

A b-tree grows and shrinks gracefully because each update modifies O(log n) pages. And the base of the logarithm is pretty big.

A typical hash table is not graceful in this way, because while each insert is O(1), you occasionally need to rehash everything into a bigger table, and that is O(n). As I noted above, linear and extensible hashing avoid this problem. An insert that forces a reorg just reorgs one bucket.

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

#197

Post by geophile »

alecco wrote: post #132
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://1…

I don't think this is correct (about mostly range queries). Scan the code base of any application, and I predict you will see 90%+ queries not involving an inequality. That is for OLTP. For analytics, the answer might be different.

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

#198

Post by anchpop »

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…

Yes, rehashing is very frustrating, especially because the hash tables default to most languages have that issue (i.e. std::unordered_map). It means that you may need 3x more available memory than what you actually want to store, because when the hash table resizes it has to allocate the size of the hash table twice over, while keeping the original hash table in memory.

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

#199

Post by darawk »

School-Cotton wrote: post #172
darawk wrote: post #126

Earlier quoted context omitted.

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.

No, you still don't understand. The worst-case runtime and the average-case runtime are different functions. There's no one "whole function" that both are part of.

They are not different functions. They are the same function. The average case is a special case of the general function in which some of the terms collapse.

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

#200

Post by darawk »

ouid wrote: post #178
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.

You're wrong about this. g in O(f) is defined as: There exists c, m such that for all n > m , c*f(n)>g(n). Big O notation doesn't care about algorithms or worst cases.

No, it doesn't care about worst cases. But the asymptotics of the generalized function of the runtime by necessity are it's worst case.
Post reply on HN