How SQL Server finds the Execution Plan in the Plan Cache Store

You know that SQL Server creates a plan for your query and keeps them in the cache for reusing when it is required. When you make a request again, how SQL Server knows that the plan is exist in the cache or not? What sort of techniques it uses for finding the plan? Let's try to understand it.

There are four main plan cache stores. These plan cache stores maintain different types of plans and plans are reused when the same request is made by users or plans are discarded when SQL Server needs space in the store (Let's discuss the techniques it uses for discarding with another post). These for stores are;

• Object plans store for storing plans for procedures, functions and triggers.
• SQL plans store for storing plans for ad-hoc queries.
• Bound Trees plan store for storing structures created by Algebrizer for views, defaults and constraints.
• Extended Stored Procedure plan store for storing plans for Extended Stored Procedures.

A store is a Hash Table and it contains series of Buckets. A Bucket contains zero or more plans and the Hash value is calculated;

• Using databaseId and objectId for Object plan, Bound Tree plan and Extended Stored Procedure plan stores.
• Using databaseId and the statement for SQL plan store.

The assignment of execution plan to store bucket is done using the Hash Value. The Plan Handle (or Cache Key) which is made up with various attributes, is used for referencing the plan in the cache.

When you make a request to SQL Server, it does following steps for find the plan in the cache;

1. Generate the Hash Value for the request for the appropriate store.
2. Search all execution plans in the bucket along with the cache key.
3. If found, it uses it, else create a new plan.

For understanding the process, let's check with a simple code;

-- Clear the cache
DBCC FREEPROCCACHE

-- Checking the number of buckets for each store
-- and how many have been used.
SELECT cc.name, buckets_count, buckets_in_use_count
FROM sys.dm_os_memory_cache_hash_tables AS ht 
 JOIN sys.dm_os_memory_cache_counters AS cc 
  ON ht.cache_address = cc.cache_address 
WHERE cc.name IN ('Object Plans','SQL Plans','Bound Trees','Extended Stored Procedures');

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate = '01/06/2014';

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate = '01/07/2014';

-- Check the cached plans
-- You will see two plans for above two statements
SELECT p.*, t.text
FROM sys.dm_exec_cached_plans p  
CROSS APPLY sys.dm_exec_sql_text(p.plan_handle) t  
WHERE --p.usecounts > 0 AND  
 text LIKE '%SELECT * FROM Sales.SalesOrderHeader%'  
 AND text NOT LIKE '%SELECT p.*%'
ORDER BY p.usecounts DESC; 

-- Check how the cache key is formed
-- Note the two bucket ids
-- And note that only object id is different
-- For SQLs, it is the internal hash of the batch text
-- not an id in sys.objects table
SELECT p.bucketid, t.text  , ph.*
FROM sys.dm_exec_cached_plans p  
 CROSS APPLY sys.dm_exec_sql_text(p.plan_handle) t  
 CROSS APPLY sys.dm_exec_plan_attributes(p.plan_handle) AS ph
WHERE --p.usecounts > 0 AND  
 text LIKE '%SELECT * FROM Sales.SalesOrderHeader%'  
 AND text NOT LIKE '%SELECT p.*%'
 AND is_cache_key = 1
ORDER BY p.usecounts DESC;