4

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.

5

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.

4

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.

  • Interesting approach. – Max Vernon Nov 21 at 14:08
2

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.

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.