Patent Description:
Frequently, the same database command can be executed multiple ways, each of which produces the same correct results. Each of the various ways a database command may be executed has a corresponding "execution plan". The database component that selects which execution plan to execute for a given query is referred to as the "optimizer".

While all execution plans for a query should produce the same correct results, the time and resources required to execute the execution plans of the same query may vary significantly. Thus, selecting the best execution plan for a query can have a significant effect on the overall performance of a database system.

When selecting among execution plans for a query, the optimizer takes into account statistics that are maintained by the database server. Based on the statistics, the database server may, for example, determine whether using one join technique will be more efficient than another, and whether accessing information from a particular index would be more efficient than accessing the same information directly from the underlying tables. Because the execution plan decision is made based on the statistics, the more accurate the statistics, the greater the likelihood that the optimizer will select the best execution plan.

Statistics that accurately reflect the current state of the database are referred to as "real-time" statistics. Unfortunately, real-time statistics are not always available to the optimizer because maintaining real-time statistics can impose a significant overhead to database command processing. Users typically have the option of executing a statistics-gathering processes to "manually" gather the real-time statistics needed by the optimizer. However, the overhead incurred by such manual statistics gathering operations can degrade performance in a manner that outweighs the performance benefit of choosing an execution plan based on real-time statistics.

To avoid such overhead, optimizers often have to select query plans based on "stale" statistics that do not reflect the current state of the database. The more "stale" the statistics, the less accurate the statistics tend to be, and the less accurate the statistics, the more likely the optimizer will select a sub-optimal query plan. For example, statistics that reflect the state of a table ten minutes ago will tend to be more accurate (and result in better query plan selection) than statistics that reflect the state of the same table ten days ago.

Numerous approaches for efficiently gathering statistics within a database system have been developed. Some such approaches are described, for example, in <CIT>, <CIT>, <CIT>, and <CIT>. One approach for gathering statistics involves waiting for a "quiet period" during which that database system is not executing Database Manipulation Language (DML) commands that change the contents of the database. During the quiet period, the database server can execute the statistics-gathering processes to refresh all of the statistics needed by the optimizer. Those statistics are then used by the optimizer until new statistics are gathered during the next quiet period.

Such "quiet periods" are also referred to as "maintenance windows", because the quiet periods are used to perform maintenance operations that would slow down user applications if not executed during the quiet period. Often, maintenance windows are strictly enforced, so that any maintenance operation (such as statistics gathering) that does not complete within one maintenance window is stalled until the next maintenance window.

When the "maintenance window" technique is used, the accuracy of the currentlyavailable statistics hinges on how much time has elapsed since the most recent maintenance window. Typically, the "maintenance window" during which statistics are gathered is overnight. Consequently, in the early morning hours, the statistics used by the optimizer of a database system may be relatively accurate. On the other hand, in the evening hours, the statistics used by the optimizer may be relatively inaccurate, since the statistics do not account for changes made by the DML commands executed during that day. Statistics are even less accurate if the statistics-gathering process is unable to finish during a single maintenance window.

The publication by <NPL>" explains how to tune Oracle SQL. A topic discussed in this publication is costs-based optimization, which refers to the overall process of choosing the most efficient means of executing a SQL statement. The database optimizes each SQL statement based on statistics collected about the actual data being accessed. The optimizer uses the number of rows, the size of the data set, and other factors to generate possible execution plans, assigning a numeric cost to each plan. The database uses the plan with the lowest cost. The publication further discloses the use of incremental statistics, which enable the database to avoid full table scans by scanning only changed partitions. When incremental statistics maintenance is enabled, the database (i) gathers statistics and creates synopses for changed partitions only, (ii) merges partition-level synopses into a global synopsis automatically, and (iii) derives global statistics automatically from the partition-level statistics and global synopses.

<CIT> discloses a data warehousing system that maintains large tables comprising a significant quantity of data. Relatively small amounts of data are added frequently. A query optimizer relies on reasonably accurate statistics for producing optimized query execution plans. However, fully recalculating statistics for an entire fact table is expensive in terms of time and computing resources. It is proposed to update the optimizer statistics by utilizing history information to locate blocks added following the most recent update to the query optimizer statistics. For example, to update a statistic of a minimum value or a maximum value among all values in a particular column, a scan of all newly added blocks is performed to calculate a min/max value for data that has been loaded since the last time statistics were fully recalculated using all available rows. These values are compared to the previous min/max values for the column, and the min/max statistics are adjusted accordingly.

<CIT> discloses counter based statistics for selecting a database query plan. <CIT> discloses a machine learning inspired solution.

Techniques are described herein for gathering statistics in a database system. The techniques involve gathering some statistics using an "on-the-fly" technique, some statistics through a "high-frequency" technique, and yet other statistics using an "prediction" technique. The technique used to gather each type of statistic is based, at least in part, on the overhead required to gather the statistic. For example, low-overhead statistics may be gathered "on-the-fly", while statistics whose gathering incurs greater overhead may be gathered using the high-frequency technique. High-overhead statistics may be predicted based on other statistics that are gathered on-the-fly. Further, these techniques may be used in conjunction with other techniques, such as executing the statistics-gathering processes during maintenance windows.

