Very large table makes the application performance too slow We have an old application that has problems with performance. I narrow it down to few spots in the system that definitely require attention.

I found one table referenced in this app with 1,332,730,786 records in it. 

Table IDSelection 
IDType varchar(20) NOT NULL, 
SelectID int NOT NULL, 
UnID int NOT NULL, 
Batch int NULL


Table has following indexes

IX_IDSelection_UnID nonclustered located on PRIMARY UnID
PK_UIDSelection clustered, unique, primary key located on PRIMARY SelectID, IDType, UnID


My concerns are 
1. This table has composite primary keys with some entries in IDType that are empty string (not NULL though). 
2. Running simple SELECT queries like below against this table takes quite some time. 

select * from IDSelection where IDType &lt;&gt; '' and Batch is not NULL ORDER by Batch desc  -- cluster index scan
select * from IDSelection where Batch = 9977    -- 8 minutes run for 19 records
select * from IDSelection where IDType = 'ParentID' and Batch is not NULL  -- 9 min 3614603 rows


If I use indexed UnID in WHERE clause like the one below, performance is great

SELECT * FROM IDSelection where UnID = 1093510


Index fragmentation is not an issue here. Would it help adding identity primary key and making current composite key as [non clustered unique index] help? What other options do we have? 

DB version is MS SQL 2014 Enterprise
How long do you think it will take to create an additional index?
How often are DML executed? Is this table being read often? 

Given this monstrosity has over 1 billion rows I would create separate filtered table with columns SelectID, IDType, UnID, Batch and apply there appropriate indexes.