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

Cases where full scans are better than indexes

jefftk.com

Post reply on HN
Print view View original

171–180 of 226 posts

Re: Cases where full scans are better than indexes

#171

Post by anyfoo »

ignoramous wrote: post #168
eklitzke wrote: post #98

Earlier quoted context omitted.

For small enough tables doing a full scan will be faster than an index. This is also true for regular non-database applications like checking if an item is present in a small collection: it's faster to do a linear scan over a small vector than it is to do a lookup in a hash table or b-tree. With a linear scan (whether it's for data on disk, or a data structure in memory) you don't have to do hashing or branching (exc…

> With a binary search you basically get worst possible case for branch predictor, because if you're searching random values whether you go right/left on each recursion level is basically random. I think folks writing databases know a thing or two about writing faster search and sort algorithms.

I'm not sure what you are trying to say, given the context of what you quoted was. Binary search has optimal worst case runtime complexity, but for small tables it is, on real computers, overall still slower than a linear scan, which effectively has the worst worst case runtime complexity (unless you start to get pathological). This is because the constant in front of the runtime complexity, the one that O-notation explicitly ignores, starts to matter: Branch prediction and cache locality come into play.

What exactly do you mean with "writing faster search and sort algorithms"?

Re: Cases where full scans are better than indexes

#172

Post by anarazel »

anarazel wrote: post #170
wiredfool wrote: post #145

Earlier quoted context omitted.

My recollection in postgres anyway is that low cardinality indexes aren't useful, because it doesn't take into account which side of the 1/99% you're on when determining to use the index. What is useful is to do a partial index on values where foo=small % ,value because then it will use that index when it matches the query, but not when it's in the majority case.

> My recollection in postgres anyway is that low cardinality indexes aren't useful, because it doesn't take into account which side of the 1/99% you're on when determining to use the index. It does take that into account. Demo: =# CREATE TABLE low_cardinality AS SELECT generate_series(-10, 1000000)

Forgot to say: Obviously a partial index is going to be considerably better, performance and size wise.

Re: Cases where full scans are better than indexes

#173

Post by mrits »

paxys wrote: post #129

I don't get it...they are just bragging about writing terrible code? There isn't a single reason given in the article about why a full scan is better than an index other than "I don't need these fancy index things, I'm perfectly happy with my 200ms query time". Well add the index anyway and add an extra 195ms sleep() call if you really want to. It's still better for your hardware and electricity bill.

While I'm not sure why you moved their recently I can see why you wouldn't have noticed how nice it used to be. As I said, it already started the decline a decade ago.

Re: Cases where full scans are better than indexes

#174

Post by josephg »

eklitzke wrote: post #98
pkulak wrote: post #68

Just because the table scan is under some threshold doesn't automatically make it better. If a table scan takes 250ms vs 0.01 for a indexed lookup, you're still gonna have to justify to me why making silicon work that damn hard is worth even the electrical use. Are you inserting and deleting so many rows that maintaining the index is prohibitive? Do you have space concerns, and are not able to keep the index in memor…

For small enough tables doing a full scan will be faster than an index. This is also true for regular non-database applications like checking if an item is present in a small collection: it's faster to do a linear scan over a small vector than it is to do a lookup in a hash table or b-tree. With a linear scan (whether it's for data on disk, or a data structure in memory) you don't have to do hashing or branching (exc…

What do you think the threshold number is where scanning a list will outperform a hash table? 10 items? 100? 1000? For what it’s worth, for small data sets I agree with you. But I think it’s very hard to be calibrated correctly on what small means here.

Re: binary search, the biggest cost to scanning data in a database is loading that data from persistent storage. A few mispredicted branches aren’t going to matter much if it means you can do fewer reads.

Re: Cases where full scans are better than indexes

#175

Post by anyfoo »

pkulak wrote: post #68

Just because the table scan is under some threshold doesn't automatically make it better. If a table scan takes 250ms vs 0.01 for a indexed lookup, you're still gonna have to justify to me why making silicon work that damn hard is worth even the electrical use. Are you inserting and deleting so many rows that maintaining the index is prohibitive? Do you have space concerns, and are not able to keep the index in memor…

> If a table scan takes 250ms vs 0.01 for a indexed lookup

I'm not sure whether the units of that latter number are still ms or now s or whatever, but either way isn't that where you are wrong? On real computers, there are lots of situations where linear access is trivially faster than a "better" data structure with theoretically better runtime complexity.

1000 accesses to a single page for a linear scan are going to be many, many orders of magnitude faster than 5 accesses chasing pointers across 5 pages that have no TLB entry, or excruciatingly worse, that need to be paged in from disk.

This is an extreme (but absolutely not unrealistic!) example for illustration. Slightly more subtle scenarios involving e.g. branch prediction have already been named by eklitzke.

This problem exists across multiple layers, not just close to the CPU like above. (As eklitzke also already mentioned with disk involvement, even if it's an SSD.)

Re: Cases where full scans are better than indexes

#176

Post by ars »

eklitzke wrote: post #98
pkulak wrote: post #68

Just because the table scan is under some threshold doesn't automatically make it better. If a table scan takes 250ms vs 0.01 for a indexed lookup, you're still gonna have to justify to me why making silicon work that damn hard is worth even the electrical use. Are you inserting and deleting so many rows that maintaining the index is prohibitive? Do you have space concerns, and are not able to keep the index in memor…

For small enough tables doing a full scan will be faster than an index. This is also true for regular non-database applications like checking if an item is present in a small collection: it's faster to do a linear scan over a small vector than it is to do a lookup in a hash table or b-tree. With a linear scan (whether it's for data on disk, or a data structure in memory) you don't have to do hashing or branching (exc…

