4 ms·

I always wondered in this situation: var topFiveSongs = low('songs') .where({published: true}) .sortBy('views') .first(5) .value();

by kolodny 12y ago

I always wondered in this situation: var topFiveSongs = low('songs') .where({published: true}) .sortBy('views') .first(5) .value(); If any db engines figure when the dataset is really large and the limit is really small (no idea what the cutoff would be), if instead of sorting and giving the first five, it instead just looks for the 5 largest/smallest. Anyone have any idea on this?

delinka 12y ago
This is what an index is for on a SQL database. You declare an index on 'published' and and index on 'views' and the engine can now optimize selection of the records you requested. Without those indices, the engine must necessarily scan every row of the table at least once. Yes, there are analyzers with the smarts to recognize that indices on particular fields would have helped a given query, but even if the engine's going to auto-create those for you, it then has to scan every row in the table to create the index that first time.
Erwin 12y ago
PostgreSQL use a "top-N sort heapsort" for this. You can see that in effect when doing "EXPLAIN ANALYZE" on a query like this. Without an index you cannot avoid a full table scan. However the top-N heapsort avoids allocating memory for ALL the rows, since you only care about the first 5 ones For example, I had a 6 million entry table sitting around, and asked for top 5 rows by an unindexed column. With LIMIT 5 applied it told me: Sort Method: top-N heapsort Memory: 95kB Without: Sort Method: quicksort Memory: 577595kB So if Postgres had to store all the 6 million rows sorted it would need 577 MB of work memory. If (see SHOW work_mem) it was below that that would lead to it writing a lot of temporary files to disk: Sort Method: external merge Disk: 144072kB Note how Postgres is more wasteful with memory usage than disk writes for temp storage. Generally a query that requires you to do a full table scan on a large table should be used sparingly however.

by kolodny 12y ago

delinka 12y ago

This is what an index is for on a SQL database. You declare an index on 'published' and and index on 'views' and the engine can now optimize selection of the records you requested. Without those indices, the engine must necessarily scan every row of the table at least once. Yes, there are analyzers with the smarts to recognize that indices on particular fields would have helped a given query, but even if the engine's going to auto-create those for you, it then has to scan every row in the table to create the index that first time.

Erwin 12y ago

PostgreSQL use a "top-N sort heapsort" for this. You can see that in effect when doing "EXPLAIN ANALYZE" on a query like this. Without an index you cannot avoid a full table scan. However the top-N heapsort avoids allocating memory for ALL the rows, since you only care about the first 5 ones For example, I had a 6 million entry table sitting around, and asked for top 5 rows by an unindexed column. With LIMIT 5 applied it told me: Sort Method: top-N heapsort Memory: 95kB Without: Sort Method: quicksort Memory: 577595kB So if Postgres had to store all the 6 million rows sorted it would need 577 MB of work memory. If (see SHOW work_mem) it was below that that would lead to it writing a lot of temporary files to disk: Sort Method: external merge Disk: 144072kB Note how Postgres is more wasteful with memory usage than disk writes for temp storage. Generally a query that requires you to do a full table scan on a large table should be used sparingly however.