Benjamin Nevarez Rotating Header Image

Inside the Query Optimizer Memo Structure

I just learned a few query-optimizer-related undocumented trace flags from my friend Dmitry Pilugin, who blogged about them in his blog in Russian, SomewhereSomehow’s Blog, and asked me if I could be interested in posting something in English. Some of these interesting trace flags allow us to see the contents of the memo structure, something I was trying to find while writing my book Inside the SQL Server Query Optimizer.

But first, a quick reminder of what the memo structure is. The memo is a search data structure that is used to store the alternatives generated and analyzed by the SQL Server query optimizer. These alternatives can be logical or physical operators and are organized into groups such that each alternative in the same group produces the same results. The query optimizer first copies the original query tree’s logical expressions into the memo structure, placing each operator from the query tree in its own group, and then triggers the entire optimization process. During this process, transformation rules are applied to generate all the alternatives, starting with these initial logical expressions. As the transformation rules produce new alternatives, these are added to their equivalent groups. Transformation rules may also produce a new expression which is not equivalent to any existing group, and which causes a new group to be created. A new memo structure is created for each optimization.

But instead of trying to explain the basics of how the memo structure works you can refer to my book, Inside the SQL Server Query Optimizer, which you can download for free from the simple-talk website. In this post I will show you how to see the contents of the memo structure. First enable the trace flag 3604 to redirect the trace output to the client executing the command, in this case SQL Server Management Studio.

DBCC TRACEON(3604)

Next I will be using the undocumented trace flags 8608 and 8615 but, although I can still use DBCC TRACEON, this time I will use the also undocumented QUERYTRACEON query hint. Please bear in mind that all these are undocumented SQL Server statements and should not be used on a production environment.

The first trace flag, 8608, will show the initial memo structure, which you can see in the Messages tab of the Query window in Management Studio.

SELECT e.EmployeeID FROM HumanResources.Employee AS e 
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (QUERYTRACEON 8608)

Running the previous query will show the following output

--- Initial Memo Structure ---
Root Group 5: Card=8.33333 (Max=10000, Min=0)
   0 LogOp_Join 0 1 4 
Group 4: 
   0 ScaOp_Comp  2 3 
Group 3: 
   0 ScaOp_Identifier  
Group 2: 
   0 ScaOp_Identifier  
Group 1: Card=17 (Max=10000, Min=0)
   0 LogOp_Get 
Group 0: Card=290 (Max=10000, Min=0)
   0 LogOp_Get

The next query uses trace flag 8615 to display the final memo structure

SELECT e.EmployeeID FROM HumanResources.Employee AS e 
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (QUERYTRACEON 8615)

which shows the following output

--- Final Memo Structure ---
Group 9: Card=1 (Max=1, Min=0)
   0 LogOp_SelectIdx 8 4 
Group 8: Card=17 (Max=10000, Min=0)
   0 LogOp_GetIdx 
Group 7: Card=1 (Max=1, Min=0)
   1 PhyOp_Range 1 ASC 4.0 Cost(RowGoal 0,ReW 0,ReB 16,Dist 17,Total 17)= 0.0058127
   0 LogOp_SelectIdx 6 4 
Group 6: Card=290 (Max=10000, Min=0)
   0 LogOp_GetIdx 
Root Group 5: Card=8.33333 (Max=10000, Min=0)
   2 PhyOp_Applyx_jtInner 1.2 7.1 Cost(RowGoal 0,ReW 0,ReB 0,Dist 0, …)= 0.00918446
   1 LogOp_Join 1 0 4 
   0 LogOp_Join 0 1 4 
Group 4: 
   0 ScaOp_Comp  2.0 3.0  Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 3
Group 3: 
   0 ScaOp_Identifier   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 1
Group 2: 
   0 ScaOp_Identifier   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 1
Group 1: Card=17 (Max=10000, Min=0)
   3 PhyOp_Range 1 ASC   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 0.0033007
   2 PhyOp_Range 2 ASC   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 0.0033007
   0 LogOp_Get 
Group 0: Card=290 (Max=10000, Min=0)
   0 LogOp_Get

You can notice that among other things the output shows information about operators, groups, cardinality information (Card) and cost estimation. I will be discussing a few more undocumented trace flags on a second post very soon.

About the author

Benjamin Nevarez Benjamin Nevarez is a SQL Server MVP and independent consultant based in Los Angeles, California who specializes in SQL Server query tuning and optimization. He is the author of "SQL Server 2014 Query Tuning & Optimization" and "Inside the SQL Server Query Optimizer" and co-author of "SQL Server 2012 Internals". With more than 20 years of experience in relational databases, Benjamin has also been a speaker at many SQL Server conferences, including the PASS Summit, SQL Server Connections and SQLBits. Benjamin’s blog can be found at http://www.benjaminnevarez.com and he can also be reached by e-mail at admin at benjaminnevarez dot com and on twitter at @BenjaminNevarez.

3 Comments

  1. [...] trace flags (you can read the first one, “Inside the Query Optimizer Memo Structure”, here). Although is not the purpose of this post to discuss the entire optimization process or go into [...]

  2. [...] 28.04.2012 Benjamin Nevarez blog — Inside the Query Optimizer Memo Structure Benjamin Nevarez blog — More Undocumented Query Optimizer Trace Flags Paul White blog — [...]

  3. [...] post Full Optimization: Search 0(ru), so won’t cover it here in details. I recommend to read Benjamin Nevarez blog — Inside the Query Optimizer Memo Structure if you are not familiar with it. For now, it is important that we may look at what alternative [...]

Add Comment Register



Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>