On Wed, Apr 8, 2015 at 2:09 PM, Richard Hipp <drh at sqlite.org> wrote:
> On 4/8/15, Dominique Devienne <ddevienne at gmail.com> wrote: > > With a LIMIT clause, in > > such a GROUP BY ORDER BY returning a large result set, would SQLite: > > 1) sort the whole result-set and then keep only the first top-N rows? > > 2) or instead do a partial-sort of the first top-N rows only, > > SQLite must examine all rows of output, obviously. But it only keeps > the top-N in memory and only sorts the top-N. If there are a total of > M candidate rows and only the top-N are to be displayed, then the > algorithm is O(M*logN) in time and O(N) in space. > Thank you Richard. --DD
