1.0 Structure of the Plan Cache and Types of Cached Objects

Article
01/09/2007

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

)

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

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

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)

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)

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

512

0x042

B0398

0x060001002

9A7DD06B801

2B040000000

00000000000

000000

0x042

B0528

0x042

B00C0

MEMOBJ_

COMPILE_

ADHOC

NULL

512

0x042

B0398

0x060001002

9A7DD06B801

2B040000000

00000000000

000000

0x042

B00C0

NULL

MEMOBJ_

COMPILE_

ADHOC

NULL

8192

0x036

141D0

0x060001002

9A7DD06B801

2B040000000

00000000000

000000

0x03F

98028

NULL

MEMOBJ_

EXECUTE

NULL

8192

0x036

141D0

0x060001002

9A7DD06B801

2B040000000

00000000000

000000

0x042

88040

NULL

MEMOBJ_

QUERYEX

ECCNTXT

FORSE

NULL

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

begin

select col1 from t1

select col2 from t1 where col1 = 50000

end

exec p1

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

0x03E

B3168

0x03E

B20C0

MEMOBJ_

XSTMT

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B2F60

0x03E

B20C0

MEMOBJ_

XSTMT

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B2538

0x03E

B20C0

MEMOBJ_

COMPILE_

ADHOC

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B2948

0x03E

B20C0

MEMOBJ_

PLAN

SKELETON

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B2B50

0x03E

B20C0

MEMOBJ_

STATEMENT

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B2D58

0x03E

B20C0

MEMOBJ_

STATEMENT

NULL

512

0x03E

B23A8

0x05000100

95555D02B8

21EB030000

0000000000

0x042

00028

NULL

MEMOBJ_

EXECUTE

NULL

8192

0x036

12380

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

32040

NULL

MEMOBJ_

QUERY

EXECCNTXT

FORSE

NULL

8192

0x036

12380

0x05000100

95555D02B8

21EB030000

0000000000

0x041

74040

NULL

MEMOBJ_

QUERY

EXECCNTXT

FORSE

NULL

8192

0x036

12380

0x05000100

95555D02B8

21EB030000

0000000000

0x03E

B20C0

NULL

MEMOBJ_

COMPILE_

ADHOC

NULL

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

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

exec PlanBreakdown 0x040D40C0

-- See the summaries for each plan.

select * from PlanSummary

-- See the details for each plan.

select * from PlanDetails

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

Connection 2:

create procedure p1

begin

---long running queries

select * from t1 where col1 = 5;

select * from t2 where col1 = 10;

---long running queries

end

exec p1

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

1.0 Structure of the Plan Cache and Types of Cached Objects

Additional resources