Sunday, March 4, 2012

DAX Query Plan, Part 3, Vertipaq Operators

The Vertipaq operators are an important subset of leaf-level operators which are responsible for preparing and sending queries to the Vertipaq Engine for execution and receiving query results. Table 1 is a list of all Vertipaq operators. You can see them in DAX Query Plan trace events by running the sample queries in column 3 against the tabular AdventureWorks database.

Table 1. Vertipaq Operators

Logical Operators
Description
Example
Scan_Vertipaq
This RelLogOp is the foundation of all other Vertipaq logical operators. It represents a basic Vertipaq query that joins a root table with related tables following many-to-one relationships, determines which rows are retrieved by testing against Vertiscan predicates, and groups the resultset by output columns.
evaluate ‘Product’
GroupBy_Vertipaq
This RelLogOp renames columns and adds rollup columns to a Vertipaq query.
evaluate summarize(‘Product’, rollup(‘Product Category’[Product Category Name], ‘Product’[Product Name]))
Filter_Vertipaq
This RelLogOp adds a Verticalc predicate to a Vertipaq query.
evaluate filter('Product', right([Product Name], 4) = "Tire")
Sum_Vertipaq
This ScaLogOp adds a SUM aggregation to a Vertipaq query.
evaluate row("x", sum('Internet Sales'[Sales Amount]))
Min_Vertipaq
This ScaLogOp adds a MIN aggregation to a Vertipaq query.
evaluate row("x", min('Internet Sales'[Sales Amount]))
Max_Vertipaq
This ScaLogOp adds a MAX aggregation to a Vertipaq query.
evaluate row("x", max('Internet Sales'[Sales Amount]))
Count_Vertipaq
This ScaLogOp adds a COUNT aggregation to a Vertipaq query.
evaluate row("x", countrows('Internet Sales'))
DistinctCount_Vertipaq
This ScaLogOp adds a DISTINCTCOUNT aggregation to a Vertipaq query.
evaluate row("x", distinctcount('Internet Sales'[Due Date]))
Average_Vertipaq
This ScaLogOp adds an AVERAGE aggregation to a Vertipaq query.
evaluate row("x", average('Internet Sales'[Sales Amount]))
Stdev.S_Vertipaq
This ScaLogOp adds a STDEV.S aggregation to a Vertipaq query.
evaluate row("x", stdev.s('Internet Sales'[Sales Amount]))
Stdev.P_Vertipaq
This ScaLogOp adds a STDEV.P aggregation to a Vertipaq query.
evaluate row("x", stdev.p('Internet Sales'[Sales Amount]))
Var.S_Vertipaq
This ScaLogOp adds a VAR.S aggregation to a Vertipaq query.
evaluate row("x", var.s('Internet Sales'[Sales Amount]))
Var.P_Vertipaq
This ScaLogOp adds a VAR.P aggregation to a Vertipaq query.
evaluate row("x", var.p('Internet Sales'[Sales Amount]))
Physical Operators


VertipaqResult
This IterPhyOp iterates over the resultset returned by a Vertipaq query.
You can find this operator in the physical plan tree after running any of the above queries.



The Vertipaq Engine runs the fastest when it executes a query in pure Vertiscan mode, which is when the query only contains simple aggregations and simple predicates. A simple aggregation aggregates a single column or counts rows of the table. A simple predicate, called Vertiscan predicate in Table 1, typically looks like [Column] = 5 or [Column] IN { 5, 6, 7, … } or ([Column1], [Column2]) IN { (5, 6), (7, 8), … } where the numbers are data IDs. Note that all column values are encoded as integer data IDs inside the Vertipaq Engine. The Vertipaq Engine extends its basic Vertiscan capabilities through its own calculation engine, called Verticalc. When aggregation expressions or predicate expressions become more complex, the Vertipaq Engine builds calculation trees to evaluate those expressions and can even call back to the DAX Formula Engine for help on those operators it doesn’t support natively. For example, when the aggregation expression is maxx('Internet Sales', year([Due Date])), the Vertipaq Engine calls back to the DAX Formula Engine to evaluate the Year function. Similarly, complex predicate expressions are also evaluated using the Verticalc technology therefore are called Verticalc predicates in Table 1. The Vertipaq Engine typically runs slower when it has to invoke Verticalc evaluations during query execution therefore the DAX Formula Engine converts filter predicates into Vertiscan slices whenever possible.

