The objective of the task : to implement the functionality of the autocomplex of addresses (settlements, 3 million records) with 2 characters, while if characters are not entered, there should be 10 popular settlements according to the number of requests.

The difficulty is as follows : the current structure of the database of our CMS is such that the addresses (the list of settlements with all the relevant data attached) are stored in 3 tables.

If you implement autocomplete search by name using SELECT .. LIKE .. taking into account 2x JOIN the selection from the database takes a long time .. if you enter a nonexistent term, the search works in 15-30 seconds (indexes are created). It needs to be done so quickly to help the user complement the text.

You cannot change the current database structure, but it is possible to create your own based on it.

What are the options for solving the problem?

It is possible to create a separate table with two main fields, id - a foreign key to the main data table, text - a string to search. Next, look at this table to avoid JOIN s,

Or can it somehow be presented as a binary search tree? Keep a temporary table to search in memory? etc

  • You can try to make the view and update it periodically. It may be a little faster. Perhaps the best solution would be in memory database - ArchDemon 3:17 pm
  • Your proposal with a separate table id, text looks very much even working. Of course, if there is an index on this text field and when searching by the first letters (and not from the middle). The database index is the very binary search tree. It is very likely that you will need to add another third field - the popularity index. It will have to be counted at some events. But it can be used when searching. Although it is possible that this rating should be kept in some other form so that the database could use it directly in the index - Mike
  • For reference (information for consideration) - in Russia there are 2386 cities and urban-type settlements, and the total number of settlements is 155511 (210 census), but in the world it is about 3 million. cities (population of the Earth ~ 7.5 billion people) - avp
  • You can use a full-text indexer. SphinxSearch or ElasticSearch. Judging by the formulation, you can immediately put all the necessary data in such an index and, for the autocomplete, do not use the database. It will be much faster plus the full-text search buns - abu

0