xbmc/xbmc — pull request #1047 by Montellese (2012-06-05 14:30:01+00:00)
Title: [GSoC] unified sorting & limiting implementation

For those who don't want to read the whole story, scroll down to the conclusion ;-)

These commits form the second PR based on my GSoC work. As the ultimate goal of my GSoC work is to provide easy filtering of media listings in the GUI through SmartPlaylists it is necessary to make sure that the sorting used by the SmartPlaylist implementation gives the same results as the sorting used by GUI listings like Movies, TV Shows, Albums etc. Currently this is not the case because for SmartPlaylists the sorting (and limiting) is done through SQL (i.e. it's done in the database engine) whereas the sorting (there's no limiting) of GUI listings is done through sorting implementations in SortFileItem.h/cpp. The SmartPlaylist sorting implementation especially lacks the possibility to implement more complex sortings like "Sort by Name ignoring articles" which simply can't be achieved in SQL. But doing the sorting (and especially the limiting) directly in the database also means faster retrieval of the items/metadata from the database.

This work unifies the sorting implementation of SmartPlaylists and GUI listings. For GUI listings this is just a change in the implementation of CFileItemList::Sort() and using SortUtils instead of SSortFileItem but for SmartPlaylists this means to get away from doing the sorting and limiting in the database engine through SQL and instead using the same (new) SortUtils implementation. To match the speed of doing the sorting and limiting in SQL I ran a lot of tests and basically what takes most of the time in calls like GetMoviesByWhere, GetEpisodesByWhere etc is actually retrieving the data from the query's result set and placing them in CFileItem objects. Also for SmartPlaylists which e.g. only want to retrieve the first 100 of 2000 episodes the database engine does a great job in sorting and limiting the result set before we ever get to the point of retrieving the data and placing it in CFileItem objects. If we'd just always retrieve all metadata/items, then do the sorting using SortUtils and then apply the limiting by erasing the unneeded items we would loose a lot of speed (this highly depends on the ratio of limit over total) so jmarshall and I came up with the following approach:

1. Run the usual SQL query without any sorting or limiting
2. Based on the sorting that is applied only retrieve the necessary data from the result set for every item (e.g. when the user wants to sort by rating, only retrieve the rating data)
3. Do the sorting on that list of items with limited metadata and apply the limiting by erasing unneeded items
4. For the remaining items retrieve all the data available in the data set and place them in CFileItem objects.

In special cases like when there is no sorting step 2 and 3 can be skipped or if there is no sorting but limiting, the limiting can be done directly in SQL. These special cases bring additional speed ups to the whole process.
To be able to only retrieve the full metadata for the remaining items (after the sorting and limiting) there exist two approaches:
* Loop through the list of remaining items (M items) and through the query's result set (N items) and look until we find the item in the result set that matches the current item in the sorted/limited list (e.g. based on the database ID). Worst case this will be O(N^2) if only sorting and no limiting was applied. This approach can be very slow and managed to double or triple the time it took to retrieve, sort and limit the items from the database.
* Remember the position of the items with limited metadata in the result set and access the result set as a vector of results directly instead of using the usual iterator-style access with m_pDS->next() etc. This way there is no need to search for the matching item in the database's result set after the sorting and limiting because we know for every sorted item where the corresponding result is located in the database's result vector.

My final observations and runtime measurements show that the new implementation is a bit faster than a raw SQL query because of the direct access to the result set as a vector. The only case where the new implementation may be slower than a raw SQL query is when both sorting and limiting is applied. If the ratio of limited items over total items is very small it can be up to 3-4 times slower. The larger the ratio the better the new sorting implementation is. Starting from a ratio of approximately 0.8 the new implementation is faster than the raw SQL query.

Conclusion
----------------
The new sorting implementation provides the same sorting implementation for GUI listings and for SmartPlaylists which makes it possible to use SmartPlaylists directly for filtering GUI listings and provides SmartPlaylists with the same sorting features like "Sort by Name ignoring articles" which currently isn't possible. Furthermore in most cases it speeds the processing/retrieval of items in a SmartPlaylist up except for cases where both sorting and limiting is applied and the limit number is small compared to the total number of available items. With this new implementation theoretically all more or less hard-coded SQL queries could be replaced by specific SmartPlaylists without getting different results concerning the order of items.
Last but not least this provides a huge speedup for JSON-RPC queries which retrieve items from our music and video library. JSON-RPC provides the possibility to limit the number of items returned but with the current implementation we were stuck with retrieving/processing all items and then erasing the unneeded ones. Therefore the retrieval time didn't scale at all when limiting was applied in a request. Now the retrieval time scales perfectly with the requested limits which can provide a huge boost to users with huge media collections because the client can implement some kind of pagination by loading the first 100 (or whatever) items (which will be much faster than retrieving all of them) and only retrieve the next items once the user scrolls far enough down in the list.