MySQL indexing issue when trying to search for a part of a string/word

What we're running into: --------------------- Engine: MySQL. We've been working on a filter where an user can search for a reference number. However, we've ran into an issue with performance on bigger data sets. We need to search for partial words; say we have the reference AB12345678 - the user wants to find this reference by either searching AB, B123, 1234 or any other combination which contains part of this string. We have an INDEX on reference & date We're currently using LIKE %STRING%, but this cannot be indexed - and performance is bad in certain situations: **(1)** When we search for AB we get a fast result. **(2)** When we search for AB12345678 we get a slow result. Both situations have ORDER BY date & LIMIT. When we turn off either ORDER BY or LIMIT with situation **(2)**, we also get a fast result. A slow result is around 14-15 seconds of query execution time. The dataset contains around 300k results. What we've tried so far: ---------------------- We tried implementing FULLTEXT indexes and MATCH .. AGAINST queries, however MATCH .. AGAINST doesn't allow us to search for both sides, the * wildcard is only allowed at the end of the input string. We've also tried removing the INDEX on date. This gave us faster results (around 1/3th of the time) however, the query still took around 4-5 seconds. We're kinda lost on the best implementation that can improve our performance on this query and how we can best solve it right now. What method should we use to get our performance back and be able to search on both sides? Below is part our query which has slow results (we removed the SELECT part): SELECT SQL_NO_CACHE * FROM orders o0_ WHERE 1=1 AND o0_.customer_id = 130 AND (o0_.reference LIKE '%AB12345678%') ORDER BY date4 DESC LIMIT 50 OFFSET 0;