SQL Server 2014: Index Seek is taking more than 20 seconds (using LIKE '%Value%')

Hello,

I've a table with half million rows. I want to fetch records based on below query:

SELECT Col1, Col2
FROM Table
WHERE Col3 LIKE '%Value%'

Using aforesaid query, Index scan was using by execution plan & taking around 25 seconds Then I modified query with below

SELECT Col1, Col2
FROM Table
WHERE (Col3 IS NOT NULL And Col3 LIKE '%Value%')

After that it was using Index Seek. But still take 20 seconds (5 seconds saved, but need in less than 1 second). FYI, it returns around 100 thousand records after 20 seconds.

Do you have any idea to boost it (except database/table partitioning)?


Best Regards,