Row-positioning problems are greatly simplified when a unique, sequential integer key has been established for a table. When this is the case, the key becomes a virtual record number, allowing ready access to any row position in the table similarly to an array. This can allow medians to be computed almost instantly, even over distribution sets with millions of values. Here’s an example:

This query does several interesting things. It begins by constructing a table to hold the distribution and adding a million rows to it. Each iteration of the loop fills the c1 column with a new random number (all the rows inserted by a single operation get the same random number). The table effectively doubles in size with each pass through the loop. The top 344,640 rows are taken with each iteration in order to ensure that the set doesn’t exceed a million values. The 344,640 limitation isn’t significant until the final pass through the loop—until then it grabs every row in financial_median and reinserts it back into the table (after the next-to-last iteration of the loop, the table contains 655,360 rows; 344,640 = 1,000,000-655,360). Though this doesn’t produce a random number in every row, it minimizes the time necessary to build the distribution so we can get to the real work of calculating its median.

Next, the query creates a clustered index on the table’s c1 column in order to sort the values in the distribution (a required step in computing its median). It then adds an identity column to the table and switches the table’s clustered index to reference it. Since the values are already sequenced when the identity column is added, they end up being numbered sequentially by it.

The final step is where the median is actually computed. The query looks up the total number of rows (so that it can determine the middle value) and returns the average of the two middle values if there’s an even number of distribution values or the middle value if there’s an odd number.

In a real-world scenario, it’s likely that only the last step would be required to calculate the median. The distribution would already exist and be sorted using a clustered index in a typical production setup. Since the number of values in the distribution might not be known in advance, I’ve included a step that looks up the number of rows in the table using a small query on sysindexes. This is just for completeness—the row count is already known in this case because we’re building the distribution and determining the median in the same query. You could just as easily use a MAX(k1) query to compute the number of values since you can safely assume that the k1 identity column is seeded at one and has been incremented sequentially throughout the table. Here’s an example:

Note the use of the SIGN() function in the median computation to facilitate handling an even or odd number of values using a single BETWEEN clause. The idea here is to add 1 to the index of the middle value for an even number of values and 0 for an odd number. This means that an even number of values will cause the average of the two middle values to be taken, while an odd number will cause the average of the lone middle value to be taken—the value itself. This approach allows us to use the same code for even and odd numbers of values.

Specifically, here’s how this works: the SIGN() expression adds one to the number of values in the distribution set in order to switch it from odd to even or vice versa, then computes the modulus of this number and 2 (to determine whether we have an even or odd number) and returns either 1 or 0, based on its sign. So, for 1,000,000 rows, we add 1, giving us 1,000,001, then take the modulus of 2, which is 1. Next, we take the SIGN() of the number, which is 1, and add it to the number of rows (divided by 2) in order to compute the k1 value of the second middle row. This allows us to compute the AVG() of these two values in order to return the financial median. For an odd number of values, the modulus ends up being 0, resulting in a SIGN() of 0, so that both terms of the BETWEEN clause refer to the same value—the set’s middle value.

The net effect of all this is that the median is computed almost instantaneously. Once the table is set up properly, the median takes less than a second to compute on the relatively scrawny 166 MHz laptop on which I'm writing this book. Considering that we’re dealing with a distribution of a million rows, that’s no small feat.

This is a classic example of SQL Server being able to outperform a traditional programming language because of its native access to the data. For a 3GL to compute the median value of a 1,000,000-value distribution, it would probably load the items into an array from disk and sort them. Once it had sorted the list, it could retrieve the middle one(s). This last process—that of indexing into the array—is usually quite fast. It’s the loading of the data into the array in the first place that takes so long, and it’s this step that SQL Server doesn’t have to worry about since it can access the data natively. Moreover, if the 3GL approach loads more items than will fit in memory, some of them will be swapped to disk (virtual memory), obviously slowing down the population process and the computation of the median.

For example, consider this scenario: A 3GL function needs to compute the financial median of a distribution set. It begins by loading the entire set from a SQL Server database into an array or linked list and sorting it. Once the array is loaded and sorted, the function knows how many rows it has and indexes into or scans for the middle one(s). Foolishly, it treats the database like a flat file system. It ignores the fact that it could ask SQL Server to sort the items before returning them. It also ignores the fact that it could query the server for the number of rows before retrieving all of them, thus alleviating the need to load the entire distribution into memory just to count the number of values it contains and compute its median. These two optimizations alone—allowing the server to sort the data and asking it for the number of items in advance—are capable of reducing the memory requirements and the time needed to fill the array or list by at least half.

But SQL Server itself can do even better than this. Since the distribution is stored in a database with which the server can work directly, it doesn’t need to load anything into an array or similar structure. This alone means that it could be orders of magnitude faster than the traditional 3GL approach. Since the data’s already “loaded,” all SQL Server has to concern itself with is locating the median value, and, as I’ve pointed out, having a sequential row identifier makes this a simple task.

To understand why the Transact-SQL approach is faster and better than the typical 3GL approach, think of SQL Server’s storage mechanisms (B-trees, pages, extents, etc.) as a linked list—a very, very smart linked list—a linked list that’s capable of keeping track of its total number of items automatically, one that tracks the distribution of values within it, and one that continuously maintains a number of high-speed access paths to its values. It’s a list that moves itself in and out of physical memory via a very sophisticated caching facility that constantly balances its distribution of values and that’s always synchronized with a permanent disk version so there’s never a reason to load or store it explicitly. It’s a list that can be shared by multiple users and to which access is streamlined automatically by a built-in query optimizer. It’s a list than can be transparently queried by multiple threads and processors simultaneously—that, by design, takes advantage of multiple Win32 operating system threads and multiple processors.

