php - Caching around 15k records during autosuggest -

i've got form, uses autosuggest search around 15k records (store addresses) in database. i'm using php (5.5 in dev, 5.4 in prod) , mysql. search algorhytm works in such way:

1. assume query: brand city.
2. explode query keywords: brand, city.
3. search database %brand% or %city%.
4. merge results, , sort them wages (if record occures in both arrays - wage of increments).
5. slice results i.e. 10.
6. send them client.

i know, not efficient, works < 1k records. tried apc , memcached, amount of data, i'm receiving memory leak.

do have idea, how can improve search engine? in advance.

edit:

example query:

select `store`.`id` `id`, `store`.`user_id` `user_id`, `store`.`name` `name`, `store`.`tags` `tags`, `store`.`is_reported` `is_reported`   `stores` `store`   `name` '%żabka%'   order `store`.`name` asc 

table structure:

create table if not exists `stores` (   `id` int(11) unsigned not null auto_increment,   `user_id` int(11) unsigned not null default '0',   `name` varchar(250) collate utf8_polish_ci not null,   `tags` varchar(250) collate utf8_polish_ci not null,   `is_reported` int(1) unsigned not null,   primary key (`id`),   key `id` (`id`) ) engine=innodb  default charset=utf8 collate=utf8_polish_ci auto_increment=11957 ; 

and example row:

11954 | 0 | zielony market - ul. geodetów 76, 07-200 wyszków | ul.,geodetów,76,07-200,wyszków | 0

now think, should create seperate columns brand, city , street. right?

expanding on previous comment, sounds might doing multiple things wrong here @ once.

i’d suggest trying (after setting appropriate index on name column, if that’s column searching in):

select foo, bar, baz stores name '%brand%' or name '%city%' order (name '%brand%') + (name '%city%') desc, name asc limit 10 

the sum of 2 values in order rank matching records how many of searched words found in name column – in context, mysql treat true 1 , false 0, if both matches find match, sum 2, 1 1. sorting alphabetically store name happens afterwards, because number of found matches has higher priority relevance of record.

give go , see how please (don’t forget index); if performance not great, please edit question show explain statement query says (by putting explain in front of query, explain select … , executing it).