Leveraging an index on another column with the same ordering guarantee

Question

I have a massive table that is only indexed by the auto-increment column, which is also populated with the current timestamp (which is not indexed).

CREATE TABLE MyTable
(
    ID BIGINT NOT NULL IDENTITY(1, 1) PRIMARY KEY
    ,AuditTimestampUtc DATETIME NOT NULL DEFAULT(GETUTCDATE())
    ,...
)

If I need to query by the creation timestamp of the row, how can I do it efficiently? Adding an index is not feasible because of how gargantuan the table is (hundreds of millions to billions of rows), as we cannot afford the downtime, and I am performing a rare debugging task in a readonly environment, which is essentially

SELECT [...] FROM MyTable WHERE AuditTimestampUtc BETWEEN @Start AND @End

I am trying to debug a novel issue, and have not had to do this task before, so I would have difficulty making the argument for creating a new index. And unfortunately there is quite a process for processing a request to create and sanitize a full database dump (especially given its size), or cloning it to another environment. I have an outdated dump to experiment with, but running the final query will be supervised through a read-only account on production.

Writing a custom binary search seems like overkill, especially in a RDBMS, but alas computers are not mind-readers, even though it is apparent to a person that the identity column can be used as a surrogate ordering* to efficiently search the table by creation time.

_{*Assuming nobody enables IDENTITY_INSERT to violate this temporal ordering guarantee.}

---

P.S. I do not believe the database platform is very relevant to this question for the first time ever (ignoring the specific syntactical differences of declaring the index/default constraint/etc) but I am using SQL Server.

Answer 1

You could create a temporary table containing just the two columns you're interested in, using the key column as a pointer into the "real" table. Something like:

CREATE TABLE #t
(
    ID int NOT NULL
    , AuditTimestampUtc datetime NOT NULL
);

Insert rows from MyTable like this:

INSERT INTO #t WITH (TABLOCKX) (ID, AuditTimeStampUtc)
SELECT mt.ID
    , mt.AuditTimeStampUtc
FROM dbo.MyTable mt

Then create an index on the table like this:

CREATE CLUSTERED INDEX t_AuditTimeStampUtc
ON #t (AuditTimeStampUtc);

Now, you should be able to query the "real" table, making use of the index on the #temp table, as in:

SELECT <columns from mt>
FROM dbo.MyTable mt
    INNER JOIN #t t ON mt.ID = t.ID
WHERE t.AuditTimeStampUtc >= '2019-06-01 00:00:00'
    AND t.AuditTimeStampUtc < '2019-07-01 00:00:00'

The query above will, probably, do an index seek on the non-clustered index t_AuditTimeStampUtc, with a nested loops join into MyTable. This may be faster than just querying the original table. Especially if you need to do multiple queries like this against MyTable.

Copying data from a large table might seem like a bad idea. If the original table had only the two columns, then yes, I'd agree it's a dumb thing to do. However, if MyTable has many columns, the temp table will only occupy a small fraction of the space of the main table, and will be much more efficient.

Answer 2

Here is a binary search algorithm I wrote for this task, modified from the pseudo-code on the Wikipedia page that should work for both deleted rows and NULLs.

DECLARE @SearchValue DATETIME = '2019-11-20'--make sure to be cognizant of time zones

--begin algorithm

DECLARE @LowerID BIGINT, @CurrentID BIGINT, @UpperID BIGINT
DECLARE @CurrentValue DATETIME
DECLARE @DidFind BIT = 0, @IterationCount INT = 0

SELECT
    @LowerID = MIN(ID)
    ,@UpperID = MAX(ID)
FROM MyTable

SET @CurrentID = (@LowerID + @UpperID) / 2--midpoint (implicit round down)

