sql - What's the asymptotic complexity of GroupBy operation?

Question

I am interested in the asymptotic complexity (big O) of the GroupBy operation on unindexed datasets. What's the complexity of the best known algorithm and what's the complexity for algorithms that SQL servers and LINQ are using?

Answer 1

Ignoring the base SQL that the group by is working on, when presented to the GROUP BY operation itself, the complexity is just O(n) since the data is scanned per-row and aggregated in one pass. It scales linearly to n (the size of the dataset).

When Group By is added to a complex query the equation changes, O(n) becomes the upper bound that the Group By adds to the overall equation; it could be less if the inner complex query is such that in the resolution of the base query, the data is already sorted.