15 ms·
A Tale of Query Optimization
- thomaswang 7y agoI think the root of your issue is the %text% leftsided % is horribly slow.
- zimpenfish 7y agoAddressed in the article: > The pattern matching query itself is taking only 5 seconds independently. Matching millions of unique URLs is clearly not a problem.
- thomaswang 7y agoAssuming it only loops once in the query yes, that's 5 seconds. But (and I'm guessing here) having it in the where directly leads to something like a n+1 issue for full tablescan/non indexed queries as a right or non anchored i/like quickly leads to without the propper index. What I'm meaning to say is that, the issue is not solved, it is simply worked around by narrowing down the set queried, not really postgres magic but usage of own data knowhow. I believe a Trigram index whould solve the issue at its root.
- manish_gill 7y agoThanks, I'll take a look at this approach.
- Someone 7y agoAs thomaswang says, that assumes that the query planner recognizes that it can hoist that query part out of the loop (https://en.wikipedia.org/wiki/Loop-invariant_code_motion https://en.wikipedia.org/wiki/Loop-invariant_code_motion) If it doesn’t, and runs it again and again, time will add up (possibly by less than 5 seconds for each time it gets run because the data could stay in memory) That theory was only disproved at “Move the sub-query into a CTE” section. Also, I’m not familiar with Postgres, so I don’t know whether it could significantly affect timing, but the query benchmarked at 5231.765 ms isn’t identical to that in the larger query. The latter has ::text[] added. I also would try and replace AND r_time > to_timestamp(1547585600) AND r_time < to_timestamp(1549177599) by AND r_time BETWEEN to_timestamp(1547585600+1) AND timestamp(1549177599-1) because the query optimizer might not detect that in this query.
- manish_gill 7y agoBETWEEN is soemthing that is on the "Don't do this" page of Postgres. :) https://wiki.postgresql.org/wiki/Don%27t_Do_This#Don.27t_use_BETWEEN_.28especially_with_timestamps.29 https://wiki.postgresql.org/wiki/Don%27t_Do_This#Don.27t_use... the ::text[] addition had no impact on perf. I actually constructed this post from my notes at the time so might missed have a few things here and there. The bit about query planner recognizing things is exactly what the challenge is to be honest. Like I said at the end, the good mental model of SQL helps a lot, and mine is decent-ish I hope but can still learn a lot. :)
- Someone 7y agoThat’s why I added the +1 and -1 fragments :-) I thought those computed the smallest larger/largest smaller time stamp. I didn’t realize that time stamps weren’t integers in PostgreSQL, though, so that is a bug. Are you sure your query, which uses an interval that is open at both ends, is correct?
- zimpenfish 7y ago> As thomaswang says, that assumes that [...] In a subsequent comment, yes; but in the original comment I responded to, there was nothing about the surrounding context, only (basically) "left % is slow".
- thomaswang 7y agoSorry to say, but I stand my ground. I believe it is the left % that is the root issue. As said without further explanation in my initial comment. (it's the same issue on almost every database, and I have never seen it not, being the main culprit, and the solution that never seme to fail is always index)
- vbezhenar 7y agoWith Oracle 9i query “name like ?” was never optimized to use index. Even when parameter was “pref%”, query took minutes. But with query “name like ‘pref%’” it used index and was lightning fast. So I had to rewrite my code from using prepared statements to manually escape and inline values. Felt weird!
- slifin 7y agoQuery optimisation is such an underated skill, imo it should be prioritised as a core skill for any backend developer
- jjeaff 7y agoIt seems there are a lot of new "lead" developers out their that don't even understand rdbms, much less how to optimize them. A lot these days seem to be coming into the field thinking that SQL is old hat and nosql is the future. You should see this newly rebuilt e-commerce system I saw recently all built on mongo. The hoops jumped through and special functions created and work-arounds were just astounding. They basically had to build their own rdbms layer in node to interface with their mongo datastore. All this because the new hotshot developer convinced management that this was the only way to solve the DB bottlenecks they were having. ...because "MySQL will just never be able to query the product table in less than a few seconds since it has 'millions' of rows". An entire system rewrite to solve a problem that probably could have been solved with a few indexes. And now they are going to have to implement some things in MySQL again, because all the node.js code is getting overly complicated.
- codegladiator 7y ago> "lead" developers out their that don't even understand rdbms Just lead ? I am interviewing "Full stack rockstars" who haven't who think SQL is unfit for every purpose. Frustrating, but a good filter.
- sovnade 7y agoThanks - good investigation. We're replatforming a legacy app from Oracle to Postgres in the near future and I'm sure we'll see stuff just like this. Definitely saving so I can refer back.
- gopalv 7y agoHaving hit this sort of problem too many times, I now recommend a DNS style FQDN in all my click-stream data. The domain stored as ".com.google.mail" etc. This breaks down a lot of these sort of queries with a simple enough '.com.google%' filter and which gets evaluated internally even on min-max zones. Gets turned into ">= '.com.google.' and <= '.com.google.\u0ff'" in byte comparisons. Even then it doesn't really help with the array syntax - because the condition doesn't get pushed there.
- blattimwind 7y agoArguably domain names written the way they usually are has been wrong since the beginning, for obvious reasons.
- jteppinette 7y agoOptimizing a large database (billions of rows) has been the bane of my existence over the last couple months. But, when you finally get that 10x / 100x performance improvement, it’s all worth it... until the next thing.
- kjeetgill 7y agoI've recently started working on a service with a MySQL database of a few billion rows. I'm used to developing on lower KVs like RocksDB or something. Any broad, general advice? Cool tricks you've learned? Bulk deletes and a relatively high continuous write rate are killing me right now. I kinda hate how manual batching deletes and then having to verify them takes.
- etaioinshrdlu 7y agoFewer, but larger queries/statements. Think about the query to add any indexes that may help. Less concurrency may help. I bet you have deadlock problems with high continuous writes and deletes... maybe you can queue or otherwise delay your writes and then insert with a single thread... Use a lower transaction isolation level if possible.
- ploxiln 7y agoDeleting lots of rows is perhaps the biggest weakness you are running into. What I do for some cases is "LIMIT 4000", sleep for 1 second, and repeat until no rows affected (tweak the numbers for your situation obviously) (usually this is for a periodic expiry/cleanup task).
- _vertigo 7y agoIt’s probably worth mentioning that at least in MySQL, this is dangerous if using statement based replication. https://dev.mysql.com/doc/refman/8.0/en/replication-sbr-rbr.html#replication-sbr-rbr-sbr-disadvantages https://dev.mysql.com/doc/refman/8.0/en/replication-sbr-rbr.... https://dev.mysql.com/doc/refman/8.0/en/replication-features-limit.html https://dev.mysql.com/doc/refman/8.0/en/replication-features...
- AaronFriel 7y agoI wonder if a CTE with both sets and `intersect` between them would be more efficient than &&.
- manish_gill 7y agoThis is something I didn't consider. Will definitely try it out. Thanks!
- jteppinette 7y ago> https://www.postgresql.org/docs/11/queries-with.html https://www.postgresql.org/docs/11/queries-with.html The optional RECURSIVE modifier changes WITH from a mere syntactic convenience into a feature that accomplishes things not otherwise possible in standard SQL. Am I incorrect in thinking that "standard" CTEs don't have an impact on performance. When I saw this in the article and how it had no performance improvements it reaffirmed my assumption.
- wolf550e 7y agoPostgreSQL materializes all CTEs so it has a big impact on performance. It's a hack that works around lack of optimizer hints in PostgreSQL to force the execution plan you want. Only in PostgreSQL 12 did they change this: https://www.postgresql.org/docs/devel/release-12.html#id-1.11.6.5.5.3.4 https://www.postgresql.org/docs/devel/release-12.html#id-1.1...
- jteppinette 7y ago> https://dba.stackexchange.com/a/13117 https://dba.stackexchange.com/a/13117 Also, a CTE should never be used for performance. You will almost never speed things up by using a CTE, because, again, it's just a disposable view.
- wolf550e 7y agoInformation about SQL in general should not be confused with information about specific RDBMS. That SE answer is about MS SQL Server. What I wrote was specific to PostgreSQL which does a specific weird thing using CTEs where they are materialized. In SQL Server, CTEs are not materialized and are just used to organize the query, to make it more readable. If I wrote about PostgreSQL heap organized tables, would you object and say I'm wrong because MS SQL Server tables are index-organized, clustered on the primary key?
- jjluoma 7y agoI find this a little bit funny, > I was extremely suspicious of the EXISTS optimization, since it changes the logic to exit early. Does this this mean that if one has found an answer, it is somehow sensible thing not to return the answer right away?
- abraae 7y agoWith a database, that depends if you want "all the answers" or "any answer". Exists is the latter.
- ccleve 7y agoIt isn't clear to me why so few of these optimization articles talk about temporary tables. They are my go-to solution for many situations. Temporary tables are great because they break the problem down into smaller pieces. They make the query much more understandable. They are way easier to debug. They are way less sensitive to failing because the query optimizer decides to do things differently because table statistics have changed. They will often eliminate the need for exotic syntax. You also have the opportunity to add secondary indexes to these tables. When you create a temporary table, you are essentially doing the work of the optimizer yourself. That's perfectly ok if you know things about the data that the optimizer doesn't or hasn't successfully figured out on its own. They're not for every situation; they only work well when the intermediate tables are small and fit in memory. But that is very frequently the case.
- whitehouse3 7y agoOne reason you may not see CTE's or temp tables included in these articles is because their specifics are tightly coupled to the schema of your DB. It's hard to write a generic example in Stack Overflow that would work for someone else. But like you said: if you know the DB schema then temp tables make SQL easier to read, write, and reason about.
- malisper 7y agoI can definitely relate to the struggle of debugging slow SQL queries. I've been optimizing Postgres for the last three years for my day job. There's nothing like spending hours trying to determine why a query is slow, only to discover some bizarre incantation makes the problem go away. I had one case where adding OFFSET 0 to a query, which did not change the semantics of the query, made the query ~10x faster. It turned out that due to a reference to a large column being inlined in a dozen different places, Postgres was detoasting[0] that column a dozen times more than it needed to. Adding the OFFSET 0 prevented the subquery from being inlined and made it so Postgres only detoasted the column once. In general, I think optimizing a database is way harder than it needs to be. A lot of it is black magic and it requires a ton of expertise that many teams don't have. Even though I've been doing it for years, I still struggle with figuring out what indexes I should create to make a query fast. I recently started a startup in an attempt to make optimizing databases easier. I built a Postgres extension that records information about queries as they run. It's basically the same information you would get for EXPLAIN ANALYZE, but you get it for every query at query time. Then, using this information, I'm able to make specific recommendations about how you should optimize your database. I can give advice on how you should structure your schema and what indexes you should create in order to maximize the performance of your queries. This way, even teams that don't have much in-house Postgres experience won't have to spend hours or even days trying to figure out how to make their queries faster. If this sounds interesting to you, I would be happy to chat. You can reach out to me at michael@perfalytics.com. It's my goal to use the expertise I've built up over the last couple of years to make scaling Postgres a truly painless experience. [0] https://malisper.me/postgres-toast/ https://malisper.me/postgres-toast/
- ChrisSD 7y agoIsn't there some irony in fact that SQL was meant to abstract away the "how" of getting records? If you need to optimize through implementation specific quirks, then wouldn't a more direct api be preferable?
- Shorel 7y agoAll abstractions can be a bit leaky. That doesn't make them useless.
- davidgould 7y agoThis article could be improved by including the Postgres EXPLAIN output so the reader could follow along the deductive process.
- web007 7y agoIm confused - did they not EXPLAIN their query? That's the first step in ANY slow query debugging! I kept waiting to see EXPLAIN output so I could say "oh, there's your table scan" and nothing ever showed up.
- coleifer 7y agoUnbelievable that this is even getting upvotes. Anyone with a basic understanding of relational databases could see that nested o(n) ilike filter was the problem. I kept reading in the hopes that maybe something actually interesting was going on, besides ineptitude. Disappointing. When you have a huge list like that in a filter, the answer is to treat it like a table and perform a join. Then the query planner can optimize the ordering of the loops. But this is just mind-boggling ignorance dressed up as a "debugging horror story".
- FrancoisBosun 7y agoYou know about such trick, others may not. I loved this article for the thought process, not for the nested loop error.
- jdreaver 7y agoGet over yourself. This is a well-written article in which the author lays out their thought process for optimizing a slow SQL query. The article certainly provides more value to someone who may not be an RDBMS expert than your comment does.
- michaelmcmillan 7y agoThen, for a small subset of data, I manually verified that all results were correct. Where’s your test suite man? :)
- perlgeek 7y agoThe frustrating thing about such optimizations is how badly they fit with the rest of the software development and testing workflow. Ideally, you want to write a test that prevents a performance regression, but then you need to set up a test database with the right data characteristics (but not real data, for privacy concerns), need the hardware to handle that, need to maintain that database through future schema changes and so on. It would also be nice to have some kind of mechanism that can tell you that the optimization is no longer necessary when you switch to a new DB version with an improved optimizer. Most organizations don't have the engineering capabilities or capacities to provide this kind of tooling and infrastructure, so the benefits of CI/CD often don't apply to such changes.
- fabian2k 7y agoI'm a bit confused why they didn't use EXPLAIN ANALYZE at all in this case. Debugging performance issues in Postgres without it makes it unnecessarily hard. I'm not entirely sure without being able to try it myself, but I suspect it should have immediately identified in sufficient detail where most of the time in that query was spent .
- ComodoHacker 7y agoA funny bit: >I started googling for a way to do set-intersection in Postgres without using the && and it wasn’t going anywhere. That's what SQL was made for! It's called 'join'. Perhaps is wasn't the best idea to store session's urls in an array and not in a table. (It's called normalization.)
- ddebernardy 7y ago> Then, for a small subset of data, I manually verified that all results were correct. This could have been automated with a full join. with A as queryA, B as queryB select A full join B on all applicable fields where A is null or B is null. Alternatively, you could also do: A except B union all B except A. Either way you get the rows in A that aren't in B and rows in B that aren't in A -- no manual check needed, and you could have run that on the entire set instead of or in addition to counting rows.
- superjisan 7y agoThis is pretty great. I've been meaning to find a good story and helpful guidelines for making queries faster as I taught students about SQL.