Ranking and Numbering rows – and subsets of rows – in T-SQL
I recently had to deal with a scenario where I needed to pivot out some rows after ordering (ranking) them according to specific rules so I could present some rows of data as columns, but in a specific order (don’t ask why, it’ll make me grind my teeth about data analysts that don’t understand how to analyse data…). The ordering in itself was only part of the solution, as to Pivot the data, the keys need to be specified in the query, so the natural keys can’t be used. The scenario is set out below:
Fig 1: Rank and Pivot. The Rank column needed to be added
My first thought was that I’d have to solve this with a cursor, which wasn’t a practical option as there were 1.5m rows of data to process, and if my solution involves a cursor I instantly think it’s a lousy solution. However I was pleased to discover the T-SQL function ROW_NUMBER() which allows you to add row numbering to ordered data and even subgroups of that data. (The below samples use the AdventureWorks2008 database.)
First up, basic row numbering:
SELECT ROW_NUMBER() OVER (ORDER BY ProductId) AS ID_Key
, [ProductID]
, [LocationID]
, [Shelf]
, [Bin]
, [Quantity]FROM [Production].[ProductInventory]
WHERE [ProductID] IN (1,2,3,4)
The above query adds an ID key to the data based on ordering by the ProductID field. The ROW_NUMBER() function requires an OVER clause to know on what basis it should assign the key, and this has to be an ORDER BY statement. The end result looks like this:
Fig 2: Simple row numbering
You can extend this to order within a subgroup, by specifying a PARTITION BY clause so ROW_NUMBER() operates with that subgroup. In the example below I partition by ProductId:
SELECT ROW_NUMBER() OVER (PARTITION BY ProductId ORDER BY Quantity DESC) AS Subset_ID_Key
, [ProductID]
, [LocationID]
, [Shelf]
, [Bin]
, [Quantity]FROM [Production].[ProductInventory]
WHERE [ProductID] IN (1,2,3,4)
Which yields this result, with the ranking now only applying within a Product Id:
Fig 3: Row numbering within a Subgroup
Which can then be pivoted on the rank, as the key of the rank is now known:
SELECT ProductID
, [1] AS Bin_1
, [2] AS Bin_3
, [3] AS Bin_3FROM
(
SELECT ROW_NUMBER() OVER (PARTITION BY ProductId ORDER BY Quantity DESC) AS Subset_ID_Key
, [ProductID]
, [Bin]FROM [Production].[ProductInventory]
WHERE [ProductID] IN (1,2,3,4)
) AS Pivot_Source
PIVOT
(
MAX(Bin)
FOR Subset_ID_Key IN ([1],[2],[3])
) AS Pivot_Output
Which yields this final output:
Fig 4: Ranked and Pivoted
All done within a single query, and not a cursor in sight. ROW_NUMBER() was a great function to discover!
MSDN Documentation is here for:
- ROW_NUMBER() – the key function
- OVER – ordering and subgrouping the results of ROW_NUMBER
- PIVOT – for pivoting out the results
Use the Index, Luke
While I’m on a T-SQL bent, I stumbled upon (literally, beware of StumbleUpon as a way to waste heroic amounts of time) a free eBook called “Use The Index, Luke”. Its by a chap called Markus Winand, who I freely admit to having never heard of (and Google isn’t particularly enlightening).
However it’s a work in progress explaining in relatively clear terms what database indexes are, how they work and how they can impact performance. It’s a pretty important topic for anyone who writes SQL – so I’d recommend reading what’s there and tracking it’s progress.
Why to avoid DISTINCT and GROUP BY to get unique records
This is a quick and dirty post on the use of DISTINCT or GROUP BY to get unique records, based on something I helped a developer with over the last couple of weeks.
Their thought process was that because they were getting duplicate records, the easiest way to get rid of them was to slap a DISTINCT at the start of the query to get unique results. Which, in a sense, is OK – because it worked (sort of).However there’s two very good reasons why this is not always a good approach.
#1: Your query is wrong
If you are getting back duplicate records, what it probably means is that you are really doing your query wrong. The below example is an admittedly imperfect example of this – as the first query returns far more than intended – but was close to what I was dealing with:
USE AdventureWorks
/* Query 1: Using DISTINCT to try to eliminate duplicates */
select DISTINCT
s.Name,
CASE
WHEN sc.ContactTypeID = 11 THEN ‘Y’
ELSE ‘N’
END AS ’OwnerContact’
from Sales.Store s
left join Sales.StoreContact sc
ON s.CustomerID = sc.CustomerID/* Query 2: Using a properly formed WHERE clause */
select s.Name,
‘Y’ AS ’OwnerContact’
from Sales.Store s
left join Sales.StoreContact sc
ON s.CustomerID = sc.CustomerID
WHERE sc.ContactTypeID = 11
What I’m trying to illustrate with the example above is that if you consider more carefully what records you are bringing back in your joins, you are less likely to end up with duplicates. By making sure you are only joining to tables in such a way as to bring back the data you need is going to reduce the risk of other errors creeping in.
#2: Performance
If you are getting duplicate records, you are bringing back more data than you need. On top of this the DISTINCT or GROUP BY operations are having to go over the whole returned data set to identify unique records. This can get pretty expensive pretty quicky in terms of database operations.
From my perspective badly performing queries are a lesser sin than incorrect ones. I doubt many business users will be making decisions based on query length, but they will on the data you serve up to them.
Summing up
All I want to do in this post is make you pause and think before doing a DISTINCT or GROUP BY purely to eliminate duplicates – especially if you don’t really understand why you are getting them. A better designed and more accurate query can often get rid of the dupes and cut off the risk of bad data in the future.
Update 25 Jul 2011: Mark Caldwell articulates it better than me @ SQL Team Blog: Why I Hate DISTINCT
An SQL alternative to the SCD
In SQL 2008 a new T-SQL construct was added - the MERGE operation. (Ok, pedants will know this wasn’t new to Oracle, but it was new to SQL Server).
This operation allows for the merging of a dataset into a reference dataset – which can be remarkably similar to Insert / Update operations effected by the Slowly Changing Dimension transformation. However the way it operates is very different. Instead of the SCD’s row by row evaluation approach, the MERGE operation is a set based operation. What this means is it compares the whole of the source dataset to the reference dataset in a single pass. This has significant implications for performance – on a site where I implemented this the operation which took 1,200 seconds in the SCD cut down to 51 seconds using a Merge.
There are limitations and differences to be aware of:
- You cannot directly return row counts for Insert / Update / Ignore operations in the Merge
- As it is a bulk operation a single row will cause failure of the whole batch
- There’s no GUI – just hand crafted SQL
- Less error trapping / logging options
- More flexibility in terms of actions when matches / non matches are found
The main reason why you would consider the SQL Merge – it handles Type 1, and with a little cunning, Type 2 dimensions – in a fraction of the time it takes the SCD to plod through. It’s still not as fast as a proper in memory comparison using something such as TableDifference – but it’s always good to know you have something else available in your toolkit.
Further information:
- Using the SQL MERGE Statement for Slowly Changing Dimension Processing – from the Kimball Group
- How to create type 1 & 2 SCD’s using standard SSIS components (other than the SCD) (at the bottom of the post) – Benny Austin
Multiple LIKE clauses in a single WHERE statement
I recently came up against a scenario where, in amongst a number of other filters, I had to deal with a couple of wildcard criteria. As there is no option to have multiple LIKE clauses in native SQL, such as WHERE Field LIKE IN (‘%Option1%’,'%Option2%’), I feared I was stuck with having to duplicate my WHERE clause in its entirety for each LIKE operation – until I found this cunning bit of code (from the thread here):
/* Apply Multiple LIKE clauses in a single WHERE clause */
SELECT *
FROM [AdventureWorks].[Person].[Contact]
WHERE CASE
WHEN FirstName LIKE ‘Gusta%’ THEN 1
WHEN FirstName LIKE ‘Cath%’ THEN 1
END = 1
An elegant solution!
Handling Recursive Hierarchies in SQL Server
I was recently posed a question on handling recursive hierarchies which left me completely stumped, so I had to find a good solution to it. This post will cover all that, but first -
…what is a Recursive Hierarchy?
A recursive hierarchy is a one where children of parent members can be parents themselves, such as an Organisation chart, or chart of accounts. A simple example is shown below, where the node A2 is both a child of A1 and a parent of A4 & A5:
Fig 1: A Simple Recursive Hierarchy
Handling these within a database environment can be difficult because the number of parent / child relationships (aka “Depth”) can vary, so it is impossible to create a fixed width table to accomodate them for their future growth. Consequently, most operational systems store these in a simple two level tabel which records the parent / child relationships only, as shown below.
Fig 2: The Parent Child Table
From the operation systems point of view this is usually all it needs to function as they usually only need to know the relationship one step in either direction, which this table satisfies. Determining the parent of A2 or the children of A2 can be determined with a simple SELECT query.
How do they cause difficulties for reporting?
The difficulty faced in a SQL based reporting situation is that you cannot easily determine relationships between parents and grandchildren, great-grandchildren, etc. without nesting queries. The specific problem with this is that you cannot know from a parent exactly how many levels of children lie below it. Vice versa, you cannot know how many levels of parents a child record has. Consequently you cannot know in advance how deep to nest your queries. From a practical standpoint as well, these relationships could be hundreds or thousands deep, and writing that query can pose problems in itself, even if you know there are exactly 1,567 levels in it!
The problem I was posed was superficially simple – if every level of such a hierarchy can have values, such as laid out below, how do you determine the aggregate value for a given parent and all its children?
Fig 3: The Values Table
For a tiny example such as this, nested queries is an option – your sub selects would only have to go two deep at most. But what if the depth changed, or ran into the tens or hundreds? Also, how do you create the generic query for any node in the tree? And for added complexity, what if there are multiple trees in the hierarchy? The problems are not trivial to resolve, but I have located two good solutions.
Solution 1: The LR Method
The first, and in my view most elegant, comes from Michael J. Kamfonas in his article “Recursive Hierarchies: The Relational Taboo!“, which I strongly recommend reading to fully grasp the solution. His solution is to pre-number each node in the hierarchy with a value that on the Left forms a lower bound and on the Right an upper bound that allows you to select all nodes under it using a BETWEEN clause. A picture explains this concept clearly, with the L Value in Pink and the R Value in Green:
Fig 4: The LR Method applied to a Recursive Hierachy
So as you can see for node A2, the range between its L Value of 2 and R Value of 7 encompasses the L Values of all its children (A4 with 3, and A5 with 5). So to select all the nodes below A2 there is no need to resolve any relationships, you can simply select all children nodes based on their L values.
In database terms, the output looks like this:
Fig 5: The L R Table
So, if I wanted to know the sum of all the values below any given node, I would use this pseudo SQL:
SELECT SUM(Value)
FROM ValuesTable vLEFT JOIN LR_Table lr
ON v.Node = lr.NodeWHERE lr.L_Value
BETWEEN (SELECT L_Value FROM LRTable WHERE Node = ‘ParentNode’)
AND (SELECT R_Value FROM LRTable WHERE Node = ‘ParentNode’)
To demonstrate this in practice, I have created some SQL which creates a recursive hierarchy table as in Fig 2, a values table as in Fig 3 and an LR table as in Fig 5. The LR table is then populated with L/R values by a simple cursor which logs its activity to the message window so you can see what it is doing. I don’t think it will win any prizes for efficiency, but it works! The code sample then closes out with a T-SQL sample which calculates the sum of all it and its childrens values. Download the sample code here.
Solution 2: Kimball Helper Table
Unsurprisingly, Ralph Kimball also has an approach. His involves the use of a “Helper Table” which he describes in his article “Helper tables handle dimensions with complex hierarchies“. As for solution 1 I advise reading the article as I will only go into the practical implications of his approach.
The Kimball approach requires creating a table that stores every path from each node in the tree to itself and to every node below it. Looking at the example below, this means creating one row per node, plus one row for each path down the tree for each parent node to all of its children.
Fig 6: Paths to capture in a Helper Table
The helper table also includes a few extra flags – the Level Depth from the top parent, and flags for the top level parent nodes (Topmost) and lowest level children nodes (Lowest). The output table ends up looking like this:
Fig 7: The Kimball Helper Table
This makes navigating relative positions in the hierarchy simpler, and allows the answering of the original question easy as all that is required is to join on the Values table to the Helper table for the given parent node, as below:
SELECT SUM(Value)
FROM HelperTable rLEFT JOIN ValuesTable v
ON r.ChildNode = v.NodeWHERE ParentNode = ‘ParentNode’
However – as you will see from my sample code – populating these tables is much more complex. The sample code creates and populates the recursive hierarchy table as in Fig 2, a values table as in Fig 3 and an Helper table as in Fig 7. The process of populating the table is a mix of cursors, inserts and updates and is much trickier to get right than the LR method, because of the higher demands for information, such as Depth from Parent.
Recursive Hierarchies – no problem!
Above are two solid approaches to the Recursive Hierarchy problem. The code samples provided should help you get started on understanding how to handle these scenarios when trying to report against them in Database based reporting scenarios such as in SSRS. SSAS and other OLAP based reporting handles all of this in its stride however, as described here, for example.
If you find issues with my code samples or see improvements, i’d love to know about them, so please keep me posted about your experiences with them.
Finally, I will close out with the old joke on the subject:
To truly understand recursion,
you must first understand recursion
10 Essential SQL Tips for Developers
10 Essential SQL Tips for Developers courtesy of Eric Shafer – covers some important basics – if you scan through that list and don’t understand all 10 points, make an effort to ensure you do – they aren’t mind boggling obscurities but important basics.
ti7mfkj6sr
Count the number of rows in every Table in a Database in no time!
Here is a piece of T-SQL code that uses DMV’s (Dynamic Management Views) to give an approximate row count of every table in your database in virtually no time at all. Bear in mind it is running off collected statistics so won’t always be 100% accurate – but it’s far quicker than doing a Count(*) on a table by table basis when you just need a rough idea when doing sizing. In case you don’t know what DMV’s there are, go poke around in SSMS – [Database] > Views > System Views and see what’s there. Anyway, the code:
SELECT s.[Name] as [Schema] , t.[name] as [Table] , SUM(p.rows) as [RowCount] FROM sys.schemas s LEFT JOIN sys.tables t ON s.schema_id = t.schema_id LEFT JOIN sys.partitions p ON t.object_id = p.object_id LEFT JOIN sys.allocation_units a ON p.partition_id = a.container_id WHERE p.index_id in(0,1) -- 0 heap table , 1 table with clustered index AND p.rows is not null AND a.type = 1 -- row-data only , not LOB GROUP BY s.[Name], t.[name] ORDER BY 1,2
For a very swift explanation – sys.schemas and sys.tables list the schemas and tables in the database, so joining these together on schema_id gives a list of all tables by schema in the database. Adding on sys.partitions then pulls in the partitions associated with each table, and finally sys.allocation_units pulls in the allocation units, which i’m not quite sure what they are – the guts of this query were pulled from another blog which I embarrasingly can’t trace back to now.
I’m no expert on DMV’s so if you have any views on the quality of this query – please leave a comment with your thoughts.