The on-the-fly technique involves storing statistics information reflects changes made by DML operations at the time the DML changes are performed, and as part of the same process that performs the DML changes. According to one embodiment, rather than updating the on-disk copy of the statistics (which is typically found in a dictionary table of the database) to reflect the statistic changes caused by a DML operation, "delta statistics" are stored in an in-memory statistics repository.

In one embodiment, the in-memory delta statistics that are generated in this manner are periodically flushed to disk reserved for delta statistic. When the optimizer needs statistics to help select which competing query plan to execute for a given query, the optimizer may call an API that retrieves the needed delta statistics from the in-memory repository, the corresponding delta statistics from the dictionary table, the corresponding base statistics and merges them all to create "updated statistics" that are then used by the optimizer to decide among execution plans.

Maintaining on-the-fly statistics in this memory first provides "fresh" statistics without incurring the overhead that would be required for each DML operation to update the on-disk statistics in the dictionary table in real-time. Such overhead would be significant, since any number of concurrently executing DML operations would have to contend to obtain a write lock on the relevant statistics in the dictionary table. Because of the freshness of the updated statistics, the optimizer is able to more accurately select the most efficient query plans. The stats are flushed from the memory to the disk in a background job. Therefore the overhead is not visible to foreground applications.

In one embodiment, the delta statistics are also stored separately on disk from the base statistics. This provides an isolation between the two statistics so that we can easily turn on and turn off usage of delta statistics. This is not only beneficial for testing but also provides a control in the rare case where delta statistics are hurting query performance.

According to one embodiment, some statistics that are not maintained using the on-the-fly technique are gathered using a "high-frequency" gathering technique. According to the high-frequency gathering technique, the database system does not wait for a maintenance window to gather statistics. Instead, the database server periodically initiates a background statistics-gathering process. The background statistics-gathering process is able to gather and store statistics regardless of what other processes are executing in the foreground. In one embodiment, the statistics-gathering process is configured to begin processing only if no other instance of the statistics-gathering process is active. To reduce the negative effect the statistics-gathering process has on performance of concurrently executing foreground processes, the amount of CPU-cycles allocated to the statistics-gathering process is capped (e.g. at no more than <NUM>% of available CPU-cycles).

Predicted statistics are statistics that are predicted from historical information. For example, the database server may store a history of timestamps, row counts, and number of distinct values (NDV) for a column. If the historical data indicates that the NDV of the column tends to increase by <NUM> for every <NUM> rows added to the table, then the database server may predict, based on on-the-fly statistics that indicate that <NUM> rows have been added to the table, that the NDV count for the column is <NUM> more than the NDV values stored at the latest-refresh-time.

The prediction models are built on the columns that have significant NDV change in the history, only for which there would be value in prediction because the column NDV is prone to change over time.

The prediction model is automatically maintained in the background, either in the maintenance windows or the high frequency statistics processes. New models are built and existing models are refreshed in the model gathering process. A model can be enabled or disabled depending on whether its quality satisfies our metric.

Before trying to refresh an existing model, a check is made to determine if there has been enough new statistics points gathered since last model creation time. For models that no longer satisfy the quality metric, their usage is disabled instead of dropping them. In this way, the system avoids repeatedly building the same model on the same history data of a column, which is a waste.

Once a model is built, the system periodically extrapolates the NDV with on-the-fly statistics and store the extrapolated result on disk. During query compilation time, the extrapolated NDV is used with other on-the-fly statistics. In other words, the extrapolation is done offline and does not incur overhead during query compilation time.

A database system may maintain statistics at various levels. For example, a database system may maintain table-level statistics, column-level statistics, and index-level statistics. Table-level statistics include, for example, the number of rows in a table, and the number of blocks in a table.

Column-level statistics include, for example, the lowest value in a column (MIN), the highest value in the column (MAX), the average column width (in bytes), the cardinality of the column, and a histogram of values in the column.

An index is implemented using a tree structure (e.g. a B-tree or B+tree, etc.), and index-level statistics include: number of leaf nodes in the index, the depth of the index tree, the total size of index, the number of distinct keys, a clustering factor, etc. Other types of statistics may be used for other types of indexes, which are exemplary embodiments that do not fall within the scope of the invention.

As mentioned above, gathering on-the-fly statistics involves storing, at the time the DML changes are performed, statistics information that reflects changes made by DML operations. In one embodiment, the statistics information is stored in an in-memory statistics repository by the processes that are performing the DML operations that affect the statistics. Referring to <FIG>, it is a block diagram of a database system, according to an embodiment. The database system includes a database server <NUM> that has volatile memory <NUM>. Within the volatile memory <NUM>, the database server <NUM> maintains an in-memory statistics repository <NUM> for those statistics that are gathered on-the-fly.

