Markus Winand's Blog

Posts Tagged ‘postgresql’

Finding the Best Match With a Top-N Query

In Performance on 2010-09-29 at 11:16

There was an interesting index related performance problem on Stack Overflow recently. The problem was to check an input string against a table that holds about 2000 prefix patterns (e.g., LIKE 'xyz%'). A fast select is needed that returns one row if any pattern matches the input string, or no row otherwise.

I believe my solution is worth a few extra words to explain it in more detail. Even though it’s a perfect fit for Use The Index, Luke it’s a little early to put it as an exercise there. It is, however, a very good complement to my previous article Analytic Top-N queries—so I put it here.

Although the problem was raised for a MySQL database, my solution applies to all databases that can properly optimize Top-N queries.

Read the rest of this entry »