Dude, where’s my plan (part 1).

When a plan is cached it is stored in one of four cache stores.  Query  sys.dm_os_memory_cache_counters to see the cache stores in SQL Server.  There are four cache stores that handle plans and plan related objects.  They are Object Plans, SQL Plans, Bound Trees, and Extended Stored Procedures.

SELECT *
FROM sys.dm_os_memory_cache_counters
WHERE type in
    ('CACHESTORE_OBJCP','CACHESTORE_SQLCP',
     'CACHESTORE_PHDR','CACHESTORE_XPROC')

Each of these cache stores holds different types of plans.  In general I’m only going to look the cache stores for Object Plans and SQL Plans.  The Object Plans cache store holds the plans for stored procedures, triggers and functions.  The SQL Plans cache store holds the plans prepared queries, ad-hoc queries and parameterized queries.

Each cache store contains a hash table. I think the wikipedia entry about hash tables is a pretty good intro for those who don’t really know much about them (as I didn’t before I started studying the plan cache.) Each hash table contains multiple buckets and it is in these buckets that the plans are stored.  Typically in a hash table a key identifies a single index value (though sometimes multiple keys can point to the same index producing what is known as a hash collision…more on this later).   This index value is the bucket (or slot) that contains the item being stored.   The number of buckets each cachestore can be seen by querying sys.dm_os_memory_cache_hash_tables.

The question is, how does SQL Server use the plan cache and why do I care?  The reason I care is because understanding how plans are hashed and stored can help me identify when I’m having problems with plans not being reused or if I’m having performance problems because of long hash chains.    Also, it is nifty to see how SQL Server is working behind the scenes.

According to Kalen Delaney the hash key used is determined by this algorithm: (object_id * database_id) mod (hash table size).

What this should mean is that if I take the object id, multiply it by the database id and then mod it by the hash table size I should get the bucket that the plan is going to be stored in.  For my first test this worked great but I noticed that this didn’t work consistently for all my plans.  So after a little research I learned that the formula above isn’t exactly correct.  Well, I’d better say, it doesn’t exactly work like I thought it would.

I was still thinking in terms of unlimited storage space for a number.  Unlike people who’ve been programming in C for years I wasn’t thinking that the result of a 32-bit unsigned integer multiplied by another 32-bit unsigned integer had to fit in the space allowed to a 32-bit unsigned integer.  The chance of overflow is great.  My first example that appeared to work didn’t overflow the space allowed so I didn’t see any problems with it.  As I began to look at other examples the results weren’t correct and I had to figure out why.

One of the ways of solving the overflow problem is to wrap back around when you run out of space.  A 32-bit unsigned integer can hold a range of values from 0 to 4294967295, or 4294967296 values total.  If you are at 4294967295 and add 1 to that the result is zero.  Since multiplication is simply adding the same number over and over again it should be relatively easy to figure out what the result would be after wrapping around again and again.

Rather than figure that out I looked for a shortcut.  If the two numbers I multiple together are greater than 4294967295 I can mod this number by 4294967296 to get what the final number would have been had I manually calculated what it would eventually wrap around to.

So now the trick is to test the theory out on the compiled plans in the plan cache.

For objects like stored procedures and triggers this is relatively easy because the object id and the database id are presented in sys.dm_exec_query_plans DMV.  For ad hoc plans it is a bit harder.  The object id is created by hashing the batch text and it isn’t shown in sys.dm_exec_query_plans.  It is however shown in sys.dm_exec_plan_attributes.  The problem with sys.dm_exec_plan_attributes is how it presents each attribute.  Each attribute is a row and not a column in the DMV.  This means to get it in row form I have to pivot it.

;WITH PlanAttributePivot (plan_handle, objectid, dbid)
AS
(
    SELECT plan_handle, pvt.objectid, pvt.dbid
    FROM
    (
        SELECT plan_handle, epa.attribute, epa.value
        FROM sys.dm_exec_cached_plans
        OUTER APPLY sys.dm_exec_plan_attributes(plan_handle) AS epa
        WHERE cacheobjtype = 'Compiled Plan') AS ecpa
        PIVOT (MAX(ecpa.value) FOR ecpa.attribute IN
        ("objectid", "dbid")
    ) AS pvt
)
SELECT *
FROM PlanAttributePivot PA
INNER JOIN sys.dm_exec_cached_plans cp
on cp.plan_handle = PA.plan_handle

Now that I have the object ids and database ids I need to put it through the substitute hashing function I created, (((objected * databaseid) MOD 4294967296) MOD buckets_count).  Since the plans I’m interested in are stored in different cachestores there can be a different bucket count for each store.  In my query I have to delinate by the store the plan will be stored in and use the bucket count for that store. This query worked for all the plans in my plan cache with the exception of CLR Compiled Func which appear to be stored in a different store altogether.