The database server <NUM> is operatively coupled to one or more persistent storage devices, which are collectively represented by disk <NUM>. The storage devices persistently store a database <NUM> that is managed by database server <NUM>. Database <NUM> includes a table <NUM> that stores user data and a dictionary table <NUM> that persistently stores statistics associated with database <NUM>, including table statistics, column statistics and index statistics. For example, dictionary table <NUM> may store table statistics for table <NUM>, column statistics for each column in table <NUM>, and index statistics for an index <NUM> that is built on one or more columns of table <NUM>.

Because the on-the-fly statistics information is stored in response to the commit of the DML operations that affect the statistics, the statistics information in the in-memory statistics repository <NUM> is very fresh. Further, since the statistics information is stored in in-memory statistics repository <NUM> rather than committed to the dictionary table <NUM>, the overhead associated with maintaining the statistics is significantly reduced. Further, unlike the statistics in dictionary table <NUM>, which are typically maintained in a table-like structure, the statistics stored in in-memory statistics repository <NUM> may be stored in structures that optimize access efficiency, such as linked lists, hash tables, or a combination thereof.

According to one embodiment, on-the-fly statistics are maintained during data change operations, such as INSERT, DELETE, UPDATE and MERGE, regardless of whether the operations affect a single row or a large number of rows, and regardless of whether the operations use conventional or direct path insertion methods. (Direct path insertion techniques typically require a lock on the entire table into which rows are being inserted, and inserted rows are stored on newly allocated blocks, rather than writing to any already-allocated blocks of the table. ) As mentioned above, the maintenance of on-the-fly statistics is performed by the process that is performing the data change operation that affects the statistics.

Currently on-the-fly statistics are maintained only for the cheapest statistics. According to one embodiment, the database server maintains on-the-fly statistics for at least: table row count, table block count, column minimum, and column maximum values, number of nulls, average column length of columns. This is only an example of the statistics for which a database server may maintain on-the-fly statistics, and the techniques described herein are not limited to any particular set of on-the-fly statistics. Nevertheless, the framework, i.e., the in-memory repository, the tables for delta statistics on tables, the flushing mechanism are all general for other types of statistics.

For the purpose of explanation, the maintenance of on-the-fly statistics shall be explained using an example in which a DML command inserts ten rows into a table <NUM> that has three columns c1, c2 and c3. Such an insert operation can affect statistics for the table <NUM>, the columns, and any indexes (e.g. index <NUM>) associated with table <NUM>, as shall be explained hereafter. It shall be further assumed that dictionary table <NUM> contains statistics that are accurate as of a most recent execution of the corresponding statistic-gathering process. The commit time of the most recent execution of a statistics-gathering process shall be referred to herein as the "latest-refresh-time". Often, the latest-refresh-time will be during the most recent maintenance window.

One table-level statistic affected by the insertion of ten rows into table <NUM> is the "row count" of table <NUM>. According to one embodiment, the database server <NUM> performs on-the-fly tracking of the DML changes (inserts, deletes, updates) that happen on each table since the latest-refresh-time. For example, immediately after the latest-refresh-time, the dictionary table <NUM> may indicate that table <NUM> as <NUM> rows, and in-memory statistics repository <NUM> may include a "delta" value of <NUM>, indicating that no rows have been added or deleted to table <NUM> since the latest-refresh-time.

In response to the insertion of the ten rows into table <NUM>, the database server <NUM> may update the in-memory statistics repository <NUM> by incrementing the delta row count value by <NUM> to indicate that ten rows have been added since the latest-refresh-time. In one embodiment, access to each statistic within the in-memory statistics repository <NUM> is governed by a latch. Thus, to update the in-memory statistics, the DML process would obtain a latch on the delta row count value for table <NUM> within in-memory statistics repository <NUM>, increment the delta row count value by <NUM>, and then release the latch on the delta row count value.

