0

I'm making a website in PHP where the user can search a big MySQL database. The user is shown the first result. I want the next button to take the user to the next result, and so on.

The trivial solution is for each result page to execute the user's search query again and use OFFSET and LIMIT to get the n-th result that is displayed. But this feels like a Schlemiel the Painter's algorithm: re-executing the same query over and over to get to the n-th result is inefficient.

Since others must have faced this situation before: how is this typically solved?

  • 2
    It should not be inefficient, this is what DBMS's are designed for. You give them a set of input parameters and internally it should make the most efficient result set coming back. You are passing an OFFSET and LIMIT that kind of goes against what the algorithm is describing. – pllee Sep 16 '13 at 21:47
  • 1
    IMO this is one of those areas where no matter what happens it's got warts and eventual performance issues... If you can, step back and look at it as a user-experience problem: If someone's paging too far into the results, that's the real problem, and something needs to change so that they don't have to. – Darien Sep 16 '13 at 23:44
  • Try pagination on SQL Server 2000 and you will understand Schlemiel 's plight. – Mike Sep 17 '13 at 16:22
  • There are lots of php mysql pagination questions on stackoverflow.com – Aaron Kurtzhals Sep 17 '13 at 20:51
  • @AaronKurtzhals Sure, just not my question. – Daniel A.A. Pelsmaeker Sep 17 '13 at 20:55
1

It's not Shlemiel's algorithm; getting page 16 takes pretty much exactly as long as getting page 1.

Yes, you do need a new query per page, but each of these queries gets only one page's worth of data. The alternatives are worse: If you get all data in one go and then filter it, you will still need one query per request, but now each of these queries gets the entire result set, and you'll be doing the partitioning in PHP - but a DBMS is much better at this than your hand-written PHP code. You could cache the whole thing, but this has two downsides: you still query the entire data set on first load, which means any request on a stale cache takes way longer than necessary, and you need to implement caching, which could add some significant overhead. Also, just like in the uncached example, you still need to do the pagination in PHP.

Should it turn out that your solution is too slow, you should first look at your database schema. Make sure you have the appropriate indexes on the relevant tables. Denormalize if you have to. If that doesn't cut it, consider caching individual pages.

And finally, if you need search functionality that scales, consider using something that specializes in indexing documents, e.g. Solr. These things are much better at indexing and searching documents than MySQL could ever hope to be.

  • Getting page 16 takes longer than getting page 1, according to this question. It has to count records from the start every time, making it a Schlemiel's algorithm. Maybe its just not that noticeable in small data sets and small offsets. – Daniel A.A. Pelsmaeker Sep 17 '13 at 18:51
1

So this is basically the best thing you can do in my opinion. It's far more scallable than keeping the whole result set in-memory and reusing it between page requests. But of course it's hard to judge without seeing your software requirements first.

If you need something more sophisticated then depending on your use case you can cache results from your query locally, or if the results rarely change you can even pre-generate the page in the back-end (one query at certain intervals, users get static results). This is basically what CQRS is designed to deliver:

http://martinfowler.com/bliki/CQRS.html
http://www.udidahan.com/2009/12/09/clarified-cqrs/

Excerpt: "CQRS is about coming up with an appropriate architecture for multi-user collaborative applications. It explicitly takes into account factors like data staleness and volatility and exploits those characteristics for creating simpler and more scalable constructs.

Standard layered architectures don’t explicitly deal with either of these issues. While putting everything in the same database may be one step in the direction of handling collaboration, staleness is usually exacerbated in those architectures by the use of caches as a performance-improving afterthought."

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.