DECLARE @obj_buckets_count int
DECLARE @sql_buckets_count int
DECLARE @boundtree_buckets_count int
DECLARE @xproc_buckets_count int
SELECT @obj_buckets_count = buckets_count
FROM sys.dm_os_memory_cache_hash_tables
WHERE type = 'CACHESTORE_OBJCP'
SELECT @sql_buckets_count = buckets_count
FROM sys.dm_os_memory_cache_hash_tables
WHERE type = 'CACHESTORE_SQLCP'
SELECT @boundtree_buckets_count = buckets_count
FROM sys.dm_os_memory_cache_hash_tables
WHERE type = 'CACHESTORE_PHDR'
SELECT @xproc_buckets_count = buckets_count
FROM sys.dm_os_memory_cache_hash_tables
WHERE type = 'CACHESTORE_XPROC'
;WITH PlanAttributePivot (plan_handle, objectid, dbid)
AS
(
    SELECT plan_handle, pvt.objectid, pvt.dbid
    FROM
    (
        SELECT plan_handle, epa.attribute, epa.value
        FROM sys.dm_exec_cached_plans
        OUTER APPLY sys.dm_exec_plan_attributes(plan_handle) AS epa
    ) AS ecpa
    PIVOT (MAX(ecpa.value) FOR ecpa.attribute IN
    ("objectid", "dbid")) AS pvt
),
CalculatedBuckets (plan_handle,bucketid)
AS
(
    SELECT
    PA.plan_handle
    ,(cast(PA.objectid as bigint) * cast(PA.dbid as bigint))%4294967296%@obj_buckets_count [bucketid]
    FROM PlanAttributePivot PA
    INNER JOIN sys.dm_exec_cached_plans cp
        ON cp.plan_handle = PA.plan_handle
    WHERE cp.objtype in ('Proc','Trigger') and cacheobjtype <> 'Extended Proc'
    UNION ALL
    SELECT
    PA.plan_handle
    ,(cast(PA.objectid as bigint) * cast(PA.dbid as bigint))%4294967296%@sql_buckets_count [bucketid]
    FROM PlanAttributePivot PA
    INNER JOIN sys.dm_exec_cached_plans cp
        ON cp.plan_handle = PA.plan_handle
    WHERE cp.objtype in ('Adhoc','Prepared')
    UNION ALL
    SELECT
    PA.plan_handle
    ,(cast(PA.objectid as bigint) * cast(PA.dbid as bigint))%4294967296%@boundtree_buckets_count [bucketid]
    FROM PlanAttributePivot PA
    INNER JOIN sys.dm_exec_cached_plans cp
        ON cp.plan_handle = PA.plan_handle
    WHERE cp.cacheobjtype in ('Parse Tree')
    UNION ALL
    SELECT
    PA.plan_handle
    ,(cast(PA.objectid as bigint) * cast(PA.dbid as bigint))%4294967296%@xproc_buckets_count [bucketid]
    FROM PlanAttributePivot PA
    INNER JOIN sys.dm_exec_cached_plans cp
        ON cp.plan_handle = PA.plan_handle
    WHERE cp.cacheobjtype in ('Extended Proc')
)
SELECT CB.bucketid,cp.bucketid,*
FROM CalculatedBuckets CB
INNER JOIN sys.dm_exec_cached_plans cp
    ON cp.plan_handle = CB.plan_handle
--WHERE cp.bucketid <> CB.bucketid

With this I can easily compare the bucket ids SQL Server produced with the pseudo hash I created.  Uncommenting the WHERE clause at the end and I can see where they don’t match.   I’m pleased with the results.  The database I tested this on had over 14,000 plans in the cache store and the only ones that didn’t match were the CLR compiled functions.  A little research showed that these probably live in a different store so I didn’t worry about it.

One of the problems with a hash table is the chance of hash collisions.  This happens when hashing different keys produces the same hash value or bucket.  This leads to multiple plans being stored in the same bucket.  When SQL Server is looking for a plan to reuse it uses the same hashing algorithm to determine the bucket to look in.  It then must search each plan in the bucket to see if it matches certain criteria (more on this in the next post).  If the number of plans in the bucket is excessive SQL Server will have to search through a large number of plans to find one that matches (and to find if there isn’t a matching plan).  Looking at the columns in sys.dm_os_memory_cache_hash_tables will show some general information about how the buckets have been used.  The column buckets_max_length tells you how long the longest hash chain is.

In my next post I plan on looking more at how plans are reused and talk about how SQL Server finds the right plan after it has found the right bucket.