Jan 172013
 

In my previous post, I talked about ways to generate a sequence of contiguous numbers from 1 to 1,000. Now I'd like to talk about the next levels of scale: generating sets of 50,000 and 1,000,000 numbers.

Generating a set of 50,000 numbers

When starting this series, I was genuinely curious how the different approaches would scale to larger sets of numbers. At the low end I was a little dismayed to find that my favorite approach – using sys.all_objects – was not the most efficient method. But how would these different techniques scale to 50,000 rows?

    Numbers table

    Since we have already created a Numbers table with 1,000,000 rows, this query remains virtually identical:

    SELECT TOP (50000) n FROM dbo.Numbers ORDER BY n;

    Plan:

    n_50000_num

    spt_values

    Since there are only ~2,500 rows in spt_values, we need to be a little more creative if we want to use it as the source of our set generator. One way to simulate a larger table is to CROSS JOIN it against itself. If we did that raw we'd end up with ~2,500 rows squared (over 6 million). Needing only 50,000 rows, we need about 224 rows squared. So we can do this:

    ;WITH x AS 
    (
      SELECT TOP (224) number FROM [master]..spt_values
    )
    SELECT TOP (50000) n = ROW_NUMBER() OVER (ORDER BY x.number) 
    FROM x CROSS JOIN x AS y
    ORDER BY n;

    Note that this is equivalent to, but more concise than, this variation:

    SELECT TOP (50000) n = ROW_NUMBER() OVER (ORDER BY x.number) 
    FROM 
    (SELECT TOP (224) number FROM [master]..spt_values) AS x
    CROSS JOIN
    (SELECT TOP (224) number FROM [master]..spt_values) AS y
    ORDER BY n;

    In both cases, the plan looks like this:

    n_50000_spt

    sys.all_objects

    Like spt_values, sys.all_objects does not quite satisfy our 50,000 row requirement on its own, so we will need to perform a similar CROSS JOIN.

    ;;WITH x AS 
    (
      SELECT TOP (224) [object_id] FROM sys.all_objects
    )
    SELECT TOP (50000) n = ROW_NUMBER() OVER (ORDER BY x.[object_id]) 
    FROM x CROSS JOIN x AS y 
    ORDER BY n;

    Plan:

    n_50000_allobj

    Stacked CTEs

    We only need to make a minor adjustment to our stacked CTEs in order to get exactly 50,000 rows:

    ;WITH e1(n) AS
    (
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
    ), -- 10
    e2(n) AS (SELECT 1 FROM e1 CROSS JOIN e1 AS b), -- 10*10
    e3(n) AS (SELECT 1 FROM e2 CROSS JOIN e2 AS b), -- 100*100
    e4(n) AS (SELECT 1 FROM e3 CROSS JOIN (SELECT TOP 5 n FROM e1) AS b)  -- 5*10000
      SELECT n = ROW_NUMBER() OVER (ORDER BY n) FROM e4 ORDER BY n;

    Plan:

    n_50000_stack

    Recursive CTEs

    An even less substantial change is required to get 50,000 rows out of our recursive CTE: change the WHERE clause to 50,000 and change the MAXRECURSION option to zero.

    ;WITH n(n) AS
    (
        SELECT 1
        UNION ALL
        SELECT n+1 FROM n WHERE n < 50000
    )
    SELECT n FROM n ORDER BY n
    OPTION (MAXRECURSION 0);

    Plan:

    n_50000_recur

    In this case there is a warning icon on the sort – as it turns out, on my system, the sort needed to spill to tempdb. You may not see a spill on your system, but this should be a warning about the resources required for this technique.

    Performance

    As with the last set of tests, we'll compare each technique, including the Numbers table with both a cold and warm cache, and both compressed and uncompressed:

    n_50000_res1
    Runtime, in milliseconds, to generate 50,000 contiguous numbers

    To get a better visual, let's remove the recursive CTE, which was a total dog in this test and which skews the results:

    n_50000_res2
    Runtime, in milliseconds, to generate 50,000 contiguous numbers (excluding recursive CTE)

    At 1,000 rows, the difference between compressed and uncompressed was marginal, since the query only needed to read 8 and 9 pages respectively. At 50,000 rows, the gap widens a bit: 74 pages vs. 113. However, the overall cost of decompressing the data seems to outweigh the savings in I/O. So, at 50,000 rows, an uncompressed numbers table seems to be the most efficient method of deriving a contiguous set – though, admittedly, the advantage is marginal.

