Why databases use ordered indexes but programming uses hash tables • Hacker News Board

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

#201

Post by School-Cotton » Wed, Dec 11, 2019, 4:10 AM UTC

darawk wrote: post #199

School-Cotton wrote: post #172

Earlier quoted context omitted.

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.

I don't know what to say at this point. Any reputable reference will disagree with you, including the two Stack Overflow links I posted, or even the Wikipedia article on big-O notation, which doesn't say anywhere that it has to do with the worst case of algorithms.

> They are not different functions. They are the same function.

Sure, if you expand the term "function" to include "random variable", which is legitimate to do in some fields of math... but we're talking about deterministic functions from the natural numbers (or real numbers) to the real numbers here. Which is what big-O notation is defined for.

Can you write down the deterministic function from N->R giving the "runtime" of some algorithm? (I mean the actual function, not big-O).

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

#202

Post by andrewflnr » Wed, Dec 11, 2019, 4:16 AM UTC

misterman0 wrote: post #121

geophile wrote: post #68

Earlier quoted context omitted.

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.

Also, JSON and its ilk.

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

#203

Post by namibj » Wed, Dec 11, 2019, 7:29 AM UTC

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.

Ideally, with io_uring(2)/DPDK/SR-IOV-NVMe, you can skip enough syscalls to drop their performance impact below 1%.

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

#204

Post by n3k5 » Wed, Dec 11, 2019, 2:03 PM UTC

tempguy9999 wrote: post #190

91aintprime wrote: post #180

Earlier quoted context omitted.

funny enough, a hash code defines an order on a set

Is it in any sense a useful order though? You can assign any order to any set of objects, but you'd want it to be useful. A hash - the more hash-ey it is, the less the order means AFAICS.

For the purpose of making a tree data structure, all linear orderings would be equally useful. Hashing only provides a partial order, so it's important to choose a hash function that won't assign the same hash to large batches of items.

But it only needs to have this property for hashes of one particular size, whereas a hash map requires a function that behaves well for a variety of hash sizes. So there's an opportunity for using a cheaper hash function.

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

#205

Post by unethical_ban » Wed, Dec 11, 2019, 10:56 PM UTC

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…

Prematurely optimizing for death by a thousand cuts is what you're proposing.