3

I need to find a way to efficiently process a large amount of data in PHP/MySQL. Here's the situation:

I have a database table with, say, one million records. Based on user input from PHP, I need to rank all of those one million records according to a non-trivial calculation step, so that I can pick the top scoring items. My problem is that this scales very poorly from a memory usage standpoint, particularly at the sorting step, if I rearrange the data into columns and use array_multisort.

Alternative methods I can think of are:

  • Doing the calculations in PHP and reinserting the data with the scores into a temporary table, retrieving the highest scoring items using a SELECT ... ORDER BY score ... LIMIT query
  • Doing the calculations in PHP and outputting the data with the scores into a CSV file, then calling the command-line sort utility, then reading in the top X number of lines
  • Doing the calculations in MySQL using a stored procedure and retrieving the top X number of items, as in option 1. My concern with this is whether the DB is well suited for the number crunching this would involve

This has got to be a fairly common problem for things like search engines. Scalability is the number one priority, but performance has to be pretty good too. Is one of these approaches best, or is there some other great option that I'm not even considering?

Improve this question
3
  • 2
    I think that knowing how non-trivial the non-trivial crunching is might help. Commented Jun 21, 2011 at 2:37
  • Perhaps it may be faster to write a C++ / C program to do the calculations and pass it back to PHP or perhaps you could look at hiphop Commented Jun 21, 2011 at 2:42
  • cwallenpool: Sorry, I don't think I can disclose. Suffice it to say that it's probably too complex to do on the DB, row-by-row. GWW: I didn't know hiphop existed, that could definitely be an option. Commented Jun 21, 2011 at 5:34

3 Answers 3

Reset to default
1

Assuming your dataset is too large to store in memory.... If you only need the top n items, you can keep only the top results in memory as you page through the 1 million rows. This would also work with the temporary table idea of yours, writing the top records from each batch.

Another option would be to write a user defined function:

http://dev.mysql.com/doc/refman/5.1/en/adding-functions.html

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I considered a user-defined function, but decided against it, on account of my assumption that the function is too complex to have the DB execute it on all million or more rows. Your first option may be the best way. I think that all I need now is to find an efficient heap implementation to hold the top X nodes.
Yep, that worked brilliantly. I went with your first suggestion and then used an SplHeap of size X to keep track of the top X items. Very low memory overhead, low DB load, and excellent performance. Very elegant solution.
@acjohnson55, I'm glad the heap worked for you. UDFs are written in C generally and dynamically linked into the MySQL runtime. It's probably worth understanding this option, even if you don't go this route.
Oh, I was under the impression that MySQL only allowed stored procedures in its interpreted language. A UDF in C would definitely be a possibility. I will look into this option, because performance past after 200,000 items starts to get into the several second range, and it definitely needs to be scalable past one million
1

Why not do part or all of your calculation when you store the row. That way you only have to do it once and you have lots of time to do it in.

Improve this answer

1 Comment

If you mean when the row is generated, that won't work, because the results depend on the row data and the user's given parameters. Multiple users will be using at once, each with their own parameters.
0

Doing it in a complex ORDER BY is the best out of all the options you mentioned, if it's possible. But for one million records you will still encounter problems.

Sounds like you are doing things the hard way, trying to keep all your data in one place and order it on the fly. Is there no way to do scoring beforehand, even if it's a few scores you combine at request time for a custom sort key?

How complex are the user's queries? If you are trying to do fulltext search you should get software specialized for that task.

Improve this answer

1 Comment

The data is such that without user input, any given item may be the top scorer. I considered sampling over all possible user inputs and storing precomputed scores with each row, but for a million rows, that really starts to challenge the storage limitations. The queries aren't complex, they're simply target numbers that have to be matched against database fields subject to a fairly complicated calculation with a number of tunable parameters.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.