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

161–170 of 226 posts

Re: Cases where full scans are better than indexes

#161

Post by tomnipotent »

hinkley wrote: post #141
tomnipotent wrote: post #117

Earlier quoted context omitted.

Every major RDBMS requires an index for both constraints.

FK constraints however are a pretty common gotcha. You have a table that allows deletes, and every table that has a column pointing to that table gets scanned on each delete operation. So you have to add an index on that column, or start talking about tombstoning data instead of deleting it, but in which case you may still need the FK index to search out references to an old row to replace with a new one.

An FK also adds the burden of keeping a copy of each related row during the lifespan of a transaction. This means small-but-frequently-updated tables that are joined to a lot can be a source of unexpected headaches.

Re: Cases where full scans are better than indexes

#162

Post by Aachen »

Moral of the post: don't do premature optimization. Common adage but it's a good reminder and example of it.

Aside from one case where OP argued that the queries were so rare compared to the data updates that maintaining the index is more expensive. Which is also pretty classic when you're taught about indexes.

What I recently learned the hard way about indexes is that they're slow when you have to read "large" chunks of a table to find an answer, in my case computing a median for an area. I'm indexing geospatial data and Europe+NA are overrepresented. When you view an area the size of ~Germany, the query would take 20 minutes and compute the median over ~3% of all records whereas a full table scan (whole world) took something like 40 seconds (with the median being computed over the same 3%, it would just evaluate the WHERE clause against every row instead of finding rows to include via the index). That's the power of a sequential read as compared to reading an Rtree. I haven't had such bad experiences with Btree indexes, not sure if that would behave just as badly. On the other hand, if you ask for an area the size of Amsterdam, the index is normal fast, and for <50 rows it's basically instant whereas the full table scan would still take the same 40 seconds.

Re: Cases where full scans are better than indexes

#164

Post by iLoveOncall »

Aachen wrote: post #162

Moral of the post: don't do premature optimization. Common adage but it's a good reminder and example of it. Aside from one case where OP argued that the queries were so rare compared to the data updates that maintaining the index is more expensive. Which is also pretty classic when you're taught about indexes. What I recently learned the hard way about indexes is that they're slow when you have to read "large" chunk…

Adding an index is an incredibly expensive task on a dataset so big that it needs one to be added.

It's something that is likely to require massive engineering effort on a live system.

Removing an index, on the other hand, is never an issue.

It's not at all premature optimization, it's simply basic software design.

Re: Cases where full scans are better than indexes

#165

Post by remram »

watermelon0 wrote: post #65
PhilipRoman wrote: post #37

Earlier quoted context omitted.

200ms for 180k entries sounds way too slow. Just tested on my 150k line log file and it takes about 10ms on average for various kinds of patterns with various hit frequencies. On an unrelated note, from a quick check with "strace", gnu grep seems to detect when output is redirected to /dev/null as no write syscalls are being made in that case.

Unrelated note intrigued me, so I went looking in the source code; detection is here: https://git.savannah.gnu.org/cgit/grep.git/tree/src/grep.c#n... Interesting that they would optimize for this use case.

Especially since grep -q exists. It would never come to my mind to direct grep's output to /dev/null, I wonder how this optimization came to be?

Re: Cases where full scans are better than indexes

#166

Post by Aachen »

iLoveOncall wrote: post #164
Aachen wrote: post #162

Moral of the post: don't do premature optimization. Common adage but it's a good reminder and example of it. Aside from one case where OP argued that the queries were so rare compared to the data updates that maintaining the index is more expensive. Which is also pretty classic when you're taught about indexes. What I recently learned the hard way about indexes is that they're slow when you have to read "large" chunk…

Adding an index is an incredibly expensive task on a dataset so big that it needs one to be added. It's something that is likely to require massive engineering effort on a live system. Removing an index, on the other hand, is never an issue. It's not at all premature optimization, it's simply basic software design.

Read OP's post please. They're talking of systems where it was acceptable to always do full table scans, in one case having 350 rows.

Not "an incredibly expensive task on a dataset so big that it needs one". Thus I read OP's post as recommending to not do premature optimization (without using those words literally).

Re: Cases where full scans are better than indexes

#167

Post by mumblemumble »

lazide wrote: post #154
winrid wrote: post #132

Earlier quoted context omitted.

Are you just trying to create employment for yourself? This is amazingly bad advice. I literally get hired to fix these setups by people that take this approach. Yes, it's good to periodically review query plans. But designing and planning for data retrieval is part of a design process. And it's easy. Even Django since 2003 allowed you to define indexes inside your models. Got a 100m record table and you're adding a…

It sounds like he's thinking of it from the DBA perspective, where they have to react to sudden changes in behavior from devs with little or no warning - since the devs don't talk to them. DBAs doing proactive index creation when they don't know what the devs are doing is indeed futile. The devs, however, should definitely be doing proactive database design/planning whenever they do anything, since they can (and will…

Exactly this.

The company had actually banned new uses of ORM and was in the process of eliminating existing usage of it while I was there. We had discovered that teams that used ORM had much higher production incident rates than teams that didn't, and it was fairly directly attributable to lack of understanding and predictability of what was happening in the database.

Maybe not a huge deal if you're in a low-load situation. But HFT requires the A game at all times because you never know when some exciting news that causes trading volume to increase 50-fold almost instantaneously might happen.

For the record, I was a dev and not a DBA. But I did work closely with the DBAs. And I was pretty irritated when I found out ORM was banned, because it definitely made the "writing new code" part of the job more laborious. But, hey, learning experience - it turns out that it was the right move. In the long run we were able to move faster once we stopped having to deal with the blowback from breaking things quite so often.

It's a little bit like when I play Mario Kart with my kids. Why do I go so much faster than them? Mostly because they are constantly pushing hard on the accelerator button, while I ease off the gas and even hit the brakes sometimes. They think speed management is annoying. I think that I spend a lot less time bouncing off of walls and giving precious coins to Lakitu.

Re: Cases where full scans are better than indexes

#168

Post by ignoramous »

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…

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

Re: Cases where full scans are better than indexes

#169

Post by birdyrooster »

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.

Why do you think that? Seems like a hard problem.

Re: Cases where full scans are better than indexes

#170

Post by anarazel »

wiredfool wrote: post #145
ksherlock wrote: post #54

Earlier quoted context omitted.

You should also consider how unique that field is. If half your widgets are blue and half your widgets are red, indexing the color is probably not helpful (ie, the query planner will ignore the widget_color index and do a full table scan). A rule of thumb number I vaguely recall is 10%

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)
Post reply on HN