question.md

I see a few issues with your code that could be slowing it down. Let's try to go through them together:

1. SELECT * - Unless you really need all the columns, SELECT * is not a good practice: it prevents the optimizer from using indexes because looking up all the columns usually exceeds the cost of scanning the whole table
2. nolock - It is not a "go faster" switch: it instructs the engine to ignore locks posed by other sessions and not lock rows while reading them. This could end up reading rows more than once or skipping them altogether, besides reading rows not yet committed by other sessions. Make sure you understand what are the effects on your query.
3. p.col5 in ( -- list of 20 strings ) or p.col5 in ( -- list of 3000 strings ) can be collapsed in a single p.col5 in ( -- list of 3020 strings )
4. You should probably save your strings in a temporary table or table parameter, because passing too many literals on a query can exhaust the resources of the query optimizer (it usually times out trying to spool your literals somewhere). Your temporary table or table parameter should have an (unique) index to help the optimizer figure out what to do with those values.
5. Creating indexes on your base table for equality predicates usually helps. I would create and index at least for col1, col3 and col4, based on the selectivity of the predicates.