/*YAMC
Yet Another Median Calculation
SQL Server 2005 gives us yet another way to calculate a median. The secret is the ROW_NUMBER() function, it can be used to find the "middle" row. ROW_NUMBER() is a bit special because an alias for it cannot be used in a predicate in the same query. Either a CTE or sub-query can be used to get around this.
The basic idea is to order the data on the value for which you need to calculate a median, then select the row whose ROW_NUMBER() is half the size of the result of the query. There is a problem though, if the number of rows is even, there is no single "middle" row.
The options here are to pick a value between the "middle" rows or just pick one of the rows. The value between the two "middle" values is called the financial median. If the first of the two "middle" rows is used it is called the statistical median.
*/
-- this is a very simple example table
-- we will use as a source of data for
-- median calculations
create
table data
(
id int Primary Key,
value float
)
-- see then end of this note for a helper
-- script that will fill the table with
-- some random data.
/*
Now we look at some solutions using CTE's
*/
-- this calculates the financial median
with positions
as(
select (1 + Count(*)) / 2 as mid,
1-(count(*) % 2) as even
from data
),
rows
as
(
select value,
row_number() over (order by value) as rn
from data
)
select AVG(value) from rows JOIN positions on
rn in (positions.mid, positions.mid + positions.even)
/*
The first CTE, positions, calculates the a couple of aggregates on our sample data.
position.mid is the number of the middle row if the number of rows is odd, otherwise it is the number of the first middle row.
position.even is a marker that is one if the number of rows is even and zero otherwise.
The second CTE, rows, calculates the row number of each value in our sample data when ordered by value. The ROW_NUMBER() is aliased as rows.rn. You might be tempted use this alias in a predicate of this CTE to shortcut the calculation of the median, but an alias for the ROW_NUMBER() function cannot be used in a predicate of the expression that defines it.
The final expression selects the average value of the values from the positions CTE whose row number is either position.mid or position.mid + position.even. Note that when the number of rows in data is odd both position.mid and position.mid + position.even will be the same value.
The result of averaging one or two rows will be the financial median for the values in the data table.
Another way to calculate the median, which can be used in versions of SQL Server prior to 2005, is to move the sorted values into a temporary table that has an identity column. The identity column is, in effect, the same as the ROW_NUMBER(). Then, as the ROW_NUMBER based solution does, pick the "middle" row
*/
-- temp table median calculation of median
declare
@positions TABLE
(id int identity, value float)
insert into @positions
select value from data order by value
DECLARE @mid int
DECLARE @even int
SELECT @mid = (1 + count(*))/2,
@even = 1 - (count(*) % 2)
from @positions
select AVG(value) from @positions
where id in (@mid, @mid+@even)
/*
Is there any advantage to using the ROW_NUMBER based solution? If you compare the actual execution plan of the two calculations run in a single batch, the ROW_NUMBER based one has an insignificant advantage, 48% vs. 52% of the overall plan on my test system.
The ROW_NUMBER solution does have one nice feature though, it is a SQL expression and the temporary table solution is a batch, not an expression. You can use this fact to improve the relative performance of the ROW_NUMBER based calculation. If you know you are going to do this median calculation very often you can add an index to the value column of the data table. This, of course, is not for free, you are making a space/time tradeoff by spending space to cut down time.
*/
-- index to speed up ROW_NUMBER
-- based median calculation
create
index value_indx on data(value)
/*
With this index in place you will find a notable difference between the execution plans for the ROW_NUMBER and temporary table calculations, the ROW_NUMBER calculation takes up only 37% of the overall plan on my test system.
The reason for this is that when there is no index that sorts the values the ROW_NUMBER calculation must build a temporary table itself and sort it, just like temporary table calculation does. But the temporary table solution always builds the temporary table, even if there is a index available to sort it. The ROW_NUMBER solution mearly has to walk over the index to find the middle value.
Calculating the statistical mean, the one that always uses one of the values from the table, takes a bit more work, but not much.
*/
-- calculation of statistical mean
with
positions
as
(
select (1 + Count(*)) / 2 as mid,
1-(count(*) % 2) as even
from data
),
rows
as
(
select value,
row_number() over (order by value) as rn
from data
)
select TOP 1 value from rows JOIN positions on
rn in (positions.mid, positions.mid + positions.even)
ORDER BY rn
/*
For the statistical mean you must sort the results by row number and pick the first one. If you want the last one then do an DESC sort.
This calculation isn't a real aggregate, but you can get some of the effect of an aggregate by wrapping it inside of an inline table valued user defined function. Note that because the ROW_NUMBER calculation is a SQL expression you can do this. The temporary table solution can only be wrapped into a multi-line user defined function.
*/
-- median TVF
-- note that this function
-- always returns a table
-- with a single row
CREATE
FUNCTION dataMedian()
returns table
return
with
positions
as
(
select (1 + Count(*)) / 2 as mid,
1-(count(*) % 2) as even
from data
),
rows
as
(
select value,
row_number() over (order by value) as rn
from data
)
select AVG(value) as median from rows JOIN positions on
rn in (positions.mid, positions.mid + positions.even)
/*
So if you now want to get all the values in the data table that are greater than the median you can do something like:
*/
Select
id, value from data JOIN dbo.dataMedian()
ON value > median
/*
So that is yet another median calculation for SQL Server. In some cases it will may provide better performance than using a temporary table, but at the cost of space. It not worse that using a temporary table and gives you the option of making the space/time tradeoff whenever you feel it is necessary.
*/
-- helper script to fill sample TABLE data
set
nocount on
declare @index int
set @index = 20001
while @index > 0
BEGIN
Insert into data values (@index, RAND() * 1000)
set @index = @index - 1
END