Slow search by LIKE and other values (1 million rows+) I'm currently developing a kind of search website where one can search for business companies in my country. The database table has 1 million rows and quite a few colums (42 columns).

But I find it very slow. Is that because of the query I'm executing, or the database?

I have created indexes on several columns wich are used in the search query too, but often when a query is run, it times out on 30 seconds.

The query run would look something like this:

SELECT *
FROM companies
WHERE ( navn LIKE ?
      OR keywords LIKE ? )
   AND ( ( forretningsadresse_fylke = ?
           AND ( forretningsadresse_kommune = ?
                  OR forretningsadresse_kommune = ?
                  OR forretningsadresse_kommune = ? ) )
          OR ( forretningsadresse_fylke = ?
               AND ( forretningsadresse_kommune = ?
                      OR forretningsadresse_kommune = ?
                      OR forretningsadresse_kommune = ? ) )
          OR ( forretningsadresse_fylke = ? )
          OR ( forretningsadresse_fylke = ?
               AND ( forretningsadresse_kommune = ? ) ) ) 


Engine: InnoDB.
Collation: utf8 - default collation


If any other info is needed, please say so. What could I do to speed up the search? Thanks in advance.

Edit: extra info.
Indexed columns: PRIMARY (id), organisasjonsnummer, navn, forretningsadresse_fylke, forretningsadresse_kommune, keywords
Not sure about mysql but in mssql like '%val' is a full scan 

Multiple keywords in a varchar(200) column is probably not the best design.  Spit the keyswords into separate words into a separate table with a FK back to company.ID.  So each word would be a row. Then you can search on keyword.value = 'xxx' and use an index.