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.

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%)".

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.

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.

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.

Indexing shouldn't follow the theoretical worst case, it should follow what's actually in your table.

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.

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.

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.

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

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.

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;