Tuning the performance of data warehouse queries

Data manipulation languages and the query optimization problem

A data warehouse (DW) and the underlying database (DB) it is built on can be viewed as collections of data intended for shared, collective use within an organization. This implies that a DB or DW represents a named, structured, and interpretable body of user data. Physically, the data in a DB is represented in machine-readable form. The logical structure of the data and access to it are maintained by the DBMS. Access to data through the DBMS is carried out using data manipulation languages. A data manipulation language is used to provide access to data when storing it in a DB or retrieving it from one.

Regardless of whether a DB is distributed or centralized, the data resides in the operating system's files on the computer(s) involved. Input/output and updating of data in the DB, searching for data required for reading, adding new data, modifying existing data, and deleting data that is no longer current are all carried out by the DBMS and require sharing the processor, memory, and communication resources in use. The performance of a DW or DB is defined by the average system response time for performing a search operation and delivering the required information. System response time depends on many factors, such as network bandwidth, DBMS throughput, the processing power of the computers used, the read/write speed of the physical storage media, and so on. It also depends on the logical structure of the DB and the language tools used for data access.

Therefore, in order to better understand the essence of query optimization processes in relational databases, we must first discuss the main types of data manipulation languages. Today, two main types of such languages are distinguished: procedural and declarative.

Procedural data manipulation languages

Most database systems prior to the adoption of SQL technology were based on procedural, or navigational, data manipulation languages. Examples of such database systems include ADABAS (Software Ag.), IDMS, IMS (IBM Corp.), and dBase. Procedural data manipulation languages require the programmer to code the program logic needed to navigate the physical data structure in order to identify and access the required data. For example, when using ADABAS, the programmer must write code to specify data records (FIND), obtain the specified set of data and organize a loop to iterate through it (GET), and also provide code to update the retrieved data for the user.

If an application program references physical data structures, it naturally becomes dependent on them. Such application programs require code modification whenever the physical data structure changes. For example, if an index in dBase is dropped, all application programs that use it must be modified.

The dependency between the application program and the physical data structure significantly increases the cost of developing and maintaining such programs. During the development of large, complex computer systems, discrepancies between the designed physical structure of the DB and the implementation of the domain's functionality in the programs are very often discovered at various stages of the project. To eliminate such discrepancies, the database administrator must make changes to the physical structure.

Such changes to the physical and logical schemas of the DB conflict with all existing programs that reference these changed physical structures. These programs must be modified to reflect the changes in the DB schema. If an application program relies heavily on the changed physical structure to navigate the DB and its program logic is built around this navigation, significant recoding of the program may be required. On the other hand, maintaining existing systems often requires changes to the DB schema, and naturally such a dependency drives up the cost of maintaining user applications.

In addition, it should be noted that procedural data manipulation languages are usually context-dependent in their implementation. As a result, application programs become entirely tied to the specific DB system for which they were developed. This binding of application programs to specific DB systems significantly limits their portability.

Declarative data manipulation languages

With the advent of SQL technology and relational database systems, it became possible to break the relationship between application programs and physical data structures. Declarative data manipulation languages only specify what data the application program needs, leaving it to the DBMS to determine how to navigate the physical data structure to access the required data. SQL is an example of a declarative data manipulation language.

The concept of application program independence from the physical data structure provides several significant advantages.

• Reflecting requirements for changes in data structures has little effect on existing application programs. For example, if an existing index becomes outdated, it can be freely dropped and a new index created (including on different attributes) without affecting existing programs. The newly created index may either improve or degrade program performance. However, one can be confident that the existing programs will run without errors. It is assumed that the SQL command will be prepared before execution, although some relational DBMSs, such as those in the MS SQL Server family, can automatically recompile the stored SQL command access plan (SQL access plan). In procedural data manipulation languages, it is not always obvious what caused a program to fail — changes in the physical structure or its inconsistency with the program logic.
• Application program complexity is reduced. The DBMS, rather than the programmer, determines how to navigate the physical data structure. This frees the programmer to solve other tasks, since this aspect of programming is often the most complex part of the program logic.
• The number of errors in application programs is reduced. The complexity of data access often leads to programming errors if the programmer is not highly skilled or is not sufficiently careful in coding. The main advantage of a computer is its ability to perform simple instructions at high speed and without errors. Consequently, the DBMS essentially replaces the programmer in determining how to navigate the physical data structure to access the required data.

