{"id":3317,"date":"2020-05-17T17:59:57","date_gmt":"2020-05-17T17:59:57","guid":{"rendered":"https:\/\/nenadnoveljic.com\/blog\/?p=3317"},"modified":"2020-05-17T17:59:59","modified_gmt":"2020-05-17T17:59:59","slug":"suboptimal-sort-calculation","status":"publish","type":"post","link":"https:\/\/nenadnoveljic.com\/blog\/suboptimal-sort-calculation\/","title":{"rendered":"Suboptimal Sort Calculation"},"content":{"rendered":"

There is a substantial difference in how MS SQL Server and Oracle estimate the cost of a sort operation. The critical point isn’t in the algorithm itself. As we shall see, the problem exists rather on a much more basic level – in the inputs variables. On the one hand, Oracle relies on column statistics to produce accurate estimates. On the other hand, MS SQL Server uses data type size declared in the column definition. But this value is just the static maximum size that a column can store. The actual data size is, in fact, often much lower. Consequently, the estimates will be out of the ballpark in such cases. It goes without saying that this can have a detrimental effect on performance. I’ll be showing such a case and provide a workaround for affected queries.<\/p>\n

But first of all, let me demonstrate how both products calculate the sort cost. The versions I used are SQL Server 2019 and Oracle 19c.<\/p>\n

Oracle<\/h1>\n

I’ll be using the following data model with Oracle:<\/p>\n

create table t ( \n  c_type_size_1<\/span>_length_1 varchar2(1<\/span>),\n  c_type_size_4000<\/span>_length_1 varchar2(4000<\/span>),\n  c_type_size_4000<\/span>_length_4000<\/span> varchar2(4000<\/span>)\n);\n\ninsert into t \n  select 'A', 'A', LPAD('A',4000<\/span>,'A') from dual connect by level<=1e4 ;\n  \ncommit ;\n\nexec dbms_stats.gather_table_stats(null,'T');<\/code><\/pre>\n
Basically, I created a table with three varchar2 columns. I inserted a single character into two columns with different max sizes: varchar2(1) and varchar2(4000). Finally, I inserted a long string into the varchar2(4000) column.<\/p>\n
With the following statements we can observe how the calculation changes over two dimensions. One is the data type size in the column definition. The other is the actual data size:<\/p>\n
\nselect c_type_size_1_length_1 from t order by 1 ;\nselect c_type_size_4000_length_1 from t order by 1 ;\nselect c_type_size_4000_length_4000 from t order by 1 ;\n<\/code><\/pre>\n
Here’s, for example, the execution plan for the last statement:<\/p>\n
SELECT * FROM table(DBMS_XPLAN.DISPLAY_CURSOR);\nselect c_type_size_4000_length_4000 from t order by 1\n\nPlan hash value: 961378228\n\n-----------------------------------------------------------------------------------\n| Id  | Operation          | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |\n-----------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT   |      |       |       |       |  4037 (100)|          |\n|   1 |  SORT ORDER BY     |      | 10000 |    38M|    39M|  4037<\/span>   (1)| 00:00:01 |\n|   2 |   TABLE ACCESS FULL| T    | 10000 |    38M|       |   737<\/span>   (0)| 00:00:01 |\n-----------------------------------------------------------------------------------\n<\/code><\/pre>\n
The cost attributed to the sort operation also entails the cost of its child operation. Consequently, the contribution of the sort operation itself is 3300 (4037<\/span>–737)<\/span>.<\/p>\n
The table below shows the sort costs for all three cases.<\/p>\n\n\n\n\n\t\n\n\t\n\t\n\t
actual size, max size<\/th>cost<\/th>\n<\/tr>\n<\/thead>\n
1, 1<\/td>1<\/td>\n<\/tr>\n
1, 4000<\/span><\/td>1<\/span><\/td>\n<\/tr>\n
4000, 4000<\/td>3300<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n
As you can see, the cost didn’t increase after storing a single character in the varchar2(4000) column. The optimizer ignored the data type max size and used the actual data size. This is correct, because the resource consumption depends on the actual result set size and not on the defined column limit.<\/p>\n
By the way, the following column statistics were used for estimating the actual data size:<\/p>\n
col column_name format a30\nselect column_name,avg_col_len from dba_tab_columns  where owner='SYS' and table_name='T';\n\nCOLUMN_NAME                    AVG_COL_LEN\n------------------------------ -----------\nC_TYPE_SIZE_1_LENGTH_1                   2\nC_TYPE_SIZE_4000_LENGTH_1                2\nC_TYPE_SIZE_4000_LENGTH_4000          4001<\/code><\/pre>\n
MS SQL Server<\/h1>\n
Unfortunately, MS SQL Server handles it the other way around. I’m using a similar data model to prove that:<\/p>\n
create table t ( \n  c_type_size_1_length_1 nvarchar(1),\n  c_type_size_4000_length_1 nvarchar(4000),\n  c_type_size_4000_length_4000 nvarchar(4000)\n);\n\n\ninsert into t\nSELECT TOP (10000)\n  'A', 'A', right(replicate('A',4000) + 'A',4000) \n  FROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2 \n  OPTION (MAXDOP 1);\n\nCREATE STATISTICS c_type_size_1_length_1 \n  ON t ( c_type_size_1_length_1 ) with fullscan ;\n  \nCREATE STATISTICS c_type_size_4000_length_1 \n  ON t ( c_type_size_4000_length_1 ) with fullscan ;\n\nCREATE STATISTICS c_type_size_4000_length_4000\n  ON t ( c_type_size_4000_length_4000 ) with fullscan ;\n\n\nselect c_type_size_1_length_1 from t order by 1 ;\n\nselect c_type_size_4000_length_1 from t order by 1 ;\n\nselect c_type_size_4000_length_4000 from t order by 1 ;<\/code><\/pre>\n
In the following execution plan the result set contains a single character that was retrieved from the nvarchar(4000) column c_type_size_4000_length_1:<\/p>\n
\"\"<\/a><\/p>\n
According to the output above, the data size used for the cost calculation is 4011B, even though the effective length of stored information was 1.<\/p>\n
Curiously, the column statistics are accurate, but the optimizer didn’t use them at all:<\/p>\n
Statistics for INDEX 'c_type_size_4000_length_1'.\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\n                            Name                         Updated                            Rows                    Rows Sampled                           Steps                         Density              Average Key Length                    String Index\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n       c_type_size_4000_length_1             May 15 2020 11:04AM                           10000                           10000                               1                               0                               2                             YES                                                           10000                               0\n\n                     All Density                  Average Length<\/span>                         Columns\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n                               1                               2<\/span>       c_type_size_4000_length_1\n\n                 Histogram Steps\n                    RANGE_HI_KEY                      RANGE_ROWS                         EQ_ROWS             DISTINCT_RANGE_ROWS                  AVG_RANGE_ROWS\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n                               A                               0                           10000                               0                               1<\/code><\/pre>\n
Comparing the costs of sorting different columns also confirms that the data type size is used in the sort calculation cost:<\/p>\n\n\n\n\n\t\n\n\t\n\t\n\t
actual size, max size<\/th>cost<\/th>\n<\/tr>\n<\/thead>\n
1, 1<\/td>0.30734<\/td>\n<\/tr>\n
1, 4000<\/span><\/td>56.34279<\/span><\/td>\n<\/tr>\n
4000, 4000<\/td>56.34279<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n
In other words, MS SQL Sever ignored the column statistics.<\/p>\n
As we shall see later, a misestimate in the sort cost calculation can cause a butterfly effect leading to performance disasters with more complex execution plans.<\/p>\n
Case study<\/h1>\n
Below is the model of a recent production issue:<\/p>\n
drop table t_big\n\ncreate table t_big( n1 integer, n2 integer )\n\ninsert into t_big\nSELECT TOP (100000)\n  1, CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id]))\n  FROM sys.all_objects s1 CROSS JOIN sys.all_objects AS s2\n  OPTION (MAXDOP 1);\n\ndrop table t_small\n\ncreate table t_small ( \n  n1 integer, \n  c_type_size_1_length_1  nvarchar(1), \n  c_type_size_4000_length_1  nvarchar(4000)\n)\n\ninsert into t_small values (1,'A','A')<\/code><\/pre>\n
Let’s consider the following query that joins two tables producing a large result set due to the large driving table. For reference, we’re first selecting the small column, that is nvarchar(1), from the small table.<\/p>\n
select \n\tc_type_size_1_length_1\n  from t_big left outer join t_small on t_big.n1 = t_small.n1 \n  order by t_big.n2<\/code><\/pre>\n
\"\"<\/a><\/p>\n
Expectedly, sort was applied to the hash join (HJ) output. The optimizer figured out correctly that this is an efficient plan, because the cost of sorting the result set containing 1 character column is low.<\/p>\n
But the execution plan changes for worse after selecting the nvarchar(4000) column, although the data is exactly the same (only the declared data size changed):<\/p>\n
select \n\tc_type_size_4000_length_1\n  from t_big left outer join t_small on t_big.n1 = t_small.n1 \n  order by t_big.n2 ;<\/code><\/pre>\n
\"\"<\/a><\/p>\n
Simply put, because of the increased data type size (not the actual data, though!) the optimizer wrongly decided that sorting the whole result set at the end is too expensive. The large table was sorted before joining it with the small table by using nested loop (NL), instead. As a consequence, NL generated 100’000<\/span> page visits on the small table:<\/p>\n
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 't_big'. Scan count 3, logical reads 384, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 't_small'. Scan count 1, logical reads 100000<\/span>, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.<\/code><\/pre>\n
To quantify the magnitude of this damage, we’ll compare the execution statistics with those produced by the same query, but with HJ enforced:<\/p>\n
select \n\tc_type_size_4000_length_1\n  from t_big left outer hash join<\/span> t_small on t_big.n1 = t_small.n1 \n  order by t_big.n2<\/code><\/pre>\n
The small table was accessed only once<\/span> with HJ:<\/p>\n
(100000 rows affected)\nTable 't_big'. Scan count 3, logical reads 384, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 't_small'. Scan count 1, logical reads 1<\/span>, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 'Workfile'. Scan count 2, logical reads 280, physical reads 31, page server reads 0, read-ahead reads 249, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.\nTable 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.<\/code><\/pre>\n
\"\"<\/a><\/p>\n
In conclusion, the sort cost overestimate caused an increase of logical reads by several orders of magnitude.<\/p>\n
Anti-pattern<\/h1>\n
Based on the example above, we can generalize an anti-pattern to be found in the affected execution plans. Potentially troublesome queries can have a premature sort that feeds a NL, which, in turn, produces a logical read explosion.<\/p>\n
Workaround<\/h1>\n
Is there a way to fix that (apart from obvious options of reducing the data type size to a bare minimum or eliminating unnecessary order by clauses)?<\/p>\n
You can try producing a better execution plan and enforce it in the query store. To do this, you can temporarily increase the CPU cost weight to make the sort more attractive to the optimizer. The sort cost, namely, consists chiefly of the IO cost.<\/p>\n
First, check the actual weights:<\/p>\n
DBCC    TRACEON (3604);\nDBCC    SHOWWEIGHTS;\n\nDBCC Opt Weights CPU: 1.000000  IO: 1.000000 SPID 54<\/code><\/pre>\n
Second, increase temporarily the CPU weight and clear the proccache:<\/p>\n
DBCC SETCPUWEIGHT(100)\nDBCC FREEPROCCACHE<\/code><\/pre>\n
(Keep increasing the CPU weight until you get a better plan.)<\/p>\n
Third, restore the old weight value once you got a good plan:<\/p>\n
DBCC SETCPUWEIGHT(1)<\/code><\/pre>\n
Finally, fix the new plan in the query store.<\/p>\n
Below we can see such a plan that I enforced in the query store after applying the described procedure.<\/p>\n
\"\"<\/a><\/p>\n
Summary<\/h1>\n
In summary, unlike Oracle, MS SQL Server uses the data type length from the column definition instead of column statistics for estimating sort operation cost. Consequently, the sort cost will be massively overestimated for underused columns. This will inevitably lead to bad plans. There isn’t a good solution for this. But in some cases, it is feasible to temporarily increase CPU weight to obtain a better plan that can then be pinned in the query store.<\/p>\n
Related blog posts<\/h1>\n
In this blog post I didn’t cover any details of the sort calculation. I’ve been focusing on a very specific inefficiency in MS SQL Server, instead, and comparing it to Oracle.<\/p>\n
But I was already dealing in detail with the sort cost calculation in Oracle in the following articles:<\/p>\n