Ever since the MDX days, users have been complaining that the Formula Engine is single-threaded when it executes a single query. The problem is partially solved when the DAX Formula Engine pushes calculations down to the Vertipaq Engine. Not only is the Vertipaq Engine multi-threaded, it is also able to greatly reduce the number of calculations by taking advantage of large blocks of continuous rows with identical values for those columns referenced by the calculation. Therefore, the DAX Formula Engine tries very hard to push operations down to the Vertipaq Engine whenever possible and it is highly desirable to see mostly Vertipaq operators in DAX Query Plan events.

Caveats of Understanding Vertipaq Operators in DAX Query Plan Trees

As a brand new feature in Denali, the DAX Query Plan has plenty of room for future improvements. Here I am going to highlight three aspects of the current implementation which might confuse users who are trying to read DAX Query Plans for the first time.

1.      The display of Vertipaq operators is too closely tied to the underlying implementation, as a result, users might see multiple nested Vertipaq operators in a plan tree but only a single Vertipaq query is issued. For example, if you run Query 1, you will see four Vertipaq operators, Sum_Vertipaq, Filter_Vertipaq, Filter_Vertipaq, Scan_Vertipaq, in the DAX Query Plan/DAX Vertipaq Logical Plan event, as shown in Figure 1, but only a single Vertipaq SE Query Begin/Vertipaq Scan event. As you can see in Figure 1, a Scan_Vertipaq operator serves as the foundation for all other Vertipaq operators, each aggregation or Verticalc filter has its own operator, and the cascading operators are displayed in a chain of parent-child relationships even though aggregations and Verticalc filters are eventually folded into a single Vertipaq query.

// Query 1
evaluate row("x",
            sumx(
                        filter(
                                    'Internet Sales',
                                    Related(Product[List Price]) < 10
                                    && Related(Customer[Yearly Income]) < 50000
                        ),
                        [Sales Amount]
            )
)



2.      As mentioned in the second installment of the DAX Query Plan blog series, spools are not first-class citizens in Denali DAX Query Plans, but users can still detect the presence of spools in Denali DAX Query Plan trees indirectly through the presence of physical operators which sit directly on top of spools such as the Spool LookupPhyOp or the Spool_IterOnly, Spool_LookupOnly, Spool_SliceIndex IterPhyOps. Let’s call them spool operators in this post to make it easier to refer to them.  If you run Query 2 and examine the physical plan tree shown in Figure 2, you can see a Spool_IterOnly operator with a child VertipaqResult operator. Since the real child operator of Spool_IterOnly is a spool, what’s with the VertipaqResult IterPhyOp? As it turns out, some iterators supply the rows needed to fill a spool when it is materialized and DAX Query Plan shows iterator subtrees which are used to populate the spool as child operators of the spool operator. In Denali, a spool is always constructed to receive the resultset of a Vertipaq query, hence VertipaqResult operator is always a child of a spool operator. An important property of a spool operator is #Records, highlighted in Figure 2, which tells you how many rows of data are in the underlying spool and is currently the most important property to help identify performance problems of a query. When VertipaqResult is the sourcing iterator, this property tells you how many records are returned by the Vertipaq Engine.

// Query 2
evaluate values(Product[List Price])






3.      As stated earlier, Verticalc evaluations may call back to the DAX Formula Engine for unsupported logical operators which in turn would construct the corresponding physical operator trees just as it would when the calculation happens entirely in the Formula Engine. Sometimes the callback functions can be very expensive themselves but those physical operators are not shown in the plan tree. If you run Query 3 you will see in the Vertipaq SE Query Begin event, shown in Figure 3, that the Vertipaq Engine calls back to the DAX Formula Engine for its help with the Year function, but the corresponding physical operator does not show up in the DAX Query Plan/DAX Vertipaq Physical Plan event, shown in Figure 4.

// Query 3
evaluate row("x", maxx('Internet Sales', year([Due Date])))



Special Properties of Scan_Vertipaq RelLogOp

