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

31–40 of 205 posts

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

#31

Post by kgwxd »

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…

I've seen it happen in Azure Blob Storage when a container hit about 10 million files, it took 2 hours.

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

#32

Post by cellar_door »

gruez wrote: post #29
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".

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.

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

#33

Post by asdfasgasdgasdg »

This isn't a bad article, but I would be interested in seeing a follow-up where, instead of guessing, the author asks some database professionals. They are out there! We don't have to reinvent from first principles. I would guess this question could be asked and answered by known authorities on e.g. the PostgreSQL mailing lists.

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

#34

Post by cwalv »

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…

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-level hash tables, but it still causes some unpredictability. Trees, on the other hand, have worst case performance of O(log n).

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

#35

Post by dplavery92 »

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.

This, I believe, is the exactly the behavior the parent commenting was describing (and bemoaning.) If you you have to check against every term in a linked list (an operation proportional to the length of the list), then your hash table ceases to be constant-time once you get collisions. In that case, if you have a hash table of fixed size, but arbitrarily increase the number of entries in the table, then the look-up time tends as O(n).

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

#36

Post by dexen »

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…

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

--

[1] without guessing, we already know a small interpreter that fits in L1 can be blazing fast.

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

#37

Post by cperciva »

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.

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

#38

Post by zadokshi »

jamesfmilne wrote: post #14
redcalx wrote: post #5

For one, a database may receive a query such as "WHERE x >=10 AND x <=100". I.e. having an ordered index is useful for accessing ranges, whereas a hash lookup is always just for a single entry. The question then becomes - why are lookups in RAM more likely to be single lookups rather than ranges (and stats on ranges)? Partly at least because DBs provide a query language that make range based queries easy to do, and j…

Everything is driven by the business case. Is there a business case to optimise for range queries? If so, optimise for that. Is there a business case for individual record queries? Then optimise for that. Is there a case for both? Then optimise for that. The biggest lie of the 21st century is convincing JavaScript/Ruby/Python/Clojure/whatever programmers that web development is something sexier/holier/worthier than b…

Oracle forms vs modern web development is a little Off topic but I’ll bite.

Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product?

Oracle forms will get you 80% of the way there, and the final 20% will be impossible.

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

#39

Post by [deleted] »

asdfasgasdgasdg wrote: post #33

This isn't a bad article, but I would be interested in seeing a follow-up where, instead of guessing, the author asks some database professionals. They are out there! We don't have to reinvent from first principles. I would guess this question could be asked and answered by known authorities on e.g. the PostgreSQL mailing lists.

[deleted]

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

#40

Post by d_burfoot »

As a programmer, I always use an ordered map (Java TreeMap) in preference to hash tables. My reasons:

- It is much easier to write a transparently correct comparison method for a new object that I want to use as a key. With hash tables you need to worry that your hash function might not be properly distributed.

- With hash tables you have to worry that your language's under-the-hood resize/reallocate algorithm works well, or you need to make sure you choose the capacity and load factor numbers correctly. Even if things work as expected, you might end up paying a penalty because, for example, the array backing the hashtable was auto-resized to 128 million elements when you only need 70 million.

- Java TreeMap has lots of cool utility methods like pollFirstEntry (pull off the first K/V pair), higherMap (view of map that only includes pairs with higher key), etc.

- TreeMap key traversal is deterministic!! The worst bug I encountered in years of programming work was caused by non-determinism in HashMap traversal (you could blame Java's implementation here, I suppose).

- The O(1) vs O(log N) performance difference is minor to the point of being undetectable in every case I've ever encountered.

- When you do something with the data in the map, you often want to sort by key anyway: might as well have the sort taken care of by the data structure.

Post reply on HN