Puzzle - Counterfeit Coins

SQL Server Magazine (February 2008) has the following puzzle:

• This puzzle is from Clifford Jensen. Suppose you have 10 stacks of coins, with 10 coins in each stack. One stack consists of 10 counterfeit coins and the other 9 stacks each consist of 10 legitimate coins. Each legitimate coin weighs exactly 1 gram. Each counterfeit coin weighs exactly 0.9 grams. You have a digital scale that’s graduated in tenths of grams. Using the scale to take only one reading, determine which stack has the 10 counterfeit coins. You can weigh any number of coins from any number of stacks, but must you weigh them all together (i.e., you can take only one reading from the scale).
  

It is obvious that the solution has to be one in which coins of all 10 stacks are used in some way. In order to distinguish one stack from another, we need to take different number of coins from different stacks. So one solution is

1. Label the 10 stacks (arbitrarily) from 1 to 10
2. Take n coins from stack n, where n = 1, 2, …, 10. Put them on the scale and take a reading.
3. Focus only on the single decimal digit. If it is 9, then the counterfeit stack is stack number 1; 8: stack 2; 7: stack 3; 6: stack 4; 5: stack 5; 4: stack 6; 3: stack 7; 2: stack 8; 1: stack 9. So, if we let j be the decimal digit from the reading, then the stack with all counterfeit coins is stack number (10 - j).
   
   

Understanding SQL plan_generation_num

SQL Server 2005 provides two important dynamic views sys.dm_exec_cached_plans (P) and sys.dm_exec_query_stats (S) to help understand cached plans and their statistics. Joining on [plan_handle], P and S have a 1-to-0 relationship. P has a record for every compiled plan in the plan cache, and S can have a record for every query statement in the corresponding cached plan. S can be empty for a cached plan of cache object types "Parse Tree" or "CLR Compiled Proc" or for objects such as system stored procedures, ad hoc queries, prepared statements, etc. Since I am mainly interested in user stored procedures and their compilation/recompilation frequency, for our purposes, P and S have a 1-to-many relationship - a cached plan for a stored procedure in P has one or more corresponding recoreds in S, one for each query statement in the stored procedure.

There are a lot of interesting columns in P and S, especially in S, and here I will only discuss what I have learned about plan_generation_num in S. SQL Server 2005 treats the compiled plan for a stored procedure as an array of subplans, one for each query statement. If an individual subplan needs recompilation, it does so without causing the whole plan to recompile. In doing so, SQL Server increments the plan_generation_num on the subplan record to be 1 + MAX(plan_generation_num for all subplans). The general distribution of plan_generation_num among all subplans for a given plan is such that it has multiple of 1's and distinct numbers > 1. That is because all subplans start with 1 as their plan_generation_num. Appendix A is the query for learning plan_generation_num.

Based on the above discussion, the higher the maximum(plan_generation_num) for a cached plan, the more frequent the plan has been recompiled. Be aware that it is not the recompilation of the whole plan but rather of the individual subplans that is building up maximum(plan_generation_num).

Appendix A.
Following is a query to list all plan_generation_num for a stored procedure
---- Analze recompilation via.plan_generation_num
DECLARE @vcName VARCHAR(50);
SELECT @vcName = 'qp_Temp';
SELECT
P.plan_handle,
S.statement_start_offset, S.statement_end_offset,
S.plan_generation_num,
S.execution_count,
P.usecounts,
S.creation_time,
S.last_execution_time,
sqlSmt = SUBSTRING(T2.text, (S.statement_start_offset/2) + 1, ((CASE WHEN S.statement_end_offset > 0 THEN S.statement_end_offset ELSE DATALENGTH(T2.text) END - S.statement_start_offset)/2) + 1),
L.query_plan,
TL.query_plan,
obj = OBJECT_NAME(T.objectid),
T.objectid,
P.cacheobjtype,
P.objtype,
T.text
FROM sys.dm_exec_cached_plans P
INNER JOIN sys.dm_exec_query_stats S
ON P.plan_handle = S.plan_handle
OUTER APPLY sys.dm_exec_sql_text(P.plan_handle) T
CROSS APPLY sys.dm_exec_query_plan(P.plan_handle) L
OUTER APPLY sys.dm_exec_sql_text(S.sql_handle) T2
CROSS APPLY sys.dm_exec_text_query_plan (P.plan_handle, DEFAULT, DEFAULT) TL
WHERE P.cacheobjtype = 'Compiled Plan' AND
T.text NOT LIKE '%dm_exec_cached_plans%' AND
P.objtype = 'Proc' AND T.dbid = DB_ID()
AND OBJECT_NAME(T.objectid) = 'qp_Temp'
ORDER BY P.plan_handle, S.statement_start_offset, S.statement_end_offset

