Results of the SQL Performance Quiz
use-the-index-luke.com
use-the-index-luke.com
I don't think it was guessing so much as reasoning that fetching 100 rows (and filtering by value) instead of 10 rows doesn't have significant real-world impact unless the row data is particularly large. I'll admit I didn't think of the out-of-index lookup, but my main thought was 100/1000000 vs 10/1000000 isn't a big deal unless the DB is running on an abacus.
Edit: In other words it was 100 or 10 aggregated rows. A extra WHERE clause will change the values of each of the rows rather than just filter the rows from 100 to 10. (Which a HAVING clause would do.)
It's called a covering index.
The trick is the fact that the GROUP BY means that "It used to return 100 it now returns 10" is a red herring, it still has to read every row to make up those 10.
SELECT date_column, count(*)
FROM tbl
WHERE a = @a
AND b = @b
GROUP BY date_column;
SELECT a, date_column
FROM tbl
WHERE a = @a
SELECT a, date_column
FROM tbl
WHERE a = @a
AND b = @b
http://dev.mysql.com/doc/refman/5.0/en/group-by-optimization...
> The GROUP BY does not begin with the first part of the key, but there is a condition that provides a constant for that part:
> SELECT c1, c2, c3 FROM t1 WHERE c1 = 'a' GROUP BY c2, c3;
If we're told that:
SELECT a, date_column FROM tbl WHERE a = @a
Returns 100 rows.
Then:
SELECT a, date_column FROM tbl WHERE a = @a AND b = @b
Will only have to scan column b over 100 rows.
Even without an index that will always be neglible, not compared to using the index to grab 100 rows from 10million but just compared to running a query and returning results at all.
The reason that the original can be a lot slower is that the 100 and 10 rows of results are comprised of a lot more rows of actual information, because of the grouping.
You're right that:
SELECT a, date_column FROM tbl WHERE a = @a AND b = @b
would be a lot slower, given the same data, but that isn't the scenario, the group by has implications about what "returns 100 rows, returns 10 rows" actually means in terms of data read.
Query 2 will perform the same index seek but will need to do a key lookup on each row and filter.
It's not negligible. The 100 results are not comprised of a lot more information in this case, regardless of the grouping, because the 1st query does not access the table.
Edit:
I happen to have a table laying around with a little over a million rows and set up a similar set of queries.
The query optimizer suggested the index seek taking 6% of total operation time while the key lookup taking up the other 94%. The rest was negligible.
I didn't think about the fact that the original one was an index-only scan, so went with "Roughly the same", since outside of that property the performance is similar.
Too bad there is no way to get good data on why people thought that way without a much longer quiz.
It is already a highly selective query. Adding a 100 bookmark lookups will not cause a material change in performance, unless this query is being executed 1000s of times per second, in which case maybe your real problem lies elsewhere.
Is it? The first query is always O(1). The worst case for the latter query is that it must aggregate over 999,910 rows.
Consider the case where all values of 'a' are 123, and all values 'b' are 42, except 90.
Indexing shouldn't follow the theoretical worst case, it should follow what's actually in your table.
Regarding O(1), the first query would be some form of O(n log n) or O(log n) depending on the table/index data structures.
In this case, I take n = 1,000,000
The first query is likely O(log(x)) where x is number of distinct values of a. I approximated that to be O(1) relative to n.
I could be wrong here, or we could have seen different questions, or we are just interpreting the question differently.
I hope no optimizer would say that. It is well defined that filtering, as expressed in the where clause (if it uses indexes or not) happens before group and aggregate, and that grouping happens on the result of the filtering. If the optimizer could choose one way or the other, you'd have different results. If you want to group and aggregate first, you need to explicitly express that with a subquery.
At least on MSSQL, I would expect a query plan like so:
1. Index seek WHERE a = 123, yielding ~100 rows. [1]
2. Bookmark lookup with results from (1), yielding ~100 rows.
3. Filter (2) WHERE b = 42 and project date_column, yielding ~10 rows.
4. Aggregate (3) by date_column, yielding ~10 rows or less.
[1] Important caveat. I interpret this line,
Current situation, selecting about hundred rows out of a million:
....to mean selection of 100 rows from the base table, rather than projection of 100 rows in the result, post-aggregation.
But if he really means a SELECT statement that returns 100 rows, then we have no idea how selective the WHERE clause is, and my answer changes to "The query will be much slower (impact >10%)".
No, it already said it only took 100 rows, it can't get worse from that.
Now if he actually meant the final result set was 100 rows (meaning after the group by) that's different. But that's not what he actually said, so the question is misleading.
Such 100 random IOs will cost 0.5 sec on 1 iron platter HDD for example. So the query performance will degrade significantly until either the table is already preloaded into memory or you use SSD drives.
That's an incredibly, incredibly, iffy and mostly wrong statement which depends on arguably a corner case which doesn't often reflect reality (factors include which DBMS, row ordering, table size, cache size, block size, page size, RAM size, Hard Disk seek time, HDD throughput.
The only case where that's likely is performing a very cold query on a very large randomly distributed table once (and probably only once).
Even a table of 1 million rows with ~30B per row could easily be read into memory in about 300ms (100MB read time + ~5ms seek time, or ~= 5+(1e6*rowsize/ (100e3)) )
Query Optimizers do exactly this.
>That's an incredibly, incredibly, iffy and mostly wrong statement which depends on arguably a corner case which doesn't often reflect reality (factors include which DBMS, row ordering, table size, cache size, block size, page size, RAM size, Hard Disk seek time, HDD throughput.
you're welcome to specify iron platter HDDs which would do 100 random IOs in significant different time than 0.5 sec.
>Even a table of 1 million rows with ~30B per row could easily be read into memory in about 300ms (100MB read time + ~5ms seek time, or ~= 5+(1e6*rowsize/ (100e3)) )
>Query Optimizers do exactly this.
Not always. If it has enough info, it may take a full table scan path in such a case. Still it will be about the same time - 300ms vs. 0.5 sec. i mentioned.
Of course it is for cold queries. You forgot to mention, i guess, that full table scan you propose may by-pass DB cache (default depends on DB, modern tendency is by-pass by default), and thus second query will take the same time, while table blocks brought in by random IO would frequently be stored in DB cache thus making second query run somewhat faster - depends on how much data was brought in.
To be frank, knowing the difference in how to write an inner and outer join when given a three table schema and a desired output is a frightening filter of candidates. Having an instinct that some type of index could help a query probably makes you a db wizard.
Even just asking for a basic understanding at the "use this to look up that" level -- since SQL syntax is easy to learn if you know what you want, and whoever does the recruiting has taken to mostly finding us new college graduates -- filters out an absurd number of candidates.
I guess it's the same thing as makes FizzBuzz a useful question.
Sure, I write a SQL query now and again, but if I have to join I look it up. I don't do it a lot. If I had to do it a lot for you, I would learn it inside out.
If I told you I was a DB wizard, then sure, I better already know how to join. But I know tons of people that don't really do SQL. They are eminently hire-able and valuable.
source: a guy (me) who was bounced out of an interview because he didn't recall some specific detail about boost::shared_pointer().
I think at this point, most HN'ers would accept that a work sample test (of some limited scope and effort) is a better test than any interview question or whiteboard coding process. From that perspective, no question is really a good one. Unfortunately, at my workplace, there are strict rules in place specifically prohibiting this type of applicant process.
Remember the promise of a "declarative language" where you just had to tell it what you want, and it took care of the details?
This quiz is about performance tuning, not correctness. For plenty of valuable real-people use cases, it's plenty fast without any performance tuning.
Honestly though the nice thing about SQL is you can quickly get something that works, and then use tracing tools to figure out what is taking longer than it should.
You could argue CSS is a failure, because designers don't know that
#sidebar .widget
.widget
http://stackoverflow.com/questions/5797014/why-do-browsers-m...
How can you apply a blanket "premature" to this? The questions are simply "can this be improved?". There's nothing premature about it, it is a quiz.
"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." --Donald Knuth
I am not sure what the exception is about. I agree 100% with the rest of your comment.
Think of the first question. If you're going to use a function to transform data, you're going to take a performance hit vs. just doing and indexable operation against the data.
If you want a facility that will magically figure out what you want when you are unable to express what you want, good luck. That's unicorn territory.
"On two occasions I have been asked, 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question." ~ Charles Babbage
It's like calculus, you can compute efficiently or inefficiently it has nothing to do with calculus.
The same developers that make retarded SQL queries make god awfully slow programs with their pointer chasing mess because they don't understand that their programs run on actual real hardware and that a cache miss is pretty much the single most expensive operation a modern CPU can make by 2 to 3 orders of magnitude.
They just go on and on about interfaces, inline methods, virtual methods, etc, and never check whether their fancy smancy object fits on a cache line. Its the same with databases they just talk about 'webscale' and 'big data' abandon SQL and then wonder why their DB explodes once it reaches 100 GB.
There were other query languages that were less of a messy compromise. QUEL, for example was based more rigorously on relational calculus. I think it never took off because the dumbed-down SQL was a little easier for programmers to conceptualize initially.
Fortunately I've landed pretty good jobs in spite of employer myopia, and work for a SV salary and a SV company though I live in a non-tech town in North Carolina. Just venting a frustration.
I'm surprised people didn't score better on this, it's a very simple concept. :-/
Most troubling to me was how people who chose the MySQL option did so much worse than pretty much every other database. (I took the MySQL option, even though I work on MS SQL these days, and got 4 out of 5.) I suppose for people who consider MySQL to be a toy RDBMS, that's less "troubling" than "confirming current perception."
But yeah, I was kind of surprised that he was surprised about why PostgreSQL folks failed: they just didn't think about whether the index was optimal.
They both have about 50M rows, with statistically identical data. I was running near-identical large queries on both, with the same execution plan (nested-loop join with index lookups), and getting vastly different timings.
This being a staging environment, these tables are re-populated by truncating them and running an ETL tool. What turned out to be happening, is that in one case the source query on the ETL tool was sorted by the foreign key, and in the other it wasn't. So in one case all those fetch-by-index-lookup operations added to to essentially a partial table scan, and in the other they added up to what you'd expect where blocks would be fetched in random order and probably re-fetched after falling out of cache.
Although I worked a lot with SQL in past, I think good knowledge of only a NoSQL system (e.g. GAE Datastore) would give you enough understanding of how simple indexes are, and how to deal with them to pass this pure SQL test.
Would like to hear a feedback from someone with only NoSQL experience after taking that test.
A = X + (1 - X) / 2
2A = 2X + 1 - X = X + 1
X = 2A - 1
X = A - 0.5
The correct lucky guess fraction (amount of the right answers to discard) is:
A - X = A - (2A - 1) = 1 - A
doing Map reduce with non of your fancy pants hadoop malarky
Ps and we had to build our own build system using CPL (prime JCL)
SQL's syntax is ugly because it was designed in the 70s where some people had quite different ideas what a DSL should look like (hey, COBOL, you are guilty, too!)
They're a pain in the ass.
Don't get me wrong, I have no problem with SQL as such but it has some shortcomings. Probably most things can be blamed on its age.
Why is the syntax of INSERT and UPDATE statements unnecessarily distinct? They do almost the same thing. Why are the values and column names in the INSERT statements' syntax separated and not with an UPDATE statement.
Why are there keywords that consists of more than one word? (Maybe the same ill-guided idea as with COBOL that being able to "read" SQL would make it easier to write/maintain?)
The syntax of SQL is in many places not tight enough, so you often have to hunt down a missing comma or typo, because the SQL parser is just not able to find out what you've done wrong.
I think the whole readable natural language premise is a neat idea, but much in the same way that natural language can be easily complicated, so too, with SQL. Heap abstractions of logic and arithmetic on top, and it gets even worse. But it's still a cool idea. If it works out in your favor, you'll get self documenting code. But alas, there is no floor or cieling to the complexity one can introduce, be it deliberately or accidentally. And not only is it the query itself (or the author) that might over complicate matters. The data schema, defined by the DDL, can easily induce unwanted complexity in subtle ways, and this might be a problem deliberately placed beyond the reach of the person attempting to read or change the data locked within.
As for complaints about parsers, that's not a deficiency of the language. It's a deficiency of the tools used. If the development environment isn't presenting problems to the developer in a convenient manner, then the utility sucks. Get a new one. Don't blame the text-mode clients though. They are just as bare-bones as a command line, and deliberately so. At a certain level, SQL can be regarded the same way a shell script might be regarded, in terms of possessing the convenience of (or lack thereof) a basic TTY command interpretter. But there's no real reason why it should be impossible to create a SQL script authoring tool, which provides syntax validation as convenient as any compiled language might employ, when communicating compilation errors to the developer.
I honestly love SQL...I consider it a noble language:) It is the only declarative language out there that is still used today, and there are some solid reasons for that.
However, I believe the biggest mistake that was made in the creation of SQL was to try to emulate natural language flow patterns. This makes it hard to format and edit, and when people optimize towards writability, they kill readability (such as the use of leading commas. The lack of any real standard indentation practice makes it cooperative work frustrating. And the natural language flow actually confuses the writer/reader into thinking that order of operations is linear, as opposed to the FROM->WHERE->GROUP BY->HAVING->SELECT->ORDER BY->LIMIT order. This makes for really annoying logical bugs, such as how filter conditions in the where clause on a left-joined table can effectively turn your left join into an inner join.
This is actually a big issue because your ability to have complex declarative constraints goes up with table width, so breaking off potentially nullable columns also removes them from being available for cross-column check constraints.
One of the reasons I started working on the PGObject Perl framework[1] was because I found that if I hand-coded the SQL and programmed around that, I was more productive, and had fewer bugs.
The approach taken (based on our experience with LedgerSMB) is to focus on rules for mapping object oriented calls to stored procedure calls. The framework is of course PostgreSQL-only (and relies a lot on system catalog lookups).
My experience, backing what you are saying, is that if you know what you are doing, and you write good, maintainable stored procedures/UDF's then the power is totally worth it. Unfortunately, there are still some obstacles, and most of these are tooling.
I think the hatred of SQL from the parent (in the context of this quiz) is that if you separate performance from result, as SQL does, then you have to think about performance differently. In theory you code for results first and then tune performance later. In practice, this only gets you so far and you need to code with some knowledge of performance limitations. I know I have been bitten as badly as anyone else.
But, the tradeoff is that when I write more of my code into my queries, I get better performance, fewer bugs, and a significantly smaller codebase. The knowledge is worth it warts and all.
(When I have some really nice code samples, I will submit to HN)
[1] The official repos are the repos with names starting with "PGObject" at https://github.com/ledgersmb
The reason that you don't notice is that most of the times this stuff does not matter at all. Not because ORMs solve anything.
I'll let my ORM generate basic CRUD statements; the kind of statement which typically only involves PK lookups. But I find it better to write my own SQL statements for important queries, and of course let the ORM map the result set into objects. In fact, with enough experience, I've also found it _faster_ to just write a query in SQL versus learning yet another DSL or query builder API.
I'm a bit ashamed by how bad MySQL users performed at this test.