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

61–70 of 226 posts

Re: Cases where full scans are better than indexes

#61

Post by jmcomets »

captainmuon wrote: post #25

The inverse is also true, often you have linear or even quadratic lookup times when something like an index can give you the result "immediately". I wish languages other than SQL had a concept of adding an index. Imagine a variant of Python's list or C++'s vector where you can add indicies on arbitrary fields of the contents, like a more flexible dict. Something like (pseudocode) books = List and then you could up by…

In my experience these type of abstractions end up bloated with too many concerns which adds maintenance overhead. It's a lot simpler to simply add a `HashMap` and cover with tests, than use an abstraction.

I want languages to do less magic, not more, since I read code more than I write it.

Re: Cases where full scans are better than indexes

#62

Post by VWWHFSfQ »

cactusplant7374 wrote: post #15
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.

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

> Indexes are such an easy thing to add.

Indexes can have catastrophic consequences depending on the access patterns of your table. I use indexes very sparingly and only when I know for sure the benefit will outweigh the cost.

Re: Cases where full scans are better than indexes

#63

Post by electroly »

jefftk wrote: post #58
electroly wrote: post #6

If the data is small, then the index will also be small, so it doesn't really matter either way. The reason to avoid indexes is if you can't accept the time or space cost. Only the last of OP's examples is a situation where choosing an index causes a problem; the rest are examples where an index isn't necessary but does not cause problems. Several examples are so trivial that you'd be crazy to use an external databas…

In cases where your data is small enough that you don't need an index, an index is adding technical complexity. In some cases that will be small (you are already using a database and it has built-in support for the kind of index you need) and then, sure, go ahead. But in other cases it will not be so small (you can't get indexes without switching to a more complicated tool, you'd need a somewhat unusual kind of index…

I think we're in agreement here; this is the part where I said "Several examples are so trivial that you'd be crazy to use an external database at all". For your shell history, you not only don't need indexes, you don't need the database either (as you conclude in the post). But if you're already in the database, it falls into that first "the index feature is right there" category. This HN thread is full of people skipping the index on their SQL tables in situations where I would write the index. Mostly I think people are just missing that you need to write indices in response to queries rather than what you're imagining when you first create the table.

Re: Cases where full scans are better than indexes

#64

Post by jdmichal »

ydnaclementine wrote: post #19

What is the rule that you use on which fields to index? I've been following the general when adding fields: if the field is mentioned in a sql WHERE, ORDER BY, or GROUP BY EDIT: JOINs

The answer will heavily depend on what you're doing.

CRUD patterns where you're pulling out a small group of rows from several tables, you probably want indexes on `JOIN` clauses so that you can quickly find those links using nested loop index scans. And maybe a few indexes on common ways to find records.

Analytics patterns where you're aggregating a large number of rows, indexing `JOIN`s won't help you, because you really want hash or merge joins anyway. Instead, tune your indexes for `WHERE` clauses, because you want a filtered index scans instead of table scans on the reads.

You also want to learn about cardinality and selectivity. Ideally your indexes are organized by selectivity.

Re: Cases where full scans are better than indexes

#65

Post by watermelon0 »

PhilipRoman wrote: post #37
zokier wrote: post #4

> I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries 200ms is order of magnitude more than I'd prefer for interactive use

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.

Re: Cases where full scans are better than indexes

#66

Post by fnordpiglet »

electroly wrote: post #32
fnordpiglet wrote: post #24

Earlier quoted context omitted.

In the case i mention above of log data where data access patterns dominate storage without retrieval computing indices up front is absurdly expensive and challenging at extreme scales. In that case minimal time and perhaps probabilistic indices computed on ingestion and extremely parallel brute force search on search works out both in terms of unbounded scale and cost - by like one to two orders of magnitude.

Indeed, we also use an unindexed store for our logs (having migrated to that from a system that was indexed). This is clearly not the "data is so trivially small that nothing matters" situation that the OP is describing in 4 of the 5 of their examples. I hope you can see this isn't at all incompatible with my post.

I can. I’m just pointing out there are definitely cases where indexing sucks. I agree the original post doesn’t touch those cases.

Re: Cases where full scans are better than indexes

#67

Post by jmcomets »

pyrophane wrote: post #29

I think the risk of creating indexes prematurely is really that you will make assumptions about how your table is going to be queried that don't turn out to be correct, so you create indexes that you will never need, even if the table gets large. That probably isn't the end of the world, but it can make it harder for others to understand what is going on in your database (indexes can also be a form of documentation)…

FWIW, most DBMS have built-in index usage stats, and it's not too difficult to query. In my previous job we had a Postgres health dashboard that notably showed `log10(index size) / index hits`, making it pretty clear when some recently added index was useless.

My opinion is that indexes should be either logical (ex: used for exclusion constraints) or purely for performance (tradeoff space for better QPS). Query patterns change, specs change, so monitoring your DB's performance is the way to go.

Re: Cases where full scans are better than indexes

#68

Post by pkulak »

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 memory, or maybe even on disk? The Bash history thing makes sense, because indexing is a lot of work. But otherwise, just use an index and move on to the next problem.

EDIT: Has anyone else forgotten to add an index, then noticed the performance regression a year later? That's always fun, because now adding the index could mean downtime, and even knowing if or how much is difficult because putting that much data somewhere else to test isn't trivial. No thank you.

Re: Cases where full scans are better than indexes

#69

Post by tomnipotent »

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.

Considering how much data is written to support redo/undo/wal logs, a single index for user id is very little overhead.

Re: Cases where full scans are better than indexes

#70

Post by david422 »

themerone wrote: post #34
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…

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

But when you have a 100 places all adding little slowdowns it can be difficult to realize.
Post reply on HN