Query optimization

The SQL component of the DBMS that determines how to navigate the physical data structures to access the required data is called the query optimizer.

The navigational logic (a variant of the algorithm) used to access the required data is called the access path or access method.

The sequence of actions performed by the optimizer that implements the chosen access paths is called the execution plan.

The process used by the query optimizer to determine the access path is called query optimization.

During the query optimization process, access paths are determined for all types of SQL DML commands. However, the SQL SELECT command presents the greatest difficulty in solving the problem of choosing an access path. That is why this process is usually called query optimization rather than data access path optimization. It should also be noted that the term "query optimization" is not entirely accurate — in the sense that there is no guarantee that an actually optimal access path will be obtained during the query optimization process. A more suitable term might be "query improvement" — for example, the best possible access path for a given cost (in terms of computational complexity). Nevertheless, the standard, generally accepted term "query optimization" is used throughout to avoid confusion.

Early versions of relational DBMSs processed queries in a simple, straightforward manner without any attempt to optimize either the query itself or the access path. This resulted in unacceptably long query processing times and led some application programmers to believe that relational DBMSs were impractical and unsuitable for a wide range of practical applications. In order to increase query processing speed, extensive research and testing were carried out to find ways of improving query processing efficiency.

Thus, query optimization can be defined as the sum of all the techniques applied to improve query processing efficiency.

Syntactic optimization

The first success in query optimization was finding a way to reformulate a query such that the new representation of the query produced the same result but was more efficient for the DBMS to process.

Example 24.1. Consider the following query, which retrieves data from the tables PRODUCT and VENDOR:

SELECT VENDOR_CODE, PRODUCT_CODE, PRODUCT_DESC
FROM VENDOR, PRODUCT
WHERE VENDOR.VENDOR_CODE = PRODUCT.VENDOR_CODE AND VENDOR.VENDOR_CODE = "100";

The most obvious way of processing this query is as follows.

1. Form the Cartesian product of the tables PRODUCT and VENDOR.
2. Restrict the resulting table to the rows that satisfy the search condition in the WHERE clause.
3. Perform a projection of the resulting table onto the list of columns specified in the SELECT clause.

Let us estimate the cost of processing this query in terms of I/O operations. Suppose, for the sake of concreteness, that the VENDOR table contains 50 rows and the PRODUCT table contains 1000 rows. Then forming the Cartesian product will require 50,050 read operations and write operations (into the result table). Restricting the result table will require more than 50,000 read operations, and, if 20 rows satisfy the search conditions, 20 write operations. Performing the projection operation will cause another 20 read operations and 20 write operations. Thus, processing this query will cost the system 100,090 read and write operations.

The basic idea behind syntactic optimization lies in applying equivalent algebraic transformations. SQL is an algebraic language for manipulating sets (represented as tables). Every SELECT statement is equivalent to some formula of this language. There is a set of algebraic rules for identity transformations of formulas over sets. For the query in this example, the following equivalence can be used

This means that restriction by the search condition can be performed as early as possible, in order to limit the number of rows that need to be processed later. Applying this rule to the query given above, we obtain the following query processing procedure.

1. Restricting by the search condition on the second table (VENDOR_CODE = "100") will require 1000 read operations and 20 write operations.
2. Performing the join of the result table obtained in step 1 with the VENDOR table will require 20 read operations on the result table, 100 read operations on the VENDOR table, and 20 write operations into the new result table

In this case, processing the query will require 1120 read operations and 40 write operations to obtain the same result as in the first case. The transformation described in this example is called syntactic optimization (syntax optimization).

There are many formulas for performing such transformations, and all modern query optimizers use transformation rules to represent a query in a more efficient form for processing. From an implementation standpoint, it is very important that these automatic transformations free the programmer from having to search for an equivalent form of the query in order to obtain the best possible implementation, since the optimizer usually produces the same final form that you could obtain manually.

Rule-based optimization

