"fits in ram" ok got it
Cases where full scans are better than indexes
201–210 of 226 posts
Re: Cases where full scans are better than indexes
#202Just 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…
Benchmarking this (for non-database applications) is really interesting because you get to find the crossover point, and it's usually in the hundreds of items. An algorithm that searches maximum 50 items in a hash table but does it across many hash tables could be made much faster using a linear search.
Some of his examples aren't great, though. The cost of adding an index to a database you're already using and which has a reasonably small amount of data is low, and the benefit of getting a few hundred ms less latency for your users is underappreciated. A hundred million records is definitely above the limit at which e.g. prefix search on a mobile device becomes painful.
Re: Cases where full scans are better than indexes
#203Earlier 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...
Interesting. But the doc doesn't go as far as to say it's faster, just fast - any measurements for eg string keys?
Re: Cases where full scans are better than indexes
#204Earlier quoted context omitted.
> Justify the dev time to save micro-pennies worth of electricity to me instead. The time spent justifying it is longer than the dev time itself. Any semi experienced engineer will throw basic indexes into their data model without even thinking and cover the most common use cases. If they never use them… who cares? It took no time to add.
An RDBMS is not the best data store for all data. Sometimes flat files or other are the simplest tool for the job, as shown in the article. Adding a database to any of those tools would definitely not be worth the trade-off.
My statement assumed that as a starting point. To be fair, the decision to use a database or other format, given a reasonable amount of experience, is also a fairly quick thought process. By the time I open my editor to write my first line of code I’ve already made my choice.
Re: Cases where full scans are better than indexes
#205Earlier quoted context omitted.
Modern DB engines can enforce Unique or PK constraints without indexes. Yes, they perform scans.
Every major RDBMS requires an index for both constraints.
After checking the docs, you are right, I stand corrected. I was pretty sure Oracle and DB2 don't.
Re: Cases where full scans are better than indexes
#206Just 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…
I am glad the query execution planner (mostly) takes the strain. When it doesn’t it is a 99% chance you need to promote an ORM generated query to a, human<<<<< well probably GPT generated explicit one.
Re: Cases where full scans are better than indexes
#207“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.
Joins, however, scale exponentially if you only have full table scans.
Re: Cases where full scans are better than indexes
#208Earlier quoted context omitted.
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.
Joins, however, scale exponentially if you only have full table scans.
Yeah but it's not like you get 10 new customers and that suddenly adds 10 more joins to your query in the middle of the night. At least I hope not.
Re: Cases where full scans are better than indexes
#209Earlier quoted context omitted.
When building systems we are always making trade-offs between the present and the future. It's only "stealing time from future you" when you make bad trade-off; otherwise it's prioritization. In this case, leaving out an index for full text search meant I didn't need to maintain the software for that index either, which would have been stand-alone at the time I was building this. Possibly this even was a choice that…
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.
Re: Cases where full scans are better than indexes
#210Earlier 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.
Which is why they use b-trees and not binary search.