How-to: Ranking Search Results

Question

I have a webapp development problem that I've developed one solution for, but am trying to find other ideas that might get around some performance issues I'm seeing.

problem statement:

• a user enters several keywords/tokens
• the application searches for matches to the tokens
• need one result for each token
  • ie, if an entry has 3 tokens, i need the entry id 3 times
• rank the results
  • assign X points for token match
  • sort the entry ids based on points
  • if point values are the same, use date to sort results

What I want to be able to do, but have not figured out, is to send 1 query that returns something akin to the results of an in(), but returns a duplicate entry id for each token matches for each entry id checked.

Is there a better way to do this than what I'm doing, of using multiple, individual queries running one query per token? If so, what's the easiest way to implement those?

edit
I've already tokenized the entries, so, for example, "see spot run" has an entry id of 1, and three tokens, 'see', 'spot', 'run', and those are in a separate token table, with entry ids relevant to them so the table might look like this:

'see', 1 
'spot', 1 
'run', 1 
'run', 2 
'spot', 3 

Answer 1

you could achive this in one query using 'UNION ALL' in MySQL.

Just loop through the tokens in PHP creating a UNION ALL for each token:

e.g if the tokens are 'x', 'y' and 'z' your query may look something like this

SELECT * FROM `entries` 
WHERE token like "%x%" union all 
    SELECT * FROM `entries` 
    WHERE token like "%y%" union all 
        SELECT * FROM `entries` 
        WHERE token like "%z%" ORDER BY score ect...

The order clause should operate on the entire result set as one, which is what you need.

In terms of performance it won't be all that fast (I'm guessing), however with databases the main overhead in terms of speed is often sending the query to the database engine from PHP and receiving the results. With this technique this only happens once instead of once per token, so performance will increase, I just don't know if it'll be enough.

Answer 2

I know this isn't strictly an answer to the question you're asking but if your table is thousands rather than millions of rows, then a FULLTEXT solution might be the best way to go here.

In MySQL when you use MATCH on your indexed column, each keyword you supply will be given a relevance score (calculated roughly by the number of times each keyword was mentioned) that will be more accurate than your method and certainly more effecient for multiple keywords.

See here: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html

Answer 3

If you're using the UNION ALL pattern you may also want to include the following parts to your query:

SELECT COUNT(*) AS C
...
GROUP BY ID
ORDER BY c DESC

While this is a really trivial example it does get you the frequency of the matches for each result and this could be a pseudo rank to start with.

Answer 4

You'll probably get much better performance if you used a data structure designed for search tasks rather than a database. For example, you might try looking at building an inverted index. Rather than writing it youself, however, you might also want to look into something like Lucene which does most of the work for you.