12 ms·
Use SQL subqueries to count distinct 50x faster
- mattmanser 13y agoSQL what? MySQL? SQL Server? Postgre? Oracle DB? SQL Lite?
- troels 13y agoThe very first paragraph on the page says: NB: These techniques are universal, but for syntax we chose Postgres. Thanks to the inimitable pgAdminIII for the Explain graphics.
- alexchamberlain 13y agoI agree this is extremely important; every optimiser is different!
- brazzy 13y agoI disagree; the article is essentially about manual query optimization. Theoretically, a great optimizer could do this by itself, but the fully optimized query will run the same way pretty much everywhere; query execution engines are not very different, basically grace hash joins and B-trees.
- falcolas 13y ago> the fully optimized query will run the same way pretty much everywhere This is not correct. The query will still be run through an optimizer, and the optimizer will still pick its own path of execution based on indexes and data uniqueness (as identified from the table metadata or its own dives into the data). There are ways to force an optimizer to take a certain path, but those are dependent on which DB you're using. Unfortunately, the original dataset doesn't exist online, so we can't verify their claims that it really is database agnostic.
- buckbova 13y agoAnd then there are table statistics or fragmented indexes that cause the optimizer to choose a different path. Even when you've done everything and you think the optimizer should choose a particular index it will surprise you.
- corresation 13y agoAs I detailed elsewhere, the problem with this assumption is that you are one-off optimizing by encoding metadata about the data in the query. So while this specific query has been made more optimal, the underlying problem with the database remains, and thus you will invariably face and then have to work around the same problem numerous times. Or more often one won't because the legacy of hundreds of slow but not terrible queries accumulate. It becomes a death by a thousand cuts, which is the end result of many heavily used databases. My example in SQL Server sees the simple addition of a single distinct index to give that same metadata to the query planner, yielding the identical plan for the first and last. And this same benefit will flow to every query that follows the same path.
- jeroen 13y agoStructured Query Language See wikipedia: https://en.wikipedia.org/wiki/SQL https://en.wikipedia.org/wiki/SQL
- joevandyk 13y agoIn PostgreSQL, you can use CTEs to force certain subqueries to run before others. That technique would be useful here, and would clean up the code a bit.
- bgilroy26 13y agoI didn't know what Common Table Expressions were. I had always called them WITH queries. It's good to learn the name. http://www.postgresql.org/docs/8.4/static/queries-with.html http://www.postgresql.org/docs/8.4/static/queries-with.html
- brunnsbe 13y agoCTEs are found in SQL Server as well: http://technet.microsoft.com/en-us/library/ms190766(v=sql.105).aspx http://technet.microsoft.com/en-us/library/ms190766(v=sql.10...
- pradocchia 13y agobut CTEs in SQL Server are not an optimization boundary like they are in Postgres. This makes a big difference in their proper use. In SQL Server, aside from recursion, CTEs are purely syntactic sugar and thus a tool for organizing code. Whereas in Postgres, due to the optimization boundary, they are a tool for query tuning. If you rewrite a query in Postgres using CTEs just to clean it up, you are doing it wrong, since the CTEs will also affect the planner.
- radiowave 13y agoRight, but that's assuming that performance is the most pressing constraint. Sometimes it's confidence in the query producing the right result, or maintenance further down the line.
- atwebb 13y agoAm I incorrect in stating that this isn't necessarily true? Just because a statement is earlier in a script doesn't mean it will be optimized first.
- tomaac 13y agoIs there any reason why would one Start Every Word In Sentence With Capital Letter? I find it hard to read. Sorry for offtopic.
- sleepyhead 13y agoBy 'every word' you mean 'every word in the subheadings'?
- simonw 13y agoTitle Case is still very common in the USA (see http://www.nytimes.com/ http://www.nytimes.com/ for an example, their house style is to use it for all of their headlines). You hardly ever see it in the UK these days.
- damien 13y agoThey're headings, not sentences...
- freeman478 13y agoI find it disapointing that the optimizer of the database is not able to get to the fastest result by itself. A broken promise of declarative languages I guess.
- joevandyk 13y agoI wish more people were working on planner optimization/stats. It's a hard problem though, I know I'm nowhere near smart enough for it.
- saosebastiao 13y agoI don't think it is a matter of intelligence, just skillset. Query planners could go a long way with a few people with strong relational logic skills that could prove logical equivalence of expressions.
- lvh 13y agoThe declarative language promise was that it would be possible to perform such optimizations. Indeed, by-and-large, query planners do a pretty great job. I don't think it was ever a promise that query planners would be able to always find the fastest query for what you want.
- jerf 13y agoI read the declarative language promise as you will never have to know what's going on under the hood. This is never true in any non-trivial declarative language being used for non-trivial work. I have developed a very negative initial reaction to anything that claims to be "declarative".
- Pxtl 13y agoLikewise. The more declarative a platform is, the more I'm trusting its abstractions to never leak, because when I do I'm going to have to learn every agonizing minute detail of how it works under the hood. SQL is a tiny kernel of beautiful relational mathematics wrapped up in a 3-foot ball of ugly implementation hacks. NoSQL is what happens when you throw out the beautiful kernel and just keep the hacks, so it's not really better I guess.
- dasil003 13y agoVery nice first blog post. Definitely caught my attention right away and made me curious about the company.
- brazzy 13y agoAn email subscription function for blog updates but no RSS or Atom feed? Seriously?
- Jailbird 13y agoOn the assumption that aside from publishing some useful information, the blog post is also meant to drive awareness for Periscope... even a small landing page with some expected features or more information about the product-to-be would be a good idea. (I saw the one-liner at the bottom of the post but would suggest a bit more to pique the interest of more people. If I missed it, my apologies.)
- sehrope 13y agoIf the author is reading please post the EXPLAIN ANALYZE results for these queries. I'd much prefer the raw text psql output to the GUI representation in pgAdmin. More importantly it has the actual numbers for the intermediate steps to see which is the culprit. Also, any idea how many times each variation was executed? 10M rows is not that big. At 1K per row (which is probably an overestimate) that comes out to 100 MB. That easily fits in memory. After the first full scan all of it would come from the cache. It's not a fair comparison unless you flush the cache between tests.
- hglaser 13y agoOP here. It's no EXPLAIN ANALYZE, but here are the EXPLAINs at least. The originals were averages of 10 runs. These EXPLAINs are just quick runs on my laptop, so no promises. :) First query: QUERY PLAN ----------------------------------------------------------------------------------------------------- Sort (cost=3475858.60..3475859.56 rows=385 width=22) Sort Key: (count(DISTINCT time_on_site_logs.user_id)) -> GroupAggregate (cost=3370756.94..3475842.06 rows=385 width=22) -> Sort (cost=3370756.94..3405784.03 rows=14010837 width=22) Sort Key: dashboards.name -> Hash Join (cost=44.90..558337.80 rows=14010837 width=22) Hash Cond: (time_on_site_logs.dashboard_id = dashboards.id) -> Seq Scan on time_on_site_logs (cost=0.00..365621.11 rows=14016911 width=8) -> Hash (cost=29.40..29.40 rows=1240 width=22) -> Seq Scan on dashboards (cost=0.00..29.40 rows=1240 width=22) (10 rows) Second Query: QUERY PLAN ----------------------------------------------------------------------------------------------------- Sort (cost=2709630.36..2709631.09 rows=291 width=26) Sort Key: (count(DISTINCT time_on_site_logs.user_id)) -> Merge Join (cost=2604392.06..2709618.45 rows=291 width=26) Merge Cond: (time_on_site_logs.dashboard_id = dashboards.id) -> GroupAggregate (cost=2604392.06..2709521.80 rows=291 width=8) -> Sort (cost=2604392.06..2639434.34 rows=14016911 width=8) Sort Key: time_on_site_logs.dashboard_id -> Seq Scan on time_on_site_logs (cost=0.00..365621.11 rows=14016911 width=8) -> Index Scan using dashboards_pkey on dashboards (cost=0.00..87.00 rows=1240 width=22) Third Query: QUERY PLAN ----------------------------------------------------------------------------------------------------------------- Sort (cost=436381.86..436382.36 rows=200 width=26) Sort Key: log_counts.ct -> Hash Join (cost=436308.72..436374.22 rows=200 width=26) Hash Cond: (dashboards.id = log_counts.dashboard_id) -> Seq Scan on dashboards (cost=0.00..29.40 rows=1240 width=22) -> Hash (cost=436306.22..436306.22 rows=200 width=12) -> Subquery Scan on log_counts (cost=436302.22..436306.22 rows=200 width=12) -> HashAggregate (cost=436302.22..436304.22 rows=200 width=4) -> HashAggregate (cost=435705.66..435944.28 rows=23862 width=8) -> Seq Scan on time_on_site_logs (cost=0.00..365621.11 rows=14016911 width=8)
- taspeotis 13y agoIt would be useful if the data was loaded into different RDBMS' and their execution plans compared. My understanding is that MySQL has the worst query planner and Oracle the best. MSSQL sits somewhere in between, near PgSQL but better in a few areas. I think MySQL basically gives up optimizing the moment you ask it to do a correlated subquery. I use MSSQL at work and given it some really dumb schemas and really dumb queries and it still manages to pick good plans. It wouldn't surprise me if MSSQL generated the "optimal" plan from the first query. It doesn't choose good plans if you break 3NF by a long shot or avoid the most obvious indexes. Otherwise the only thing to watch out for is stale stats and parameter sniffing. Oracle 12c has adaptive plans which would be a great addition to MSSQL in the fight against parameter sniffing. Basically it figures out that it's probably got the wrong plan ("this nested loop join stopped making sense about 10,000 rows ago") and adjusts it accordingly. Again, wouldn't be surprised if Oracle got it "right" from the first query.
- michaelmior 13y agoHistorically the MySQL query planner has been pretty bad, although it's improved significantly in the past couple years. It was particularly bad dealing with subqueries as you mentioned, although several of the performance issues have been solved in MySQL 5.6. https://mariadb.com/kb/en/subquery-optimizations-map/ https://mariadb.com/kb/en/subquery-optimizations-map/
- falcolas 13y agoYup, this. Of course, it hurts that there are probably less than 10 people in the world who fully understand the optimizer (and the majority are employed by Monty); though I'm sure the MySQL folks at Oracle are getting there.
- pradocchia 13y agoI agree with everything you've said, however I want to add that the general technique of compressing your data through pre-aggregation is a sound one, whether it is performed auto-magically by the optimizer, or manually through whatever hooks your DMBS provides.
- Shivetya 13y agoAnyone have the table layouts they are using? I was going to attempt to run them through Visual Explain which is the tool I use on the iSeries which employs DB2. A simple analysis over a very rotten table, doing a count(distinct) over a very varied field resulted in Table Scan -> Temp Distinct Hash Table -> Hash Scan -> Final Results (330.022 ms) for a table with no keys and slightly over three million records. I would love to do the same exact statements he is but need the table layout to replicate. I am curious if our analyzer would see a difference, it is really hard to "trick it" or beat it.
- aritraghosh007 13y agoAmazon RedShift (based on Postgres) has an approximate function that can be used to return results faster while calculating distinct values from a large table with an error approximation of +2% (http://docs.aws.amazon.com/redshift/latest/dg/r_COUNT.html http://docs.aws.amazon.com/redshift/latest/dg/r_COUNT.html). To give some perspective, we ran a test query on a RedShift table with > 900 million records to fetch unique user id's. With the approximate function applied, the results were returned in 8 seconds while it took the usual distinct query 51 seconds, ~84% faster !
- morgo 13y agoMy understanding is that it just implements the postgres protocol, its query planner is now completely different. "ParAccel's DBMS engine is built for analytics, initially based on PostgreSQL" -> http://en.wikipedia.org/wiki/ParAccel http://en.wikipedia.org/wiki/ParAccel
- corresation 13y agoI love that they're discussing this, and kudos to them, but unless the specific details are described (e.g. "and there are lots more log lines than dashboards and users" - what does that mean? That dashboard_id is nullable and many rows log entirely different things? That would be a significant problem unto itself. What is the cardinality of users, dashboards, and sets thereof), it's hard to really take much from it. As a general recommendation I advise database developers to avoid exactly this sort of "outsmart the planner" behavior because it paints you into a corner -- data cardinality changes, schemas change, and you have large, clever queries that turn into a significant net detriment. They can absolutely be necessary in some cases, but this does not look like one of them.
- pradocchia 13y agoI think this was more an exposition on the general technique than specific recommendation. The general theme should be, "how do I make my database do less work?" followed by a list of techniques, including "pre-aggregate to reduce volume". In this case, the pre-aggregates are in-line. Whether in-line pre-aggregates are appropriate will depend on context, just as you say.
- jeffdavis 13y ago"As a general recommendation I advise database developers to avoid exactly this sort of "outsmart the planner"" Probably wise in general. This particular case is peculiar because postgres doesn't optimize distinct aggregates at all (see my other comment: https://news.ycombinator.com/item?id=7115707 https://news.ycombinator.com/item?id=7115707 ), so it's possible that the rewritten query is actually more optimizable than the original. The original query won't adapt to changing data sizes or distributions as well as the rewritten one. This is not fundamental, nor universal. It's a specific limitation of postgres, so I still agree with your general advice. And postgres may fix this, so your advice may prove to be true even in this situation in the long run.
- np422 13y agoSince they are using postgresql, it might be relevant to know that count distinct have for a very long time been a weak spot for pg. Since release 9.3 index-only scans have been implemented and performance of count distinct queries improved significantly - no more full table scans. Wiki page: https://wiki.postgresql.org/wiki/Slow_Counting https://wiki.postgresql.org/wiki/Slow_Counting It would be fun to have access to the same dataset or a more detailed description of the tables involved for further tinkering ....
- Fishkins 13y agoJust a nit pick, but index-only scans were added in 9.2 https://wiki.postgresql.org/wiki/Index-only_scans https://wiki.postgresql.org/wiki/Index-only_scans
- bottompair 13y agoThis is why heavy ORM's like Hibernate are only good for the most simplistic (and tiny data) use cases. Every situation I've been in where queries can't be optimized appropriately for specific use cases like this involve engineers who "don't do Sql" and have made heavy use of something like Hibernate. Then scratch their heads when dashboards take minutes to load. The next step is usually to jump into a column oriented data store, document store, or some other technology they understand even less than Sql.
- markkanof 13y agoYou seem to be calling out Hibernate as the problem, but really the problem is the developers that either don't understand or refuse to interact with a major component of their application (the SQL database). A good ORM will make CRUD actions quick to implement and will get out of the way when more complex queries are needed.
- bottompair 13y agoTrue. Hibernate isn't really the issue - more the existence of Hibernate sometimes creating lazy engineering. I guess I'm old school - my preference (even with simple CRUD) is to build the queries myself if nothing else to avoid object models in code being translated into often flawed data schema by the ORM (if you happen to let your ORM create database objects for you). Even with simple CRUD I've had to unwind faulty implementations where a smallish (50GB) database was being eager fetched into memory because of poor ORM config and overuse of FK relationships - when a user did something as simple as logging into the app. And I'm not talking junior developers - some of these guys were 10+ years at Amazon.
- BigTuna 13y agoI've been rattling my cage about this problem for a few years now. There's room and need for an "ORM/DBA" position in our industry. Most of the common production packages are both complex and flawed enough to justify a full time position, and yet I've seen so many companies lose hours of productivity floor-wide because the dev group's [N]Hibernate knowledge has been pressed beyond its limits.
- ionforce 13y agoThis technique seems quite obvious... You would only write the first query if you didn't know what you were doing. So... The advice here seems to be, know what you're doing.
- squintychino 13y agoIf you're someone who doesn't know what they're doing, then this wouldn't seem quite obvious, would it? So this post is probably not meant for you, but rather for people that are not as experienced in SQL. This logic seems quite obvious...
- saosebastiao 13y agoIs there any relational logic reasoning that would prove that the query planner couldn't theoretically optimize the first query into the execution plan of the third?
- platz 13y agoI'm curious if the optimizer in MS SQL Server handles this better.
- 727374 13y agoMy first thought when reading this was that MSSQL (which i'm most experienced with) would automatically optimize this query. I'd think postgres can too. If I saw this happen in MSSQL I'd start by clearing the statistics for the table. My second thought was that 20 seconds is a long time for a query and there's probably a better solution using a materialized view.
- corresation 13y agoOP - Can you please run your original query with a minor variation- select dashboards.name, count(distinct time_on_site_logs.user_id) from time_on_site_logs join dashboards on time_on_site_logs.dashboard_id = dashboards.id group by time_on_site_logs.dashboard_id, dashboards.name order by count desc
- hglaser 13y agoGood idea. Times are from my laptop, which is less beefy than the test rig we used: First query: 996s First query with your variation: 593s Second query: 67s Third query: 21s
- corresation 13y agoDo you have a FK from dashboard_id to dashboards.id by chance? I assume no, as the query is presumably still forced to do an early existence test of the inner join before aggregating.
- wcummings 13y agoYou need not look further than this to understand why denormalized data is crucial for High Availability/Low Latency applications.
- chris_wot 13y agoSo much for SQL being an declarative language. Whilst I'm impressed, I'm curious why the query optimizer can't pick up this as an optimization.
- yeukhon 13y agoI wonder how efficient ORMs out there doing. My believe is that once performance profiling is done, and the crucial bottleneck is identified, people will replace the original call to ORM with a custom SQL query. But heck, sometimes db language driver (like pymongo, python-mysql - just giving out example what I mean by language driver) are not optimized either. :) so a careful post-profiling analysis is required.
- j-kidd 13y agoWith SQLAlchemy, I have done similar optimizations against mssql by changing a few lines of ORM code. Without SQLAlchemy, I imagine I'd have to change dozens of hand written SQL queries. A good ORM helps you to generate the exact SQL you need.
- yeukhon 13y agoI am really surprised that you are using SA as ORM on MSSQL (sorry, since I don't touch mssql :) and most people I deal with are either MySQL or Postgres users). > A good ORM helps you to generate the exact SQL you need. Right, but sometimes it's the driver that behave badly. (One of those days when I claim to have free time I should dig deeper, do a good performance analysis.. one day...)
- besenthil 13y agoDB2 9.7 optimzer doest this as part of query optimization