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

91–100 of 226 posts

Re: Cases where full scans are better than indexes

#91

Post by sumtechguy »

electroly wrote: post #52
deepsun wrote: post #41

Earlier quoted context omitted.

> There's nothing you can do in an index for a table with 350 rows I meant if you have 100s of indices -- it might be slow even on small tables. I actually had a production issues from using a lot of indices, but it's not apples-to-apples with current discussion, because the table sizes, DBMS and update rates were much larger, fixed by removing indices and splitting table into multiple.

Wow! You're right; I wasn't considering that anyone would try to have that many indices. 100 is a lot. I should qualify my statement and say that you won't get in trouble with one index on a small table. I've edited my post accordingly.

In those sort of cases your schema is probably not the correct pattern and needs to be reviewed.

I had one proj where they had 40 indexes on one table. Inserts were terrible for that table. No one wanted to touch it as it happened to be the table where everything was at. They started pulling out 'nosql' sharding and other sorts of tools to fix it. Anything to not change that table with 200+ columns and 30 indexes and the flotilla of stored procs to go with it. They even ported it from MSSQL to Oracle. Thinking somehow magically oracle was going to make the poor schema run faster.

Re: Cases where full scans are better than indexes

#92

Post by lazide »

zht wrote: post #89
leetrout wrote: post #85

Earlier quoted context omitted.

Agree but you can always add an index without downtime. It just becomes a money and complexity issue ;)

can you do this (on a large table) without adding significant IO load/clogging up replication for an extended period of time?

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.

Re: Cases where full scans are better than indexes

#93

Post by MaulingMonkey »

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…

Justify the dev time to save micro-pennies worth of electricity to me instead.

A typical naive index won't help with my regular expression based queries, which aren't easily accelerated by an index. Or given an in-memory index, you've just increased memory use from O(1) to O(N), and I'll OOM on large files. Perhaps you'll throw a database at the problem, complicating I/O (especially when the data is generated/accessed by third party tools that aren't database based), tying me to yet another library's update cycle, and perhaps forcing me to tackle the additional problem of cache invalidation. Perhaps I need reverse lookups, in which case whatever forward indexing I might've pessemistically added ahead of time will be of no help at all.

If it'a a 5 second "this is probably the right choice" kneejerk reaction, maybe it's fine. Or if you're google indexing the internet, I suppose. But I am frequently plagued by shit, buggy, useless indexes that merely distract from the proper alexanderian solution to the gordian knot - brute force - wasting more time than they ever saved, for both people and CPUs.

Re: Cases where full scans are better than indexes

#94

Post by lazide »

Vvector wrote: post #84
abtinf wrote: post #45

Earlier quoted context omitted.

> paying-user table index-free Presumably, that means they created a new table intended to be straight-joined back to the user table. No need to search a column.

Joining a table on a column without an index will require a linear scan of the column. You almost always want an index on JOIN columns

The primary key (userid?) will almost always be indexed implicitly. You’d usually have to go out of your way to avoid it.

So it was probably being joined by an indexed column, but without an explicitly defined index.

Re: Cases where full scans are better than indexes

#95

Post by mschuster91 »

lazide wrote: post #92
zht wrote: post #89

Earlier quoted context omitted.

can you do this (on a large table) without adding significant IO load/clogging up replication for an extended period of time?

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 be too much for IO burst credits

Re: Cases where full scans are better than indexes

#96

Post by mastax »

mastax wrote: post #73

> I recently came across someone maintaining a 0.5GB full text index to support searching their shell history, 100k commands. I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries. I just started using a tool that stores my bash history and replaces C-R that I found on HN, it's written in Rust and uses SQLite of course. But it'll randomly cause commands to pause for a fe…

Okay getting real off-topic now (welcome to HN) but this is not what I expected:

https://github.com/ellie/atuin/issues/952#issuecomment-15378... https://github.com/openzfs/zfs/issues/14290

Apparently when SQLite calls `ftruncate` on the `-shm` file, ZFS will sometimes block for several seconds. Maybe it's waiting for txg timeout? Strange.

Re: Cases where full scans are better than indexes

#97

Post by wswope »

zvmaz wrote: post #83
vivegi wrote: post #80

Once upon a time (25+ years ago) I used to maintain an Oracle database that had around 50M records in its main table and 2M records in a related table. There were a dozen or so dimension (lookup) tables. Each day, we would receive on the order of 100K records that had to be normalized and loaded into database. I am simplifying this a lot, but that was the gist of the process. Our first design was a PL/SQL program tha…

> Set theory is your friend and SQL is great for that. Could you tell us how set theory was useful in your case?

The implication is that the PL/SQL job was operating rowwise.

Batch processing, backed by set theory in this case, is far more efficient than rowwise operations because of the potential for greater parallelism (SIMD) and fewer cache misses.

E.g., if inserting into a table with a foreign key pointing to the user table, batch processing means you can load the user id index once, and validate referential integrity in one fell swoop. If you do that same operation rowwise, the user id index is liable to get discarded and pulled from disk multiple times, depending on how busy the DB is.

Re: Cases where full scans are better than indexes

#98

Post by eklitzke »

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 (except possibly to terminate the loop). 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. This is true for in-memory data structures, and it's even more true on disk, since disks (even SSDs) are especially optimized for linear scans compared to random accesses.

It's been a while since I looked at this, but I think MySQL and Postgres both take this into account and will let you add indexes to small tables but will actually ignore them and do a full table scan for all queries if the table is small enough.

Re: Cases where full scans are better than indexes

#99

Post by pkulak »

MaulingMonkey wrote: post #93
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…

Justify the dev time to save micro-pennies worth of electricity to me instead. A typical naive index won't help with my regular expression based queries, which aren't easily accelerated by an index. Or given an in-memory index, you've just increased memory use from O(1) to O(N), and I'll OOM on large files. Perhaps you'll throw a database at the problem, complicating I/O (especially when the data is generated/accesse…

> Justify the dev time to save micro-pennies worth of electricity to me instead.

KEY (user_id)

I mean, it's a dozen characters. Do you need to know how fast I type before you run the calculation?

Re: Cases where full scans are better than indexes

#100

Post by pkulak »

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, that's correct. If you do an explain for a tiny table, as long as your stats are up to date, the index will be ignored. In that case, it's there for insurance if the table grows in the future.
Post reply on HN