1.0 Structure of the Plan Cache and Types of Cached Objects

[sshekar]

First published on MSDN on Jan 09, 2007

<br/><!--<br/> table.MsoNormalTable<br/> {mso-style-parent:"";<br/> font-size:10.0pt;<br/> font-family:"Times New Roman";<br/> }<br/> p.MsoNormal<br/> {mso-style-parent:"";<br/> margin-bottom:.0001pt;<br/> font-size:12.0pt;<br/> font-family:"Times New Roman";<br/> margin-left:0in; margin-right:0in; margin-top:0in}<br/>--><br/>

The plan cache is comprised of 4 separate cache stores: Object Plans (CACHESTORE_OBJCP), SQL Plans (CACHESTORE_SQLCP), Bound Trees (CACHESTORE_PHDR), and Extended Stored Procedures (CACHESTORE_XPROC). Each of these four cache stores conform to a uniform caching policy with respect to costing and removal of entries. Within each cache store is a hash table that is divided into hash buckets. Each hash bucket may contain one or more cached entries. The hash value of all cache entries is computed as (object_id * database_id) mod (hash table size), and this specifies the hash bucket. A cache key is used to find an exact match for a plan in the cache store hash table bucket.

In the plan cache we cache the following types of objects: compiled plans (CP), execution plans (MXC), algebrizer trees (ProcHdr), Extended Procs (XProcs) and inactive cursors. Among these, compiled plans, algebrizer trees and extended procs are top level objects where as the execution plans and inactive cursors are dependant objects (dependant on the compiled plans). The section below describes each of these objects in greater detail including which of the four cache stores they reside in.

1.1 Types of Cached Objects

1.1.1 Compiled Plans (CP)

When a query is compiled, a compiled plan is generated for the query. The cost of compiling a query each time is large; therefore we cache the compiled plans. There are two cache stores in which compiled plans are stored depending on the type of the compiled plan. If the query is dynamic sql or prepared, the compiled plan is stored in the SQL Plans (CACHESTORE_SQLCP) cache store. For modules like stored procedures, functions and triggers, the compiled plan is stored in Object Plans (CACHESTORE_OBJCP) cache store. Since the compiled plans are valuable and should to be kept in cache, when the cache stores are under memory pressure, cache removal policies ensure that these entries are not amongst the first to be removed. Compiled plans are also shared across multiple users.

Compiled plans are generated for the entire batch, and not on a per statement (query) level. Therefore for a multi-statement batch, the compiled plan can be thought of as an array of plans containing the query plan for statements in that batch. It is important to understand that for a batch with multiple queries in it, the compiled plan will have the compiled query plans for all the queries in the batch.

Internally each individual statement in a batch is represented by a CStmt (short for Compiled Statement). Each CStmt has the query plan for that particular statement. A compiled plan therefore has an array of CStmts that are in turn stored in a plan skeleton. In addition to the plan skeleton, the compiled plan also contains the parameter collection, symbol table, the top level memory object and the execution plans.

Compiled Plans are non re-generatable entries since we can potentially get different compiled plans for queries compiled under different conditions or at different times. For consistency however, we want to keep the compiled plans in cache and re-execute the same plan to get the same behavior.

1.1.2 Execution Plans (MXC)

Execution plans are run time objects and are dependant objects of a compiled plan. They cannot exist independent of a compiled plan. Just like the compiled plans there are two types of MXCs: SQL MXC and OBJ MXC. Being dependant objects (of compiled plans) they don’t live a separate cachestore. The compiled plan has 2 linked lists for MXCs: a lookup (or free) list and an enum list. The lookup list stores the free (or currently not in use) MXCs. The lookup list is used to get the MXC memory needed to execute a batch. The enum list is used to enumerate all the MXCs associated with the compiled plan, and is used by some dynamic management views (DMVs) and to generate statistics like total memory used by a batch. MXCs themselves contain the runtime parameters, local variable information; object ids for objects created at run time, run time state like currently executing statement amongst other things.

During query execution, we generate an execution plan (MXC) from the compiled plan of the batch. Individual statement compiled plans get converted into to runtime query plans (XStmts). The XStmts are stored as a linked list inside the CStmts.

Unlike compiled plans, execution plans are single user. For example, if there are N users executing the same batch simultaneously, there will be N MXCs associated with the same compiled plan. There is therefore a 1:N mapping between compiled plans and execution plans.

MXCs are re-generatable given a compiled plan. Relative to compiled plans they are also relatively inexpensive to re-generate.