As you have seen in the previous examples, the Scan_Vertipaq operator is at the core of every Vertipaq query and has several special properties worth mentioning here. To show you all the properties of Scan_Vertipaq, run Query 4 and then look at its logical plan.

// Query 4
define measure 'Internet Sales'[Total Sales Amount] = Sum([Sales Amount])
evaluate
            calculatetable(
                        addcolumns(
                                    crossjoin(values('Date'[Month]), distinct('Product Category'[Product Category Name])),
                                    "YTD",
                                    calculate([Total Sales Amount],
                                                filter(
                                                            All('Date'[Month]),
                                                            'Date'[Month]
                                                            <=
                                                            earlier('Date'[Month])
                                                )
                                    )
                        ),
                        'Date'[Calendar Year] = 2003
            )



Below is the longest line I extracted from the logical plan with operator specific properties in bold face.



Scan_Vertipaq: RelLogOp DependOnCols(1, 2)('Date'[Month], 'Product Category'[Product Category Name]) 4-141 RequiredCols(1, 2, 133)('Date'[Month], 'Product Category'[Product Category Name], 'Internet Sales'[Sales Amount]) Table='Internet Sales_78de3956-70d9-429f-9857-c407f7902f1e' -BlankRow JoinCols(2)('Product Category'[Product Category Name]) SemijoinCols(3)('Date'[Month])

As you can see, in addition to the common properties DependOnCols, range of column numbers, and RequiredCols, Scan_Vertipaq also has a couple of extra properties:

·        Table

Displays the internal ID of the root table in Denali. I think this should change to user friendly table name in the future.

·        Whether the blank row is requested

DAX introduced an optional blank row to an IMBI table in order to deal with any incoming referential integrity violations. When users want to include this blank row in the resultset of a Vertipaq query, query plan shows +BlankRow; when users don’t want to include the blank row in the resultset, query plan displays –BlankRow. In Query 4 I deliberately used both the Values function and the Distinct function inside the CrossJoin function to demonstrate the difference, see Figure 5 which was an excerpt from the logical plan.


·        JoinCols

The columns from this table which are needed for natural join with other tables. JoinCols are a subset of DependOnCols, the latter is actually a union of the former and the DependOnCols of all semi-join filter operators.

·        SemijoinCols

The columns from this table which are needed for natural semi-join with filter tables. The DAX Formula Engine simplifies the logical operator tree by converting most explicit semi-join filters to Vertiscan slices or Verticalc slices so that the filtering operations happen inside the Vertipaq Engine, and since DAX Query Plan/DAX Vertipaq Logical Plan events are fired after the simplification stage, users typically don’t see the SemijoinCols property. But when SemijoinCols do show up in the plan, the DAX Formula Engine may have to fetch more columns back, join with the filter tables, and then remove unwanted SemijoinCols by grouping on the desired output columns. When this happens, the Vertipaq operator can be quite expensive as a lot of post-processing happens in the Formula Engine before the final resultset can be returned.

Understand Performance Differences between Equivalent Queries

To conclude today’s post, let’s run two queries which are written in different ways but return the same results and use DAX Query Plans to figure out why they perform differently. Both Query 5 and Query 6 use the AddColumns function to simulate adding a calculated column to the ‘Date’ table. The calculated column calculates the sum of [Sales Amount] after filters the ‘Internet Sales’ table based on a predicate that depends on a column value from the current row. While it is natural to write the calculation as sum of filter as done in Query 5, to get much better performance, you should split the sum and the filter into separate functions and then calculate the sum by adding the filter to the filter context, see Query 6. Compare their logical plans, shown in Figure 6 and Figure 7 respectively, you can see that Query 5 executes both the SumX function and the Filter function in the Formula Engine but Query 6 only executes the Filter function in the Formula Engine but pushes the SumX down to the Vertipaq Engine through the Sum_Vertipaq operator. Since today we have learned that it is always good if calculations can be pushed down to the Vertipaq Engine, Query 6 runs a lot faster than Query 5. So write your DAX expressions to take advantage of Vertipaq operators.

// Query 5
evaluate
            addcolumns(
                        'Date',
                        "x",
                        sumx(
                                    filter('Internet Sales', [Order Date] <= [Date]),
                                    [Sales Amount]
                        )
            )
 

