An in-depth look at SQL Server Memory–Part 2

Before you read this, I would strongly recommend reading Part 1 first.

The memory architecture evolved in a big way from SQL 2000 to 2005. Basically, in 2000, all we had was the procedure cache (used to cache compiled plans and execution plans, execution contexts, etc.) and the buffer pool. However, in 2005, with the increase in the variety of memory consumers, and the addition of new features, the number of caches increased dramatically. In this part of the memory series, I'll try to do a deep dive into the caching mechanism of SQL server.

 

Common Caching Framework:

SQL Server implements a common caching framework. The highlight of this framework is its inbuilt ability for both lifetime and visibility management of entries. Both lifetime and visibility are controlled by a "Clock Algorithm".

 

Lifetime Management:

Under this algorithm, there are "Clock Hands" that sweep the cache at regular intervals. Every time the clock hand steps on a not-in-use entry, it decreases cost by some amount. If the entry is not in use and its cost is zero, the clock hand makes the entry invisible and then attempts to remove it from the cache. In fact, Lifetime of an entry is managed by an embedded reference count in the Clock Entry Info class. After this count goes to 0, an entry is destroyed.

There are 2 types of clock hands, internal and external. An external clock hand is moved by the resource monitor (RM) when the whole process gets into memory pressure. The internal clock hand is used to control the size of a cache relative to other caches. You can think of the internal clock hand as a way to put a max cap on a single cache. If this mechanism didn’t exist, it would be possible for a single cache to push the whole process into different types of memory pressure. To avoid this type of situation, the internal clock hand starts moving after the framework predicts that the procedure cache’s max cap is reached.

 

Visibility Management:

Visibility of an entry is implemented by a pin count embedded in the Clock Entry Info class. Keep in mind that pin count and reference count are different mechanisms. Reference count manages lifetime, and pin count manages visibility. For an entry to be visible, its pin count needs to be visible and have a value larger than 0. It also needs to be non-dirty and not marked for single usage. A pin count of 1 means that the entry is visible and is currently not in use.

 

Procedure Cache:

The procedure cache is, in most cases, the biggest consumer of SQL Server memory after the buffer pool. In this section, I'll seek to discuss the architecture and working of the Procedure cache in detail.

 

Components:

The main types of objects that can be stored in the procedure cache are described as follows:

1. Compiled Plans: When the query optimizer finishes compiling a query plan, the output is a compiled plan. A compiled plan is a set of instructions that describes exactly how SQL Server will implement a query. If you submit a T-SQL query for execution, all you have supplied is a set of logical instructions. There may be thousands of different ways that SQL Server could execute the query. The compiled plan for this query, though, would tell SQL Server exactly which physical query operators to use. For example, the compiled plan would specify whether to use an index seek, an index scan, or a table scan to retrieve rows from each table. A compiled plan represents a collection of all the query plans for a single T-SQL batch or stored procedure. Compiled plans are re-entrant, i.e. if multiple users are simultaneously executing the same stored procedure, they can all share a single compiled plan.

2. Execution Contexts: While executing a compiled plan, SQL Server has to keep track of information about the state of execution. The execution context tracks a particular execution’s parameter and local variable values, which statement in the plan is currently being executed, and object IDs for any temp objects created during execution. If two users are executing the same stored procedure at the same time, each user has his or her own execution context, but the two users may share a single compiled plan. Execution contexts cannot be shared simultaneously, but once one user is done with an execution context, it can be reused by the next user to execute the same query. For this reason, execution contexts are cached. Every execution context is linked to a particular compiled plan. Execution contexts are much cheaper to create than compiled plans, so under memory pressure they are always aged out of cache before compiled plans.

3. Cursors: Cursors track the execution state of server-side cursors, including the cursor’s current location within a resultset. Cursors have the same relationship to a compiled plan as execution contexts; every cursor is tied to a particular compiled plan. Like execution contexts, cursors can be used by only one connection at a time, but the compiled plan that the cursor is linked to can be concurrently used by multiple connections.
    

4. Algebrizer Trees: The query optimizer does not directly act on raw query text; it needs a more structured input. The Algebrizer’s job is to produce an algebrizer tree, which represents the logical structure of a query. As part of this process, the Algebrizer performs tasks like resolving table, column, and variable names to particular objects in the database. It also determines the data types of any expressions in the query. Since we have the compiled plans, we do not need to cache Algebrizer trees. The only exceptions are the Algerbizer trees for views, defaults and constraints. They are cached because a view may be referenced by many different queries. Caching the view’s algebrizer tree prevents SQL Server from repeatedly having to parse and algebrize the view every time another query is compiled that references the view.

 

