[pdubs]

No query optimizer would look at this and say "1M rows? Let's group and aggregate before filtering." Not to mention, the question specifically states that a=? would return 100 rows and a=? and b=? would return 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.

[thwarted]

No query optimizer would look at this and say "1M rows? Let's group and aggregate before filtering."

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.

[jcampbell1]

I don't see that a=? rule. By selecting "100" rows out of a million, I think that means 100 distinct dates.

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.