Website Down

A client called about its website being down. Even a simple page requested would show a blank screen, but without any browser error. The website was ping-able with decent responses. The IP returned from the DNS was correct - I had to check the IP because the client just renewed the domain registration and I was afraid the renewal somehow caused the IP associated with the website to be changed. That was not the case. Just to be sure. I also got the confirmation by "View Source" in the browser which showed the correct site info.

I then reviewed the System event log and noticed an recent installation of Windows Security updates KB941644 and KB943485. I tried to call Microsoft Product Support Services at 1-866-PCSAFETY for free security updates support to find out if Microsoft had any knowledge, but got no answer. I searched the web and found some complaints related to the updates, and one particular about the proxy being messed up and the user having to uninstall the updates to fix the problem. My client did not use a proxy server but that message told me that the updates might have changed something on the web server to interfere with Internet browsing or even page rendering. I checked the web server's log and noticed 404 errors associated with the GET from external Ips - and interestingly, from Intranet Ips, browsing the web site had not problem. Another important piece of info was that from the web server, I could not browse www.msn.com, www.microsoft.com, etc - the display showed the same blank screen just as an Internet user would get trying to browse my client's website, even though I could browse other web sites such as www.google.com. With the above facts, I first uninstalled the updates, but that did not fix the problem. So, something else was changed. I then went to Internet Options and restored the default settings. Whala! Everything started to work again.

That was a very unfortunate experience. My client's production web site was down for quite some time just because Microsoft sent out the updates without any warning about the potential effects. In this case, my client did nothing wrong, and it just followed Microsoft's recommendation. I hope Microsoft will be more thorough in QA and provide better guidance about its future updates.

Session Settings for SSB Activation Procedure

According to BOL, the session settings for internal activation are the default databases options:
"Service Broker executes internally activated service programs on a background session distinct from the connection that created the message. The options set for this session are the default options for the database."
Pasted from <http://msdn2.microsoft.com/en-us/library/ms171585.aspx>

The default options for out database are "OFF" for all the relevant settings. But the activation procedure when activated reports that the followings settings are turned "ON":
ANSI_NULL_DFLT_ON
ANSI_NULLS
ANSI_PADDING
ANSI_WARNINGS
CONCAT_NULL_YIELDS_NULL
QUOTED_IDENTIFIER

Where did these settings come from? ANSI_NULLS and QUOTED_IDENTIFIER are understandable because they are creation time settings. The others are not set as the database defaults.

First, I thought those settings are from the set_options attribute of the cached plan. But the following query
SELECT P.usecounts, A.set_options FROM sys.dm_exec_cached_plans P OUTER APPLY sys.dm_exec_plan_attributes(P.plan_handle) A
CROSS APPLY sys.dm_exec_sql_text(P.plan_handle) T
WHERE A.attribute = 'set_options'
AND P.cacheobjtype = 'Compiled Plan' AND P.objtype = 'Proc'
AND T.text LIKE '%procName%'; -- replace procName with the name of the activation procedure
reports that this set of sestings are compiled with the cached plan:
ANSI_NULLS
ANSI_PADDING
ANSI_WARNINGS
ARITHABORT
ARITHIGNORE
DISABLE_DEF_CNST_CHK
IMPLICIT_TRANSACTIONS

So that is not it. What is most strange about the set_options of the cached plan is IMPLICIT_TRANSACTIONS which should not be set at all in normal situations because of its unexpected effects on @@TRANCOUNT.

The settings reported from within the activation procedure are the desired behavior settings with the exception of missing ARITHABORT but it is implicitly implied by ANSI_WARNINGS. Also, these 6 settings are exactly the same as those for an ADO.Net connection. These 6 except for CONCAT_NULL_YIELDS_NULL belong to the group of settings controled by ANSI_DEFAULTS. ANSI_DEFAULTS include two other settings: CURSOR_CLOSE_ON_COMMIT and IMPLICIT_TRANSACTIONS. The following is quoted from BOL:
"The SQL Native Client ODBC driver and SQL Native Client OLE DB Provider for SQL Server automatically set ANSI_DEFAULTS to ON when connecting. The driver and Provider then set CURSOR_CLOSE_ON_COMMIT and IMPLICIT_TRANSACTIONS to OFF. The OFF settings for SET CURSOR_CLOSE_ON_COMMIT and SET IMPLICIT_TRANSACTIONS can be configured in ODBC data sources, in ODBC connection attributes, or in OLE DB connection properties that are set in the application before connecting to SQL Server. The default for SET ANSI_DEFAULTS is OFF for connections from DB-Library applications."