Once some progress had been made in improving query processing, efforts were also made to improve methods of accessing tables. This concerns the development of access methods based on the use of indexes and hashing functions. However, the use of indexing and hashing techniques increases the complexity of query processing. For example, if a table has indexes on three different columns, any one of them can be used to access the table (in addition to sequential access to the table in the physical row order).

In addition, many new algorithms have appeared for performing table joins. The two most basic join execution algorithms are:

• Nested Loop Join. In this algorithm, a row is read from the first table, called the outer table, and then each row of the second table, called the inner table, is read as a join candidate. Then the second row of the first table is read, and again each row of the second table, and so on until all rows of the first table have been read. If the first table has M rows and the second has N, then M x N rows are read;
• Merge Join. This join method assumes that the tables are sorted (or indexed) such that rows are read in the order of the values of the column(s) on which they are joined. This allows the join to be performed by reading rows from each table and comparing the values of the join columns for as long as the values match. With this method, the join completes in a single pass through each table.

Join operations obey both the commutative and associative laws. Consequently, it is theoretically possible to perform joins in any order. For example, all the following statements are equivalent.

(A JOIN B) JOIN C

A JOIN (B JOIN C)

(A JOIN C) JOIN B

However, different access paths, join algorithms, and join execution orders can result in significantly different performance. Consequently, when joining several tables, each of which has several indexes, there can be several hundred different combinations to choose from for the join order, join algorithms, and retrieval access paths. Each of these combinations produces the same result, but with different performance characteristics.

One of the earliest approaches to dealing with the combinatorial complexity of performing joins consists of establishing heuristic rules for choosing between access paths and join methods, an approach called rule-based optimization. In this approach, weights and preferences are assigned to alternatives based on generally accepted principles. Using these weights and preferences, the query optimizer generates possible execution plans until the best execution plan satisfying these rules is reached. Some of the rules used by optimizers of this type are based on the placement of variable service tokens (variable tokens), such as table and column names, within the syntactic structures of the query. When these names are placed differently, a significant difference in query execution performance can sometimes occur. For this reason, rule-based optimizers are said to be syntax-dependent, and one of the methods for tuning optimizers of this type of DBMS involves placing tokens in different positions within the statement.

Rule-based optimization provides satisfactory system performance in situations where the heuristics are accurate. However, the generally accepted rules are often not accurate. To detect such situations, the query optimizer must consider data characteristics such as:

• the number of rows in the table;
• the range and distribution of values in a given column;
• the row length and, accordingly, the number of rows per physical disk page;
• the height of the index;
• the number of leaf pages in the index.

These data characteristics can strongly affect query processing efficiency. Using such characteristics leads to the following type of optimization.

Cost-based optimization

Cost-based query optimization is similar to rule-based optimization, except that the cost-based optimizer uses statistical information to select the most efficient query execution plan. The cost of each alternative query execution plan is estimated using statistics, such as the number of rows in a table and the number and distribution of values in a table column. Cost formulas typically take into account the amount of I/O and the CPU time required to execute the query plan. Such statistics are stored in the system catalog and maintained by the DBMS.

To understand how statistics can be used to choose a query execution plan, consider the following query against the CUSTOMER table:

SELECT CUST_NBR, CUST_NAME
FROM CUSTOMER
WHERE STATE = "FL";

If an index exists on the STATE column, a rule-based optimizer would use it to process the query. However, if ninety percent of the rows in the CUSTOMER table have FL in the STATE column, using the index would actually result in slower query execution than a simple sequential scan of the table. A cost-based optimizer, on the other hand, would discover that using the index provides no advantage over a sequential scan of the table.

The cost-based approach to optimization today represents something of an art in query optimization technique. Most relational DBMSs employ cost-based optimizers.

The sequence of query optimization steps

Although the query optimizers of modern relational DBMSs differ in complexity and design principles, they all follow the same basic stages in performing query optimization.

• Parsing. The optimizer first breaks the query down into its syntactic components, checks for syntax errors, and then converts the query into its internal representation for further processing.
• Conversion. Next, the optimizer applies query transformation rules and translates it into a format that is optimal from a syntactic standpoint.
• Develop alternatives. Once the query has passed through syntactic optimization, the optimizer develops alternatives for its execution.
• Create execution plan. Finally, the optimizer chooses the best query execution plan, either by following a set of heuristic rules or by calculating the cost of each execution alternative.