When a delta row count change is maintained within in-memory statistics repository <NUM> in this manner, the real-time row count can simply be computed by combining the DML changes (the delta row count from in-memory statistics repository <NUM>) and the old row count stored in the dictionary table <NUM> ("tab$. row_count): <MAT>.

On-the-fly delta statistics are initially maintained in in-memory statistics repository <NUM>. In one embodiment, the delta-statistics in the in-memory statistics repository <NUM> are periodically flushed to disk <NUM> via a background flush process (e.g. every <NUM> minutes). The flushed-to-disk statistics are illustrated in <FIG> as flushed-statistics <NUM>. After the flush, the delta statistics in the delta row count in in-memory statistics repository <NUM> may be reset to zero. In such an embodiment, to get the up-to-date row count, the database server <NUM> combines the information from three sources: <MAT>.

For example, assume that the row count stored in the dictionary table is <NUM>. That is, as of the latest-refresh-time, table <NUM> had <NUM> rows. Assume that, after the latest-refresh-time, <NUM> rows were inserted and <NUM> rows were deleted. A record of the <NUM> insertions and <NUM> deletions (or a delta row count of <NUM>) would be maintained in the in-memory statistics repository <NUM>. At that point, the information from the in-memory statistics repository <NUM> may be written to disk <NUM> as flushed stats <NUM>. In response to the in-memory statistics being flushed to disk, the delta row count statistics in the in-memory statistics repository <NUM> are reset. Then, additional DML operations may result in <NUM> more inserted rows, and <NUM> more row deletions (a new delta row count of <NUM>). At that point in time:.

By merging these statistics, the database server <NUM> may produce an on-the-fly row count of <NUM>+(<NUM>-<NUM>)+(<NUM>-<NUM>) = <NUM>. The optimizer may then use the on-the-fly row count of <NUM> as a basis for selecting among execution plans for a query.

According to one embodiment, a copy of the flushed delta row count and a copy of the dictionary table <NUM> row count may be cached in volatile memory <NUM>. In such an embodiment, the generation of the real-time row count is faster because all three of the components thereof are available from the volatile memory <NUM>.

In yet another embodiment, the database server does not maintain a delta row count in volatile memory. Instead, the row count within the dictionary table <NUM> is updated every time a DML operation that affects the row count is committed. In such an embodiment, the dictionary table <NUM> will always reflect an updated row count. However, the DML operations will have to contend for write permission to update the row count within table <NUM>.

In a clustered database system that includes multiple database servers, each database server may maintain its own delta row count in its volatile memory. In such clustered systems, the database servers may periodically merge and synchronize their in-memory delta row count values.

For the purpose of explanation, an embodiment has been described in which the delta statistics are "reset" in volatile memory after being flushed to disk. However, in an alternative embodiment, flushing the statistics of a table to disk allows the volatile memory to be reused for other statistics. Thus, after a flush to disk of the delta statistics of table <NUM>, the in-memory statistics repository <NUM> may no longer have any delta statistics for table <NUM>. New delta statistics for table <NUM> are then added to in-memory statistics repository <NUM> if/when another DML process performs an action that affects the statistics of table <NUM>. Freeing up volatile memory after statistics are flushed is desirable because there may be long periods during which no DML affects a table, and it would be wasteful to continue to consume volatile memory for that table's statistics during those periods.

In the example given above, computing an on-the-fly version of the row count involved merging the delta row count from volatile memory <NUM>, the delta row count flushed to disk (e.g. in flushed statistics <NUM>), and the row count from the dictionary table <NUM>. However, merging statistics also occurs to combine the statistics from different DML processes.

For example, within a single instance of a database server, multiple DML process may be executing concurrently, each of which is performing insertions that affect the row count of table <NUM>, and the MIN/MAX values of the columns of table <NUM>. In one embodiment, each concurrent DML process maintains its own delta statistics and, upon committing, causes those statistics to be merged into server-wide delta statistics maintained in-memory statistics repository <NUM>. As mentioned above, access to the server-wide statistics maintained in the in-memory statistics repository <NUM> may be governed by latches.

Further, multiple database server instances may be executing DML operations that affect the same statistics. In one embodiment, each of those database server instances maintains its own server-wide statistics in its respective volatile memory, and periodically merges its server-wide statistics with the server-wide statistics of all other database server instances. The merger of the server-wide statistics may be performed, for example, by flushing each server's server-wide statistics to disk <NUM>, and then merging the statistics into dictionary table <NUM>. In one embodiment, a lock is used to serialize write access to each of the statistics maintained in dictionary table <NUM>.

The way that statistic values are merged is based on the statistic in question. For example, merging the delta MIN values of a column (obtained from multiple DML processes in a server, or server-wide delta MIN values from multiple server instances) is performed by selecting the minimum of the delta MIN values. Similarly, merging the delta MAX values of a column is performed by selecting the maximum of the delta MAX values. On the other hand, merging the delta row count statistics of a table (obtained from multiple DML processes in a server, or server-wide delta row counts from multiple server instances) involves summing the delta row count statistics.

Another table-level statistic for which database server <NUM> may perform on-the-fly tracking is the block count of table <NUM>. On disk <NUM>, the data for table <NUM> is stored in segments, and every segment has an associated extent map that records the total number of blocks consumed by the table. The extent map is changed as part of the DML process that performs the changes that cause new extents to be added to a table. Consequently, to obtain an on-the-fly block count of table <NUM>, the database server <NUM> simply reads the block count from the extent map of table <NUM> before optimizer consumes this information.

Columns-level statistics include minimum value, maximum value, number of distinct values (NDV), number of nulls, average column length, and histogram. These are much harder to maintain on-the-fly, than a table's row count and block count. However, reducing the staleness of such statistics is important, because significant errors may occur if the optimizer uses stale column-level statistics from dictionary table <NUM>.

For example, consider the scenario where the optimizer is determining an execution plan for the query "SELECT name FROM emp WHERE age > <NUM>". Assume that the actual MAX value in the age column of table emp is <NUM>, but the stale MAX value recorded in dictionary table <NUM> is <NUM>. This scenario may occur, for example, if a row with age=<NUM> has been inserted since the latest-refresh-time. When the optimizer uses the stale MAX value of <NUM>, the optimizer may conclude that no rows will satisfy the condition "age > <NUM>", and based on this erroneous conclusion, the performance of processing the query may suffer, due to use of inaccurate statistics.

To avoid errors caused by the optimizer's use of stale column-level statistics, on-the-fly column-level statistics are computed for the minimum and maximum value of columns, according to an embodiment. Therefore, for those tables whose statistics have not been recently refreshed, the optimizer has access to up-to-date minimum and maximum values of each column. Among other things, access to real-time minimum and maximum values of each column helps the optimizer accurately identify and handle out-of-range queries.

Similar to on-the-fly table statistics tracking, on-the-fly MIN/MAX tracking involves performing extra work whenever a DML operation happens. In one embodiment, the work performed depends on whether the DML operation is performing inserts, deletes, or both (where updates are treated as deletes followed by inserts).

For on-the-fly MIN/MAX tracking for insert operations, a "delta" minimum value, and a "delta" maximum value for each column are maintained within in-memory statistics repository <NUM>. After performing a statistics-gathering operation (e.g. during a maintenance window) for the MIN/MAX values of columns, the dictionary table <NUM> is updated with the MIN/MAX for each column, and delta MIN/MAX values in in-memory statistics repository <NUM> are initialized. According to one embodiment, the delta MIN/MAX are initialized to ZERO, not the MIN/MAX values stored in the dictionary table, and the in-memory repository only tracks the MIN/MAX of the delta data change performed since the latest-refresh-time.

In an alternative embodiment, the delta MIN/MAX are initialized to the MIN/MAX values stored in the dictionary table. For example, assume that table <NUM> has the columns "age" and "salary". Assume further that dictionary table <NUM> indicates the MIN/MAX values for "age" are <NUM>/<NUM>, and the MIN/MAX values for "salary" are <NUM>,<NUM>/<NUM>,<NUM>,<NUM>. Under these circumstances, the delta MIN/MAX values stored in in-memory statistics repository <NUM> are initialized to <NUM>/<NUM> for the age column, and <NUM>,<NUM>/<NUM>,<NUM>,<NUM> for the salary column.

Assume that immediately after the latest-refresh-time at which those statistics were stored in dictionary table <NUM>, a DML operation is executed in which ten rows are inserted into table <NUM>. The process that performs the DML also performs statistics maintenance by:.

Thus, assuming that the highest age inserted in the <NUM> inserted rows is <NUM>, the DML performing the insert operations would update the delta age-maximum value stored in in-memory statistics repository <NUM> to <NUM> because <NUM> is greater than the current delta age-maximum value of <NUM>.

Similarly, if the lowest age inserted in the <NUM> inserted rows is <NUM>, then the DML operation performing the inserts would update the delta age-minimum value stored in in-memory statistics repository <NUM> to <NUM> because it is less than the current delta age-maximum value of <NUM>. The DML operation that performs the inserts would also update the delta salary MIN/MAX values in a similar fashion.

Since in-memory statistics repository only has the delta MIN/MAX, the optimizer will compute the freshest statistics on-the-fly by merging in-memory MIN/MAX and the dictionary table and use these statistics to process query.

Of course, on-the-fly maintenance of column-level statistics, such as MIN and MAX of each column, takes time and memory/disk space. Further, because the statistics-gathering overhead is performed by the foreground DML process that affects the statistics, the statistics-gathering overhead will affect the performance of the user application and might degrade the user experience. According to one embodiment, to minimize the work done in the foreground, techniques are provided that implement a sample-based live MIN/MAX, instead of an exact MIN/MAX. That is, to reduce the overhead required to maintain on-the-fly MIN/MAX column statistics, only a subset of the inserted rows are considered when determining the MIN/MAX values inserted during a DML operation.

For example, assume that a DML operation inserts <NUM> rows. Without sampling, the values inserted in each column by each of the <NUM> rows would need to be analyzed to determine the MIN/MAX values that are inserted by the DML operation into each of the columns. According to one embodiment, rather than analyze the values inserted in each of the <NUM> rows, the database server <NUM> takes a random sampling of the <NUM> rows. The random sampling may, for example, select only <NUM> of the <NUM>, rows. Determining the MIN/MAX values for each column of the <NUM> rows that belong to the sampling will incur significantly less overhead than would be required to determine the MIN/MAX values for all <NUM> inserted rows.

Referring to <FIG>, it is a flowchart that illustrate steps performed by database server <NUM> to maintain on-the-fly per-column MIN/MAX statistics, according to an embodiment. At step <NUM>, the database server receives a DML command that inserts rows (either through INSERT operations, or as part of UPDATE operations). At step <NUM>, a sample is created from the rows to be inserted during the DML command. For example, the sample may be created by randomly selection one of every <NUM> rows to be inserted by the DML command. The actual sampling technique may vary, and the statistics maintenance techniques describe herein are not limited to any particular sampling technique.

At step <NUM>, the database server <NUM> determines per-column sample MIN/MAX values for the rows in the sample. Finally, at step <NUM>, the sample MIN/MAX values derived in this manner are combined with the delta MIN/MAX values stored in in-memory statistics repository <NUM>. In one embodiment, the steps illustrated in <FIG> are performed by the same process that is performing the DML operation that inserts values. However, because MIN/MAX values are only determined for the sample, the overhead that the process incurs to perform statistics maintenance is significantly less that if all inserted rows were processed.

When on-the-fly delta statistics are generated based on a sampling, rather than all inserted values, the resulting statistics may be inaccurate. For example, assume that the current delta MAX age is <NUM>, the MAX age in the sample is <NUM>, and the MAX age in all inserted rows is <NUM>. Under these circumstances, the delta MAX age would be updated to <NUM>, even though a row where age=<NUM> was inserted in to the age column.

Another circumstance that may lead to inexact statistics is the use of insert-only delta statistics. Insert-only delta statistics are delta statistics that only take into account the effect that insertions have on statistics, even though the DML operations may involve more than just insertions.

In one embodiment, rather than incur the extra overhead to ensure that the delta MIN/MAX statistics are accurate after updates and/or deletes, the delta statistics for MIN/MAX are allowed to become inaccurate. That is, the delta MIN/MAX statistics are only updated to account only for the inserts made by DML operations. Even though the insert-only delta MIN/MAX statistics may be inaccurate, the insert-only delta MIN/MAX statistics will tend to be more accurate than the statistics stored in dictionary table <NUM>, which do not take into account any changes since the latest-refresh-time. Further, for columns in which values are necessarily increasing, such as date columns for a sales table, only taking into account the inserted values may still lead to an accurate MAX statistic.

Unlike on-the-fly statistics gathering, high-frequency statistics gathering does not cause the same processes that are performing the DML operations that affect statistics to perform any additional work to maintain or update the statistics. Instead, high-frequency statistics gathering involves executing a statistics-gathering process in the background while allowing DML operations to continue to execute in foreground processes.

Because the statistics-gathering process is executing in the background, the CPU resources that are made available to the statistics-gathering process may be limited. For example, in one embodiment, the statistics-gathering process is allowed to consume no more than <NUM>% of the CPU clock cycles available to database server <NUM>.

The statistics-gathering process is considered "high-frequency" because the statistics-gathering process is initiated much more frequently than the occurrence of "maintenance windows". For example, in some systems, a maintenance window may occur only once every <NUM> hours. In contrast, a high-frequency statistics-gathering process may be started every <NUM> minutes.

The operations performed by statistics-gathering processes may take longer to execute than the interval that triggers the execution of the statistics-gathering processes. For example, a high-frequency statistics-gathering process may take <NUM> minutes to complete, even though the interval for executing the process if <NUM> minutes. Therefore, according to one embodiment, the database server <NUM> is designed to only start a new statistics-gathering process for a particular statistic or set of statistics if no other instance of the statistics-gathering process is active for that same statistic or set of statistics.

For example, if a MIN/MAX statistics-gathering process is initiated for a particular table at <NUM>:00pm, but has not finished by <NUM>:<NUM>, no new MIN/MAX statistics-gathering process for that particular table is initiated <NUM>:<NUM>. Instead, the currently-active MIN/MAX statistics-gathering process is allowed to continue without having to compete for resources with other statistics-gathering processes associated with the same column MIN/MAX statistics.

In the example given above, high-frequency statistics are gathered at fixed time intervals. However, gathering statistics at fixed time intervals may be too frequent in some cases, and not frequent enough in other cases. If gathered too frequently, then the overhead of statistics gathering affects the performance of the system. If not gathered frequently enough, then the optimizer does not have fresh statistics to make the optimal execution plan selections.

It is expected that the number of DMLs that a table will experience is drastically increased during the ramp-up stage (when a table is initially populated, as during an initial migration of a table) and gradually becomes less and less active. When it is in ramp-up stage, statistics should be gathered very often to keep up with the data change. The same frequency will not be applicable when the size of the table reaches a certain order of magnitude.

Therefore, according to one embodiment, for high-frequency background statistics collection, instead of gathering statistics at a fixed frequency, an adaptive frequency is used which depends on the real workload. Only if the stale statistics of the table become critical is it highly possible that the optimizer will be misled by the statistics. Consequently, in one embodiment, background statistics collection is invoked only under those circumstances. Thus, in one embodiment, statistics maintenance is a demand-driven operation that needs to take action in both foreground and background, as shall be described in detail hereafter.

According to one embodiment, the database server <NUM> maintains a queue for statistics-gathering. Each entry in the statistics-gathering queue identifies a database structure, such as a table, partition, or index, for which it is time to gather statistics. The condition that triggers the insertion of an entry in the queue for statistics gathering is that the staleness of a database object exceeds a staleness threshold (e.g. <NUM>%).

In one embodiment, as a foreground action, the database server <NUM> detects that a table exceeds the percentage staleness threshold and puts an entry for the target table into the queue waiting for background statistics collection. In a clustered database environment, the DML monitoring information in the volatile memory of each server node may not be sufficient to determine the staleness. Consequently, in such an embodiment, the statistics information in volatile memory of each server node is flushed to disk to make the staleness determination.

According to one embodiment, the database server creates a job that periodically wakes up to flush the DML monitoring info to disk, for example, every <NUM> minute. While flushing to disk the statistics of a particular table, the stale percentage of the particular table is computed. If the threshold is exceeded, the database server puts an entry for the particular table, an entry for the table is placed into a waiting queue.

In an alternative embodiment, a mechanism continuously checks whether the target queue is empty or not. If the queue is empty, the DML monitoring info for the various database objects that have experienced DML is flushed to disk. While flushing to disk the statistics of a particular table, the stale percentage of the particular table is computed. If the threshold is exceeded, the database server <NUM> puts an entry for the particular table into a queue for statistics-gathering.

In yet another embodiment, during the commit of a DML operation, the database server <NUM> computes the staleness on the fly to add objects involved in the current transaction to the queue for statistics gathering if the staleness of those objects exceeds the <NUM>% threshold. The benefit of the DML-based staleness determination is that it is fully driftdriven, not time-driven. However, since the DML is executed in the foreground, the staleness determination is also executed in the foreground. As an action taken in the foreground, its overhead should be thoroughly minimized to reduce the effect on user applications.

The queue for statistics-gathering may be shared by multiple distinct database server instances. According to one embodiment, every database server instance may add entries to the queue, and every database server instance may process entries that are at the head of the queue.

To process an entry that is at the head of the queue, a database server instance reads the database object identified in the entry, marks the entry as "in progress", and initiates the appropriate statistics-gathering operations to gather statistics for that database object. Upon completion of the statistics-gathering operations, the database server instance removes the entry from the queue (or marks the entry as "done") and updates the statistics for the database object in the dictionary table <NUM>.

As stated earlier, it may be too expensive to maintain some statistics in real time. According to one embodiment, a predictive approach is used to predict approximate real-time values of those statistics.

For example, in one embodiment, the number of distinct values (NDV) of columns is not maintained in real time because to find out whether the value of a column in the row being inserted is new (the NDV should be incremented by <NUM>) or old (the NDV remain the same) the value would have to be compared to the values of the column in the rows already present in the table. However, in many cases, the number of distinct values correlates with other types of statistics, e.g. count of rows, timestamps. If the correlated statistics are maintained in real-time, they can be used to derive the current NDV.

According to one embodiment, the database server generates on-the-fly predictions of certain statistics as follows:.

For example, assume that timestamps and row counts and NDVs for a table have been recorded for N points in the past (e.g. each of the last <NUM> days). This historic information can be used to create a prediction model that takes on-the-fly gathered statistics (e.g. timestamps, row counts) as inputs and outputs predicted NDV values. The prediction mechanism may be, for example, a machine learning engine. In a machine learning engine embodiment, the machine learning engine may be trained by feeding the machine learning engine the N records of (timestamp, row count), along with the corresponding previouslyrecorded NDV values.

Once the machine learning engine is trained in this manner, the database server <NUM> may cause the machine learning engine to generate an on-the-fly prediction of the NDV for the column by (a) gathering on-the-fly values for timestamp and table row count using the techniques described above, and (b) feeding those values to the trained machine learning system. While not guaranteed to be exact, the NDV value generated in this manner may be significantly more accurate than the stale NDV stored in the dictionary table <NUM>, particularly if many DMLs have operated on the column since the latest-refresh-time of the NDV statistic for that column.

As explained above, different statistics present different statistics-gathering challenges. Some statistics, for example, can be maintained with significantly less overhead than other statistics. Further, some statistics may be more accurately predicted than other statistics. Therefore, according to one embodiment, a database system is provided with different statistics-gathering approaches for different statistics.

Referring to <FIG>, it is a flowchart that illustrates how statistics are maintained by a database that implements a multi-tiered statistics gathering approach, according to an embodiment. Step <NUM> indicates that the way in which a statistic is gather is based on the type of statistic. For statistics, such as table row count, whose gathering incurs relatively small overhead, on-the-fly statistics gathering is performed, as illustrated at step <NUM>. As explained at step <NUM>, during on-the-fly statistics gathering, the process that performs the DML that affects the statistics also performs the operations for statistics gathering. For table row count, for example, the operation may involve updating an in-memory delta row count based on how many rows were inserted by the DML in question.

For statistics that require more overhead, high-frequency background statistics-gathering operations may be performed (step <NUM>). As indicated in step <NUM>, the background processes that perform the high-frequency statistics gathering may be initiated periodically, or based on the staleness of the corresponding database objects. In the latter case, adaptive-frequency may involve determining a degree of statistics staleness for each database object. For those that exceed a specified degree of staleness, an entry is added to a queue for statistics gathering. Background processes may read the record at the head of the queue, and gather the statistics for the database object associated with the entry.

Finally, for statistics that require significant overhead to gather on-the-fly, but that may be predicted with reasonable accuracy based on other statistics, statistics prediction may be used (step <NUM>). As indicated in step <NUM>, generating an on-the-fly prediction of a statistic may involve feeding on-the-fly values of predictor statistics to a trained machine learning engine. Based on the on-the-fly values of the predictor statistics, the machine learning engine outputs a predicted value for the predicted statistic. For example, a trained machine learning engine may output an NDV value for a column based on the current row count and MIN/MAX values for the column.

The complementary relationship of those three statistics maintenance techniques is as follows:.

The term "cloud computing" is generally used herein to describe a computing model which enables on-demand access to a shared pool of computing resources, such as computer networks, servers, software applications, and services, and which allows for rapid provisioning and release of resources with minimal management effort or service provider interaction.

A cloud computing environment (sometimes referred to as a cloud environment, or a cloud) can be implemented in a variety of different ways to best suit different requirements. For example, in a public cloud environment, the underlying computing infrastructure is owned by an organization that makes its cloud services available to other organizations or to the general public. In contrast, a private cloud environment is generally intended solely for use by, or within, a single organization. A community cloud is intended to be shared by several organizations within a community; while a hybrid cloud comprises two or more types of cloud (e.g., private, community, or public) that are bound together by data and application portability.

Generally, a cloud computing model enables some of those responsibilities which previously may have been provided by an organization's own information technology department, to instead be delivered as service layers within a cloud environment, for use by consumers (either within or external to the organization, according to the cloud's public/private nature). Depending on the particular implementation, the precise definition of components or features provided by or within each cloud service layer can vary, but common examples include: Software as a Service (SaaS), in which consumers use software applications that are running upon a cloud infrastructure, while a SaaS provider manages or controls the underlying cloud infrastructure and applications. Platform as a Service (PaaS), in which consumers can use software programming languages and development tools supported by a PaaS provider to develop, deploy, and otherwise control their own applications, while the PaaS provider manages or controls other aspects of the cloud environment (i.e., everything below the run-time execution environment). Infrastructure as a Service (IaaS), in which consumers can deploy and run arbitrary software applications, and/or provision processing, storage, networks, and other fundamental computing resources, while an IaaS provider manages or controls the underlying physical cloud infrastructure (i.e., everything below the operating system layer). Database as a Service (DBaaS) in which consumers use a database server or Database Management System that is running upon a cloud infrastructure, while a DbaaS provider manages or controls the underlying cloud infrastructure, applications, and servers, including one or more database servers.

