CREATE TABLE dbo.IntervalDatetimesRIT ( id INT NOT NULL, node AS datediff(second,convert(datetime,'19700101',112),upper) - datediff(second,convert(datetime,'19700101',112),upper) % POWER(2, FLOOR(LOG((datediff(second,convert(datetime,'19700101',112),lower) - 1) ^ datediff(second,convert(datetime,'19700101',112),upper))/log(2))) PERSISTED NOT NULL, lower DATETIME NOT NULL, upper DATETIME NOT NULL, CONSTRAINT PK_IntervalDatetimesRIT PRIMARY KEY(id), CONSTRAINT CHK_IntervalDatetimesRIT_upper_ge_lower CHECK(upper >= lower), CONSTRAINT CHK_IntervalDatetimesRIT_lower_ms CHECK(DATEPART(ms,lower)=0), CONSTRAINT CHK_IntervalDatetimesRIT_upper_ms CHECK(DATEPART(ms,upper)=0) ); CREATE INDEX node_lower_13313 ON dbo.IntervalDatetimesRIT(node, lower); CREATE INDEX node_upper_13313 ON dbo.IntervalDatetimesRIT(node, upper);
CREATE FUNCTION dbo.leftAndMiddleNodes(@lower AS DATETIME, @upper AS DATETIME) RETURNS @T TABLE ( minNode INT NOT NULL ,maxNode INT NOT NULL ) AS BEGIN DECLARE @node AS INT = 1073741824; DECLARE @step AS INT = @node / 2; WHILE @step >= 1 BEGIN IF DATEADD(second,@node,convert(datetime,'19700101',112)) > @lower SET @node -= @step; ELSE IF @lower > DATEADD(second,@node,convert(datetime,'19700101',112)) BEGIN INSERT INTO @T VALUES(@node,@node); SET @node += @step; END ELSE BREAK; SET @step /= 2; END; INSERT INTO @T VALUES(DATEDIFF(second,convert(datetime,'19700101',112),@lower),DATEDIFF(second,convert(datetime,'19700101',112),@upper)); RETURN; END;
CREATE FUNCTION dbo.rightNodes(@lower AS DATETIME, @upper AS DATETIME) RETURNS @T TABLE ( node INT NOT NULL PRIMARY KEY ) AS BEGIN DECLARE @node AS INT = 1073741824; DECLARE @step AS INT = @node / 2; WHILE @step >= 1 BEGIN IF @upper > DATEADD(second,@node,convert(datetime,'19700101',112)) SET @node += @step ELSE IF DATEADD(second,@node,convert(datetime,'19700101',112)) > @upper BEGIN INSERT INTO @T(node) VALUES(@node); SET @node -= @step END ELSE BREAK; SET @step /= 2; END; RETURN; END;
/* Original/classic/slow query DECLARE @l AS DATETIME = '20000701 00:00:00', @u AS DATETIME = '20000704 14:25:18'; SELECT id FROM dbo.IntervalDatetimesRIT WHERE upper >= @l AND @u >= lower */ -- Optimized query, using the Relational Interval Tree DECLARE @l AS DATETIME = '20000701 00:00:00', @u AS DATETIME = '20000704 14:25:18'; SELECT I.id FROM dbo.IntervalDatetimesRIT AS I JOIN dbo.leftAndMiddleNodes(@l, @u) AS L ON I.node BETWEEN L.minNode AND L.maxNode AND I.upper >= @l UNION ALL SELECT I.id FROM dbo.IntervalDatetimesRIT AS I JOIN dbo.rightNodes(@l, @u) AS R ON I.node = R.node AND @u >= I.lower
CREATE TABLE dbo.IntervalDatesRIT ( id INT NOT NULL, node AS cast(datediff(day,convert(date,'19100415',112),upper) - datediff(day,convert(date,'19100415',112),upper) % POWER(2, FLOOR(LOG((datediff(day,convert(date,'19100415',112),lower) - 1) ^ datediff(day,convert(date,'19100415',112),upper))/log(2))) -32768 as smallint) PERSISTED NOT NULL, lower DATE NOT NULL, upper DATE NOT NULL, CONSTRAINT PK_IntervalDatesRIT PRIMARY KEY(id), CONSTRAINT CHK_IntervalDatesRIT_upper_ge_lower CHECK(upper >= lower) ); CREATE INDEX node_lower_13310 ON dbo.IntervalDatesRIT(node, lower); CREATE INDEX node_upper_13310 ON dbo.IntervalDatesRIT(node, upper);
CREATE FUNCTION dbo.leftAndMiddleNodes(@lower AS DATE, @upper AS DATE) RETURNS @T TABLE ( minNode SMALLINT NOT NULL ,maxNode SMALLINT NOT NULL ) AS BEGIN DECLARE @node AS INT = 32768; DECLARE @step AS INT = @node / 2; WHILE @step >= 1 BEGIN IF DATEADD(day,@node,convert(date,'19100415',112)) > @lower SET @node -= @step; ELSE IF @lower > DATEADD(day,@node,convert(date,'19100415',112)) BEGIN INSERT INTO @T VALUES(@node-32768,@node-32768); SET @node += @step; END ELSE BREAK; SET @step /= 2; END; INSERT INTO @T VALUES(DATEDIFF(day,convert(date,'19100415',112),@lower)-32768,DATEDIFF(day,convert(date,'19100415',112),@upper)-32768); RETURN; END;
CREATE FUNCTION dbo.rightNodes(@lower AS DATE, @upper AS DATE) RETURNS @T TABLE ( node SMALLINT NOT NULL PRIMARY KEY ) AS BEGIN DECLARE @node AS INT = 32768; DECLARE @step AS INT = @node / 2; WHILE @step >= 1 BEGIN IF @upper > DATEADD(day,@node,convert(date,'19100415',112)) SET @node += @step ELSE IF DATEADD(day,@node,convert(date,'19100415',112)) > @upper BEGIN INSERT INTO @T(node) VALUES(@node-32768); SET @node -= @step END ELSE BREAK; SET @step /= 2; END; RETURN; END;
/* Original/classic/slow query DECLARE @l AS DATE = '20000701', @u AS DATE = '20000704'; SELECT id FROM dbo.IntervalDatesRIT WHERE upper >= @l AND @u >= lower */ -- Optimized query, using the Relational Interval Tree DECLARE @l AS DATE = '20000701', @u AS DATE = '20000704'; SELECT I.id FROM dbo.IntervalDatesRIT AS I JOIN dbo.leftAndMiddleNodes(@l, @u) AS L ON I.node BETWEEN L.minNode AND L.maxNode AND I.upper >= @l UNION ALL SELECT I.id FROM dbo.IntervalDatesRIT AS I JOIN dbo.rightNodes(@l, @u) AS R ON I.node = R.node AND @u >= I.lower
Back to SQL Server main menu. Mail your comments to gertjans@xs4all.nl.