From a conceptual standpoint, SQL Server’s storage/retrieval mechanisms and a large virtual memory–based 3GL array or linked list are not that different; it’s just that SQL Server’s facilities are a couple orders of magnitude more sophisticated and refined than the typical 3GL construct. Not all storage/retrieval mechanisms are created equal. SQL Server has been tuned, retuned, worked, and reworked for over ten years now. It’s had plenty of time to grow up—to mature. It’s benefited from fierce worldwide competition on a number of fronts throughout its entire life cycle. It has some of the best programmers in the world working year-round to enhance and speed it up. Thus it provides better data storage and retrieval facilities than 95% of the 3GL developers out there could ever build. It makes no sense to build an inferior, hackneyed version of something you get free in the SQL Server box while steadfastly and inexplicably using only a small portion of the product itself.

One thing we might consider is what to do if the distribution changes fairly often. What happens if new rows are added to it hourly, for example? The k1 identity column will cease to identify distribution values sequentially, so how could we compute the median using the identity column technique? The solution would be to drop the clustered index on k1 followed by the column itself and repeat the sort portion of the earlier query, like so:

Obviously, this technique is impractical for large distributions that are volatile in nature. Each time the distribution is updated, it must be resorted. Large distributions updated more than, say, once a day are simply too much trouble for this approach. Instead, you should use one of the other median techniques listed below.

Note that it’s actually faster overall to omit the last two steps in the sorting phase. If the clustered index on c1 is left in place, computing the median takes noticeably longer (1–2 seconds on the aforementioned laptop), but the overall process of populating, sorting, and querying the set is reduced by about 15%. I’ve included the steps because the most common production scenario would have the data loaded and sorted on a fairly infrequent basis—say once a day or less—while the median might be computed thousands of times daily.

Computing a median using CASE is also relatively simple. Assume we start with this table and data:

This query returns the median value:

Here, we generate a cross-join of the #dist table with itself, then use a HAVING clause to filter out all but the median value. The CASE function allows us to count the number of i values that are less than or equal to each d value, then HAVING restricts the rows returned to the d value where this is exactly half the number of values in the set.

The number returned is the statistical median of the set of values. The statistical median of a set of values must be one of the values in the set. Given an odd number of values, this will always be the middle value. Given an even number, this will be the lesser of the two middle values. Note that it’s trivial to change the example code to return the greater of the two middle values, if that’s desirable:

A financial median, on the other hand, does not have to be one of the values of the set. In the case of an even number of values, the financial median is the average of the two middle values. Assuming this data:

here’s a Transact-SQL query that computes a financial median:

The middle values of this distribution are 3 and 4, so the query above returns 3.5 as the financial median of the distribution.

Since Transact-SQL doesn’t include a MEDIAN() aggregate function, computing vector or partitioned medians must be done using something other than the usual GROUP BY technique. Assuming this table and data:

here’s a modification of the first example to return a vector median:

"K1" is the vectoring or partitioning column in this example. If Transact-SQL had a MEDIAN() aggregate function, “k1” would be the lone item in the GROUP BY list.

A situation that none of the median queries presented thus far handles very well is the presence of duplicate values in the distribution set. In fact, in all of the examples thus far, a duplicate value near the median will cause the query to return NULL or omit the corresponding partition. The problem is that these queries group by the c1 column in the first instance of the work table. Grouping automatically combines duplicate values so that a query cannot distinguish between multiple instances of the same value. Properly handling duplicate values requires the HAVING clause to be reworked. Assuming we start with this table and data:

here’s a modification of the statistical median query that handles duplicate values:

Likewise, here’s the financial median query modified to handle duplicate values:

As you can see, things start to get a bit complex when duplicate values enter the picture. Here’s a variation of the financial median query that makes use of a key column (k1) and handles duplicates as well:

Another alternative to SELECT’s TOP n extension is the SET ROWCOUNT command. It limits the number of rows returned by a query, so you could do something like this in order to return the topmost rows from a result set:

Returning the Bottom n Rows is equally simple. To return the bottommost rows instead of the topmost, change the ORDER BY to sort in descending order.

While this solution is certainly straightforward, it can’t handle duplicates very flexibly. You get exactly three rows, no more, no less. Ties caused by duplicate values are not handled differently from any other value. If you request three rows and there’s a tie for second place, you won’t actually see the real third place row—you’ll see the row that tied for second place in the third slot instead. This may be what you want, but if it isn’t, there is a variation of this query that deals sensibly with ties. It takes advantage of the fact that assigning a variable using a query that returns more than one row assigns the value from the last row to the variable. This is a rarely used trick, and you should probably comment your code to indicate that it’s actually what you intended to do. Here’s the code:

This query uses DISTINCT to avoid being fooled by duplicates. Without it, the query wouldn’t handle duplicates any better than its predecessor. What we want to do here is assign the value of the third distinct value to our control variable so that we can then limit the rows returned by the ensuing SELECT to those with values less than or equal to it. So, if there are duplicates in the top three values, we’ll get them. If there aren’t, no harm done—the query still works as expected.

A sliding aggregate differs from a cumulative aggregate in that it reflects an aggregation of a sequence of values around each value in a set. This subset “moves” or “slides” with each value, hence the term. So, for example, a sliding average might compute the average of the current value and its preceding four siblings, like so:

Note that the sliding averages for the first four values are returned as running averages since they don’t have the required number of preceding values. Beginning with the fifth value, though, SlidingAverage reflects the mean of the current value and the four immediately before it. As with the running totals example, you can replace AVG() with different aggregate functions to compute other types of sliding aggregates.