// Query 6
evaluate
            addcolumns(
                        'Date',
                        "x",
                        calculate(
                                    sum('Internet Sales'[Sales Amount]),
                                    'Internet Sales'[Order Date] <= earlier([Date]),
                                    all('Date')
                        )
            )
 


Tuesday, January 31, 2012

DAX Query Plan, Part 2, Operator Properties

Last time we learned that DAX Query Plans are tree structures formatted as indented text with each text line representing a single operator node in a tree. A text line begins with an operator name followed by a colon and then properties of the operator. Today we study the operator properties. You will see that for the four types of operators, ScaLogOp, RelLogOp, LookupPhyOp, and IterPhyOp, each type has a fixed set of common properties, and an individual operator may contain extra properties to provide supplemental information. We’ll focus on the semantics of the common properties in this post.

List of Columns
In a DAX Query Plan, a list of columns is shown as a list of comma-delimited column numbers in a pair of parentheses plus a list of comma-delimited fully-qualified column names in another pair of parentheses, see Figure 1. In a degenerate case, two pairs of empty parentheses, ()(), represent an empty list. Note that some properties, like LookupCols and IterCols, are not shown in the plan when they contain no columns, but other properties, like DependOnCols and RequiredCols, are always shown even when their list of columns is empty.

Column numbers are helpful when you need to disambiguate two separate references to the same column. When you execute Query 1 against the tabular AdventureWorks database, the logical plan, shown in Figure 2, assigns different numbers to column ‘Date’[Month]: number 1 refers to the column in the outer table scan and number 2 refers to the column in the inner table scan. Column numbers are not chosen to be globally unique, but rather unique within a local context.
// Query 1
define measure 'Internet Sales'[Total Sales Amount] = Sum([Sales Amount])
evaluate
  calculatetable(
    addcolumns(
      values('Date'[Month]),           -- outer scan
      "YTD",
      calculate([Total Sales Amount],
          filter(
            All('Date'[Month]),        -- inner scan
            'Date'[Month]              -- refer to inner scan
            <=
            earlier('Date'[Month])     -- refer to outer scan
          )
      )
    ),
    'Date'[Calendar Year] = 2003
  )

Common Properties of Logical Plan Nodes

Here are the properties common to all scalar logical operators (ScaLogOp):


·         DependOnCols
Marks columns from the left-side of a tree on which the current logical operator depends. The current operator may return a different value for each distinct combination of values of DependOnCols. Some table scanning functions, e.g. AddColumns and Filter, create a row context using its left child subtree and then evaluate the value of its right child subtree in this context. This creates a dependency of the right child subtree on some columns from the left child subtree. DependOnCols captures this correlation between the two sides of a tree. Figure 3 shows an example where a ScaLogOp subtree on the right depends on some columns from two RelLogOp subtrees on the left. At the bottom level of a tree, DependOnCols are established by either an explicit reference to a column on the left or by a leaf table scan that joins directly or indirectly (through SetFilter arguments of Calculate function) to columns on the left. DependOnCols are then propagated up through intermediate parent nodes to the root node of the right subtree. Since DAX automatic cross-table filtering rules can be tricky sometimes, beginners can use this property to help them figure out whether their measures have the correct dependencies on external row contexts.

·         Data type
One of the six data types DAX supports. Values returned by the operator must be either of this data type or be the BLANK value.

·         DominantValue
Captures the sparsity of a scalar logical operator. When DominantValue is NONE, the operator is dense, otherwise, it is sparse. When a scalar subtree is sparse, DAX Formula Engine may pick a physical plan that can be orders of magnitudes faster than a na├»ve physical plan. For example, if the predicate child operator of a Filter operator has a DominantValue of FALSE, DAX Formula Engine can construct an iterator physical plan for the predicate subtree that automatically skips large chunks of rows which would otherwise return FALSE and be thrown away any way by the Filter operator.  For users coming from MDX background, this reminds them of the huge performance difference between block mode vs. cell-by-cell mode. The technique to derive the sparsity of a scalar subtree is very sophisticated and beyond the scope of this post. It’s enough to know that a sparse scalar operator is the key to great performance in many common query patterns.

