Optimal MYSQL query for longest prefix matching in a table with 5 million rows

user3122574

I've a table with 5 million of rows

CREATE TABLE dummy_table (
            num VARCHAR(16) NOT NULL DEFAULT 0,
            rsid VARCHAR(16) NOT NULL,
            list VARCHAR(128) NOT NULL,
            PRIMARY KEY (num, rsid)
            );  

num field in the table is the prefix of some dynamic number('123457467890' in above query). Now I need to fetch list column based on num and rsid and in this num must be the longest prefix match of incoming number. For getting list I've a below query:

select list 
from dummy_table 
where '123457467890' like CONCAT(num, '%') 
  and rsid = '123' 
order by LENGTH(num) desc LIMIT 1;

NOTE: 123457467890`: this number will be different each time we throw a query

Now the problem is for executing this query, MYSQL is taking about 0.80 seconds which is very high in my case. I need to throw more than 1000 query in a second. Is there any way to optimize this query to this extent. Can anyone help to achieve this result?

MatBailie

My first optimisation would be:
- Add another column "length"
- Add an index on (rsid, length DESC, num)

Now your query is only very slightly different:
- SELECT list FROM dummy_table WHERE '123457467890' LIKE CONCAT(num, '%') AND rsid = '123' ORDER BY length DESC LIMIT 1;

But, by including the length in the index, the query should be able to stop at the first hit.

However...

This is always going to be a costly process. The worst case scenario being that you find no matches - and so have to scan the full set of (rsid = '123') records no matter what.

The optimisation above isn't going to help optimise the worst case scenarios, only the best case scenarios. (It will help more the longer the match is, but won't help as much for shorter matches.)


What you MAY be forced to do is something like...
1. Create a temporary table
2. Insert '1234567890' in to it
3. Insert '123456789' in to it
4. Insert '12345678' in to it
.
.
.
n. Insert '1' in to it

At this point you have every possible match for your search string in your temporary table.

Then your query can instead potentially use an index seek. Potentially finding 10 matches (in this case) and then finding the longest of those.

-- Index now needs to be (rsid, num, length)

SELECT
  *
FROM
  dummy_table
INNER JOIN
  your_search_table
    ON dummy_table.num = your_search_table.num
WHERE
  rsid = '123'
ORDER BY
  dummy_table.length
LIMIT
  1

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Optimal MYSQL query for longest prefix matching in a table with 5 million rows

From Dev

MySQL longest prefix matching on 1 million records against 3000 possibilities

From Dev

Slow Query on Medium MySQL Table (1 Million Rows)

From Dev

Slow Query on Medium MySQL Table (1 Million Rows)

From Dev

Trie longest prefix matching

From Dev

Query optimization on a Table with 1 Million rows

From Dev

Query large table with 50 million rows

From Dev

Very slow SELECT query in MySQL in a 10 Million rows table (single table)

From Dev

Mysql database design: table with half a million rows

From Dev

Loading 5 million rows into Pandas from MySQL

From Dev

MySQL: Update all rows in 2 table matching results of another query

From Dev

MYSQL Query matching column names to rows in another table

From Dev

Optimizing SQL query on table of 10 million rows: neverending query

From Dev

MySQL query to select rows matching criteria and rows related to the matching rows

From Dev

mysql php query find longest matching parts of input

From Dev

update query with 1.5 million rows taking long time to execute mysql

From Dev

MySQL writing a query with 2 million records to a new table

From Dev

Replace mysql query table prefix in php

From Dev

Replace mysql query table prefix in php

From Dev

MySQL: Update rows in table, from rows with matching key in another table

From Dev

Replace all rows of a select query with matching rows of another table

From Dev

Find longest matching ngrams in MySQL

From Dev

MySQL query with matching and sum - League Table

From Dev

Elasticsearch Multiple Prefix query OR Matching

From Dev

Longest Prefix between two MySQL Tables

From Dev

String Matching: Computing the longest prefix suffix array in kmp algorithm

From Dev

How to query against 18million rows?

From Dev

Rebuild Index on table with 128 million rows

From Dev

Sort table with million rows , LinQ connection

Related Related

  1. 1

    Optimal MYSQL query for longest prefix matching in a table with 5 million rows

  2. 2

    MySQL longest prefix matching on 1 million records against 3000 possibilities

  3. 3

    Slow Query on Medium MySQL Table (1 Million Rows)

  4. 4

    Slow Query on Medium MySQL Table (1 Million Rows)

  5. 5

    Trie longest prefix matching

  6. 6

    Query optimization on a Table with 1 Million rows

  7. 7

    Query large table with 50 million rows

  8. 8

    Very slow SELECT query in MySQL in a 10 Million rows table (single table)

  9. 9

    Mysql database design: table with half a million rows

  10. 10

    Loading 5 million rows into Pandas from MySQL

  11. 11

    MySQL: Update all rows in 2 table matching results of another query

  12. 12

    MYSQL Query matching column names to rows in another table

  13. 13

    Optimizing SQL query on table of 10 million rows: neverending query

  14. 14

    MySQL query to select rows matching criteria and rows related to the matching rows

  15. 15

    mysql php query find longest matching parts of input

  16. 16

    update query with 1.5 million rows taking long time to execute mysql

  17. 17

    MySQL writing a query with 2 million records to a new table

  18. 18

    Replace mysql query table prefix in php

  19. 19

    Replace mysql query table prefix in php

  20. 20

    MySQL: Update rows in table, from rows with matching key in another table

  21. 21

    Replace all rows of a select query with matching rows of another table

  22. 22

    Find longest matching ngrams in MySQL

  23. 23

    MySQL query with matching and sum - League Table

  24. 24

    Elasticsearch Multiple Prefix query OR Matching

  25. 25

    Longest Prefix between two MySQL Tables

  26. 26

    String Matching: Computing the longest prefix suffix array in kmp algorithm

  27. 27

    How to query against 18million rows?

  28. 28

    Rebuild Index on table with 128 million rows

  29. 29

    Sort table with million rows , LinQ connection

HotTag

Archive