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

171–180 of 205 posts

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

#171

Post by JadeNB »

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…

> I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write.

I think that premature optimisation applies not only to ease of writing, but even more to ease of debugging.

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

#172

Post by School-Cotton »

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

Earlier quoted context omitted.

> upper bound is what is meant I tried to make this clear in my comment - (asymptotic) "upper bound" is a concept applicable to any function from N to R. So do you mean the upper bound of the worst case, the upper bound of the average case, the upper bound of the best case, the upper bound of the worst case memory usage, the upper bound of the median price of eggs in China on the n th day since 1970, or something els…

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.

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

#173

Post by School-Cotton »

senderista wrote: post #136
mercutio2 wrote: post #42

Earlier quoted context omitted.

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

In colloquial usage among programmers "Big-O" almost always really means Big-Theta.

This is true, but it's not related to what we're talking about in this thread.

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

#174

Post by narnianal »

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…

> In a database system, the concern was traditionally to minimize page accesses

Is it really about memory access or disk loads?

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

#175

Post by narnianal »

ithkuil wrote: post #168
cesarb wrote: post #167

Earlier quoted context omitted.

Yes, and each level of the tree has the physical address of the next level, so no TLB lookup is necessary (the top of the tree, in the TTBRn or equivalent registers, is also a physical address).

oh yeah, I totally misread the comment: a page fetch is required, but that has nothing to do with the TLB indeed

what's the difference? "page fetch" is not really something that can be googled on the web.

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

#176

Post by naasking »

kodablah wrote: post #130
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.

Premature optimization concerns effort. We do a lot of things when writing code that could be considered premature optimization by your vague definition. By this definition too, staying in Java land, I should probably not instantiate my ArrayList or HashMap with a capacity even if I know it...technically premature optimization. All else equal wrt simplicity, choose the highest performing option that contains the feat…

> Premature optimization concerns effort

And the OP is correct that writing a correct comparison function needed for an ordered map is easier than writing a correct hash function that is properly distributed. So the ordered map is lower effort for that reason alone, although the other properties the OP lists also produce valid reductions of effort.

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

#177

Post by kyrieeschaton »

Most extant relational databases were originally designed pre-internet as a way to store and batch-process business records, rather than optimizing for things like single-record latency.

For the batch processing use case, you usually want to be able to do range queries with the interior nodes of the tree in memory and the actual data ending up resident on disk.

For the single-record lookup case (ie serving a user's data to them via a webpage) something like linear hashing actually does have better performance characteristics, although trees are usually good enough.

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

#178

Post by ouid »

darawk wrote: post #62
School-Cotton wrote: post #44

Earlier quoted context omitted.

Yes. The upper bound of some function. That function is not necessarily the worst-case runtime. Best-case, average-case, and worst-case can all have upper bounds. If the best case runtime as a function of data size is n/2, average case is n^2 + 5x, and worst case is e^n + 5n^2, these functions are asymptotically upper bounded by n, 2n^2, and 2e^n respectively, so they are big-O (incidentally they are also big-Omega a…

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.

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

#179

Post by travisjungroth »

naniwaduni wrote: post #55
travisjungroth wrote: post #26

Earlier quoted context omitted.

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.

The real costs of testing are clearly nonzero. If they were zero, the testing would already be done.

Real costs are certainly more than zero, but it’s almost entirely time. “Materials cost” is what I rounded off to zero. Like if you want to benchmark an idea in aviation, you’re going to have to burn some fuel.

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

#180

Post by 91aintprime »

_greim_ wrote: post #104
dajohnson89 wrote: post #64

Earlier quoted context omitted.

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.

funny enough, a hash code defines an order on a set
Post reply on HN