I don't know of any great algorithm to scan an index and get to the next unique value that is that much faster than a scan. Maybe if you could assume that the values have somewhat low cardinality and a very small percentage match the pattern (most patterns having low bit count). You only get real savings if you can skip reading a number of pages because you read pages before and after it that have the same value of x, and x doesn't match the pattern. Then, for all the matches, you need to still go to the main table and find that entry unless the index is a covering index supplying all the data needed for the query. This need may easily make the table scan faster. Maybe adding an ORDER BY x clause would increase the chance of it using the index.