Since steps 1 and 2 are performed independently of the actual data contained in the tables, there is no need to repeat them unless the query requires recompilation. Consequently, most optimizers will save the results of step 2 and reuse them the next time they re-optimize the query.

The optimizer of the MS SQL Server family of DBMSs

The optimizer of the MS SQL Server family of DBMSs, based on cost estimation, dynamically determines the query processing strategy based on the current table/index structure and data. This dynamic behavior can be overridden using optimizer hints, taking certain decisions out of the optimizer's hands and instructing it to use a particular processing strategy. This makes the optimizer's behavior static and prevents it from dynamically updating its processing strategy when the table or index structure, or the data, changes.

The MS SQL Server family of DBMSs provides tools for monitoring server performance; to understand how they work, one needs to become familiar with the terminology and principles used in performance monitoring.

Performance monitoring begins with establishing a performance baseline. A performance baseline is a set of specific performance metrics collected at the beginning of the DB's operation.

After the baseline is established, the DB administrator regularly collects performance counter readings – performance measurements taken under actual workload. The collected counter information is compared with previously collected data and with the baseline in order to identify trends in performance development.

These actions are important because the MS SQL Server optimizer relies on the collected statistics when building query execution plans.

The resources that are slowing down server performance are identified from the collected data.

MS SQL Server provides a sufficient number of counters that allow you to identify the resources and queries affecting server performance.

The MS SQL Server optimizer uses two main metrics: system response time to user queries and throughput. Response time is a subjective metric, while throughput — the number of transactions per second — is an objective measure of server performance.

The most universal tool for monitoring and analyzing MS SQL Server performance is System Monitor.

When optimizing performance, one typically focuses on the server's peak load. In determining this, it is often useful to artificially simulate user load — the so-called load testing.

A second important tool for performance analysis is the profiler, which allows you to find and log commands that take a long time to execute.

There are several more tools intended for monitoring and analyzing performance in the MS SQL Server family of DBMSs.

Note that query optimization is the responsibility of the DW administrator. The DW designer should have a general understanding of how performance tuning is performed, in order to apply this knowledge when designing DW schemas.

Statistics used by the MS SQL Server query optimizer

DBMSs in the MS SQL Server family have the ability to automatically create and update statistics. This mechanism is enabled by default. In most DB applications, developers and administrators can rely on automatic statistics creation and updating, which provides sufficiently comprehensive and accurate data statistics for the SQL Server query optimizer to choose good execution plans. It is also possible to manage statistics creation and updating manually.

An important point in ensuring high performance of DW and DB applications is the ability to update statistics asynchronously in automatic mode. This helps improve the predictability of query response time in high-performance systems.

The MS SQL Server family of DBMSs offers the following capabilities for working with statistics:

• implicitly create and update statistics — background creation and updating of statistics at a default update frequency (in SELECT, INSERT, DELETE, and UPDATE commands, using a column in a WHERE condition or in a JOIN causes statistics to be created or updated if necessary, provided automatic updating is enabled);
• manually create and update statistics — manual statistics management, with a specified update and deletion frequency ( CREATE STATISTICS, UPDATE STATISTICS, DROP STATISTICS, CREATE INDEX, DROP INDEX );
• manually create statistics in bulk — manual creation of statistics for all columns in all tables of a DB ( sp_createstats );
• manually update all existing statistics — manual update of statistics across the entire DB ( sp_updatestats );
• list statistics objects — view existing statistics objects for a table or DB ( sp_helpstats, catalog views sys.stats, sys.stats_columns );
• display descriptive information about statistics objects — view descriptions of statistics objects ( DBCC SHOW_STATISTICS );
• enable and disable automatic creation and update of statistics — enable/disable automatic creation and updating of statistics for the entire DB or for a specific table or statistics object (options ALTER DATABASE: AUTO_CREATE_STATISTICS and AUTO_UPDATE_STATISTICS; sp_autostats; and options NORECOMPUTE: CREATE STATISTICS and UPDATE STATISTICS );
• enable and disable asynchronous automatic update of statistics — enable/disable automatic, asynchronous statistics updating ( ALTER DATABASE, option AUTO_UPDATE_STATISTICS_ASYNC ).

