How to get the closest matches first from MySQL

user_6918052 0
Viewed 63

I have a table of 10 million records and and am trying to select user details like firstname, lastname and country. I need to get results back in order where (order by column="abc") would give me results where those that match are ranked on the top.

what I have tried

Query one

-- this is match slower with 45+ seconds
select firstname, lastname, town
from user_db
order by town="abc" DESC
limit 25;

Query two

-- much faster with 0.00019 seconds
select firstname, lastname, town
from user_db
order by town DESC
limit 25;

The problem

The first query also works but takes 45+ seconds while if I remove the equals expression in the (order by clause) like in the second query, it's match faster. And obviously I do use where clauses but this is a simplified example.

other notes

There are currently no joins on the query as it is just a simple select statment of user details and my setup is pretty good with 30GB ram and 2TB of storage all local.

Indexes: All columns mentioned have indexes but the (order by town="abc") clause triggers a full table search and as a result, this ends up finishing in 2 minutes

Is there a way to get results ranked by closest matches first faster within a single query? Any help will gladly be appreciated. Thank you.

mysql
4 Answers

It looks to me like your user_db table has an index on your town column. That means ORDER BY town DESC LIMIT 25 can be satisfied in O(1) constant time by random-accessing the index to the last row and then scanning 25 rows of the index.

But your ORDER BY town='abc' DESC LIMIT 25 has to look at, and sort, every single row in the table. MySQL doesn't use an index to help compute that town='abc' condition when it appears in an ORDER BY clause.

Many people with requirements like yours use FULLTEXT searching and ordering by the MATCH() function. That gets a useful ordering for a person looking at the closest matches like in the searching location bar of a web browser. But don't expect Google-like match accuracy from MySQL.

user_2056080

You can decouple the query into two queries each one being very fast.

First, create an index on town.

create index ix1 on user_db (town);

Then get the matches, with a limit of 25 rows:

select * from user_db where town = 'abc' limit 25

The query above may return any number of rows between 0 and 25: let's call this number R. Then, get the non-matches:

select * from user_db where town <> 'abc' limit 25 - R

Assemble both result sets and problem solved. Even if the second query results in a table scan, it will be concluded earlier resulting in a low cost.

user_64361910

One way is to add a new column that has a value of country="abc", then sort by this column.

I'm rebuilding my workspace right now so I cannot try it properly, but something like:

select firstname, lastname, town, town="abc" as sortme
from user_db
order by sortme desc, town, lastname, firstname
limit 25;
user_4496930

While it is unclear what you mean by "closest match" it is difficult to answer your question. Are "abd", "bc" etc regarded a close match to "abc"? Should the word "abc" appear in the town and match "abcville"?

There are a number of options.

Appearance of search string

Using a like "%abc%" where clause will find all towns with the string "abc" appearing in it.

select firstname, lastname
from user_db
where town like "%abc%"
order by town

Leave out the first % if you want to search by towns starting with "abc". The advantage is that this probably will search in the index if there is one for town. Use "abc%" to find towns starting with "abc". There is no ranking but you could add a sort.

Use a fulltext index

Create a FULLTEXT index on town:

ALTER TABLE user_db
ADD FULLTEXT(town);

And use this with a match:

SELECT 
  MATCH(town) AGAINST('abc') AS Relevance,
  firstname, lastname
FROM user_db
WHERE MATCH(town) AGAINST('abc')
ORDER BY Relevance DESC
LIMIT 15

Match uses words to calculate the match so in this case the string "abc" must appear with spaces in in the town in order to have a match. The NATURAL LANGUAGE options work well for plain texts but might not do so for town names. To be honest I have no experience with FULLTEXT and match performance but it probably is well optimized and works fairly good on large tables.

Create additional fields

As storage is cheap and time is not you might want to consider adding additional fields with search strings or alternative spellings for 'town' create all the indexes you'll need and use that as a search source. As this will need analysis of your use case it is difficult to provide an solution.

user_7189600
Related