1.1.3 Algebrizer Tree (ProcHdr)

The algerbizer tree (ProcHdr) for views, constraints and defaults are cached in the Bound Trees (CACHESTORE_PHDR) cache store. The size of the bound trees cache store hash table is about 1/10th the size of the compiled plan cache store hash tables. The memory object from which each entry is allocated is 8K memory object.

1.1.4 Extended Procs (XProc)

Extended Procs (Xprocs) are pre-defined system stored procedures like sp_ExecuteSql, sp_TraceCreate etc. They contain the function name and the DLL name of the implementation. They are stored in the Extended Stored Procedures (CACHESTORE_XPROC). The size of this cache store hash table is 127 entries. The memory object from which each entry is allocated is 256 bytes memory object.

1.1.5 Inactive Cursors

Inactive cursors are cached in the compiled plan. Just like MXCs there are two lists maintained here: the lookup list and the enum list. The lookup list stores the inactive cursors. When a cursor is de-allocated, the memory used to store the cursor is cached. On subsequent re-execution of the batch with this cursor, the cached cursor memory is reused and re-initialized as an active cursor. The enum list has the list of active and inactive cursors and is used to enumerate all cursors for a compiled plan.

Cursors are re-generatable given a compiled plan. Relative to compiled plans they are also relatively inexpensive to re-generate.

1.2 Understanding Memory Layout of Compiled Plan using DMVs

For a detailed summary of the memory layout refer to this posting . In this section we will take a look at the DMVs and learn more about the memory layout of compiled plans through examples.

Sys.dm_exec_cached_plans has the plan_handle and the memory_object_address associated with every compiled plan. The plan_handle is a hash value derived from the compiled plan of the entire batch, and is guaranteed to be unique for every compiled plan. The plan_handle therefore serves as an identifier for a given compiled plan and is used by sys.dm_exec_cached_plans to retrieve the compiled plan for a batch.

The DMV sys.dm_os_memory_objects can be used to get information on all the top-level and sub-level memory objects associated with a compiled plan. This DMV has the memory_object_address as well as the parent_address of all the memory objects. It has also has the pages used by the memory object. The total of the pages_allocated_count of all the top level objects represents the total memory used by the compiled plan. This DMV also tells us the type of the memory object. The following memory object types are associated with a compiled plan:

MEMOBJ_COMPILE_ADHOC: Top level 8K compiled plan PMO.

MEMOBJ_QUERYEXECCNTXTFORSE: Top level 8K PMO Query execution context for SE, one for every XStmt that is a query.

MEMOBJ_EXECUTE: Top level 8K MXC PMO, contains the non recompilable XStmts in the batch).

MEMOBJ_PLANSKELETON: Sub PMO 512 bytes, allocated from the top level CP PMO. Maintains an array of CStmts.

MEMOBJ_STATEMENT: Sub PMO 512 bytes per non-recompilable CStmt created from top level CP PMO

MEMOBJ_XSTMT: Sub PMO 512 bytes for every recompilable XSTMT created from top level CP PMO).

MEMOBJ_CURSOREXEC: Sub PMO 512 bytes, one for every cursor.

Therefore given a plan_handle or the memory_object_address of a compiled plan, the memory layout of a compiled plan can pretty much be re-constructed from the DMV sys.dm_os_memory_objects. The function below does precisely that:

create function CompPlanDetails(@current_plan_address int, @plan_handle varbinary(64))

returns @details table

(

plan_handle varbinary(64) null,

memory_object_address varbinary(8) not null,

parent_address varbinary(8) null,

type nvarchar(60) null,

name nvarchar(256) null,

pages_allocated_count int not null,

page_size_in_bytes int not null,

page_allocator_address varbinary(8) not null

)

as

begin

-- Get the plan handle

if (@plan_handle is null)

select @plan_handle = plan_handle from sys.dm_exec_cached_plans where memory_object_address = @current_plan_address;

-- Get all top level pmos into a temp table.

with TopLevelPMOs as

(

select @plan_handle as plan_handle, mo2.memory_object_address, mo2.parent_address, mo2.type, mo2.name, mo2.pages_allocated_count, mo2.page_size_in_bytes, mo2.page_allocator_address

from sys.dm_os_memory_objects mo join sys.dm_os_memory_objects

mo2

on mo2.page_allocator_address = mo.page_allocator_address

where mo.memory_object_address = @current_plan_address

)

-- find sub-pmos from all top level pmos, and add them plus the top level pmos into the result table.

