Determine least number of columns required for unique (clustered) index I'm in the situation where I am encouraged to tune an existing database and in the process either introduce or remove indexes as seem best fit. 

I was looking at a certain table and noticed that the Database Tuning Adviser had been previously used, due to the fact that a lot of the indexes began with _dta_..... (Hooray!)

I had a glace at the Clustered Index on said table 

CREATE CLUSTERED INDEX [_dta_index_TABLENAME_c_5_1970822083__K6_K8] ON [dbo].[TABLE_NAME]
([register] ASC, [deleted] ASC)
WITH (
         PAD_INDEX = OFF,
         STATISTICS_NORECOMPUTE = OFF,
         SORT_IN_TEMPDB = OFF,
         DROP_EXISTING = OFF,
         ONLINE = OFF,
         ALLOW_ROW_LOCKS = ON,
         ALLOW_PAGE_LOCKS = ON
     ) 
     ON [PRIMARY]
 GO


So the index isn't unique and probably has a very special distribution in the histogram. Both columns register and deleted are defined as NULL in the table DDL:

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[TABLE__NAME](
    [delete]      [smallint] NULL,
    [timestamp]   [int] NULL,
    [root_id]     [int] NULL,
    [object_id]   [int] NULL,
    [object_type] [int] NULL,
    [register]    [int] NULL,
    [reg_type]    [int] NULL,
    [deleted]     [int] NULL
) ON [PRIMARY]

GO


...which got me thinking. 

Question

How can I determine the least required number of columns to create an UNIQUE index with the following premises:


Seeing as delete will contain either a 1 or 0 I omitted this column from my train of thoughts
I don't know the data
I do know the number of records is 58'934'964 (and growing by 20 every second)
I do know the distinct counts of each column:  

delete      = 1
timestamp   = 29'030'385
root_id     = 1'744'414
object_id   = 58'934'823
object_type = 33
register    = 9'229'854
reg_type    = 8
deleted     = 723'952



What I tried

I had a look at the sys.dm_db_missing_index_details DMV to determine if SQL Server knows when to create an UNIQUE index. 

select 

sddmid.index_handle, 
db_name(sddmid.database_id), 
so.name, 
sddmid.object_id, 
sddmid.equality_columns, 
sddmid.inequality_columns, 
sddmid.included_columns, 
sddmid.statement 

from sys.dm_db_missing_index_details sddmid
join sys.objects as so 
    on so.object_id = sddmid.object_id
where database_id = db_id('DATABASE')
and so.name = 'TABLE_NAME'


But no details in that view.

Possible Solution

Would I really have to perform a statement over all columns like this:

select 
-- distinct single column
count(distinct delete), count(distinct timestamp), count(distinct root_id),...
-- distinct double column
count(distinct delete,timestamp), count(distinct delete,root_id), ...
--- distinct triple column
count(distinct delete,timestamp,root_id), count(distinct delete,timestamp,object_id), ...
--- distinct quadruple column
count(distinct delete,timestamp,root_id,object_id), ...
...
from TABLE_NAME 


until I have found a combination that is distinct/unique?

I guess there is a better solution...
I don't know how useful this will prove to be as I've not tested it out thoroughly, but you should be able to utilize Statistics Density Vector values to see what columns (and column combinations) will provide a higher likelihood of unique values.  The script listed below basically pulls all the Density Vector values for all stats on a given table.  This is not complex as it looks for the lowest Density Vector with the lowest Average Record Length.  Whatever records appear first in this result set should be your best candidates for unique columns.

OF NOTE: This only evaluates statistics that exist, so you may need to create multi-column statistics to fill in any gaps as auto-generated stats are limited to single columns.  

Why is this better than the count approach? 

You can specify sample rates with statistics which should reduce analysis times on larger tables, and the table scan (and locking that will come with it) when running the various COUNT aggregations also won't occur when creating the stats against a busy system.

Here's the script:

SET NOCOUNT ON

-- provide table name you wish to analyze
DECLARE @tableName NVARCHAR(256) = 'dbo.TABLE__NAME'
      , @statsName NVARCHAR(128), @dSQL NVARCHAR(1024)

DECLARE @stats_densityVector TABLE
(
    StatName    NVARCHAR(1024),
    AllDensity  REAL,
    AvgLength   BIGINT,
    Columns     NVARCHAR(1024)
)

DECLARE statsHeader CURSOR
FOR
    SELECT  name AS stats_name
    FROM    sys.stats s
    WHERE   s.object_id = OBJECT_ID(@tableName)

OPEN statsHeader
FETCH NEXT FROM statsHeader
INTO    @statsName

WHILE @@FETCH_STATUS = 0
BEGIN

    SET @dSQL = 'DBCC SHOW_STATISTICS (''' + @tableName + ''', ' + @statsName + ') WITH DENSITY_VECTOR, NO_INFOMSGS'
    INSERT INTO @stats_densityVector (AllDensity, AvgLength, Columns)
    EXEC (@dSQL)

    UPDATE @stats_densityVector
    SET StatName = @statsName
    WHERE StatName IS NULL

    FETCH NEXT FROM statsHeader
    INTO    @statsName
END

CLOSE statsHeader
DEALLOCATE statsHeader

SET NOCOUNT OFF

SELECT  OBJECT_SCHEMA_NAME(s.object_id) + '.' + OBJECT_NAME(s.object_id) AS table_name
        , dv.*
        , sp.rows_sampled
        , sp.rows
        , (1.0 * sp.rows_sampled) / (1.0 * sp.rows) AS sample_pct
FROM sys.stats s 
        CROSS APPLY sys.dm_db_stats_properties (s.object_id, s.stats_id) sp
        INNER JOIN @stats_densityVector dv
            ON dv.StatName = s.name
WHERE s.object_id = OBJECT_ID(@tableName)
ORDER BY dv.AllDensity, dv.AvgLength


Here's a dbfiddle.uk example of how this would work on a contrived example.