Yes but when the table is so small even if the index is slower it hardly matters because the table is so small.

Or in other words add the index every single time, unless you have so many writes and such a large table that the actual writes slow down the index.

Leaving out an index on a small table never helps anything.

Re: Cases where full scans are better than indexes

#177

Post by Shorel »

josephg wrote: post #174
eklitzke wrote: post #98

Earlier quoted context omitted.

For small enough tables doing a full scan will be faster than an index. This is also true for regular non-database applications like checking if an item is present in a small collection: it's faster to do a linear scan over a small vector than it is to do a lookup in a hash table or b-tree. With a linear scan (whether it's for data on disk, or a data structure in memory) you don't have to do hashing or branching (exc…

What do you think the threshold number is where scanning a list will outperform a hash table? 10 items? 100? 1000? For what it’s worth, for small data sets I agree with you. But I think it’s very hard to be calibrated correctly on what small means here. Re: binary search, the biggest cost to scanning data in a database is loading that data from persistent storage. A few mispredicted branches aren’t going to matter mu…

> But I think it’s very hard to be calibrated correctly on what small means here.

It depends.

If you measure or determine somehow the sizes of the L1-L2-L3 caches in the CPU, the relative speed and size of the main memory, and the relative speed and size of the local storage (in contrast with for example network-remote data), then it is a matter of performing some arithmetic, and just to be on the safe side, some benchmarks.

Any data set that fits into the CPU cache is definitely small, for a particular CPU.

If you want to decide a number that applies to every and all hardware, then it goes from hard to basically impossible.

Re: Cases where full scans are better than indexes

#178

Post by ignoramous »

anyfoo wrote: post #171
ignoramous wrote: post #168

Earlier quoted context omitted.

> With a binary search you basically get worst possible case for branch predictor, because if you're searching random values whether you go right/left on each recursion level is basically random. I think folks writing databases know a thing or two about writing faster search and sort algorithms.

I'm not sure what you are trying to say, given the context of what you quoted was. Binary search has optimal worst case runtime complexity, but for small tables it is, on real computers, overall still slower than a linear scan, which effectively has the worst worst case runtime complexity (unless you start to get pathological). This is because the constant in front of the runtime complexity, the one that O-notation e…

> What exactly do you mean with "writing faster search and sort algorithms"?

- Branchless binary search: https://news.ycombinator.com/item?id=35737862 / https://news.ycombinator.com/item?id=14598098

- Static B-Trees for faster binary search: https://news.ycombinator.com/item?id=30376140

Presumably there's even more literature on the topic.

Re: Cases where full scans are better than indexes

#179

Post by grogers »

mschuster91 wrote: post #95
lazide wrote: post #92

Earlier quoted context omitted.

It’s worth noting that if your DB instance is so heavily loaded that this is a real concern, you already have a huge problem that needs fixing.

AWS is particularly bad with their performance credit system on RDS... and there's to my knowledge no way to tell MySQL to limit index creation IOPS, which means in the worst case you're stuck with a system swamped under load for days and constantly running into IO starvation, if you forget to scale up your cluster beforehand. Even if the cluster is scaled to easily take on your normal workload, indexing may prove to…

You can use gh-ost (or most other online schema change tools) to get around that. You'll still have some necessary increase in write load since you are double-writing that table but you can control the pacing of the data backfill (gh-ost gives even more control as it doesn't use triggers to duplicate writes). It's not quite as simple as just running ALTER TABLE on the master though.

Re: Cases where full scans are better than indexes

#180

Post by jameshart »

jefftk wrote: post #147
jameshart wrote: post #105

Earlier quoted context omitted.

Stealing time from future you also doesn’t pay off. Future you wants to take vacations and change jobs and have family events and sleep and stuff. It doesn’t take much work to do the back of envelope math: How long should these queries take? Less than two seconds? How much slower do they get as record counts increase? 100ms every 250,000 records? Okay, so this will become intolerably slow when the record count hits a…

When building systems we are always making trade-offs between the present and the future. It's only "stealing time from future you" when you make bad trade-off; otherwise it's prioritization. In this case, leaving out an index for full text search meant I didn't need to maintain the software for that index either, which would have been stand-alone at the time I was building this. Possibly this even was a choice that…

Feeling a little bit like you’re applying a motte and Bailey argument here.

The bold claim in the article was that there are many circumstances where adding an index isn’t necessary. Diverse examples were given. These included a MySQL database, where adding an index is no additional maintenance overhead whatsoever (FULLTEXT idx in the table DDL). The implication was that there are many circumstances that affect many people where even cheap and easy to implement indexes were not needed.

Now when challenged you’re retreating to the more defensible position that in the case where you’re querying an ad hoc data structure where you would have to implement your own index that that is often a bad trade off. Or maybe it was a bad tradeoff because this was a small app you were building that you knew you would be the long term maintainer for.

But that’s not what I’m talking about is it, and I don't know all the specific circumstances of your single specific project where this was the right choice, so we’re not going to get anywhere.

Post reply on HN