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

151–160 of 226 posts

Re: Cases where full scans are better than indexes

#151

Post by jasonwatkinspdx »

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…

So, forgetting an index and then growth pushing you over the threshold is a valid concern. I think every dev has run into that at some early point in their career.

But what your comment is skipping past is there's potentially a 100x or higher difference in throughput for sequential scans vs indexes. If you know the data will have a bounded size this means indexes aren't necessarily a good choice. SSDs have narrowed this gap a great deal but it still exists because of latency and unpredictable prefecting. It even exists with pure in memory applications. Another key aspect is how much of the data the query ends up touching. If you're hitting 25% of the data anyhow a linear scan is likely faster.

There's also more niche ideas like arranging to convoy multiple queries along one linear scan, something impossible with indexed scans.

It's useful to know about this asymmetry and that sometimes a brute force linear scan is in fact the best tool.

Re: Cases where full scans are better than indexes

#152

Post by holoduke »

eterm wrote: post #39
raldi wrote: post #2

When I wrote Reddit Gold (now called Reddit Premium) I intentionally left the paying-user table index-free, looking forward to the day it would become necessary. It hadn’t happened by the time I left the company, even though sales were exceeding expectations.

That goes against my intuition, because the performance would be more impacted (beneficial to have an index) where you have very few bits set on a boolean field. If you have 10m users and 100 have "IsPremium = 1" then an index massively speeds up anything with WHERE IsPremium = 1, compared to if the data is fairly evenly spread between IsPremium = 1 and IsPremium = 0 where an index won't be much benefit. So low sales…

Having a separate table containing all the premium users is different than an extra column in the normal user table. In the extra table example you don't really need an index (in premium user table) if you have only 100 premium users

Re: Cases where full scans are better than indexes

#153

Post by holoduke »

SoftTalker wrote: post #20
cactusplant7374 wrote: post #15

Earlier quoted context omitted.

Indexes are such an easy thing to add. I don't get it. Seems like under optimization when you consider the tradeoffs.

They add overhead to updates and inserts. If you don't need them, why take that hit. Know your data.

My experience is that it's uaually better to add indices where it's expected to be needed beforehand. Adding indices on large production tables will millions of rows can bring down databases for hours or even days worst case. It's tricky to manage.

Re: Cases where full scans are better than indexes

#154

Post by lazide »

winrid wrote: post #132
mumblemumble wrote: post #23

Earlier quoted context omitted.

I used to be one of the "keep the database running" people at a high frequency trading firm. So, super high pressure; any outage meant we were potentially hemorrhaging money at a brain-melting pace. My lessons from that experience were twofold. First, you can't plan for sudden performance regressions ahead of time. The number of stars that have to align for that anticipatory index to actually help you are just too gr…

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!) cause emergencies and downtime by not considering the impact of how they are interacting with/using the database.

If the devs are directly writing SQL, this is also relatively easy to get them into doing. If they're using a heavyweight ORM, it's nearly impossible to figure out what SQL it's going to run sometimes (and difficult to even trigger in a test), and so the devs often won't even try.

Re: Cases where full scans are better than indexes

#155

Post by BeefWellington »

raldi wrote: post #2

When I wrote Reddit Gold (now called Reddit Premium) I intentionally left the paying-user table index-free, looking forward to the day it would become necessary. It hadn’t happened by the time I left the company, even though sales were exceeding expectations.

It's not really index-free if a separate table has constraints of any kind.

Re: Cases where full scans are better than indexes

#156

Post by bawolff »

pixl97 wrote: post #87
themerone wrote: post #34

Earlier quoted context omitted.

Usually things will slow down gradually or fail right away under production loads.

W.U.C.T Works until critical threshold. In enterprise software I noticed software tends to work in a WUCT'ed up manner. Things may slow down over time, but no one complains about it because "the software is just slow", then suddenly one day you hit the timeout component of some higher layer and then the software is completely and utterly broke.

Everything has a critical threshold. Even your perfect db schema will still eventually run out of disk. There are no magic solutions that work on all scale levels.

Re: Cases where full scans are better than indexes

#157

Post by [deleted] »

bob1029 wrote: post #116
jameshart wrote: post #22

“We’ll add an index when it gets slow” is saying “screw the guy who’s on call the night this system starts timing out”. Invisible cliffs in your code that it will fall off at some unknown point in the future are the antithesis of engineering. If you deliberately aren’t implementing indexing, know at what point indexing would begin to matter. Put in place guard rails so the system doesn’t just blow up unexpectedly. Th…

> Invisible cliffs in your code that it will fall off at some unknown point in the future are the antithesis of engineering. I think this describes the general shape of problem seen in any engineering domain. After a certain point of time (i.e. unknown), we can no longer guarantee certain properties of the system. This is why we add all kinds of qualifiers and constraints in our discussions with the customer. Certain…

[deleted]

Re: Cases where full scans are better than indexes

#158

Post by abtinf »

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

Two relations with a one-to-one relationship implies identical primary keys. Most implementations default to creating an index on the primary key.

In this case, the premium user table only needs the user id primary key/surrogate key because it only contains premium users. A query starting with this table is naturally constrained to only premium user rows. You can think of this sort of like a partial index.

One consequence of this approach is that queries filtering only for non-premium users will be more expensive.

Re: Cases where full scans are better than indexes

#159

Post by lmm »

jameshart wrote: post #22

“We’ll add an index when it gets slow” is saying “screw the guy who’s on call the night this system starts timing out”. Invisible cliffs in your code that it will fall off at some unknown point in the future are the antithesis of engineering. If you deliberately aren’t implementing indexing, know at what point indexing would begin to matter. Put in place guard rails so the system doesn’t just blow up unexpectedly. Th…

Indices are far more likely to cause a cliff than to remove one, IME. Full table scans are linear and grow linearly. Indices are crazy fast until one day they're suddenly not.

Re: Cases where full scans are better than indexes

#160

Post by taeric »

I feel this somewhat generalizes. "Cases where a simple list/array is better than a hashed collection." Which, oddly has the perverse problem of "when you should give up on a single collection of your data, and embrace storing it in different ways."

That is, few folks seem to internalize or consider that every index is essentially a copy of the data. A complete copy, if you are doing a fully projected index. So, when is it better to just do a full scan over something else? Well, its probably never better in isolation of every other concern. But, when is it better to just do a scan of the data over duplicating it in a place that would let you hash in? Depends on how much extra work you are doing because of it?

Having typed that, really I think the trick is to ask yourself roughly (not exactly, amusingly) what it means to add an index. Or to use a hashtable. Or to use a list and a hashtable. And realize that the question of using an index is the same as the question of keeping another copy of your data somewhere.

Post reply on HN