In addition, SQL Server Management Studio allows you to view and manage statistics objects through a graphical interface; they can be viewed in Object Explorer, in a special folder under each table object.

MS SQL Server implements numerous metrics and mechanisms that affect statistics, allowing the query optimizer to improve its choice of execution plan by analyzing a wider range of queries, or to provide finer-grained control over statistics collection. The following metrics and mechanisms can be highlighted:

• String summary statistics – the frequency distribution of substrings when analyzing character fields. Helps the optimizer better estimate the selectivity of conditions using the LIKE operator;
• Asynchronous auto update statistics – asynchronous, automatic statistics updating, via the AUTO_UPDATE_STATISTICS_ASYNC option of the ALTER DATABASE statement. When this option is enabled, MS SQL Server automatically updates statistics in the background. In this case, the query that triggered the statistics update is not blocked, and the previously accumulated statistics are used instead. This helps provide greater predictability of query response time for certain types of workloads;
• Computed column statistics – statistics on computed columns can be collected manually or automatically;
• Large object support – support for large objects, such as columns of type ntext, text, and image, as well as the newer data types nvarchar(max), varchar(max), and varbinary(max) — these can also now be defined as columns for which statistics are collected;
• Improved statistics loading framework – an improved framework for loaded structure statistics allows the optimizer to obtain statistics on internal mechanisms, making it possible to cover all statistics-related aspects, thereby improving result quality and, accordingly, optimization and performance;
• Increased ability to automatically create statistics on computed columns – the ability to automatically create statistics on computed columns;
• Minimum sample size – the minimum sample size is set at 8 MB when computing data, or equals the size of the table if it is smaller than this size;
• Increased limit on number of statistics – the maximum number of statistics objects, i.e., the number of statistics per column for a single table, has been increased and is now 2000, and another 249 index statistics can be added, bringing the total number of statistics objects per table to 2249;
• Enhanced DBCC SHOW_STATISTICS output – the enhanced capabilities of DBCC SHOW_STATISTICS now allow displaying the names of statistics objects, which helps avoid ambiguity;
• Statistics auto update is now based on column modification counters – automatic statistics updating is now based on column modification counters; changes are tracked at the column level, and automatic statistics updating can be prevented for columns for which insufficient changes have been recorded;
• Statistics on internal tables – statistics on internal tables are collected for tables listed in sys.internal_tables, including XML and full-text indexes, Service Broker queues, and queries against notification tables;
• Single rowset output for DBCC SHOW_STATISTICS – a single rowset report for DBCC SHOW_STATISTICS makes it possible to output a single header, density vector, and histogram for the rowset. This simplifies the development of automated tools for processing the results of DBCC SHOW_STATISTICS execution;
• Statistics on up-to 32 columns – the number of columns in a statistics object has been increased from 16 to 32;
• Statistics on partitioned tables – statistics on table partitions are supported for partitioned tables. Histograms are supported for tables, but not for table partitions;
• Parallel statistics gathering for fullscan – for statistics collected during a full scan, the creation of a single statistics object can be parallelized for both partitioned and ordinary tables;
• Improved recompiles and statistics creation in case of missing statistics – recompilation and statistics creation in the case of missing statistics are now better handled, whether in automatic creation mode or in the case of statistics collection failures. When an execution plan created without statistics is subsequently used, statistics are generated automatically, the query is executed, and the plan is recompiled. The state of missing statistics is not persisted. For more information, refer to the appropriate version of the MS SQL Server technical documentation;
• Improved recompilation logic and statistics update for empty tables – improved recompilation logic and statistics updating for empty tables. A change from 0 to > 0 rows in a table triggers query recompilation and a statistics update;
• Clearer and more consistent display of histograms – histogram displays have become clearer and less inconsistent. Improvements have been made to DBCC SHOW_STATISTICS, as a result of which histograms are now always pre-scaled before being stored in the catalogs;
• Inferred date correlation constraints – inferred date correlation constraints have been added, with which, via the DATE_CORRELATION_OPTIMIZATION database option, SQL Server can be made to take into account correlation information for datetime-type columns between pairs of tables linked by a foreign key. This information is used to be able to determine implied predicates for a small number of queries, and is not used directly to estimate selectivity or estimated cost for the optimizer, so it is not statistics in the strict sense, but is very close to statistics, serving as auxiliary information that generally helps produce a better query plan;
• sp_updatestats – this stored procedure updates only the statistics that require updating, based on information from rowmodctr in the sys.sysindexes system view, thereby eliminating unnecessary updates for unchanged elements. For DBs with a compatibility level of 90 or higher, sp_updatestats uses settings for UPDATE STATISTICS that correspond to automatic mode for any indexes or statistics.

