Problem statement
I have a webapp called Handlr, which is easily described as “Reddit/HN with Tags”.
A simplified db scheme could be described as this:
However, there is an issue with performantly querying hierarchical Tags. Let’s say I have the following tags:
If you want to query items that belong to “Microsoft”, you’ll also need to include everything related to
- Azure, Dotnet, Windows & Office
And their associated child tags:
- Dotnet -> FSharp, CSharp
- Azure -> WebApps, AzureFunctions
Writing a query that would handle that would not be that performant and the problem would be best described as:
“How would i query all child tags in one query”
Let’s dive in
The problem seems difficult. Until you assign a left and right bower to every tag.
In the illustration below, you notice the bowers are incremented according to their hierarchy.
Now that we know the left and right bower of the ‘Microsoft Tag’, our queries become much more simple:
- Fetch all child tags from Microsoft, exlucding the Microsoft tag:
SELECT * FROM Tags
WHERE LeftBower > 1 AND RightBower < 18
- Fetch all child tags from Microsoft, including the Microsoft Tag:
SELECT * FROM Tags
WHERE LeftBower >= 1 AND RightBower <= 18
- Fetch all items related to Microsoft.
SELECT * FROM Items
JOIN TagPerItem ON Tags.ItemId = TagPerItem.ItemId
JOIN Tags ON TagPerItem.TagId = Tags.Id
WHERE LeftBower >= 1 AND RightBower <= 18
The only thing that needs to be done is trigger a stored procedure to create a table, named HTally. This stored procedure will trigger everytime a Tag has been updated to update their bower values.
Note: original script can be found here
CREATE PROCEDURE dbo.RebuildNestedSets AS
/****************************************************************************
Purpose:
Rebuilds a "Hierarchy" table that contains the original Adjacency List,
the Nested Sets version of the same hierarchy, and several other useful
columns of data some of which need not be included in the final table.
Usage:
EXEC dbo.RebuildNestedSets
Progammer's Notes:
1. As currently written, the code reads from a table called dbo.Tags.
2. The Employee table must contain well indexed Id (child) and
ParentTagId (parent) columns.
3. The Employee table must be a "well formed" Adjacency List. That is, the
Id column must be unique and there must be a foreign key on the
ParentTagId column that points to the Id column. The table must not
contain any "cycles" (an Id in its own upline). The Root Node
must have a NULL for ParentTagId.
4. The final table, named dbo.Hierarchy, will be created in the same
database as where this stored procedure is present. IT DOES DROP THE
TABLE CALLED DBO.HIERARCHY SO BE CAREFUL THAT IT DOESN'T DROP A TABLE
NEAR AND DEAR TO YOUR HEART.
5. This code currently has no ROLLBACK capabilities so make sure that you
have met all of the requirements (and, perhaps, more) cited in #3 above.
Dependencies:
1. This stored procedure requires that the following special purpose HTally
table be present in the same database from which it runs.
--===== Create the HTally table to be used for splitting SortPath
--SQL Version
CREATE TABLE [dbo].[HTally]([N] [int] NOT NULL)
SELECT TOP 1000 --(4 * 1000 = VARBINARY(4000) in length)
N = ISNULL(CAST(
(ROW_NUMBER() OVER (ORDER BY (SELECT NULL))-1)*4+1
AS INT),0)
INTO dbo.HTally
FROM master.sys.all_columns ac1
CROSS JOIN master.sys.all_columns ac2
;
--===== Add the quintessential PK for performance.
ALTER TABLE dbo.HTally
ADD CONSTRAINT PK_HTally
PRIMARY KEY CLUSTERED (N) WITH FILLFACTOR = 100
;
Revision History:
Rev 00 - Circa 2009 - Jeff Moden
- Initial concept and creation.
Rev 01 - PASS 2010 - Jeff Moden
- Rewritten for presentation at PASS 2010.
Rev 02 - 06 Oct 2012 - Jeff Moden
- Code redacted to include a more efficient, higher performmance
method of splitting the SortPath using a custom HTally Table.
****************************************************************************/
--===========================================================================
-- Presets
--===========================================================================
--===== Suppress the auto-display of rowcounts to prevent from returning
-- false errors if called from a GUI or other application.
SET NOCOUNT ON;
--===== Start a duration timer
DECLARE @StartTime DATETIME,
@Duration CHAR(12);
SELECT @StartTime = GETDATE();
--===========================================================================
-- 1. Read ALL the nodes in a given level as indicated by the parent/
-- child relationship in the Adjacency List.
-- 2. As we read the nodes in a given level, mark each node with the
-- current level number.
-- 3. As we read the nodes in a given level, convert the Id to
-- a Binary(4) and concatenate it with the parents in the previous
-- level's binary string of Id's. This will build the
-- SortPath.
-- 4. Number the rows according to the Sort Path. This will number the
-- rows in the same order that the push-stack method would number
-- them.
--===========================================================================
--===== Conditionally drop the final table to make reruns easier in SSMS.
IF OBJECT_ID('FK_Hierarchy_Hierarchy') IS NOT NULL
ALTER TABLE dbo.Hierarchy
DROP CONSTRAINT FK_Hierarchy_Hierarchy;
IF OBJECT_ID('dbo.Hierarchy','U') IS NOT NULL
DROP TABLE dbo.Hierarchy;
RAISERROR('Building the initial table and SortPath...',0,1) WITH NOWAIT;
--===== Build the new table on-the-fly including some place holders
WITH cteBuildPath AS
( --=== This is the "anchor" part of the recursive CTE.
-- The only thing it does is load the Root Node.
SELECT anchor.Id,
anchor.ParentTagId,
HLevel = 1,
SortPath = CAST(
CAST(anchor.Id AS BINARY(16))
AS VARBINARY(4000)) --Up to 1000 levels deep. (250 as uniqueidentifier)
FROM dbo.Tags AS anchor
WHERE ParentTagId IS NULL --Only the Root Node has a NULL ParentTagId
UNION ALL
--==== This is the "recursive" part of the CTE that adds 1 for each level
-- and concatenates each level of Id's to the SortPath column.
SELECT recur.Id,
recur.ParentTagId,
HLevel = cte.HLevel + 1,
SortPath = CAST( --This does the concatenation to build SortPath
cte.SortPath + CAST(Recur.Id AS BINARY(16))
AS VARBINARY(4000))
FROM dbo.Tags AS recur WITH (TABLOCK)
INNER JOIN cteBuildPath AS cte
ON cte.Id = recur.ParentTagId
) --=== This final INSERT/SELECT creates the Node # in the same order as a
-- push-stack would. It also creates the final table with some
-- "reserved" columns on the fly. We'll leave the SortPath column in
-- place because we're still going to need it later.
-- The ISNULLs make NOT NULL columns
SELECT Id = ISNULL(sorted.Id,'00000000-0000-0000-0000-000000000000'),
sorted.ParentTagId,
HLevel = ISNULL(sorted.HLevel,0),
LeftBower = ISNULL(CAST(0 AS INT),0), --Place holder
RightBower = ISNULL(CAST(0 AS INT),0), --Place holder
NodeNumber = ROW_NUMBER() OVER (ORDER BY sorted.SortPath),
NodeCount = ISNULL(CAST(0 AS INT),0), --Place holder
SortPath = ISNULL(sorted.SortPath,sorted.SortPath)
INTO dbo.Hierarchy
FROM cteBuildPath AS sorted
OPTION (MAXRECURSION 100) --Change this IF necessary
;
RAISERROR('There are %u rows in dbo.Hierarchy',0,1,@@ROWCOUNT) WITH NOWAIT;
--===== Display the cumulative duration
SELECT @Duration = CONVERT(CHAR(12),GETDATE()-@StartTime,114);
RAISERROR('Cumulative Duration = %s',0,1,@Duration) WITH NOWAIT;
--===========================================================================
-- Using the information created in the table above, create the
-- NodeCount column and the LeftBower and RightBower columns to create
-- the Nested Sets hierarchical structure.
--===========================================================================
RAISERROR('Building the Nested Sets...',0,1) WITH NOWAIT;
--===== Declare a working variable to hold the result of the calculation
-- of the LeftBower so that it may be easily used to create the
-- RightBower in a single scan of the final table.
DECLARE @LeftBower INT
;
--===== Create the Nested Sets from the information available in the table
-- and in the following CTE. This uses the proprietary form of UPDATE
-- available in SQL Server for extra performance.
WITH cteCountDownlines AS
( --=== Count each occurance of Id in the sort path
SELECT Id = CAST(SUBSTRING(h.SortPath,t.N,16) AS uniqueidentifier),
NodeCount = COUNT(*) --Includes current node
FROM dbo.Hierarchy h,
dbo.HTally t
WHERE t.N BETWEEN 1 AND DATALENGTH(SortPath)
GROUP BY SUBSTRING(h.SortPath,t.N,16)
) --=== Update the NodeCount and calculate both Bowers
UPDATE h
SET @LeftBower = LeftBower = 2 * NodeNumber - HLevel,
h.NodeCount = downline.NodeCount,
h.RightBower = (downline.NodeCount - 1) * 2 + @LeftBower + 1
FROM dbo.Hierarchy h
JOIN cteCountDownlines downline
ON h.Id = downline.Id
;
RAISERROR('%u rows have been updated to Nested Sets',0,1,@@ROWCOUNT)
WITH NOWAIT;
RAISERROR('If the rowcounts don''t match, there may be orphans.'
,0,1,@@ROWCOUNT)WITH NOWAIT;
--===== Display the cumulative duration
SELECT @Duration = CONVERT(CHAR(12),GETDATE()-@StartTime,114);
RAISERROR('Cumulative Duration = %s',0,1,@Duration) WITH NOWAIT;
--===========================================================================
-- Prepare the table for high performance reads by adding indexes.
--===========================================================================
RAISERROR('Building the indexes...',0,1) WITH NOWAIT;
--===== Direct support for the Nested Sets
ALTER TABLE dbo.Hierarchy
ADD CONSTRAINT PK_Hierarchy
PRIMARY KEY CLUSTERED (LeftBower, RightBower) WITH FILLFACTOR = 100
;
CREATE UNIQUE INDEX AK_Hierarchy
ON dbo.Hierarchy (Id) WITH FILLFACTOR = 100
;
ALTER TABLE dbo.Hierarchy
ADD CONSTRAINT FK_Hierarchy_Hierarchy FOREIGN KEY
(ParentTagId) REFERENCES dbo.Hierarchy (Id)
ON UPDATE NO ACTION
ON DELETE NO ACTION
;
--===========================================================================
-- Update the tags table
--===========================================================================
UPDATE
--t.LeftBower,t.RightBower, t.Depth
dbo.Tags
SET
LeftBower = h.LeftBower,
RightBower = h.RightBower,
Depth = h.HLevel
FROM
dbo.Tags t
INNER JOIN
dbo.Hierarchy h
ON
t.Id = h.Id
;
RAISERROR('Updated tags with bower information',0,1) WITH NOWAIT;
--===========================================================================
-- Exit
--===========================================================================
--===== Display the cumulative duration
SELECT @Duration = CONVERT(CHAR(12),GETDATE()-@StartTime,114);
RAISERROR('Cumulative Duration = %s',0,1,@Duration) WITH NOWAIT;
RAISERROR('===============================================',0,1) WITH NOWAIT;
RAISERROR('RUN COMPLETE',0,1) WITH NOWAIT;
RAISERROR('===============================================',0,1) WITH NOWAIT;
GO
Notes
If you’re using the above script for Azure, you’ll need to adjust the initial script to build the HTally table. Since ‘master.sys’ doesn’t exist.
CREATE TABLE [dbo].[HTally]([N] [int] NOT NULL)
ALTER TABLE dbo.HTally
ADD CONSTRAINT PK_HTally
PRIMARY KEY CLUSTERED (N)
;
INSERT INTO [dbo].[HTally]([N])
SELECT TOP 1000 --(4 * 1000 = VARBINARY(4000) in length)
N = ISNULL(CAST(
(ROW_NUMBER() OVER (ORDER BY (SELECT NULL))-1)*4+1
AS INT),0)
FROM sys.all_columns ac1
CROSS JOIN sys.all_columns ac2
;
Links
Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets
Alternatives
Someone pointed out the HierarchyId as a solution for Hierarchical data. That might have been a better solution at the time.
More examples on MSDN about it here