Here are properties common to all relational logical operators (RelLogOp):
·         DependOnCols
Identical to the same named property of ScaLogOp. The current operator may return a different table for each distinct combination of values of DependOnCols.
·         Range of column numbers
Although a relation may contain many columns in its heading, DAX Formula Engine is smart enough to derive the minimal subset of columns, see RequiredCols property, which are needed to answer a query. To save space, DAX Query Plan does not list all columns in the relation header, instead, it assigns continuous column numbers to all columns in the relation header and only shows <beginning column name>-<ending column name> as a part of the plan. Note that this property may be missing when a relation has no column at all.
·         RequiredCols
This is the union of DependOnCols and the subset of columns from the relation header which are needed to answer a query. For example, when you examine the logical plan, shown in Figure 4, which corresponds to Query 2, you can see that only one column, [Sales Amount], among 129 columns is a required column. In case you are wondering why ‘Internet Sales’ table has 129 columns, you can find the answer in one of my earlier posts.
// Query 2
define measure 'Internet Sales'[Total Sales Amount] = Sum([Sales Amount])
evaluate row("x", [Total Sales Amount])



Common Properties of Physical Plan Nodes
In a physical plan tree, an iterator operator supplies rows of column values to other nodes. When those rows are fed to a lookup operator, it can return a scalar value from each input row. When the rows are fed to another iterator operator, it can output any number of rows of its own columns for each input row. Therefore, both iterators and lookups share the same input property, LookupCols, but they produce different outputs. Let’s use the physical plan tree, shown in Figure 5, captured from Query 1 to illustrate the common properties of physical operators.
Here are the properties common to all lookup physical operators (LookupPhyOp):
·         LookupCols
Columns supplied by an iterator whose values are used to calculate a scalar value. In Figure 5, lookup operators 1 and 2 read their input values from iterator 3; their output values are later on used by their parent operator, LessThanOrEqualTo, to calculate a Boolean value.
·         Data type
One of the six data types DAX supports. Values returned by the operator must be either of this data type or be the BLANK value.
Here are the properties common to all iterator physical operators (IterPhyOp):
·         LookupCols
Identical to the same named property of LookupPhyOp. In Figure 5, iterator 5, which doesn’t have the LookupCols property, hence a pure iterator, supplies column 2 to iterator 4 as its LookupCols property which in turn produces output column 1.
·         IterCols
Columns output by the iterator.
It is interesting to learn that a DAX iterator can be a pure iterator, when it only has the IterCols property, or a table-valued function as in T-SQL Apply operator when it has both LookupCols and IterCols properties, or a pure row checker when it only has the LookupCols property. In the last case, the iterator serves the purpose of removing unwanted rows from other iterators.
For many DAX operators, common properties are all they offer. But some DAX operators output additional properties to provide more information about themselves. I am not going to go into details about all those operator-specific properties today because it would drag this blog on far too long. I’ll only describe the proprietary properties of one physical operator Spool_IterOnly and postpone the discussion of private properties of other operators in future blogs when we get to study individual operators.
Special Properties of Physical Operator Spool_IterOnly<>
Spool_IterOnly is a pure iterator that draws its rows from an in-memory spool which is built through some other means. DAX Formula Engine builds different flavors of in-memory spools, therefore Spool_IterOnly along with several other physical operators built from spools put the name of the spool in a pair of angle brackets <> as a part of their names. This is partly caused by the fact that spools are not first class citizens in query plan trees as of SQL Server 2012. As a result, some spool specific properties are added directly to physical operators built on top of the spool. Below is one line I extracted from Figure 5 with Spool_IterOnly specific properties highlighted in bold face. They tell us that there are 12 records in the spool and there are 240 key columns (most of which are compressed to 0 bit hence record size is not as wide as it seems) and no value columns.
Spool_IterOnly<Spool>: IterPhyOp IterCols(1)('Date'[Month]) #Records=12 #KeyCols=240 #ValueCols=0
Summary
Today we studied properties of operator nodes in DAX Query Plan trees. We have learned that some properties are common to all operators of one type and some properties are specific to a particular operator. While I described in details those common properties, I just cited one example of operator specific properties. Now that we have covered the basics of DAX Query Plans, we will be able to explore ways to take advantage of them to investigate performance issues in future posts. When we run into a specific operator of importance, I’ll explain its associated properties at that time.