Cases where full scans are better than indexes
jefftk.com
jefftk.com
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.
Even if the cluster is scaled to easily take on your normal workload, indexing may prove to be too much for IO burst credits
There are situations where the indexes end up larger than, or the same size as, the actual data and the query doesn’t meaningfully benefit from having the data indexed because, for instance, all the data is going to be analyzed anyway, or the search type doesn’t index usefully with the normal index types (like geo searches, or clustering type queries).
Adding indexes that never get used have real costs on an ongoing basis with insert/updates and schema updates too, as it adds potentially significant overhead on every operation and can make certain schema operations impossible without downtime too.
Foreign key columns, ‘soft delete’ columns (like deleted/not), basic auditing type stuff (created on, updated on, etc), ‘unique’ or external reference values like a order id or whatever (even if not a primary/unique key in the schema), basic numeric/analysis columns are almost always worth indexing though, to your point.
Stuff that is not always a clear win without some real thinking is Freeform text fields, structured binary data (like a PDF or image), geo location data without a clear existing use (tends to require specialized index types which are also expensive to load/use), etc.
Many times some preprocessing is necessary anyway to convert what you have to what you actually want, and putting that in a secondary column to be indexed is far more valuable.
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.
KEY (user_id)
I mean, it's a dozen characters. Do you need to know how fast I type before you run the calculation?
I'll assume 100WPM, call that two words, billed at $200/hour and call that $0.06, falling under "too cheap to be worth arguing against", which falls under the aforementioned:
>> If it'a a 5 second "this is probably the right choice" kneejerk reaction, maybe it's fine.
That said, there's a decent chance those 6 cents won't pay for themselves if this is a login on a single user system, with any theoretical benefits of O(...) scaling being drowned out by extra compile times, extra code to load - and I'd be plenty willing to NAK code reviews that merely attempt to replace /etc/passwd and /etc/shadow with this, as the extra time code reviewing the replacement still has negative expected ROI, and it'll be a lot more involved than a mere dozen characters.
Now, maybe we're attempting to centralize login management with Kerberos or something, perhaps with good reasons, perhaps which does something similar under the hood, and we could talk about that and possible positive ROI, despite some actual downtime and teething concerns?
Suddenly those two words cost a lot more than $0.06, and that's IF everything goes smoothly.
If you're already using a relational database you should almost certainly set up indexes on your table ids and foreign keys. But that's pretty different from the examples in the post!
I'm not anti-index, I'm anti-"if you ever have a full table scan in production you're doing it wrong".
And this is exactly the sentiment that got us where we are.
It may look a little different, but there is nothing without tradeoffs.
Including indexing everything.
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.
Because 90% of the time the RDBMS is.
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.
I think folks writing databases know a thing or two about writing faster search and sort algorithms.
What exactly do you mean with "writing faster search and sort algorithms"?
- Branchless binary search: https://news.ycombinator.com/item?id=35737862 / https://news.ycombinator.com/item?id=14598098
- Static B-Trees for faster binary search: https://news.ycombinator.com/item?id=30376140
Presumably there's even more literature on the topic.
But I see now you were referring to the branch predictor part specifically, so all good.
Re: binary search, the biggest cost to scanning data in a database is loading that data from persistent storage. A few mispredicted branches aren’t going to matter much if it means you can do fewer reads.
It depends.
If you measure or determine somehow the sizes of the L1-L2-L3 caches in the CPU, the relative speed and size of the main memory, and the relative speed and size of the local storage (in contrast with for example network-remote data), then it is a matter of performing some arithmetic, and just to be on the safe side, some benchmarks.
Any data set that fits into the CPU cache is definitely small, for a particular CPU.
If you want to decide a number that applies to every and all hardware, then it goes from hard to basically impossible.
Or in other words add the index every single time, unless you have so many writes and such a large table that the actual writes slow down the index.
Leaving out an index on a small table never helps anything.
https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
I did not read this entire thing so it's very possible it contains a benchmark somewhere but I couldn't find any when doing a quick skim.
Yes that's exactly how I knew about this!
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.
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.
I'm not sure whether the units of that latter number are still ms or now s or whatever, but either way isn't that where you are wrong? On real computers, there are lots of situations where linear access is trivially faster than a "better" data structure with theoretically better runtime complexity.
1000 accesses to a single page for a linear scan are going to be many, many orders of magnitude faster than 5 accesses chasing pointers across 5 pages that have no TLB entry, or excruciatingly worse, that need to be paged in from disk.
This is an extreme (but absolutely not unrealistic!) example for illustration. Slightly more subtle scenarios involving e.g. branch prediction have already been named by eklitzke.
This problem exists across multiple layers, not just close to the CPU like above. (As eklitzke also already mentioned with disk involvement, even if it's an SSD.)
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.
There are 100% cases where you shouldn’t use indexes. That’s not the same thing as being able to get away without an index.
That threshold doesn’t gradually creep up on you, it hits you all at once at the worst possible time.
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.
If you let WUCT run free in any complex process, you are just asking for everything to break all the time and people to do nothing but fire-fighting. So, you are much better dealing with the WUCT causes instead of insisting that software or any other component scales forever? (Because they never will, and you will just make something else bream.)
WUCT is one of the main reasons why we monitor system operations.
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 searches (a very small fraction of what the database was handling) would just slow down in a way that would have been very clear to the users.
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 about 5 million. When’s that going to happen? Never? Then we’re done here. Within a few months? Well let’s plan for that now. Within a few years? Maybe not within the lifetime of this system? Judgement call. Let’s put something in place that forces us to at least look back at this before it gets bad. Even if that’s just a google calendar reminder.
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 was, in expectation, time-saving for future me.
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 people where even cheap and easy to implement indexes were not needed.
Now when challenged you’re retreating to the more defensible position that in the case where you’re querying an ad hoc data structure where you would have to implement your own index that that is often a bad trade off. Or maybe it was a bad tradeoff because this was a small app you were building that you knew you would be the long term maintainer for.
But that’s not what I’m talking about is it, and I don't know all the specific circumstances of your single specific project where this was the right choice, so we’re not going to get anywhere.
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.
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.")
On the other hand, they are the essence of _software_ 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.
Certainly, you can make some predictions about how tables will grow over time, but there are also some potential headaches that can be incurred if you arbitrarily add indexing. "We might need to expire records to manage growth" so you go ahead and index that CreatedUtc column. Turns out, the usage patterns of your app changed such that that table is now experiencing 20x more insert volume than you could have ever anticipated and your prediction is now a gigantic liability. With 20x insert volume you would have _never_ indexed that column. You would have used some alternative path involving temporary tables, etc. Now, you are stuck with essentially same problem - a judgement call at 2am regarding whether or not you should drop an index while the rest of your team is in bed.
Since I am unable to predict the future I feel like waiting until the actual problem arises and then dealing with it at that moment is the best option. Strategically, not having an index will likely fail more gracefully than if an index is bottlenecking requests during peak load (i.e. instantaneous vs cumulative data volume).
A simple example is setting an alarm on your max load test traffic. When you get that alarm you know your system is now operating in unknown territory and it's probably time to do another load test or at least take a close look at scaling.
Look at your real world use cases, query patterns and think hard about it.
But for the queries you are building today? Don’t build them such that they will gradually slow down over time.
Nobody wants to stick around for a lecture they can see coming.
I don't think I've ever seen such a cliff where the database is using the same query plan? There's sometimes small incremental slow downs as you pass btree depth thresholds and have to add more, but tbh even that's not usually noticeable.
I have seen plenty of instances where the database decides an index is no longer the right access,but gets that wrong, and the result is terrible.. but I see that as a different issue.
Even this kind of "narrow" slowdown can be substantial. Well, I don't know specifically that it's depth thresholds, but that kind of behaviour - the table passes a certain size and it's suddenly taking 30% longer to insert/read than it did when it was 2% smaller.
> I have seen plenty of instances where the database decides an index is no longer the right access,but gets that wrong, and the result is terrible.. but I see that as a different issue.
IMO it's the same issue, at least from the perspective of the poor chump on call.
This has usually been a memory problem for us - our hot dataset no longer fits in it.
It hadn’t happened by the time I left the company, even though sales were exceeding expectations.
Of course, if the object is large scale bulk inserts, with only very occasional selects, then yes.
Would strikethrough my prior comment if it weren’t past the edit window…
Or consider the example of a developer querying frontend logs: queries are many orders of magnitude less common than writes, and (at the scale I used to work at) an index would be incredibly expensive.
- We’re already using a database, so there’s very minimal added complexity
- This is an extremely hot table getting read millions of times a day
- The scale of the data isn’t well-bounded
- Usage patterns of the table are liable to change over time
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.
So you have to add an index on that column, or start talking about tombstoning data instead of deleting it, but in which case you may still need the FK index to search out references to an old row to replace with a new one.
https://kevin.burke.dev/kevin/reddits-database-has-two-table...
According to that post, in 2010, they had about 10 million users. At a conservative 10 fields per user, you're looking at 100 million records.
I'm a bit skeptical that they table scanned 100 million records anytime they wanted to access a user's piece of data back in 2010.
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 would increase the need for an index.
That said, I'm assuming searching for "Users WHERE IsPremium = 1" is a fairly rare thing, so an index might not make much difference either way.
Presumably, that means they created a new table intended to be straight-joined back to the user table. No need to search a column.
So it was probably being joined by an indexed column, but without an explicitly defined index.
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.
[1] Edited per discussion; a large number of indices on a small table can still get you in trouble.
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.
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.
Even if all you're updating is an int32 column from 1 to 2, the RDBMS is still writing much more data than 4 bytes. At a minimum it's making a copy of the full page the data is in prior to the update (so 8k for pg, 16k for mysql) and usually multiples of that (mysql writes both before/after).
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 that looped through the 100K records that would be loaded into a staging table from a flat file, performing the normalization and inserts into the destination tables. Given the size of our large tables, indices and the overhead of the inserts, we never could finish the batch process in the night that was reserved for the records intake.
We finally rewrote the entire thing using SQL, parallel table scans, staging tables and disabling and rebuilding the indexes and got the entire end-to-end intake process to finish in 45 minutes.
Set theory is your friend and SQL is great for that.
Could you tell us how set theory was useful in your case?
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.
INTAKE_TABLE contains 100k records and each record has up to 8 names and addresses. The following SQL statements would perform the name de-duplication, new id assignment and normalization.
-- initialize
truncate table STAGING_NAMES_TABLE;
-- get unique names
insert /*+ APPEND PARALLEL(STAGING_NAMES_TABLE, 4) */ into
STAGING_NAMES_TABLE (name)
select /*+ PARALLEL(INTAKE_TABLE, 4) */ name1 from INTAKE_TABLE
union
select /*+ PARALLEL(INTAKE_TABLE, 4) */ name2 from INTAKE_TABLE
union
...
union
select /*+ PARALLEL(INTAKE_TABLE, 4) */ name8 from INTAKE_TABLE;
commit;
-- assign new name ids using the name_seq sequence number
insert /*+ APPEND */ into NAMES_TABLE (name, name_id)
select name, name_seq.NEXT_VAL from
(select name from STAGING_NAMES_TABLE
minus
select name from NAMES_TABLE);
commit;
-- normalize the names
insert /*+ APPEND PARALLEL(NORMALIZED_TABLE, 4) */ into NORMALIZED_TABLE (
rec_id,
name_id1,
name_id2,
...
name_id8 )
select /*+ PARALLEL(SNT, 4) */
int.rec_id rec_id,
nt1.name_id name_id1,
nt2.name_id name_id2,
...,
nt8.name_id name_id8
from
INTAKE_TABLE int,
NAMES_TABLE nt1,
NAMES_TABLE nt2,
...
NAMES_TABLE nt8
where
int.name1 = nt1.name and
int.name2 = nt2.name and
...
int.name8 = nt8.name;
commit;
The new id generation does a set exclusion (i.e., the MINUS operation) and then generates new sequence numbers for each new unique name and adds the new records to the table.
The normalization (i.e., the name lookup) step joins the NAME_TABLE that now contains the new names and performs the name to id conversion with the join query.
Realizing that the UNION, MINUS and even nasty 8-way joins can be done by the database engine way faster than application code was eye-opening. I never feared table scans after that. Discovering that the reads (i.e., SELECTs) and writes (i.e., INSERTs) can be done in parallel with optimization hints such as the APPEND hint was a superpower.
Using patterns such a TRUNCATE TABLE (for staging tables) at the top of the SQL script made the scripts idempotent. i.e., we could trivially run the script again. The subsequent runs will not generate the new sequence numbers for the names. With some careful organization of the statements, this became rigorous.
Although I haven't shown here, we used to do the entire normalization process in staging tables and finally do a copy over to the main table using a final INSERT / SELECT statement.
My Oracle SQL-fu is a bit rusty. Apologies for any syntax errors.
This is how I've always done things, but I'm starting to think decoupling normalization from the entire process might be a good idea. This would have simplified design on a few projects (especially the ones that grew "organically") and seems like it would scale nicely.
I'm starting to look at normalization as a completely separate concern and this has led to some fun ideas. E.g. if a system operated on flat files that were already normalized it could save time writing tools; you're at the command line and everyone involved can get their grubby mitts on the data.
?subject ?predicate ?object.
I went to a talk at Dreamforce years ago where the CTO explained their database architecture and it is interesting that the core table in Saleforce is literally a collection of triples. They have a smart optimizer that builds views, materialized views, indexes, etc. in Oracle based on the queries you run.
I built a bot that would download a lot of records from an organization, build a "machine learning" model (built by a geospatial analyst and we didn't call it that these days) that automatically assigns opportunities to salespeople, and then pushes the assignments into the system. The first time I ran the big query in the test system it timed out, then I went to the bathroom and when I came back the second time it worked perfectly. When it went to production exactly the same thing happened.
This is... not entirely true. Most of the data for each "Object" in salesforce are stored in a series of columns on a single table. These are called "flex columns" in the official whitepaper describing the architecture. [0]
However, _foreign key relationships_ are indeed stored in a table that acts like a collection of triples. This is used in place of native foreign keys, and is indeed deeply integrated with the optimizer.
[0]: https://www.developerforce.com/media/ForcedotcomBookLibrary/...
Context: Mariadb 10.2. In this table we stored traffic statistics, aggregated by IP address and day. Probably less than 200 bytes per row. They were also written per day, and then cleaned up by a cron job (every month an entire month worth of data was discarded), so "DELETE FROM traffic_stats WHERE day < ?"
This worked fine on the primary, but our monitoring told us that the replicas started to lag, and showed that they spent inordinate amounts of time on the delete statement above. Even though we had an index on the "day" column.
Even weirder, the problem didn't show up in our QA database cluster, which had far less resources (vmware vm in QA vs. pretty solid bare metal in prod).
Even more puzzling, skipping the replication step and running the DELETE statement manually was quite fast (a second or so).
After some frantic search, it turned out that, for reasons lost in time, the QA db cluster used "mixed" replication, while the prod cluster used row-based replication. In row-based replication, the leader communicates to the replicas which rows were deleted. And since we didn't have a primary key on that table, the replicas did a full-table scan to find which record to delete, and repeated that for each of the 100k records to be deleted.
Adding a primary key to the table fixed the issue immediately, and we switched to mixed replication shortly after.
Add indexes appropriately is a best practice.
200ms is order of magnitude more than I'd prefer for interactive use
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.
Interesting that they would optimize for this use case.
If it gets annoyingly slows I'll stop doing that and use a different syncing system.
And the common thing in this list of tools? They're all laggy and not a nice experience to use.
Even if queries are rare, there is often an actual human sitting waiting for the results of a query. Whereas while ingesting logs, there is no human waiting. I would prefer to burn more CPU time to save some human time.
Index everything, drop those that make things worse.
Deleting an index might be physically easy to do. But figuring out if it's safe to do is hard. You have to inspect every query you make and make sure none need that index. Once the index is there, in practice it's usually there forever.
We experienced that just a couple of weeks ago, where a missing index and an unexpected 1000x increase in volume at a customer brought the DB to its knees. Sure it was still serving queries but at such a low rate it was effectively useless.
For queries that will be run more than once, I try make sure there's an index it can use for something fairly unique.
I’d rather have a database that query performance degrade gracefully and predictably with scale than some sort of black magic mumbo jumbo wake me up in the middle of the night because it lost its statistical little puny pea brain simply because it couldn’t compute a bounded expectation any more.
Years ago I forked postgres and tried to implement the above. Initial results were promising - there were a good chunk of queries that ended up taking a different plan, and sometimes returning 100x quicker.
Alas, the postgres codebase is heindously complex, and implementing the above to be production grade would be many months work - and, due to the way postgres streams results to the client, might have actually required a change to the wire format.
It had gone under the radar because the volume with our other customers had been low enough that the table scan of the queried table wasn't noticed.
As mentioned a customer suddenly got 1000x the volume and it quickly became an issue.
But yea, we have a job running in the weekends to recalculate statistics on key tables, as we've had issues with that grinding production to a halt before.
And recently I sped up a query by 100x by removing a filter from the where clause that for some weird reason caused the DB to run a really poor plan. It was just a simple check intended to filter out some duplicates in a few edge cases, but couldn't find a way to make the DB run it as a post-predicate. Moved it to my code for the 100x performance win...
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 great. Even if you correctly guessed that a given table might be affected by one in the future, you'll never guess what fields it needs to include, and in which order, to support whatever new query or query plan change or whatever caused the problem. Second, Murphy's Law dictates that any attempt at preventing future read performance regressions by speculatively creating an index will end up causing a write performance problem instead.
Better instead to just get in the habit of periodically reviewing query plans for every query in the database. If you know the scaling characteristics of the various operations and the kinds of statistics changes are likely to cause the optimizer to choose different ones (and you should), then it's easy enough to select for better scaling characteristics. This is, incidentally, an excellent excuse for making the engineers use sprocs or a clean data access layer or something instead of a heavyweight ORM, so that you have some sensible way of getting a warning before they change queries on you. You can't effectively aim for a target that's bouncing around erratically. Even better still - and only realistically feasible if you somehow managed to win that bigger war I just proposed - set up a tool to monitor query plans and send you an alert when they change unexpectedly, so you can hear about the problem when it's still small.
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 column you want to query by interatively? Rollout an index. This is normal day-to-day software development...
The write overhead is wild speculation. 99% of business are read heavy.
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.
The company had actually banned new uses of ORM and was in the process of eliminating existing usage of it while I was there. We had discovered that teams that used ORM had much higher production incident rates than teams that didn't, and it was fairly directly attributable to lack of understanding and predictability of what was happening in the database.
Maybe not a huge deal if you're in a low-load situation. But HFT requires the A game at all times because you never know when some exciting news that causes trading volume to increase 50-fold almost instantaneously might happen.
For the record, I was a dev and not a DBA. But I did work closely with the DBAs. And I was pretty irritated when I found out ORM was banned, because it definitely made the "writing new code" part of the job more laborious. But, hey, learning experience - it turns out that it was the right move. In the long run we were able to move faster once we stopped having to deal with the blowback from breaking things quite so often.
It's a little bit like when I play Mario Kart with my kids. Why do I go so much faster than them? Mostly because they are constantly pushing hard on the accelerator button, while I ease off the gas and even hit the brakes sometimes. They think speed management is annoying. I think that I spend a lot less time bouncing off of walls and giving precious coins to Lakitu.
I can indeed imagine life being a lot different if you're on the receiving end of an unknown barrage of queries.
From an outside perspective it seems like the huge increase in volume was more the issue! It sounds like an index helped a lot, but it would also have added cost for all those customers who didn't see that jump in volume.
The other customers pay for that index as well of course but either the volume is low enough that it's trivial or it's large enough that they too saw ann increase in speed.
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<Book, indices=[Book.title, Book.author]>
[1]: https://www.boost.org/doc/libs/1_82_0/libs/multi_index/doc/i...
I want languages to do less magic, not more, since I read code more than I write it.
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 few seconds before executing (I think the hook to write the command to history gets blocked). Probably some simple bug, but I could just have my command history in a flat file and use rg or fzf in a 5 line shell function and have no lag.
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.
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" chunks of a table to find an answer, in my case computing a median for an area. I'm indexing geospatial data and Europe+NA are overrepresented. When you view an area the size of ~Germany, the query would take 20 minutes and compute the median over ~3% of all records whereas a full table scan (whole world) took something like 40 seconds (with the median being computed over the same 3%, it would just evaluate the WHERE clause against every row instead of finding rows to include via the index). That's the power of a sequential read as compared to reading an Rtree. I haven't had such bad experiences with Btree indexes, not sure if that would behave just as badly. On the other hand, if you ask for an area the size of Amsterdam, the index is normal fast, and for <50 rows it's basically instant whereas the full table scan would still take the same 40 seconds.
It's something that is likely to require massive engineering effort on a live system.
Removing an index, on the other hand, is never an issue.
It's not at all premature optimization, it's simply basic software design.
Not "an incredibly expensive task on a dataset so big that it needs one". Thus I read OP's post as recommending to not do premature optimization (without using those words literally).
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 avoids having to load a separate page for each row in the spatial index [2]
[1]: https://postgis.net/workshops/postgis-intro/clusterindex.htm...
[2]: https://www.postgresql.org/docs/current/indexes-index-only-s...
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.
2) If your load is write-heavy, you should consider trade-offs. Yes, full scans are sometimes your friends. Interesting thing to notice here that write amplification is basically same even if table is small.
Source: guy that gets hired to fix database stuff on fire.
Edit: believe me, I tried it all... refining my queries, multiple tables, bigger hardware, faster disks, changing all the tuneables... nothing was as good as adding a whack-tonne of indexes.
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) and could make your ORM code somewhat more complex.
The worst case scenario, I suppose, would be you create an index on a table that grows large
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.
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.
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.
Bigger projects, or projects that are enjoying fast growth, may well need indexing. Why? to keep search performance up under a multi-user workload and/or a mixed write-query workload. Complex multi-table searches often also benefit from judicious indexing.
Here's something to keep in mind: Successful projects often find that an unpredicted query pattern has become very popular and/or a bottleneck. Often the bottleneck is remediated in production by adding appropriate indexes. SQL's designed to add indexing without changes to the data model, for precisely that reason. It's normal to add indexes as projects grow, and no sign of bad design or expensive technical debt. (Unsuccessful projects, or projects that don't need to grow? They don't have the problem.)
Also sourcerer was a full scan of VCS metadata, on a single machine. i.e. if you listed all the commits by a certain person, it would just do a for loop in C++ going through about 1-2 M commits. They were just C++ structs in memory, and it was probably submillisecond times, even with hardware at the time
I remember reading those 2 programs and being impressed that they were both very fast, and full scans! (gsearch got slow later as the codebase grew, but the first version was a <1 second distributed grep of the whole Google codebase.)
I usually index any columns that are used in joins, or frequently used in predicates.
EDIT: JOINs
A run book for any org when writing queries should be
1) Write the query
2) Before shipping the query run the query through EXPLAIN. Did it scan or did it use an index?
3) If it scanned can you re-write it to use an existing index (the usual answer honestly).
4) Create 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.
It does take that into account. Demo:
=# CREATE TABLE low_cardinality AS SELECT generate_series(-10, 1000000) < 0 AS col;
=# CREATE INDEX ON low_cardinality (col);
=# ANALYZE low_cardinality;
=# EXPLAIN SELECT * FROM low_cardinality WHERE col = false;
┌─────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├─────────────────────────────────────────────────────────────────────────┤
│ Seq Scan on low_cardinality (cost=0.00..14425.11 rows=1000011 width=1) │
│ Filter: (NOT col) │
└─────────────────────────────────────────────────────────────────────────┘
(2 rows)
=# EXPLAIN SELECT * FROM low_cardinality WHERE col = true;
┌────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Index Only Scan using low_cardinality_col_idx on low_cardinality (cost=0.42..4.44 rows=1 width=1) │
│ Index Cond: (col = true) │
└────────────────────────────────────────────────────────────────────────────────────────────────────┘
(2 rows)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.
Well add the index anyway and add an extra 195ms sleep() call if you really want to. It's still better for your hardware and electricity bill.
I don't really understand how the downside of adding an index almost ever outweighs the potential downsides of not adding an index. I'm sure there are some cases, and that was what I was expecting to see in this article, but it just seems to boil down to being so lazy that he wants to avoid typing a few more characters.
The blog post can be summarized as "you don't need indexes on tiny tables".