insert @details

select @plan_handle, mo3.memory_object_address, mo3.parent_address, mo3.type, mo3.name, mo3.pages_allocated_count, mo3.page_size_in_bytes, mo3.page_allocator_address

from sys.dm_os_memory_objects mo3 join TopLevelPMOs

on mo3.parent_address = TopLevelPMOs.memory_object_address

union all

select * from TopLevelPMOs

return

end

go

Now let us illustrate how to use this function with an example. Consider the following single statement batch executed by exactly one user at a given time:

select t1.col2, t2.col2 from t1 join t2 on t1.col1 = t2.col1 where t1.col1 = 50000

go

Execute the query and look up the plan_handle and memory_object_address from the DMVs using the query below:

select text, plan_handle, memory_object_address

from sys.dm_exec_cached_plans cp

cross apply sys.dm_exec_sql_Text(cp.plan_handle)

go

Text	Plan_handle	Memory_object_address
select t1.col2, t2.col2 from t1 join t2 on t1.col1 = t2.col1 where t1.col1 = 50000	0x0600010029A7DD06B 8012B04000000000000 000000000000	0x042B00C0

Now pass these plan_handle and memory_object_address to the function CompPlanDetails.

select * from dbo.CompPlanDetails(0x042B00C0, 0x0600010029A7DD06B8012B04000000000000000000000000)

go

The function returns data detailing the memory layout as below:

Plan_Handle	Memory_ object_ address	Parent_ address	Type	Name	Pages_ alloca ted_ count	Page_ size _in _bytes	Page_ Alloc ator_ address
0x060001002 9A7DD06B801 2B040000000 00000000000 000000	0x042 B0938	0x042 B00C0	MEMOBJ_ XSTMT	NULL	17	512	0x042 B0398
0x060001002 9A7DD06B801 2B040000000 00000000000 000000	0x042 B0528	0x042 B00C0	MEMOBJ_ COMPILE_ ADHOC	NULL	18	512	0x042 B0398
0x060001002 9A7DD06B801 2B040000000 00000000000 000000	0x042 B00C0	NULL	MEMOBJ_ COMPILE_ ADHOC	NULL	3	8192	0x036 141D0
0x060001002 9A7DD06B801 2B040000000 00000000000 000000	0x03F 98028	NULL	MEMOBJ_ EXECUTE	NULL	1	8192	0x036 141D0
0x060001002 9A7DD06B801 2B040000000 00000000000 000000	0x042 88040	NULL	MEMOBJ_ QUERYEX ECCNTXT FORSE	NULL	1	8192	0x036 141D0

Notice that the MEMOBJ_XSTMT and MEMOBJ_COMPILE_ADHOC in the first two rows are have parent address of the top level CP PMO in row three. There is only one top level MEMOBJ_EXECUTE since the query was executed by exactly one user. If multiple users had executed the query simultaneously, then there would be more than one top level MXC.

Now consider the stored procedure below:

create procedure p1

as

begin

select col1 from t1

select col2 from t1 where col1 = 50000

end

go

exec p1

go

Executing the function CompPlanDetails with the appropriate plan handle and memory_object_address returns the following data:

Plan_ Handle	Memory_ object_ address	Parent_ address	Type	Name	Pages_ alloca ted_ count	Page_ size_ in_ bytes	Page_ Allocator_ address
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B3168	0x03E B20C0	MEMOBJ_ XSTMT	NULL	17	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B2F60	0x03E B20C0	MEMOBJ_ XSTMT	NULL	17	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B2538	0x03E B20C0	MEMOBJ_ COMPILE_ ADHOC	NULL	2	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B2948	0x03E B20C0	MEMOBJ_ PLAN SKELETON	NULL	1	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B2B50	0x03E B20C0	MEMOBJ_ STATEMENT	NULL	17	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B2D58	0x03E B20C0	MEMOBJ_ STATEMENT	NULL	17	512	0x03E B23A8
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x042 00028	NULL	MEMOBJ_ EXECUTE	NULL	1	8192	0x036 12380
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E 32040	NULL	MEMOBJ_ QUERY EXECCNTXT FORSE	NULL	1	8192	0x036 12380
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x041 74040	NULL	MEMOBJ_ QUERY EXECCNTXT FORSE	NULL	1	8192	0x036 12380
0x05000100 95555D02B8 21EB030000 0000000000 0000000000	0x03E B20C0	NULL	MEMOBJ_ COMPILE_ ADHOC	NULL	5	8192	0x036 12380