Generating a set of 1,000,000 numbers

While I can't envision very many use cases where you'd need a contiguous set of numbers this large, I wanted to include it for completeness, and because I did make some interesting observations at this scale.

    Numbers table

    No surprises here, our query is now:

    SELECT TOP 1000000 n FROM dbo.Numbers ORDER BY n;

    The TOP isn't strictly necessary, but that's only because we know that our Numbers table and our desired output have the same number of rows. The plan is still quite similar to previous tests:

    n_1MM_num

    spt_values

    To get a CROSS JOIN that yields 1,000,000 rows, we need to take 1,000 rows squared:

    ;WITH x AS 
    (
      SELECT TOP (1000) number FROM [master]..spt_values
    )
    SELECT n = ROW_NUMBER() OVER (ORDER BY x.number) 
    FROM x CROSS JOIN x AS y ORDER BY n;

    Plan:

    n_1MM_spt

    sys.all_objects

    Again, we need the cross product of 1,000 rows:

    ;WITH x AS 
    (
      SELECT TOP (1000) [object_id] FROM sys.all_objects
    )
    SELECT n = ROW_NUMBER() OVER (ORDER BY x.[object_id]) 
    FROM x CROSS JOIN x AS y ORDER BY n;

    Plan:

    n_1MM_sysall

    Stacked CTEs

    For the stacked CTE, we just need a slightly different combination of CROSS JOINs to get to 1,000,000 rows:

    ;WITH e1(n) AS
    (
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 
        SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
    ), -- 10
    e2(n) AS (SELECT 1 FROM e1 CROSS JOIN e1 AS b), -- 10*10
    e3(n) AS (SELECT 1 FROM e1 CROSS JOIN e2 AS b), -- 10*100
    e4(n) AS (SELECT 1 FROM e3 CROSS JOIN e3 AS b)  -- 1000*1000
      SELECT n = ROW_NUMBER() OVER (ORDER BY n) FROM e4 ORDER BY n;

    Plan:

    n_1MM_stack_parallel

    At this row size, you can see that the stacked CTE solution goes parallel. So I also ran a version with MAXDOP 1 to get a similar plan shape as before, and to see if parallelism really helps:

    n_1MM_stack_maxdop

    Recursive CTE

    The recursive CTE again has just a minor change; only the WHERE clause needs to change:

    ;WITH n(n) AS
    (
        SELECT 1
        UNION ALL
        SELECT n+1 FROM n WHERE n < 1000000
    )
    SELECT n FROM n ORDER BY n
    OPTION (MAXRECURSION 0);

    Plan:

    n_1MM_recur

    Performance

    Once again we see the performance of the recursive CTE is abysmal:

    n_1MM_res1
    Runtime, in milliseconds, to generate 1,000,000 contiguous numbers

    Removing that outlier from the graph, we get a better picture about performance:

    n_1MM_res2
    Runtime, in milliseconds, to generate 1,000,000 contiguous numbers (excluding recursive CTE)

    While again we see the uncompressed Numbers table (at least with a warm cache) as the winner, the difference even at this scale is not all that remarkable.

To be continued…

Now that we've thoroughly explored a handful of approaches to generating a sequence of numbers, we'll move on to dates. In the final post of this series, we'll walk through the construction of a date range as a set, including the use of a calendar table, and a few use cases where this can be handy.

[ Part 1 | Part 2 | Part 3 ]

 

Appendix : Row counts