When you send a query to SQL Server, the batch is parsed and sent to the Algebrizer, which produces an Algebrizer tree. The query optimizer uses the Algebrizer tree as input, and produces a compiled plan as output. Finally, in order to execute the compiled plan, an execution context must be created to track runtime state.

 

Architecture:

The caching infrastructure (of which Procedure cache is a part) exposes objects called cachestores. A cachestore provides a common set of memory allocation interfaces that are reused for many different memory consumers inside SQL Server. The procedure cache is split into several cachestores:

 

Cachestore	Common Name	Description
CACHESTORE_OBJCP	Object Cachestore	Stored procedures, functions, and triggers
CACHESTORE_SQLCP	SQL Cachestore	Ad hoc and prepared queries
CACHESTORE_PHDR	Algebrizer Cachestore	View, default, and constraint algebrizer trees
CACHESTORE_XPROC	Xproc Cachestore	Extended stored procedures

 

The object cachestore is used to cache compiled plans and related objects for stored procedures, functions, and triggers. The SQL cachestore holds plans for ad hoc and prepared queries. The Algebrizer cachestore and Xproc Cachestores hold algebrizer trees (for views, defaults and constraints only) and extended stored procedure objects respectively. The Object and SQL Cachestores are generally much larger than the other 2 cachestores.

 

In each cachestore, the lookup is managed using one or more hash tables. For example, in the SQL Cachestore, each plan is assigned a unique hash value, and the plans are divided into hash buckets based on these. Each bucket holds zero or more cached compiled plans. Each compiled plan may contain cached execution contexts and cached cursors.

Multiple plans may reside in the same hash bucket, but SQL Server limits the number of entries in each cachestore in an attempt to prevent excessive plan lookup times caused by long hash chain lengths. The SQL and object cachestores are each permitted to grow to approximately 160,000 entries on 64-bit servers, and approximately 40,000 entries on most 32-bit servers.

 

Memory Pressure:

As discussed earlier, the "Clock Algorithm" is used to delete old entries from a cachestore based on an LRU algorithm. From SQL 2005 onwards, the execution contexts are treated as part of the compiled plans, rather than being treated as separate cache objects. Every time a clock sweep passes a plan, the plan voluntarily releases half of its cached execution contexts, even if the plan itself is going to remain in the cache.

The background thread that ages plans out of the cache in SQL Server 2005 is called the resource monitor thread.

 

Cache Lookups and Plan Reuse:

The main purpose of cachestores (as if it wasn't obvious already) is to provide for reuse of the objects that they cache. The lookup method varies according to the object in question. For a stored procedure (CACHESTORE_OBJCP), the Database ID and the Object ID are used to look up the stored procedure plan(s).

For ad hoc and prepared queries, the text of the query is processed through a hash function. The hash function returns an integer value that is then referred to as the “object ID” of the SQL compiled plan object. SQL 2005 hashes the entire query text. SQL 2000 only hashed the first 8 KB, so there was a chance of the hash being the same for 2 long queries with, say, slightly different where clauses.

A number of things are taken into account when determining whether a plan will be reused:

• Since we hash the entire query from SQL 2005 onwards, the text of two ad hoc queries must match exactly in order for a cached plan to be reused.
• The object ID and database ID properties must also match the user’s current environment for plan reuse to take place.
• Other properties like user ID and language settings may be required to match, as well; any property of the cached object that must match in order for a lookup to succeed is referred to as a cache key. The cache keys for a plan are combined by another hash function to determine the bucket in the procedure cache where the plan will be stored.
• Different values for certain SET options can prevent plan reuse for ad hoc and prepared queries.

 

If you see multiple plans in cache for what appears to be the same query, you can determine the key differences between them by comparing the sys.dm_exec_plan_attributes DMF output for the two plans. The plan attributes that must match in order for reuse to occur will have an is_cache_key column value of 1.

 

Flushing the Procedure Cache:

The most common method of flushing the contents of the procedure cache is to run DBCC FREEPROCCACHE. In addition, ALTER DATABASE or DROP DATABASE commands, closing a database (due to the autoclose database option), and changes to sp_configure options can all implicitly free all or portions of the procedure cache.

 

In the next part, we will focus on the troubleshooting aspect of memory.

Comments

• Anonymous
  February 12, 2013
  The comment has been removed

• Anonymous
  February 12, 2013
  Hi Chintak, Thanks for appreciating. I will check on the Algebrizer tree caching and get back to you. Regards, Harsh

• Anonymous
  March 31, 2015
  Nice one