Notice that since the procedure has multiple statements we now have a memory object of type MEMOBJ_PLANSKELETON, which is an array of CStmts. CStmts have type MEMOBJ_STATEMENT and in the above example there are 2 CStmts. The memory object MEMOBJ_COMPILE_ADHOC with page size 512 bytes has the top level CP PMO as parent. This memory object is used to allocate structures for execution. The memory layout is represented pictorially in the attached file.

Another useful stored procedure to analyze the memory layout of compiled plans is PlanBreakdown. The procedure PlanBreakdown gives a detailed summary of the memory object including how many CStmts, XStmts, Mxcs, Cursors, Plan Skeletons, and Query PMOs it contains and the size of the plan. This procedure generates two tables: PlanSummary and PlanDetails. The PlanSummary table has a row per plan with total size of the plan and number of CStmts, MXCs etc. The PlanDetails table has a row for every memory object. Note that while the total size of the plan as reported in PlanSummary table is accurate, it may not be the sum of the size of each of sub objects as reported in the PlanDetails table because they do not account for fragmentation.

create proc PlanBreakdown(@plan_addr varbinary(8) = null) as

begin

set nocount on

-- results tables

if object_id('PlanDetails', 'U') is not null

drop table PlanDetails

if object_id('PlanSummary', 'U') is not null

drop table PlanSummary

create table PlanDetails

(

plan_handle varbinary(64) null,

memory_object_address varbinary(8) not null,

parent_address varbinary(8) null,

type nvarchar(60) null,

name nvarchar(256) null,

pages_allocated_count int not null,

page_size_in_bytes int not null,

page_allocator_address varbinary(8) not null

)

create table PlanSummary

(

plan_handle varbinary(64) null,

memory_object_address varbinary(8) not null,

total_size int null,

cstmt_count int not null,

cstmt_size int not null,

xstmt_count int not null,

xstmt_size int not null,

cursor_count int not null,

cursor_size int not null,

mxc_count int not null,

mxc_size int not null,

query_count int not null,

query_size int not null,

skeleton_count int not null

)

-- temp table to hold the address of every plan that we're going to dump info for.

create table #plans(plan_address varbinary(8))

if (@plan_addr is null)

insert into #plans select memory_object_address from sys.dm_os_memory_objects

where type = 'MEMOBJ_COMPILE_ADHOC' and parent_address is NULL

else

insert into #plans values (@plan_addr)

declare plan_cursor cursor local for select plan_address from #plans

open plan_cursor

declare @current_plan_address varbinary(8)

fetch next from plan_cursor into @current_plan_address

while (@@fetch_status = 0)

begin

declare @plan_handle varbinary(64)

declare @total_size int

declare @cstmt_count int

declare @cstmt_size int

declare @xstmt_count int

declare @xstmt_size int

declare @cursor_count int

declare @cursor_size int

declare @mxc_count int

declare @mxc_size int

declare @query_count int

declare @query_size int

declare @skeleton_count int

set @plan_handle = null;

set @total_size = null;

set @cstmt_count = 0;

set @cstmt_size = 0;

set @xstmt_count = 0;

set @xstmt_size = 0;

set @cursor_count = 0;

set @cursor_size = 0;

set @mxc_count = 0;

set @mxc_size = 0;

set @query_count = 0;

set @query_size = 0;

set @skeleton_count = 0;

-- grab the plan handle and total size for the plan we're working on, if it exists

-- in dm_exec_cached_plans.

select @plan_handle = plan_handle, @total_size = size_in_bytes from

sys.dm_exec_cached_plans where memory_object_address = @current_plan_address

select * into #plan_details from CompPlanDetails(@current_plan_address, @plan_handle)

-- add the plan details to the results

insert into PlanDetails select * from #plan_details

-- If we didn't find this plan in sys.dm_exec_cached_plans, then go ahead and compute

-- the total_size by aggregating the pages used of all the top-level pmo's in the plan.

-- This really should be an accurate accounting of the plan memory usage too.

if (@plan_handle is null)

select @total_size = sum(pages_allocated_count * page_size_in_bytes) from #plan_details

where parent_address is null

-- form the summary information for the given plan.

declare detail_cursor cursor local for

select type, pages_allocated_count, page_size_in_bytes from #plan_details

open detail_cursor

declare @type varchar(256)

declare @pages int

declare @page_size int

fetch next from detail_cursor into @type, @pages, @page_size

