What are solutions and tradeoffs to maintain search result consistency in a web application

Question

Consider a web application with a custom search function that must display the results in a paged manner (twenty per page with up to hundreds of thousands of total results) and the ability to drill down to individual results that maintain next/previous links to navigate through the results.

Re-executing the search on each page request to get the appropriate results for that page of data can be too expensive (up to 15s per search). Also, since the underlying data can change frequently (e.g. addition of new results), re-executing could cause the next/previous functionality to result in inconsistent behavior (e.g. the same results reappearing on a later page after having been viewed on an earlier page).

What options exist to ensure the search results can be viewed across multiple pages in a consistent manner, and what tradeoffs does each option have in terms of network, CPU, memory, and storage requirements?

EDIT: I thought caching the query search results was an obvious necessity. The question is really asking about where to cache the result set and what tradeoffs might exist to each. For example, storing the ids of the entities in the result set on the client, or storing the IDs of the entities themselves in the users session on the web server, or in a temporary table in the database. I'm not looking specifically for a single solution as different scenarios may result in different approaches (and such a question would be more suited for stackoverflow.com rather than here), but more of a design comparison between the possible approaches.

Answer 1

It's very common for search engines to just redo searches to get to your 'page 2'.

Storing search results per user can quickly become a memory/data hoarding disaster. Pulling all results out of your search index and storing it can quickly ends up being slower then just re-querying to search per 'page'/view.

If you can delay indexing to a nightly job you might get around the problem of misalignment.

Some indexing components may also support 'index generations' when you can re-query a search specifying which generation of index to use. The output would be consistently the same and align.

Answer 2

Not sure what your underlying search engine store is, but 15s search results? Meh.

Not to minimize your concerns, but using packages such as Lucene and Solr can take most of these headaches away for you. Heck, even something like MongoDB could address these issues. They're built to handle these scenarios in a much more efficient manner.

Answer 3

One way you could accomplish this, depending on how much traffic you receive, would be to setup (if you don't already have it) Edge Side Includes with the query keyword and paging parameters being part of the URL. That way additional queries on the same keywords won't even hit your application server.

You can configure the expiration time on the includes to determine how long you would want to cache your results for. Another option would be to add a parameter to the URL that you can change in-application each time that you want to update your cache.

Answer 4

Make your searches immutable

Most of the potential problems you cite can be rendered immaterial by simply caching the results of a particular search. In other words, do not re-run the search each time you display the next results page.

In a typical web application, a search function takes the form of a query result, where each page is delivered as it is needed, using some helper functions. When you perform the search, you need to cache the results of the search somewhere, and deliver each page of the search as it is requested.

In the Microsoft .NET world, this would be done using Skip() and Take() functions on a Linq query. The code might look something like this:

var searchResults = from tableToSearch 
                    where myConditions 
                    select someFieldsToDisplay;

var pageResults = searchResults.Skip((requestedPageNumber- 1) * resultsPerPage)
                               .Take(resultsPerPage)

So searchResults becomes the record set containing the results of your search, and pageResults contains the requested records from that search results for that particular page.

In most applications, the freshness of the search results is a non-issue, provided you make it clear to the user that, if they want results that are newer than two or three minutes old, they can simply perform a brand new search.

Answer 5

Trying alternative methods of searching or indexing to improve the search performance would be the first thing to try in such a situation. But, since that doesn't directly answer the question, and it's been months with no complete answer, I'm going to do my best to answer this myself (making it community wiki since I'm sure this answer can still be improved).

We require the results of a query to be presented to the user over a span of multiple web pages and that the entire result set is consistent across pages. As the original question implied and the edited question confirms, we know that the results of the initial search must be cached to ensure this consistency (freshness is less important than consistency). There are three main places in a web application where the results could be cached.

The first option is to cache the results in server memory. In this case, the query is executed and the identifiers for all of the results is saved usually in a user-specific memory area like an ASP.NET's HttpSessionState or Java's HttpSession{1}. The subset of identifiers for the required page of data is then pulled from this result set and used to load the actual data for return to the user's web browser. As each new pages are requested, the same set of identifiers are used to pull the data for those additional pages.

The next option is to cache the results in the database or other persistent storage. The resulting identifiers from executing the query are written back to the database into a temporary holding table that can be re-queried for each requested page to determine the identifiers of the entities that should be returned to the user's browser, followed by loads of the actual data.

The final option would be to package up the full list of search result identifiers and store them on the client. When requesting additional pages, the client could send the entire list back to the server for processing to determine which result records to load and display. With a slightly more heavy weight client (e.g. javascript, flash, etc.), the client itself could determine which result records are needed from their identifiers, request those from the server and update the display appropriately without needing to send the full list back to the server.

The tradeoffs here are mostly intuitive. Storing in memory requires enough memory to store all active user's search results. There could be some challenges with multiple-concurrent searches by the same user (e.g. two browser windows open), but that could be resolved with a unique search identifier as a key to the results within memory (rather than keying just on the user identifier or using a fixed key in the user-specific session data store). While probably the easiest to implement, this could be quickly problematic if there is no easy way to identify when a user is no longer active and their results can be removed from memory, or if the number of results the number of users could combine to exceed the available server memory.

Storing the results in the database adds some extra overhead in order to persist the results and re-query for the right identifiers, but that should be minimal. Some sort of cleanup job would be required to purge outdated search results when users are no longer active and their results are no longer required.

Storing the results on the client eliminates much of the application infrastructure overhead inherent with the other options (memory and storage), but instead requires more bandwidth which may impact page load times to an unacceptable level (especially on the initial load of all the identifiers). The server may still need to perform some additional work to ensure that the data requested by the client is valid and not a rogue client requesting arbitrary data it shouldn't have access to (this could likely be accomplished with encryption of the keys or cryptographically strong hashes to ensure data remains unmodified by the client)

---

{1} User sessions usually can be configured to be stored in a database instead of in server memory. The first option is really dealing only with situations where the server's memory is used to store the results. Otherwise, you're looking at the second option where the user's session is a more friendly layer on top of storing the data in the database (i.e. the second option.