When the database server requires statistics (for example, to choose among competing execution plans of a query), the database server may retrieve the statistics in a variety of ways. For example, on-the-fly delta statistics may be periodically merged into the dictionary table, and the database server may be designed to always obtain statistics from the dictionary table. On the other hand, the database server may be designed to check in-memory statistics repository <NUM> for more recently generated on-the-fly statistics, and revert to dictionary table <NUM> only when such statistics are not in the in-memory statistics repository <NUM>. In yet another embodiment, the database server may retrieve older statistics from dictionary table <NUM>, delta statistics from in-memory statistics repository <NUM>, and merge the two to provide on-the-fly statistics.

In yet another embodiment, the database server is insulated from the manner in which on-the-fly statistics are generated by providing an API through which the database server may request statistics. In response to calls made to the API, a statistics-generating process may generate the on-the-fly statistics in any one of a variety of ways. For example, depending on the actual statistics requested, the statistics-generating process may:.

The statistics-generating techniques described herein are not limited to any particular mechanism for providing desired statistics to a database server.

Claim 1:
A method comprising:
storing, on persistent storage (<NUM>), statistics that reflect a particular state of a database (<NUM>), wherein:
the database comprises an index,
the index is implemented using a tree structure,
the statistics include the number of leaf nodes in the index, the depth of the index tree, the total size of index, or the number of distinct keys;
receiving, at a database server (<NUM>), a Data Manipulation Language, DML, command;
in response to the DML command:
making one or more changes to data stored in the database (<NUM>);
generating one or more delta statistics that reflect how the one or more changes affect the statistics; and
storing the one or more delta statistics in volatile memory (<NUM>) of the database server (<NUM>);
generating one or more on-the-fly statistics, including merging the statistics on the persistent storage (<NUM>) and the one or more delta statistics; and
a query optimizer selecting a particular query plan, from among a plurality of candidate query plans for a subsequent database command, based at least in part on the on-the-fly statistics;
wherein the method is performed by one or more computing devices.