Unique constraint on multiple columns and one of them already has index

There is much stuff around about 'unique' vs 'index' and I read lot of them, but still can't find explanation for my case.

In short, my database currently has a non-clustered index on two columns.
We have some inconsistent state as a result of data duplication and I want to add a unique constraint on all four columns of the table.
Since 'unique' will create an index under the hood does it still make sense to keep the old index around?

More specifically, it goes something like:

create table Stuff (
  id PK, 
  col1 varchar not null, 
  col2 varchar not null, 
  col3 bigint not null, 
  col4 bigint not null);
create index for_search on Stuff (col3, col4);
alter table Stuff 
  add constraint data_integrity_above_all 
  UNIQUE (col1, col2, col3, col4);

and if the answer is 'yes', then would it be a good move to specify UNIQUE (col3, col4, col1, col2); column order or is it too much implicit and not end well on maintenance?

More information about the nature of the data: col3 and col4 are another table ids (but not FK); col1, col2 -- user data.

DB: SQL Server 2012

If the purpose of the unique constraint (with its associated unique index) is simply to enforce uniqueness then you should change the column order for your unique constraint to col3, col4, col1, col2 and then your index will be redundant and can be dropped.

Otherwise there may be some benefit from having another index on your table with different leading columns, you should consider your workload, if the table is often accessed with a predicate on col1 or on both col1 and col2 and maybe that is a good case to have those columns first in the key.

Also @srutzky comment about the clustered index has merit and is worth considering.

StackExchange Database Administrators Q#154906, answer score: 3