Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You can beat the binary search

lemire.me

Post reply on HN
Print view View original

171–175 of 175 posts

Re: You can beat the binary search

#171

Post by crazygringo »

10000truths wrote: post #126
skybrian wrote: post #123

Earlier quoted context omitted.

Databases often use table statistics to try to do better at generating query plans. I wonder if they use them to make indexes faster as well?

The cost plan is a crude approximation of the actual query cost. Sometimes, the query planner makes a terrible guess. Your resident DBA won't appreciate being sometimes paged at 3 AM on a Sunday. A good strategy is to freeze the query plan once you have sufficient sample size of data in the involved tables.

Unfortunately, "freezing the query plan" isn't something available in many popular databases. It's not supported by e.g. Postgres, MySQL, or SQLite.

Re: You can beat the binary search

#172

Post by codedokode »

YourDadVPN wrote: post #170
codedokode wrote: post #168

Earlier quoted context omitted.

> I was a bit confused by the if-else chains you have e.g. on line 111 where it looks like you could just use the else branch for every case? The point of "ifs" there is to replace a variable "size" with a constant like 8, 16 so that the compiler can hardcode it in the code and maybe make it more efficient (for example, instead of counting the iterations the compiler can just repeat the instruction 8 times when itera…

Fair point that binary search causes a lot of branch mispredictions. Did you ever measure whether the unrolled linear search with 8 elements outperforms a "rolled" one? Because with instruction level parallelism I wonder how much difference removing 8 mostly easily predicted (in the linear search) branches makes.

I didn't try, but loop contains a branch so there could be misprediction, which doesn't happen with unrolled loop. Also, instruction level parallelism applies to unrolled code as well.

Re: You can beat the binary search

#173

Post by EMPTYCONTOUR »

charleslmunger wrote: post #107
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

I've spent some brainpower on binary search and have not been able to beat this: https://github.com/protocolbuffers/protobuf/blob/44025909eb7... 1. Check for dense list O(1) 2. Check upper bound 3. Constant trip count binary search The constant trip count is great for the branch predictor, and the core loop is pretty tightly optimized for the target hardware, avoiding multiplies. Every attempt to get more clever made…

[dead]

Re: You can beat the binary search

#174

Post by hinkley »

mvelbaum wrote: post #86
hinkley wrote: post #81

Earlier quoted context omitted.

I swear I read an article about treaps but instead of being used to balance the tree, they used the weights to Huffman encode the search depth to reduce the average access time for heterogenous fetch frequencies. I did not bookmark it and about twice a year I go searching for it again. Some say he’s still searching to this day.

https://arxiv.org/abs/2206.12110 ?

'22 feels a bit to recent but maybe. This looks like a good spot though. I'll check the bibliography to see if they acknowledge prior art.

Re: You can beat the binary search

#175

Post by 10000truths »

crazygringo wrote: post #171
10000truths wrote: post #126

Earlier quoted context omitted.

The cost plan is a crude approximation of the actual query cost. Sometimes, the query planner makes a terrible guess. Your resident DBA won't appreciate being sometimes paged at 3 AM on a Sunday. A good strategy is to freeze the query plan once you have sufficient sample size of data in the involved tables.

Unfortunately, "freezing the query plan" isn't something available in many popular databases. It's not supported by e.g. Postgres, MySQL, or SQLite.

Perhaps not every aspect of the query plan can be dictated, but both MySQL and Postgres (with pg_hint_plan) allow you to specify hints that enforce specify join order and scan behavior for the tables in your query, which is where the majority of "unexpected change in query plan" problems will arise. As for SQLite, I'm less familiar with the knobs available for query tuning, but a cursory Google tells me that join order is respected when using CROSS JOIN, and index usage can be forced with INDEXED BY/NOT INDEXED.
Post reply on HN