You may not be trying to generate an exact number of rows; you may instead just want a straightforward way to generate a lot of rows. The following is a list of combinations of catalog views that will get you various row counts if you simply SELECT without a WHERE clause. Note that these numbers will depend on whether you are at an RTM or a service pack (since some system objects do get added or modified), and also whether you have an empty database.

Source Row counts
SQL Server 2008 R2 SQL Server 2012 SQL Server 2014
master..spt_values 2,508 2,515 2,519
master..spt_values CROSS JOIN master..spt_values 6,290,064 6,325,225 6,345,361
sys.all_objects 1,990 2,089 2,165
sys.all_columns 5,157 7,276 8,560
sys.all_objects CROSS JOIN sys.all_objects 3,960,100 4,363,921 4,687,225
sys.all_objects CROSS JOIN sys.all_columns 10,262,430 15,199,564 18,532,400
sys.all_columns CROSS JOIN sys.all_columns 26,594,649 52,940,176 73,273,600

Table 1: Row counts for various catalog view queries

  5 Responses to “Generate a set or sequence without loops – part 2”

  1. I guess if you cast n as int then Number table method would be faster. I used same query as you but cast n as int. for warm cache it took around 210 millisecond on average over 200 executions for top 1 million rows. For 50000 rows, it was around 9 milliseconds on average over 200 executions for warm cache. You can try on your machine.

    • Hi Gulli, n is actually an int. In the first post in this series I showed how I created an initial Numbers table, however I then created two additional tables which I defined beforehand (for compressed and uncompressed) and then populated from the Numbers table. You can see the column definitions here, and these are the two tables that were used for all tests in this series:

      I've updated the original post to make it clear that the Numbers table uses int. I suspect the differences in actual timings you're seeing are due to machine differences – I am running on a lowly VM on a laptop, while you are probably using a physical machine. The important part is the difference between methods, and you should see this same type of relative difference (though at different absolutes) on your machine…

  2. For spt_values I've always seen a filter on the type column as in select number from master.dbo.spt_values where type = 'p'. No DISTINCT is needed and it seeks into the clustered index (for e.g. 15 reads instead of 21 in SQL Server 2008)–but that's only for 2048 values or fewer. I've also heard that adding WITH (NOLOCK) to Numbers table accesses (including spt_values) is a boon to speed. I'm curious whether Numbers table performance improves with that hint. Row_Number() definitely beats mathematically constructing numbers from spt_values (as in N1.Number * 2048 + N2.Number). I'll do more testing when I get time.

  3. Why do you do a sort in the Recursive CTE?

    The definition itself guarantees the proper ordering, and you can avoid all the time wasted sorting an already sorted list (which, is likely slower than if it weren't already sorted).

    • Not sure why you say that. The definition of the CTE guarantees that there will be no gaps in the sequence of numbers, but there is no guarantee that it will be output in the order you expect. This is true for CTEs, derived tables, views, etc. Unless the outer query has an order by, do not rely on observed behavior to imply some guarantee about future behavior.

      Also, if the CTE "guarantees" the ordering as you suggested, then how does the ORDER BY hurt? If SQL Server guaranteed the order it would simply ignore further instructions to order and it wouldn't be dumb and sort the same set, twice, with the same ordering. So how does being explicit and specifying the order you obviously want a bad thing? Typing 8 characters?

      In this case if you are using the generated set to insert into a table, for example, you want to *guarantee* that the output will be ordered in the most efficient way for the insert. And since when you do this, it is usually a one-time or at least infrequent operation, even if that sort costs you a little more (I'm not convinced that it does), so be it. At least the destination table will have the data inserted in "pure" order right from the start, instead of having to reorganize if, for some reason, the order from the source is not aligned.

      For further information about resisting the urge to believe that observed behavior = guaranteed behavior, please see this:

      http://blogs.msdn.com/b/conor_cunningham_msft/archive/2008/08/27/no-seatbelt-expecting-order-without-order-by.aspx

 Leave a Reply

(required)

(required)