Let us give a few definitions of terms that will be used later on.

statblob object: a statistical Binary Large Object (BLOB), i.e., a large, binary statistics object. This object is stored in the internal representation of the sys.sysobjvalues catalog.

String Summary statistics: a string summary is a form of statistics that describes the frequency distribution of substrings in a record field. It is used to estimate the selectivity of LIKE predicates. It is stored in the statblob for the record field.

sysindexes object: the sys.sysindexes system catalog view, which contains information about tables and indexes.

The Predicate object: a predicate is a condition that evaluates to true or false. Predicates are used in the WHERE clause or in JOIN of database queries.

Selectivity: selectivity is the fraction of rows in the data set produced by a predicate that satisfy that predicate's condition. There are also more complex definitions of selectivity, needed to estimate the number of rows involved in joins, DISTINCT, and other operators. For example, SQL Server 2005 estimates the selectivity of the predicate "Sales.SalesOrderHeader.OrderID = 43659" in the AdventureWorks database as 1/31465 = 0.00003178.

Cardinality estimate: an estimate of the number of elements, which allows the size of the result set to be determined. For example, if table T has 100000 rows and the query contains the selection predicate T.a = 10, and the histogram shows the selectivity of T.a = 10 to be 10%, then the estimated number of elements in the fraction of rows of T that the query must process will be: 10% * 100000, equal to 10000 rows.

The LOB object: a large object, usually of the following types: image, text, ntext, varchar(max), nvarchar(max), varbinary(max).

Statistics collection in MS SQL Server

The optimizer of the MS SQL Server family of DBMSs collects the following collection of table-level statistical information, which is part of the statistics object, and uses it to estimate query cost as well:

• the number of rows in the table or index (the rows field in sys.sysindexes);
• the number of pages occupied by the table or index (the dpages field in sys.sysindexes).

The optimizer of the MS SQL Server family of DBMSs collects the following statistics on table columns and stores them in a statistics object (statblob):

• the time when the statistical data was collected;
• the number of rows used to build the histogram, and density information (described below);
• the average key length;
• the histogram of the individual column, including step numbers;
• a string summary, if the field contains character data. The output of DBCC SHOW_STATISTICS contains a String Index column, which takes the value YES if the statistics object contains a string summary.

A histogram is a set of values of a given field, limited to 200 values. All values of the field, or a sample of them, are sorted, and this ordered sequence can be split into no more than 199 intervals in such a way that the most statistically significant information is captured. As a rule, these intervals have different sizes. Below are the values, or information sufficient to obtain such information, that is stored for each step in the histogram.

• RANGE_HI_KEY — the key value that marks the upper boundary of a histogram step.
• RANGE_ROWS — the number of rows within the range (they must have key values less than their own RANGE_HI_KEY, but greater than the lower RANGE_HI_KEY value of the previous range).
• EQ_ROWS — the number of rows exactly equal to RANGE_HI_KEY.
• AVG_RANGE_ROWS — the average number of rows with distinct values within the range.
• DISTINCT_RANGE_ROWS — the number of distinct key values within this range (not including the key value of the previous range's RANGE_HI_KEY).

Histograms are built only on a single column, the one that is first in the statistics object's key column set. The histogram is built from a sorted set of column values in three steps.

продолжение следует...

Продолжение:

Часть 1 Tuning the performance of data warehouse queries
Часть 2 Analyzing queries to improve their execution speed - Tuning the