3.0 How Cache Lookups Work

Each cache store is implemented as a hash table. A hash value and cache key pair is used in order to check if the compiled plan is cached for a given query in the cache stores. The hash value of all cache objects is computed as (database_id * object_id) mod (hash table size), and this specifies the hash bucket. Note that the object_id for entries in the SQLCP cache store is the hash of the entire batch text. All attributes of a cached plan that must match in order for the look up to succeed is termed as a cache key. A cache key is used to find an exact match for a plan in that hash bucket. More information regarding cache keys can be found in BOL article on sys.dm_exec_plan_attributes.

3.1 Cache Look Up Mechanisms

There are two types of look ups for the top level cache objects: ID and text look up. For objects like procedures, functions, triggers, the ID look up is used. The ID look up first determines the kind of cache object (and cache store) we are trying to look up based on the object type. For procedures, functions, triggers we will look up a compiled plan in the OBJCP cache store. Next the cache key consisting of database id, object id, proc number, object type, context etc is used to look up the plan.

When a procedure, function or trigger is submitted for execution, the following steps are executed:

1. We do an ID look up to find the compiled plan in the cache.

a. If we find a compiled plan then we can proceed to step 2.

b. If not, then we do a name to ID resolution from the metadata cache. Once the latest IDs are obtained, then we attempt another cache look up. If that too fails, then we know the query needs to be compiled. Before compilation, we grab an exclusive lock and attempt a final cache lookup just to be sure that a compiled plan has not been inserted while we were waiting to acquire the compile lock. If this too fails, we do a full compile, insert a new compiled plan and release the compile lock.

2. Check to see if the compiled plan has any free MXCs in its lookup list.

a. If yes, then we remove it from the lookup list and use it.

b. If no, then we create one.

3. After query execution, we either return the MXC to the lookup list (if it must be cached) or destroy it.

For ID look ups we must make sure that there is only one match for a given ID. A compile lock is taken so that only one compilation can take place at a time. The other threads will be blocked waiting to acquire the compile lock. Therefore it is not possible to have duplicate plans for procedures, functions, triggers, etc. Xprocs however are an exception. Since Xproc entries consume very little memory, we avoid the need to grab an exclusive lock in this case by allowing duplicate entries for the same IDs. The look up logic is implemented such that the latest Xproc entry for an ID is returned, and the rest are aged out with time.

The text look up is used for adhoc and prepared sql batches. All dynamic sql look ups are from the SQLCP cache store and the cache key consists of the batch text, dbid (id of the database where the query was executed), set options among other things. When an adhoc query or a prepared sql batch is submitted for execution, the following steps are executed:

1. Sql text look up in the SQLMGR cache to see if we have the batch text already cached.
   1. If yes, we use this to lookup the compiled plan in the cache stores (using the CP cache store key). The compiled plan has a reference to the entry in the SQLMGR cache.
   2. If no, then this implies there is no compiled plan for this batch in the plan cache stores, and one has to be generated.

Either way at the end of step 1 we have the compiled plan for the batch.

2. Check to see if the compiled plan has any free MXCs in its lookup list.
   1. If yes, then we remove it from the lookup list and use it.
   2. If no, then we create one.
3. After query execution, we either return the MXC to the lookup list (if it must be cached) or destroy it.

Notice that during the lookup in the SQLMGR cache, we don’t hold any compile locks. Therefore it is possible to have duplicate entries in the plan cache for simultaneous compiles. Subsequent looks ups will however only return the last plan inserted, leaving other duplicate plans to just age out.

3.2 Cache Keys

The cache keys for a plan are exposed through sys.dm_exec_plan_attributes. Attributes that have is_cache_key set to 1 are cache keys for that particular plan. More information regarding sys.dm_exec_plan_attributes is available in BOL.

Consider the example query below: the query is executed once from Sql Server Management studio and using OSQL:

---this is an example for how to use sys.dm_exec_plan_attributes

if exists(select col1 from t1 where col2 > 5) declare @x int;

go

Use the query below to view the cached compiled plans:

select text, plan_handle, cacheobjtype, objtype

from sys.dm_exec_cached_plans cp cross apply sys.dm_exec_sql_text(plan_handle)

where cacheobjtype = 'Compiled Plan'

go

The cached compiled plans have the exact same query text but have different plan_handles. To understand why the same query executed using different client drivers ends up generating two different plans instead of re-using the same plan, use the query below:

select st.text, cp.plan_handle, cp.cacheobjtype, cp.objtype, pa.attribute, pa.value, pa.is_cache_key

from sys.dm_exec_cached_plans cp cross apply sys.dm_exec_sql_text(plan_handle) st

outer apply sys.dm_exec_plan_attributes(cp.plan_handle) pa

where cp.cacheobjtype = 'Compiled Plan' and cp.objtype = 'Adhoc'

and st.text not like '%select st.text%' and pa.is_cache_key = 1

order by pa.attribute;

go

The result set will point out queries with same text, but different cache key values as below:

As demonstrated above several connection properties like set options, date format, language can affect plan re-use.

Other subtle things that usually go unnoticed, but prevent plan re-use are differences in white space characters or comments in an adhoc query. Even one character difference amounts to a different plan since the hash value of the sql text is different. Note that the hash value is computed for the entire text even if the batch text is larger than 8K).

For non-dynamically bound temp tables as in the example below we add the connection spid to the cache key in order to reduce the number of re-compiles. In the example below, a select query from connection 1 is issued, followed by the select query from connection 2, followed by a re-issue of the select query from connection 1.

The cache has 2 compiled plan entries with the same sql text but different plan_handles:

Although cache key attributes exposed through sys.dm_exec_plan_attributes are identical in this case, the two cache entries are tagged with the connection spid. Thus for non-dynamically bound temp tables, connection spid is part of the cache key. Adding the connection spid to the cache key greatly reduces the number of recompiles. If this were not the case, then it would re-compile the second execution of the select query from connection 1.

Accessing inserted and deleted tables inside one CLR trigger needs to be distinguished from queries with the same text inside another CLR trigger. Hence all queries are executed inside a CLR triggers are tagged with two additional cache keys: dbid and objid of the CLR trigger that issued them. Consider the example below: We create two CLR triggers on two tables t1 and t2 with different column meta data as below. Both CLR triggers execute the same test_method() when fired.

create trigger dml_clr_trigger1 on t1 after update

as external name trigger_assembly.test_class.test_method

go

create trigger dml_clr_trigger2 on t2 after update

as external name trigger_assembly.test_class.test_method

go

In test_method() we execute the following query:

using SqlConnection connection = new SqlConnection ("context connection = true");

connection.Open();

SqlCommand command = connection.CreateCommand();    

command.CommandText = "if exists(select * from inserted) declare @x int";

command.ExecuteNonQuery();

Now if we fire both the triggers, then we should have two plans in the cache whose text is identical, but plan_handle is different.

Now there is couple of things to notice regarding the cache key attributes for these two compiled plans: First, the cache key attributes returned above for the two plans are identical. However internally we also have the objectid and the dbid of the CLR triggers as part of the cache key. They are not exposed in SQL Server 2005. Re-using the compiled plan from the inproc query inside dml_clr_trigger1 for the query inside dml_clr_trigger2 is not an option because the inserted tables in the two cases have different columns. Hence we need to cache two plans that have the exact same text, same values for other currently exposed cache keys but need a way to distinguish them. Hence we add dbid and objectid of the CLR trigger to the cache key of the queries inside CLR triggers. The second thing to notice here is the objtype of the inproc query is prepared.