well in general, "particular column does not a character" would mean a NOT LIKE '%X%' pr PATINDEX =0, right?, so that would requre a table scan of all rows, so i'm no suprised it has a big impact; every value has to be evaluated.
that would not be Sargable, so it cannot use an index.
help us help you! If you post a question, make sure you include a CREATE TABLE... statement and INSERT INTO... statement into that table to give the volunteers here representative data. with your description of the problem, we can provide a tested, verifiable solution to your question! asking the question the right way gets you a tested answer the fastest way possible!