How to search millions of record in SQL table faster?

Full-text indexing is the far-and-away best option here - how this is accomplished will depend on the DBMS you're using.

Short of that, ensuring that you have an index on the column being matched with the pattern willhelp performance, but by the sounds of it, you've tried this and it didn't help a great deal.

Stop using LIKE statement. You could use fulltext search, but it will require MyISAM table and isn't all that good solution.

I would recommend for you to examine available 3rd party solutions - like Lucene and Sphinx.
They will be superior.