WHILE @LowerID <= @UpperID
BEGIN
    SELECT
        @IterationCount += 1
        ,@CurrentValue = NULL--important to handle deleted rows

    SELECT @CurrentValue = AuditTimeStampUtc
    FROM MyTable
    WHERE ID = @CurrentID

    SELECT--debug statement
        [@LowerID] = @LowerID
        ,[@CurrentID] = @CurrentID
        ,[@UpperID] = @UpperID
        ,[@CurrentValue] = @CurrentValue

    IF @CurrentValue IS NULL--row is probably deleted
    BEGIN
        IF @CurrentID = @UpperID RAISERROR('NULL values in the table broke the algorithm', 16, 1)
        ELSE SET @CurrentID = @CurrentID + ((@UpperID - @CurrentID) / 2)--newer rows are less likely to be deleted
    END--@CurrentValue IS NULL
    ELSE
    BEGIN--@CurrentValue IS NOT NULL
        IF @CurrentValue < @SearchValue SET @LowerID = @CurrentID + 1
        ELSE IF @CurrentValue > @SearchValue SET @UpperID = @CurrentID - 1
        ELSE BEGIN
            SET @DidFind = 1
            BREAK--all done
        END

        SET @CurrentID = (@LowerID + @UpperID) / 2
    END--@CurrentValue IS NOT NULL
END

SELECT--output results
    [SearchValue] = @SearchValue
    ,[DidFind] = @DidFind
    ,[NearestID] = @CurrentID
    ,[NearestValue] = @CurrentValue
    ,[NumIterations] = @IterationCount

In my case it took 29 iterations to the find the nearest row, with a few iterations stumbling on deleted rows.

Answer 3

If you're running SQL Server 2016 or later, I would suggest you take a strong look at Columnstore Indexing.

Before I go much further down that rabbit hole, I'll suggest that for this specific issue, if you want to minimize space usage, you can create a Nonclustered Columnstore Index on the ID and AuditTimestampUtc columns.

Due to how Columnstore Indexes are stored on disk, the overall disk usage would be significantly smaller than a similar footprint taken up by a typical Nonclustered Index, especially if you use the COLUMNSTORE_ARCHIVE data compression option.

Normally, you'd want to index all columns in a table as you're limited to only one Columnstore Index per table, but again, for the sake of argument, you could start here and I suspect you will see massive speed improvement from this query.

Answer 4

Alternatively you can create your own Statistics type table.

Create table myTable_Statistics(id int default(0) ,StartTime datetime not null)

Create clustered index myTable_Statistics_id on myTable_Statistics(id)
go

Create nonclustered index myTable_Statistics_time on myTable_Statistics(StartTime)
go

    declare @Start datetime='1970-01-01'
    declare @interval int=6
    ;With CTE as
    (
    select top 700 ROW_NUMBER()over(order by number)rn from master..spt_values
    )
    insert into myTable_Statistics (StartTime)
    select (DATEADD(MONTH,@interval*(rn-1),@Start))
    from CTE

Inserting is one time process.First you need to do thorough ANALYSIS (like deciding startdate,interval etc) of your real table (myTable).

Then populate myTable_Statistics accordingly .

Copying all the data from a table that takes multiple gigabytes on disk in to memory seems like a really bad idea

Like in my case it is only 700 rows.So it will be hardly So you do not have to copy so many data.

I have no idea if my_table data will be keep populating.

If it keep populating then you can update id column of myTable_Statistics from Time to time update using CDC process.

first update may take time.

Declare @lastid int
Select @lastid=max(id) from my_table (nolock)-- It is safe to use nolock

update myTable_Statistics
set id=ca.id
from myTable_Statistics mts
cross apply(select max(id)id from my_table mt where id>@lastid and mt.Dates<=mts.StartTime)ca

Now query your real table,

declare @s datetime='1955-09-03'
declare @e datetime='2019-12-31'

declare @minid int,@maxid int

select @minid=min(id),@maxid=max(id) 
from myTable_Statistics
where StartTime>=@s and StartTime<=@e

select * from dbo.my_table
where id>=@minid and id<=@maxid
and auditTimeTamputc>=@s and auditTimeTamputc<=@e

Optimizer will definitely first use Clustered Index to select that range of data using id.

Then on that resultset further filter will be applied.

and auditTimeTamputc>=@s and auditTimeTamputc<=@e

Or to be safe,

select * from
(
select * from dbo.my_table -- mention require column name
where id>=@minid and id<=@maxid

)
where auditTimeTamputc>=@s and auditTimeTamputc<=@e