So it seems that instead of using database default options, SSB activation procedure is executed in a session environment similar to the connection of an SQL Native Client OLE DB Provider (such as SSMS client).

SET Settings for Stored Procedure

A stored procedure is unique in that it is able to control its execution context via the "environmental" SET settings. (Since a trigger is a special kind of stored procedure, can a trigger change its SET settings?). For example, we can set TRANSACTION LEVEL at the beginning of the stored procedure to control all statements in it and to provide the default for its inner stored procedures if any.
According to BOL,

• The scope of the settings SET in the stored procedure is the stored procedure itself and those settings do not affect the calling (execution) environment.
• Settings not explicitly set in the stored procedure default to those set at the execution time except for two special settings: ANSI_NULLS and QUOTED_IDENTIFIER.
• Those two settings at the creation time of the stored procedure (implicitly) exclusively control the respective behavior, ignoring the corresponding settings at the execution time or the settings SET within the stored procedure. That is, those two settings are constant for the stored procedure after its creation, and to change them, it has to be altered or dropped and created with different settings.

We can find out the two settings at the time of stored procedure creation by querying:
SELECT OBJECTPROPERTY(OBJECT_ID('spName'), 'ExecIsQuotedIdentOn');
SELECT OBJECTPROPERTY(OBJECT_ID('spName'), 'ExecIsAnsiNullsOn');

Why are those two settings special?
QUOTED_IDENTIFIER is actually a parse-time setting and the parser needs to determine if a statement like SELECT * FROM "table" is valid or not based on the setting. It makes sense that for consistency, the same behavior applied during the parsing is adopted at the time of execution without regard to any different setting. (Other parse-time settings such at FIPS_FLAGGER, OFFSETS, PARSEONLY, do not affect the execution results).
ANSI_NULLS setting can directly affect query results. It is understandable that this settting deserves the consistency treatment. The question is why other settings do not have the same special treatment. Specifically, CONCAT_NULL_YIELDS_NULL also affect query results. The optimizer needs to know these other settings when it is looking for the "best" query plan. So, SQL's resolution is that each cached plan
for a stored procedure has these setting included as part of the plan. Any change in them in the execution context will cause the optimizer to recompile and generate another plan.

Another question that has been in my mind for quite some time and still has no clear answer: what execution context is an activation stored procedure in? Since there is no explictly created session to run such a procedure, will the settings defaults to the db level settings (except for the two special settings (QUOTED_IDENTIFIER and ANSI_NULLS ), of course - they were set at the creation time) . But the default db settings are all off. Is there a risk here?
The same applies to other client apps (besides the native sqlclient used by SSMS) such as ADO.Net. BOL seems to imply that ODBC and OLEDB have automatic settings.

Cost of MAX in SQL Server 2005

Microsoft SQL Server 2005 introduced keyword MAX for defining variable-length data types such as VARCHAR (and its Unicode counterpart NVARCHAR), and VARBINARY. It has given database architects and developers a more robust choice when designing data models and writing T-SQL codes. There are many discussions on the internals, the advantages and disadvantages of using MAX. Below I summarize the main points.