while (@@fetch_status = 0)

begin

if (@type = 'MEMOBJ_XSTMT')

begin

set @xstmt_count = @xstmt_count + 1

set @xstmt_size = @xstmt_size + (@pages * @page_size)

end

else if (@type = 'MEMOBJ_EXECUTE')

begin

set @mxc_count = @mxc_count + 1

set @mxc_size = @mxc_size + (@pages * @page_size)

end

else if (@type = 'MEMOBJ_STATEMENT')

begin

set @cstmt_count = @cstmt_count + 1

set @cstmt_size = @cstmt_size + (@pages * @page_size)

end

else if (@type = 'MEMOBJ_CURSOREXEC')

begin

set @cursor_count = @cursor_count + 1

set @cursor_size = @cursor_size + (@pages * @page_size)

end

else if (@type = 'MEMOBJ_QUERYEXECCNTXTFORSE')

begin

set @query_count = @query_count + 1

set @query_size = @query_size + (@pages * @page_size)

end

else if (@type = 'MEMOBJ_PLANSKELETON')

begin

set @skeleton_count = @skeleton_count + 1

end

fetch next from detail_cursor into @type, @pages, @page_size

end

close detail_cursor

deallocate detail_cursor

insert into PlanSummary values(@plan_handle, @current_plan_address, @total_size, @cstmt_count, @cstmt_size, @xstmt_count, @xstmt_size, @cursor_count, @cursor_size, @mxc_count, @mxc_size, @query_count, @query_size, @skeleton_count)

drop table #plan_details

fetch next from plan_cursor into @current_plan_address

end

close plan_cursor

deallocate plan_cursor

end

go

To fetch the PlanSummary and PlanDetails for the stored procedure p1 in the above example use the queries below:

exec PlanBreakdown 0x040D40C0

go

-- See the summaries for each plan.

select * from PlanSummary

-- See the details for each plan.

select * from PlanDetails

go

Select * from PlanSummary returns one row as below: (note though that the data has been pivoted here for easy readability). The sizes reported here are in bytes.

plan_handle	0x05000100AB200 D4BB84137040000 000000000000000 00000
memory_object_address	0x043740C0
total_size	65536
cstmt_count	2
cstmt_size	17408
xstmt_count	2
xstmt_size	17408
cursor_count	0
cursor_size	0
mxc_count	1
mxc_size	8192
query_count	2
query_size	16384
skeleton_count	1

Now lets what happens to the memory objects when a query re-compiles:

Connection 1:

alter table t1 add col3 int

go

Connection 2:

create procedure p1

as

begin

---long running queries

select * from t1 where col1 = 5;

select * from t2 where col1 = 10;

---long running queries

end

go

exec p1

go

Execute the queries in connection 1 and 2 simultaneously. The first select query inside the stored procedure will be recompiled. Use the function CompPlanDetails to get the memory layout before executing the query in connection 1 and after executing the alter table query in connection 1. A subset of the rows returned before the query recompilation is as below:

Plan_handle	Memory_object_address	Parent_address	Type
0x05000100EAE880 7FB8415A04000000 000000000000000000	0x045A4948	0x045A40C0	MEMOBJ_ PLANSKELETON
0x05000100EAE880 7FB8415A04000000 000000000000000000	0x045A4B50	0x045A40C0	MEMOBJ_ STATEMENT
0x05000100EAE880 7FB8415A04000000 000000000000000000	0x045A4D58	0x045A40C0	MEMOBJ_ STATEMENT
0x05000100EAE880 7FB8415A04000000 000000000000000000	0x04362028	NULL	MEMOBJ_ EXECUTE

A subset of the result set returned by function CompPlanDetails after recompilation is below. After query recompilation, notice that the plan skeleton and the CStmt memory object address has been updated, while the parent address and the plan handle remain unchanged.

Plan_handle	Memory_object_address	Parent_address	Type
0x05000100EAE8807 FB8415A0400000000 0000000000000000	0x045A4F60	0x045A40C0	MEMOBJ_ PLANSKELETON
0x05000100EAE8807 FB8415A0400000000 0000000000000000	0x04362028	NULL	MEMOBJ_ EXECUTE
0x05000100EAE8807 FB8415A0400000000 0000000000000000	0x045A5168	0x045A40C0	MEMOBJ_ STATEMENT
0x05000100EAE8807 FB8415A0400000000 0000000000000000	0x045A4D58	0x045A40C0	MEMOBJ_ STATEMENT

memory_layout_example.vsd