I'll post an answer to get started. My first thought was that it should be possible to take advantage of the order-preserving nature of a nested loop join along with a few helper tables that have one row for each letter. The tricky part was going to be looping in such a way that the results were ordered by length as well as avoiding duplicates. For example, when cross joining a CTE that includes all 26 capital letters along with '', you can end up generating
'A' + '' + 'A' and
'' + 'A' + 'A' which is of course the same string.
The first decision was where to store the helper data. I tried using a temp table but this had a surprisingly negative impact on performance, even though the data fit into a single page. The temp table contained the below data:
UNION ALL SELECT 'B'
UNION ALL SELECT 'Y'
UNION ALL SELECT 'Z'
Compared to using a CTE, the query took 3X longer with a clustered table and 4X longer with a heap. I don't believe the problem is that the data is on disk. It should be read into memory as a single page and processed in memory for the entire plan. Perhaps SQL Server can work with data from a Constant Scan operator more efficiently than it can with data stored in typical rowstore pages.
Interestingly, SQL Server chooses to put the ordered results from a single page tempdb table with ordered data into a table spool:
SQL Server often puts results for the inner table of a cross join into a table spool, even if it seems nonsensical to do so. I think that the optimizer needs a little bit of work in this area. I ran the query with the
NO_PERFORMANCE_SPOOL to avoid the performance hit.
One problem with using a CTE to store the helper data is that the data isn't guaranteed to be ordered. I can't think of why the optimizer would choose not to order it and in all of my tests the data was processed in the order that I wrote the CTE:
However, best not to take any chances, especially if there's a way to do it without a large performance overhead. It's possible to order the data in a derived table by adding a superfluous
TOP operator. For example:
(SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR)
That addition to the query should guarantee that results will be returned in the correct order. I expected all of the sorts to have a large negative performance impact. The query optimizer expected this as well based on the estimated costs:
Very surprisingly, I could not observe any statistically significant difference in cpu time or runtime with or without explicit ordering. If anything, the query seemed to run faster with the
ORDER BY! I have no explanation for this behavior.
The tricky part of the problem was to figure out how to insert blank characters into the right places. As mentioned before a simple
CROSS JOIN would result in duplicate data. We know that the 100000000th string will have a length of six characters because:
26 + 26 ^2 + 26^3 + 26^4 + 26^5 = 914654 < 100000000
26 + 26 ^2 + 26^3 + 26^4 + 26^5 + 26 ^ 6 = 321272406 > 100000000
Therefore we only need to join to the letter CTE six times. Suppose that we join to the CTE six times, grab one letter from each CTE, and concatenate them all together. Suppose the leftmost letter is not blank. If any of the subsequent letters are blank that means that the string is less than six characters long so it is a duplicate. Therefore, we can prevent duplicates by finding the first non-blank character and requiring all characters after it also not be blank. I chose to track this by assigning a
FLAG column to one of the CTEs and by adding a check to the
WHERE clause. This should be more clear after looking at the query. The final query is as follows:
WITH FIRST_CHAR (CHR) AS
UNION ALL SELECT 'B'
UNION ALL SELECT 'C'
UNION ALL SELECT 'D'
UNION ALL SELECT 'E'
UNION ALL SELECT 'F'
UNION ALL SELECT 'G'
UNION ALL SELECT 'H'
UNION ALL SELECT 'I'
UNION ALL SELECT 'J'
UNION ALL SELECT 'K'
UNION ALL SELECT 'L'
UNION ALL SELECT 'M'
UNION ALL SELECT 'N'
UNION ALL SELECT 'O'
UNION ALL SELECT 'P'
UNION ALL SELECT 'Q'
UNION ALL SELECT 'R'
UNION ALL SELECT 'S'
UNION ALL SELECT 'T'
UNION ALL SELECT 'U'
UNION ALL SELECT 'V'
UNION ALL SELECT 'W'
UNION ALL SELECT 'X'
UNION ALL SELECT 'Y'
UNION ALL SELECT 'Z'
, ALL_CHAR (CHR, FLAG) AS
SELECT '', 0 CHR
UNION ALL SELECT 'A', 1
UNION ALL SELECT 'B', 1
UNION ALL SELECT 'C', 1
UNION ALL SELECT 'D', 1
UNION ALL SELECT 'E', 1
UNION ALL SELECT 'F', 1
UNION ALL SELECT 'G', 1
UNION ALL SELECT 'H', 1
UNION ALL SELECT 'I', 1
UNION ALL SELECT 'J', 1
UNION ALL SELECT 'K', 1
UNION ALL SELECT 'L', 1
UNION ALL SELECT 'M', 1
UNION ALL SELECT 'N', 1
UNION ALL SELECT 'O', 1
UNION ALL SELECT 'P', 1
UNION ALL SELECT 'Q', 1
UNION ALL SELECT 'R', 1
UNION ALL SELECT 'S', 1
UNION ALL SELECT 'T', 1
UNION ALL SELECT 'U', 1
UNION ALL SELECT 'V', 1
UNION ALL SELECT 'W', 1
UNION ALL SELECT 'X', 1
UNION ALL SELECT 'Y', 1
UNION ALL SELECT 'Z', 1
SELECT TOP (100000000)
d6.CHR + d5.CHR + d4.CHR + d3.CHR + d2.CHR + d1.CHR
FROM (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d6
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d5
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d4
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d3
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d2
CROSS JOIN (SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR) d1
WHERE (d2.FLAG + d3.FLAG + d4.FLAG + d5.FLAG + d6.FLAG) =
WHEN d6.FLAG = 1 THEN 5
WHEN d5.FLAG = 1 THEN 4
WHEN d4.FLAG = 1 THEN 3
WHEN d3.FLAG = 1 THEN 2
WHEN d2.FLAG = 1 THEN 1
ELSE 0 END
OPTION (MAXDOP 1, FORCE ORDER, LOOP JOIN, NO_PERFORMANCE_SPOOL);
The CTEs are as described above.
ALL_CHAR is joined to five times because it includes a row for a blank character. The final character in the string should never be blank so a separate CTE is defined for it,
FIRST_CHAR. The extra flag column in
ALL_CHAR is used to prevent duplicates as described above. There may be a more efficient way to do this check but there are definitely more inefficient ways to do it. One attempt by me with
POWER() made the query run six times slower than the current version.
MAXDOP 1 and
FORCE ORDER hints are essential to make sure that the order is preserved in the query. An annotated estimated plan might be helpful to see why the joins are in their current order:
Query plans are often read right to left but row requests happen from left to right. Ideally, SQL Server will request exactly 100 million rows from the
d1 constant scan operator. As you move from left to right I expect fewer rows to be requested from each operator. We can see this in the actual execution plan. Additionally, below is a screenshot from SQL Sentry Plan Explorer:
We got exactly 100 million rows from d1 which is a good thing. Note that the ratio of rows between d2 and d3 is almost exactly 27:1 (165336 * 27 = 4464072) which makes sense if you think about how the cross join will work. The ratio of rows between d1 and d2 is 22.4 which represents some wasted work. I believe the extra rows are from duplicates (due to the blank characters in the middle of the strings) which do not make it past the nested loop join operator that does the filtering.
LOOP JOIN hint is technically unnecessary because a
CROSS JOIN can only be implemented as a loop join in SQL Server. The
NO_PERFORMANCE_SPOOL is to prevent the unnecessary table spooling. Omitting the spool hint made the query take 3X longer on my machine.
The final query has a cpu time of around 17 seconds and a total elapsed time of 18 seconds. That was when running the query through SSMS and discarding the result set. I am very interested in seeing other methods of generating the data.