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

101–110 of 205 posts

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

#101

Post by mlyle »

mantap wrote: post #96
ummonk wrote: post #81

Earlier quoted context omitted.

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 optimiza…

On the other hand, if you pick a TreeMap--- odds are it will be a non-issue either way.

If it does show up on your profiles, it's easy to reconsider and say "I don't think I'll ever access this in order, after all..." and change it and see if you see a benefit.

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

#102

Post by yuushi »

garmaine wrote: post #80
dajohnson89 wrote: post #66

Earlier quoted context omitted.

of the data structures you mentioned, which are easier to work with? to implement? I code in Java and I usually use hashmaps as a go to. they're simple and fast ways to store relationships between data.

std::map in C++ is way easier to work with than std::unordered_map (which didn't even exist until C++11).

Define "way easier". The interface, at least for day to day operations, is basically identical.

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

#103

Post by cperciva »

jdsully wrote: post #48
cperciva wrote: post #37

Earlier quoted context omitted.

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.

If huge pages are used then it's very likely the page is cached in the MMU.

In addition to the limited number of cache slots available for superpages (varies depending on cpu), remember that those can be invalidated (again, depending on cpu). If you're ping-ponging processes on a single CPU, you won't necessarily have what you need in the TLB.

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

#104

Post by _greim_ »

dajohnson89 wrote: post #64
d_burfoot wrote: post #40

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…

doesn't this force you to define a comparator for everything though?

As opposed to defining a hash code for everything, yes. Parent asserts that writing obviously-correct comparators is easier.

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

#105

Post by LessDmesg »

Thorrez wrote: post #100
loeg wrote: post #87

Earlier quoted context omitted.

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

malloc() isn't O(1), but allocations in a normal GC are O(1).

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

#106

Post by eloff »

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.

The OP is talking about disk page reads, not virtual memory pages.

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

#107

Post by yuushi »

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.

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 data (this is what boost flat_map uses). All 3 (map, unordered_map, sorted vector) can have their uses, depending on what you are doing with the data.

If you need a better performing hash map, there's always Abseil as well.

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

#108

Post by bnegreve »

taneq wrote: post #53
overgard wrote: post #51

In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”

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.

Developers primarily use sorted maps because the sorted map is the default map type in C++, by name. (I would be different if you had map/sorted_map instead).

The real question, is why C++ designers chose to prioritize sorted maps (RBTrees) over unsorted maps (Hash Maps).

I don't think it's a matter of speed though. I think it's because RBTrees are safer to use. Things can go really wrong with a hashmap if you have a poor hashing function (worst case search is O(n) vs. O(log(n)) for a RBTree)

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

#109

Post by davedx »

cperciva wrote: post #103
jdsully wrote: post #48

Earlier quoted context omitted.

If huge pages are used then it's very likely the page is cached in the MMU.

In addition to the limited number of cache slots available for superpages (varies depending on cpu), remember that those can be invalidated (again, depending on cpu). If you're ping-ponging processes on a single CPU, you won't necessarily have what you need in the TLB.

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

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

#110

Post by loeg »

microtonal wrote: post #97
loeg wrote: post #83

Earlier quoted context omitted.

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.

Ordered map.
Post reply on HN