• The storage engine treats a MAX type as a hybrid of the normal variable-length type and LOB type. That is, if a column with MAX type has length <= 8,000 bytes, then it will be treated as the normal-length type - stored on an in-row data page or a row-overflow data page. Otherwise, the column will be treated as a LOB type - stored on a LOB data page.
• Because of the above internal flexibility, data types text, ntext and image can be virtually replaced by the appropriate MAX type if working exclusively in SQL 2005 and later environments.
• A VARCHAR(MAX) variable is very handy to store pre-validated XML data because of the potentially explosive size of XML data. Use TRY … CATCH block to validate text data for XML well-formedness or XML schema.
• NVARCHAR(MAX) parameters are convenient to use for defining CLR functions/triggers/stored procedures in T-SQL. A lot of people, including me, misunderstood that .Net type SqlString would translate into NVARCHAR(MAX). Actually, it translates into NVARCHAR(4000) and SqlChars translates into NVARCHAR(MAX).
• Although I have not verified it myself, some people claim statistics can not be automatically created on MAX type columns, therefore limiting the Optimizer's ability. But, statistics can created manually for a column of any type. Also, we could create an index on it if necessary (be very careful here - the unlimited column size could make the index take a huge amount of storage).
• Similarly, the Optimizer uses the column size as one of the metrics to determine the query plan. MAX certainly gives the Optimizer no clue in that regard.
  The unknown column size can cause difficulty/impossibility in calculating the number of rows per page and hence planning for the storage requirements.
• As common to any variable-length columns, updates with increased data length have the potential of causing page splits, adversely impacting performance.

In this post, I'd like to show an additional observation on using MAX variables. I have found that depending on the application, there can be a huge cost associated with using a MAX variable over its normal variable-length counterpart. As a disclaimer, I personally have not come across any such findings documented anywhere, but if that is due to my ignorance, please forgive me.
Here is some background.
We have two scalar CLR Regex functions in T-SQL, one for identifying a match (util.uf_RegexIsMatch), and the other for finding all matches first and then doing a replacement (util.uf_RegexReplace). A colleague of mine recently brought to my attention a counter-intuitive test result: when applied on a table of a half million normal VARCHAR records, util.uf_RegexIsMatch ran 3 times slower than util.uf_RegexReplace and consistently. That was very surprising. Without knowing exactly how the two Regex functions are implemented in .Net, intuitively IsMatch is doing less work than Replace, and so we were expecting the other way around and if not 3 times fasters, at least as fast, which was proven to be the case when doing comparison tests in C#.
It did not make sense. So I started a little investigation. I made sure the query plans were all right: simple table scan and after repeated runs, all the data was in the cache (SET STATISTICS IO ON showed no physical reads and only logical reads and they were the same for both). That meant both had the same IO cost and the only difference must have been in the functions themselves. Then, I looked at the CREATE FUNCTION syntax and noticed that the input parameter for util.uf_RegexIsMatch was of type NVARCHAR(MAX) and that for util.uf_RegexReplace NVARCHAR(4000). I knew the type had to be a Unicode type because that is required by all CLR objects. But could the MAX have been the cause? It was hard to believe but I decided to give it a try. I recreated the function util.uf_RegexIsMatch by using NVARCHAR(4000) for the input parameter, and re-ran the tests. Whala! The comparison went to the right direction. Also as a curiosity, making both input parameters of the same type of NVARCHAR(MAX) had the same expected and obviously slower comparison result.
In our case, we do not really need MAX, or even 4000 because the column in the table to feed the input parameters of the functions is only VARCHAR(50). I played with other numbers smaller than 4000 for the variable-length and found that made no performance difference as compared to 4000, so we standardized on NVARCHAR(4000) for the two functions. And they will be our default functions used in production. If necessary, we can create their counterparts with NVARCHAR(MAX) to handle special cases.
Is the above just a special and isolated case or does it have general validity?
Further investigation has shown that MAX in general has negative performance impact not only on CLR functions, but also T-SQL user defined functions. I suspect it is also true for stored procedures. In addition, it is true even for ad hoc query batches, which can be simulated by comparing the following two simple batches. Be sure to check "Discard results after executive" in your SSMS options so that no display will contaminate the test.
Note that a number after GO tells the query processor to execute the batch that many times.
---- Batch 1: normal variable-length variable
DECLARE @vc VARCHAR(8000);
SELECT @vc = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
GO 50000
---- Batch 2: MAX
DECLARE @vc VARCHAR(MAX);
SELECT @vc = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
GO 50000

On my notebook running XP and SQL Server 2008 (Katmai) CTE, Batch 1 completes in 12 secs and Batch 2 completes in 16 secs, consistently. That is a difference of over 30%!


In conclusion, the flexibility that comes with MAX is not free. The difference in performance from using the normal variable-length counterpart can be unexpectedly huge. We need to evaluate each situation to really justify its use and even in that case, we may be better off creating two versions of the objects (functions, stored procedures), one for handling the normal production scenarios and the other for the special cases. I personally would like to study and know more about how SQL OS allocates and de-allocate memory for MAX variables to understand the range of differences in performances.