Improving performance of query with `WHERE  ''`
Do those columns have indexes on them at all? That is rather vital information for questions like this. If there is no index covering either of those columns at all then there is nothing it can do except table scan to match those filters.

If there is at least one index covering one (or both) that it could use, it may be deciding against it anyway due to the SELECT *. If the selectivity of the index suggests to it that many rows will match then a table scan may actually be more efficient than an index seek/scan followed plus row lookups to get the rest of the data that is not contained within the index.

For instance if I run

SELECT parent_id FROM org WHERE parent_id &lt;&gt; ''


on one of our systems it performs an index seek only. Running

SELECT * FROM org WHERE parent_id &lt;&gt; ''


performs a table scan instead. If I force the index choice with 

SELECT * FROM org (WITH(INDEX(ix_org_parent_id) WHERE parent_id &lt;&gt; ''


it performs an index seek to locate the start of the records, then the RID lookups to find all the other column data. According to the query plan output it judges this to be ~6 times as costly as just doing the table scan, the estimated costs of the three queries above being 0.22926, 1.81429, and 11.1612 respectively. In this case the number of rows matching the WHERE clause is ~55% of ~50,000.