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

211–220 of 226 posts

Re: Cases where full scans are better than indexes

#211

Post by [deleted] »

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…

[deleted]

Re: Cases where full scans are better than indexes

#212

Post by pkulak »

chlorion wrote: post #193
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…

The Rust BTreeMap implementation is an example of this as well. It does a linear scan through the nodes instead of a binary search because it's actually faster in this case! https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...

Did we both just watch the latest Crust of Rust, or did you just know that? If the latter, I’m impressed!

Re: Cases where full scans are better than indexes

#213

Post by wiredfool »

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)

Guess they've improved -- That used to be a thing. Looks like it was probably in the PG13 changes to the statistics and btree indexes that did that, though it's hard to tell exactly.

Re: Cases where full scans are better than indexes

#214

Post by Aachen »

srcreigh wrote: post #184
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…

The cause of this is the likely N+1-like behaviour of indexes on un-clustered data. Two options for speeding this up a ton (they dont' make sense to use together), 1. Cluster your data using the Gist/r-tree index. postgis docs [1] great explanation 2. Use the r-tree as covering index. IE add your associated data as dimensions into the index. The gist index becomes (lat, long, weather_c, avg_altitude), etc. This avoid…

Thanks! I don't think MariaDB offers the former but it's good to know this exists and I may want to look elsewhere. This isn't the only thing I ran into with MariaDB, but I'm also hesitant to subscribe to maintaining another service into eternity when the existing database has done fine for everything (more than a decade of projects) up until this project. If I had to redo it, I'd definitely try this out though to see if it's worth it! And at work it's also a different equation. So it's useful info :)

The latter, I considered but didn't think would cut the time by more than half whereas it would need an order of magnitude or more speedup to be useful. Doing a full table scan and caching the result for certain zoom levels was the solution for me.

Re: Cases where full scans are better than indexes

#215

Post by jefftk »

jefftk wrote: post #209
jameshart wrote: post #180

Earlier quoted context omitted.

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…

> These included a MySQL database, where adding an index is no additional maintenance overhead whatsoever (FULLTEXT idx in the table DDL) MySQL didn't add support for FULLTEXT until v5.6, released 2013-02, a few years after I was working on this. At the time if I had wanted a full text search index it would have needed to be an additional service.

Looking now (no longer on my phone) it's a bit more complex than that: while MySQL has supported FULLTEXT indexes since 3.23.23 (2000-09-01) [1] if you wanted to use InnoDB (and you probably did -- it was much better than MyISAM [2]) you initially couldn't use FULLTEXT. That was added in v5.6 [3], and at the time I was developing this software the standard option was to set up Sphinx.

I've edited the post to add some of this history, so future readers understand this was about whether to add a dependency on an external indexing service.

[1] http://dev.cs.ovgu.de/db/mysql/News-3.23.x.html ("Full-text search via the MATCH() function and FULLTEXT index type (for MyISAM files). This makes FULLTEXT a reserved word.")

[2] https://stackoverflow.com/questions/7492771/should-i-use-myi...

[3] https://downloads.mysql.com/docs/mysql-5.6-relnotes-en.pdf ("MySQL now supports FULLTEXT indexes for InnoDB tables.")

Re: Cases where full scans are better than indexes

#216

Post by fulafel »

jameshart wrote: post #105
jefftk wrote: post #55

Earlier quoted context omitted.

> screw the guy who’s on call the night this system starts timing out This was a very small billing practice, and that person was going to be me. I thought then, and still think now, that I made a reasonable trade off between what would be work at the time and potential future urgent work. Additionally, this wasn't the sort of thing that would fail suddenly when you hit a critical point. Instead, running full text se…

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…

Most systems get scrapped and never go to production. Early stage is validation and search for a useful concept. It often pays off very well to steal time from the future.

Re: Cases where full scans are better than indexes

#217

Post by cwmma »

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…

it's more then that, PostgreSQL will choose to ignore the index on a per query basis, if the query will return more then some % of the table it's faster to just do the scan.

Re: Cases where full scans are better than indexes

#218

Post by wswope »

raldi wrote: post #181
wswope wrote: post #75

Earlier quoted context omitted.

This is a read-heavy workload per the OP: https://news.ycombinator.com/item?id=36071799

It was neither read-heavy nor write-heavy.

Ah, thanks for the correction; I’m guessing I read your comment too literally.

Would strikethrough my prior comment if it weren’t past the edit window…

Re: Cases where full scans are better than indexes

#219

Post by time0ut »

Macha wrote: post #88
bcrosby95 wrote: post #33

Earlier quoted context omitted.

So no primary key or uniqueness constraints?

Unlikely, given Reddit's past schema design. One table of "things", and then another table of attributes of those things in a entity,key,value format. https://kevin.burke.dev/kevin/reddits-database-has-two-table...

I built something inspired by this very post in 2013/2014. Not sure how the scale compares, but we insert ~10 million “things” with an average of 30 data attributes per day with a 30 day window. It definitely uses primary and foreign keys. It took some time to tune. Had to support an additional access pattern using a non-unique index. Had to work with a DBA to get partitioning right to handle the large write volume and manage expiration efficiently. It worked out great and is still chugging along. It does suck not having all the tools of an RDBMS at your disposal, but it was a good trade off.

Re: Cases where full scans are better than indexes

#220

Post by thesmart »

Saying there are cases where full scan is better than an index is really just describing an edge case where the default index implementation is non-optimal.

There are edge cases where default implementation of an index will not result in good performance in some use cases. For example, write heavy loads where the updated tuple values are frequently changing position in the index constantly. However, the solution is rarely "no index".

A solution is to throttle the index update by an acceptable delta through a non-default implementation.

A solution is to develop your own application-side index.

A solution is a custom PSQL function that interacts with an index in a more complicated way.

Maybe a non-default implementation is not priority right now, e.g. if scale is low. But it is always good to think ahead and to have a plan and to log the tech debt and track it responsibly so there are no surprises later. Don't build on shifty foundations.

Post reply on HN