Method of generating attribute cardinality maps

[00002] The present invention relates generally to estimation involving generalized histogram structures and more particularly to a method of result size estimation in query optimization.

[00003] One of the main uses of computers is storing and retrieving large amounts of data efficiently. The computer system used for this purpose are known as database systems and the software that manages them are known as database management systems (DBMS). The DBMS facilitates the efficient management of data by (i) allowing multiple users concurrent access to a single database, (ii) restricting access to data to authorized users only, and (iii) providing recovery from system failures without loss of data integrity. The DBMS usually provides an easy to use high-level query/data manipulation language such as the Structured Query Language (SQL) as the primary interface to access the underlying data.

[00004] SQL, the most commonly used language in modern-day DBMSs, is a declarative language. Thus, it shields users from the often complex procedural details of accessing and manipulating data. Statements or commands expressed in SQL are generally issued by the user directly, using a command-line interface. The advantage of the declarative SQL is that the statements only need to specify what answer is expected, and not how it should be computed. The actual sequence by which an SQL command is computed is known as the procedural Query Evaluation Plan (QEP). The procedural QEP for a given non-procedural SQL statement is generated by the DBMS and executed to produce the query result. Typically, for a given query, there are many alternative procedural QEPs that all compute the result required. Each QEP, however, has its own cost in terms of resource use and response time. The cost is usually expressed in terms of the I/O operations such as the number of disk reads and writes, and the amount of CPU work to execute a given QEP. The problem of devising the best procedural QEP for a query so as to minimize the cost is termed query optimization.

[00005] In all brevity, given a declarative SQL query, the DBMS's Query Optimizer module determines the best possible procedural QEP to answer it. In order to do this, the query optimizer uses a model of the underlying system to select from a large set of candidate plans an efficient plan as quickly as possible. Efficiency of the QEP is measured in terms of resource utilization and response time.

[00006] The cost incurred in evaluating a QEP is proportional to the number of operations, including disk reads, writes and CPU work required to compute the final answer from the base relations. The size of the final result of a query as well as the sizes of the base relations will be the same regardless of which QEP, from among many possible candidate QEPs, is chosen by the query optimizer. Hence the cost of a QEP depends on the size of the intermediate relations generated during the computation of the query, as this is the single most important factor responsible for the difference in the costs of various QEPs of the given query. Hence by choosing a QEP that has smaller intermediate relations then other QEPs, it is possible to minimize the cost involved in computing the final result of the given query. Although this is easy to explain, due to the large number of possible alternative QEPs, computing the sizes of the intermediate relations accurately for each possible QEP is virtually an impossible task. Hence, one approach is to approximately estimate the sizes of the intermediate relations.

[00007] A complete set of glossary is found in many undergraduate database text books, including [Elmasri and Navathe, 1994], pp 137-177.

[heading-00008] 2.1 Query Optimization: An Overview

[00009] Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the number of relations in the query increases. The query optimization process is generally divided into three distinct phases, namely query decomposition, query optimization and query execution as shown in FIG. 1.

[00010] In the query decomposition module, the declarative SQL query is first scanned, parsed and validated. The scanner sub-module identifies the language components in the text of the query, while the sparser sub-module checks the query syntax. The validator checks that all attribute and relation names are valid and semantically meaningful. The query is then translated into an internal format expressed in relational algebra in the form of a query Operator Tree. Using this operator tree as its input, the query optimizer module searches for a procedural plan with an optimal ordering of the algebraic operators. This optimal procedural plan is represented by an annotated query tree. Such trees encode procedural choices such as the order in which operators are evaluated and the method for computing each operator. Each tree node represents one or several relational operators. Annotations on the node represent the details of how it is to be executed. For example, a join node may be annotated as being executed by a hash-join, and a base relation may be annotated as being accessed by an index-scan. The choices of the execution algorithms are based on the database and system characteristics, for example, the size of the relations, available memory, type of indexes on a given attribute etc.

[00011] This fully annotated operator tree with the optimal QEP is then passed on to the query execution engine where all the low level database operations are carried out and the answer to the query is computed. An example annotated query tree is shown in FIG. 2.

[heading-00012] 2.1.1 An Example

[00013] FIG. 3 shows an example relational database from a Property Tax Assessor's office.

[heading-00014] This database consists of three relations, namely,

[none]

• [00015] TaxPayer(SIN, CityCode, Name, DOB, Balance),
• [00016] Property(Type, OwnerSIN, Tax) and
• [00017] City(CityCode, CityName, Population).
  Assume that these relations have the following cardinalities:
• [00019] |TaxPayer|=12×10⁶ tuples,
• [00020] |Property|=3×10⁶ tuples, and
• [00021] |City|=4000 tuples.
  Given these pieces of information, it is possible to answer the following declarative query:

[00023] Query: Find the name, city and tax information of all property owners.

[00024] To illustrate the large difference in the execution cost that exists among various QEPs, two QEP's are compared for this query using a simple cost model based on the number of I/O operations. Since the disk I/O is usually the dominant factor¹ in the query response time, it is assumed the cost of evaluation a QEP is given by the total number of all tuples read and written to generate the final answer. In addition, the cost of reading the two input relations and then writing the resulting relation back on to the disk is also considered.

[00025] ¹Actually, a realistic cost model should include many other factors such as various join algorithms, availability of indexes and other auxiliary access methods, effects of caching and available memory, data skew etc.

[00026] From the set of many alternatives, two possible QEPs shown in FIG. 4 are analyzed below. The QEPs execute the answer to the query as described below:

[00027] Query Evaluation Plan 1:

[00028] In the first QEP, the relations TaxPayer and City are joined to determine the city information for each person where he or she lives. This join generate an intermediate relation. This intermediate relation is then joined with the relation Property to compute the final results.

[00029] The first join requires the relations TaxPayer and City to be read. This results in 12×10⁶+4000 reads. Assuming the result of this join is written back to the disk, it would require 12×10⁶ writes. Note that the size of the intermediate result is 12×10⁶. The second join requires the above intermediate relation and the relation Property to be read. This involves an additional 12×10⁶+3×10⁶=15×10⁶ reads. Since the final result contains 3×10⁶ tuples, it requires that many write operations. Hence the total number of operations required for the first QEP is N₁=(12×10⁶+4000)+(12×10⁶)+(15×10⁶)+(3×10⁶)=42,004,000.

[00030] Query Evaluation Plan 2:

[00031] Joining the relation TaxPayer and Property, an intermediate relation with all the property owners can be obtained. This intermediate relation is then joined to the relation City to determine the information of the city for each tax payer.

[00032] In the second, QEP, the first join requires 12×10⁶+3×10⁶ reads and 3×10⁶ writes. The second join requires another 3×10⁶+4000 reads and 3×10⁶ writes. Hence the total number of operations required for the second QEP is N₂=(12×10⁶+3×10⁶)+(3×10⁶)+(3×10⁶+4000)+(3×10⁶)=24,004,000, which is almost half of the first QEP.

[00033] Using a simple cost model, this short example with two different QEPs illustrates that the cost of one plan is sometimes half of the other. Most of the real-world queries are complex queries with many relations, and with a more sophisticated realistic cost model, one can generate QEPs with substantially different costs. The task of a query optimizer is to judiciously analyze the possible QEPs and choose the one with the minimal cost.

[heading-00034] 2.2 Goals of Query Optimization

[00035] The main goals of a query optimizer are that of minimizing both the response time and resource consumption. These optimization goals are often conflicting. For example, a QEP which computes the result of a query quickly but requires all available memory and CPU resources is probably not desirable because it would virtually deprive other users from accessing the database.

[00036] Finding good solutions for a query is resource intensive, but can reduce the actual evaluation cost considerably. For example, let T_o be the time taken to find an optimal QEP and let T_c be the time taken to execute the optimal QEP and obtain the results. If the average time taken to execute a random QEP is T_avg, then ideally T_o+T_c<<T_avg.

[00037] As queries get more complex in terms of the number of relations involved or alternative algorithms for computing an operator the number of potential alternative QEPs that to be considered explodes. The number of alternatives quickly increases with the number of relations etc. into the order of millions, while the differences between the cheapest and most expensive QEP can easily be several orders of magnitude. Even with simple string queries with n relations, there are (2(n−1))!/(n−1)! different join orders. For joins involving small number of relations, this number is acceptable; for example, with n=5, the number is 1680. However, as n increases, this number rises quickly. With n=10, the number of different join orders is greater than 176 billion!

[00038] As a rule of thumb, for small queries with no more than four or five relations all QEPs are generated within a few seconds. In this case the optimization time, T_o, is often a fraction of the response time improvement gained.

[00039] Apart from the fact that the execution space of QEPs is usually very large, the computation of a single join operation itself is one of the most time consuming tasks. To compute the join of N relations, (N−1) dyadic join operations have to be performed. Since the size of the relations joined determines the cost of a single join operation, the order in which all N relations are joined is preferably chosen in such a way so as to minimize the overall cost of computing the join of N relations.

[00040] Unfortunately, finding the optimal join order has been proven to be an NP-hard problem while, at the same time, it is one area where considerable cost benefits can be derived. Only for specific join ordering cases, exact and optimal solutions have been obtained [Boral and Zaniolo, 1986, Ibaraki and Kameda, 1984]. In addition, most of the optimization techniques proposed in the literature cannot be applied to large queries. For example, two popular early day database systems, namely, System R and Ingres use algorithms that essentially perform an exhaustive search over the entire QEP domain. This is probably adequate in their implementation because they do not allow large queries with more than 15 joins.

[00041] The problem of optimizing a query can be formally states as follows:

[heading-00042] Problem 1 Given a relational query Q, an execution space E and a cost function C(QEP) over elements of E, find the query evaluation plan QEP∈E such that,

[00043] (1) QEP computes Q

[00044] (2) There does not exist QEP′∈E such that QEP′ also computes Q and C(QEP′)<C(QEP).

[00045] where the execution space E is the space of QEPs considered by the optimizer.

[00046] Finding an optimal QEP is a computationally intractable problem, especially when the query involves more than, say, ten relations. One obvious approach is to decrease the size of the execution space E, but although it would reduce the time and/or space requirement, it has the tradeoff of reducing the chances of finding good plans. Another approach consists of estimating the costs of QEPs using the standard statistical information available in the database catalog. In fact, most commercial DBMSs use some form of statistics on the underlying data information about the available resources in order to estimate the cost of a query plan approximately. Since these

[00002]

TABLE 1
Statistical Information found in a typical DBMS Catalogue
	Notation	Explanation
	NR	Number of tuples in relation R
	bR	Number of disk blocks storing relation R
	sR	Size of a tuple of relation R in bytes
	bfR	Blocking factor of relation R. This is the number of
		tuples of relation R that fit into one disk block
	δ(A, R)	Number of distinct values of attribute A in
		relation R.
	φ(A, R)	Selection cardinality of attribute A in relation R.
		Given a relation R and an attribute A of the relation,
		φ(A, R) is the average number of records that
		satisfy an equality condition on attribute A.

statistics are used to provide approximate estimates of query costs, the validity of the optimizer's decisions may be affected. On the other hand, since optimizers use these costs only for comparison purposes, approximate estimates for the costs of the QEPs are usually sufficient as long as these estimates are reasonably close to the actual cost of executing the QEP. For example, if the actual time units of execution of two plans P₁ and P₂ are 10 and 20 respectively, and the estimated times are 5 and 15, the optimizer will still pick P₁ as the less expensive plan, and this will be done correctly. On the other hand, if the estimated times are 5 and 4, the optimizer will pick the suboptimal plan P₂. This is an extremely important issue because costs of plans often differ considerably, and choosing a suboptimal plan often results in severe performance degradation, defeating the very purpose of query optimization.

[00048] Query optimizers make use of the statistical information stored in the DBMS catalogue to estimate the cost of a QEP. Table 1 lists some of the commonly used statistical information utilized in most of the current commercial DBMSs.

[00049] In addition to these pieces of information, most DBMSs also maintain information about the indices² in their catalogues. These pieces of information include values such as the average fan-out, number of levels in an index etc.

[00050] ²Indices refer to the actual data structures used to store and retrieve the physical records of base and intermediate relations.

[00051] Since the actual evaluations of all possible QEPs in space E is very difficult, like all other investigators in this area, one approach is to approximately estimating the costs of QEPs.

[00052] Consider the cost C of joining two relations R₁ and R₂ on a common attribute X, using the nested-loop join algorithm [Selinger et al., 1979]. If b_R1 and b_R2 are the number of disk blocks required for relations R₁ and R₂ respectively, then the cost formula in terms of number of disk accesses is, $𝒞=b_{R_1}+b_{R_1}\times b_{R_2}+\left(\frac{\mathrm{js}\times R_1\times R_2}{{\mathrm{bf}}_{R_1{R}_2}}\right)$
where js is the join selectivity³ of these other operators and bf_R1R2 is the blocking factor for the resulting relation.

[00054] ³Selectivity of an operator is the ratio of the result size and the product of its input sizes. For the join operator, the join selectivity js=|(R_1cR₂)|/(|R₁|×|R₂|)

[00055] From the above cost formula, it is apparent that the following quantities are crucial for the query optimizer in order to estimate the cost of such an operation:

[00056] (a) Query Result Size: The cost formula for the above join algorithm depends on the sizes of the input relations, which is true for nearly all relational operators. In a query with several operators, an input to an operator may itself be the result of another operator(s). This shows the importance of developing techniques to estimate the result sizes of these other operators.

[00057] (b) Query Result Distributions: The result size of a join or any other relational operator depends mainly on the data distribution(s) of its input relation(s). Again the input to this operator may itself be the relation which results from invoking another operator(s). This means that techniques to estimate the distribution of a query result are also desirable.

[00058] (c) Disk Access Costs: This is the cost of searching for, reading, and writing data blocks that reside on secondary storage, mainly on disk. The cost of searching for records in a file depends on the type of access structures on that file, such as its ordering, hashing, and primary or secondary indexes. In addition, factors such as whether the file blocks are allocated contiguously on the same disk cylinder or scattered on the disk affect the access cost.

[00059] The design of a good query optimizer involves developing techniques to efficiently and accurately estimate the various query result sizes. The objective of this invention is to provide new techniques that would provide more accurate query result size estimation results than the state-of-the-art methods used in the current database systems. There are other topics of concern in query optimization such as implementation algorithms for various relational operations, physical access plans for retrieving records etc., but they are not addressed herein.

[00060] In order to completely solve the above estimation problem, it is useful to develop result size estimation techniques for each of the relational operators. Most of the current commercial DBMSs employ methods based on one or more of the following techniques to estimate the above quantities:

• [00061] 1. Sampling based technique
• [00062] 2. Parametric techniques
• [00063] 3. Probabilistic counting techniques and
• [00064] 4. Non-parametric or histogram based techniques.

[00065] These techniques are briefly reviewed below. The accuracy of these estimates is often of critical importance since the selection of an optimal QEP from an exponential number of alternatives solely depends on these estimates. Despite the widespread usage of the above techniques in many commercial database systems, their accuracy has not been studied extensively.

[00066] Query optimization has been a very active research field in the database community for the last two decades.

[00067] Apart from the area itself being vast, the techniques used to optimize a query search itself are varied. At the top most level, the query optimizer has to distinguish the various query evaluation plans. This is a problem in its own right. The question of pruning these query evaluation plans, and discarding the less promising ones without actually processing them in any depth, is itself, a huge area of research. Additionally, for any given query evaluation plan, the question of estimating its efficiency without actually processing the query is a problem that has captivated much research.

[heading-00068] 3.1 A Top-down Approach to Query Optimization

[00069] Early work in query optimization essentially followed two distinct tracks, namely, the bottom up and top down. Database researchers found the query optimization problem, when posed in a general context, to be both difficult and complex—and indeed, intractable with regard to optimality. They, in the early days, mainly undertook a bottom-up approach, considering only special cases. This included, for example, finding “optimal” strategies to implement major relational operations and finding “optimal” methods to execute simple subclasses of queries. As better strategies emerged with time, researchers attempted to obtain “optimal” strategies for relatively larger and more complex queries by composing the results from the smaller building blocks.

[00070] As the number and sizes of the commercial databases grew, the need for functional optimization systems resulted in the development of full-scale query evaluation techniques. These techniques provided more general solutions and handled query optimization in a uniform, though heuristic manner [Astrahan and Chamberlin, 1975, Makinouchi et al., 1981, Niebuhr and Smith, 1976, Wong and Youseffi, 1976]. Obviously, generating a query optimization plan out of smaller building blocks, often did not achieve optimal system efficiency. This led the researchers to move towards a top-down approach that incorporated more knowledge about special-case optimization opportunities into the general procedures. This top-down approach also incorporated many general algorithms, which were augmented by combinatorial cost-minimization techniques for choosing between the various potential query evaluation plans.

[00071] Using the top-down approach, the general query optimization is divided into the following steps:

[00072] (1) Use logical transformation techniques to change the given query so that (a) the query is represented in a standardized form, (b) the query is simplified such that the same operation is not computed twice, and (c) the query is ameliorated so as to organize the computation to apply procedures developed for special case scenarios.

[00073] (2) Represent the transformed query as alternative sequences of simple elementary relational operations that are computed using known implementation techniques. This makes it possible to compute the associated execution cost for the evaluation plan. This step generates a set of potential access plans that simplify the process of evaluating the original query.

[00074] (3) Compute the execution cost for each access plan in the above access plan set.

[00075] (4) Execute the cheapest access plan and return the results.

[00076] The first step of this procedure involves logical transformation of the query, and thus it is, generally, independent of the underlying data. Hence this step is often handled at compile time. But in order to properly carry out steps (2) and (3), and to generate optimal query evaluation plan, sufficient knowledge about the underlying data distribution is required.

[00077] The face that steps (2) and (3) require some prior knowledge about the underlying data poses a number of difficulties. First of all, if the data distribution is dynamic, steps (2) and (3) can be carried out only at run time. Consequently some gain in the overall execution efficiency is sacrificed in order to minimize the optimization cost. Another difficulty is that the DBMS should maintain a catalogue or a meta-database about the pertinent statistical information about the underlying data distributions. It is obvious that in order to benefit from such as optimization strategy one must compare the costs of gathering and maintaining such information in the DBMS catalogue against the cost savings in the overall optimization process.

[heading-00078] 3.1.1 Query Transformation

[00079] Any relational algebraic query can be transformed into a number of semantically equivalent expressions. The work on transformation of a given expression into an equivalent query by means of well defined transformation rules is discussed below. The objectives of query transformation can be described as the following:

• [00080] 1. Obtaining a normalized starting point for query optimization (called standardization).
• [00081] 2. Eliminating the duplication of effort (called simplification) and
• [00082] 3. Generating query expressions that have superior evaluation performance compared to the initial query (called amelioration).

[00083] A number of works [Jarke and Schmidt, 1981, Kim, 1982, Palermo, 1972] have been done to define a normalized starting post for representing a query for the purpose of query optimization.

[00084] One of the main differences between any two equivalent expressions is their degree of redundancy [Hall, 1976]. In other words executing a query with redundant expression results in carrying out a number of unnecessary duplicated operations. Hence query simplification steps should involve the transformation of a redundant query expression into an equivalent non-redundant one by applying simple logical transformation rules listed below.

[heading-00085] 3.1.2 Transformation Rules

[00086] A transformation or equivalence rules says that expressions of two forms are equivalent. This implies that one expression can be transformed to the other while preserving equivalence. When two relations have the same attributes ordered in a different manner, and equal number of tuples, the two expressions that generate them are considered to be preserve equivalent. Modern-day query optimizers heavily use equivalence rules to transform initial expressions into simpler logically equivalent expressions.

[00087] A number of commonly used general equivalence rules for transforming relational algebraic expressions are given below. Three equivalent transformations are shown in FIG. 5. The predicates in the query expressions are denoted by θ_i, attributes are denoted by L_i, and the algebraic expression is denoted by E_i. Since the result of a relational algebraic expression itself is a relation, a relation name R can appear anywhere in place of an expression.

[00088] 1. Conjunctive selection operations can be simplified into a sequence of individual selections. This transformation operation is known to as a cascade of σ.
σ_θ1Λθs(E)=σ_θ1(θ_θ2(E)).

[00090] 2. Selection operations applied successively onto a relation are commutative.
σ_θ1(θ_θ2(E))=σ_θ2(σ_θ1(E)).

[00092] 3. In a sequence of projection operations, only the final operation is required to compute the results. This transformation operation is known as a cascade of π.
π_L1(π_L2( . . . (π_Ln(E)) . . . )=π_L1(E).

[00094] 4. Selections can be processed together with Cartesian products and θ-joins.
σ_θ(E₁×E₂)=E_1θE₂.   (a)

[00096] This expression is indeed the definition of the theta join.
σ_θ1(E₁×_θ2E₂)=E_1θ1∈θ2E₂.   (b)

[00098] 5. A theta-join operation is commutative.
E_1θE₂=E_2θE₁.

[00100] Note that the natural join operation is also commutative, since the natural-join operator is actually a special case of the theta-join operator.

[00101] 6. (a) Natural join operations are associative.
(E₁E₂)E₃=E₁(E₂E₃).

[00103] (b) Theta joins can be associative as shown below.
(E_1θ1E₂)_θ2∈θ3E₃=E₃=E_1θ1∈θ3(E_2θ2E₃).

• • [00105] where θ₂ involves attributes from only E₂ and E₃. Since any of these predicates can be empty, the Cartesian product (x) is an associative operation. It is important to observe that the properties of commutativity and associativity of join operations are important for join reordering in query optimization.

[00106] 7. The selection operation and the theta join operation are distributive under the conditions states below:

• • [00107] (a) Selection operation distributes over the theta join operation when all the attributes in selection predicate θ₀ involve only the attributes of one of the expressions (E₁) being joined.
    σ_θ0(E_1θE₂)=(σ_θ0(E₁))_θE₂.
  • [00109] (b) Selection operation distributes over the theta distribution when selection condition θ₁ involves only the attributes of E₁ and θ₂ involves only the attributes of E₂.
    σ_θ1∈θ2(E_1θE₂)=(σ_θ1(E₁))_θ(σ_θ2(E₂)).

[00111] 8. The projection operation and the theta join operation are distributive.

• • [00112] (a) Suppose the attributes L₁ and L₂ belong to the expressions, E₁ and E₂, respectively. Assume that the join predicate θ has only attributes in L₁∪L₂. This means,
    π_L1∪L2(E_1θE₂)=(π_L1(E₁))_θ(π_L2(E₂)).
  • [00114] (b) Consider a join E_1θE₂. Assume the attributes, L₁ and L₂ belong to the expression E₁ and E₂, respectively. Assume the attribute L₃ is from the expression E₁ which are involved in join predicate θ, but are not in L₁∪L₂, and let attribute L₄ of E₂ that are involved in join condition θ, but are not in L₁∪L₂. This means,
    π_L1∪L2(E_1θE₂)=π_L1∪L2((π_L1∪L3(E₁))_θ(π_L2∪L4(E₂))).

[00116] 9. The union operation and the intersection are commutative set operations.
E₁∪E₂=E₂∪E₁ and E₁∩E₂=E₂∩E₁.

• • [00118] It is important to note that set difference operation is not commutative.

[00119] 10. The union operation and intersection operation are associative set operations.
(E₁∪E₂(∪E₃=E₁∪(E₂∪E₃) and (E₁∩E₂)∩E₃=E₁∩(E₂∩E₃).

[00121] 11. The selection operation distributes with the union, intersection, and set difference operations.
σ_P(E₁−E₂)=σ_P(E₁)−σ_P(E₂).

• • [00123] When substituting the set difference (−) with either one of ∪or ∩, selection operation is distributive with the union and intersection operations.

[00124] 12. The projection and union operations are distributive.
π_L(E₁∪E₂)=(π_L(E₁))∪(π_L(E₂)).

[00126] The proof of the above equivalence is straightforward and is presented in the work of [McKenna, 1993]. Also, the preceding list is only a partial list of equivalences. More equivalence involving extended relational operators, such as the outer join and aggregation, are constructed from the above list.

[00127] The process of query simplification does not always produce a unique expression. Many non-redundant expressions exist that are equivalent to the one generated by a given equivalence transformation. The evaluation of expressions corresponding to a given query may differ significantly with respect to performance parameters, such as the size of the intermediate results and the number of relation elements accessed.

[heading-00128] 3.2 Query Evaluation

[heading-00129] 3.2.1 One-Variable Expressions

[00130] These are the simplest algebraic expressions used to select a given set of attribute values from a single relation. A simple approach to evaluate such an expression is to read every corresponding attribute value of the relation, and to check whether it satisfies each term of the expression. Obviously this approach is very expensive, especially when the query expression involves large relations. In these situations, there have been many techniques proposed to minimize the number of attribute values accessed and the number of tests applied to an accessed attribute value. These are briefly discussed below.

[00131] One of the commonly employed techniques to minimize the number of record accesses is by means of data structures that provide direct access paths, so that an exhaustive sequential search is avoided. This is accomplished by maintaining the relation in a sorted form with respect to one or more attributes so that records are easily accessed. This also facilitates a binary search on the sorted attribute values. A use of such a technique is the evaluation of range queries [Bolour, 1991, Davis and Winslow, 1982].

[00132] Another commonly used technique is hashing. Hashing technique has many variants and its major advantage is that it provides fast direct access to records without requiring that the attribute values are maintained in a sorted order.

[00133] In addition to hashing, techniques used indexes play an important role is providing direct and ordered access to records. Indexes are often combined with multi-list structures. The idea of an index is based on a binary relationship between records being accessed. Specifically the index method uses tuple identifiers or keys to establish a binary relationship between records, so that traversal becomes much faster than a sequential search. The indexing method is either one-dimensional or multi-dimensional A one-dimensional index implements record access based on a single relation attribute, whereas a multidimensional index implements record access based on a combination of attributes. Two popular approaches for implementing one-dimensional indexes are ISAM [Corporation, 1966] and B-tree [Bayer and McCreight, 1972] structures. A detailed discussion on multidimensional index structures is found in the work of Bentley and Friedman [Bentley and Friedman, 1979].

[00134] The logical transformation rules are often applied at run time to a query expression to minimize the number of tests applied to an accessed record or attribute value of a relation. Changing the order in which individual expression components are evaluated sometimes results in performance increases. A number of techniques utilizing a priori probabilities of attribute values, to obtain optimal evaluation sequences for specific cases are discussed in [Hanani, 1977].

[heading-00135] 3.2.2 Two-Variable Expressions Query expression that describe conditions for the combination of records from two relations are known as two-variable expressions. Usually two-variable expressions are formed by monadic sub-expressions and dyadic sub-expressions. Monadic expressions restrict single variables independently of each other, whereas dyadic expressions provide the relationship between both variables. In what follows the basic strategies for the evaluation of a single dyadic expression, and methods of the evaluation of any two-variable expressions are discussed.

[00136] Method 1 Nested_Iteration_Join

• • [00137] for i:=1 to N₁ do
    • [00138] read the i^th element of R₁;
    • [00139] for j:=1 to N₂ do
      • [00140] read j^th element of R₂;
      • [00141] compute the join based on join predicate;
    • [00142] end;
  • [00143] end;

[00144] There are two major approaches to implementing the join operation, namely order-dependent and order-independent strategies. The nested iteration method is a simple approach that is independent of the order of record access. In this method, every pair of records from the relation is accessed and concatenated if the join predicate is satisfied. A nested iteration based join list is Method 1.

[00145] Let N₁ and N₂ be the number of records of the relations read in the outer and inner loops respectively. It is clear that N₁+N₁*N₂ disk accesses are required to evaluate the dyadic term, assuming that each record access requires one disk access.

[00146] The nested iteration method is improved by using an index on the join attribute(s) of the relation R₂. This strategy does not require accessing R₂ sequentially for each record of R₁ as the matching R₂ records are accessed directly [Griffeth, 1978, Klug, 1982]. Hence using an index N₁+N₁*N₂*j₁₂ record accesses are needed, where j₁₂ is a join selectivity factor representing the Cartesian product of R₁ and R₂.

[00147] In a paged-memory environment, the idea of the method iteration method is extended to be nested block method [Kim, 1982]. In this method, a main memory buffer is used to hold one or more pages of both relations, where each page contains a set of records.

[00148] The nested block algorithm is essentially similar to the nested iteration method. The only difference is that memory pages are red instead of single records of the relation. Using this approach the number of disk accesses required to compute the join is reduced to P₁+(P1/B1)*P₂, where P₁ and P₂ are the number of pages required to store the outer and inner relations of the algorithm respectively and B₁ is the number of pages of the outer relation occupying the main memory buffer. It is easy to observe that it is always more efficient to read the smaller relation in the outer loop (i.e., make P₁<P₂). If the smaller relation is maintained entirely in the main memory buffer, then only P₁+P₂ disk accesses are needed to form the join.

[00149] Another approach, based on the order in which records of the relations are retrieved, is known as the merge method. In this approach, both relations are scanned in ascending or descending order of join attribute values and merged according to the join predicate. Almost N₁+N₂+S₁+S₂ disk accesses are required to form the join, where S₁ and S₂ are the number of disk accesses needed to sort the relations being joined. This method is an excellent choice when both relations are already sorted by the same criterion. Of course, when the smaller relation is completely maintained in the main memory buffer, the nested block method is more efficient. Whenever an indexing mechanism exists, then when one relation is much larger than the other, nested iteration with indexes is preferable.

[00150] The strategies developed to evaluate one-variable expressions and computation of dyadic terms are also used to evaluate any arbitrary two-variable expressions. These strategies mainly differ in the manner they implement the access paths and methods, namely indexing mechanisms and the order in which the component expressions are evaluated.

[00151] [Blasgen and Eswaran, 1976], [Niebuhr and Smith, 1976], and [Yao, 1979] describe many different approaches and compare their conclusion that usually there is no a priori best algorithm for a general evaluation process and thus the query optimizer must rely on heuristics or alternatively choose the optimal plan through an expensive cost comparison of potentially many alternatives for each query.

[heading-00152] 3.2.3 Multi-variable Expressions

[00153] A query optimizer designed to process any arbitrary query should incorporate strategies for evaluating multi-variable expressions.

[00154] One of the popular techniques, known as parallel processing of query components evaluates an expression by avoiding repeated access to the same data. This is usually achieved by simultaneous or parallel evaluation of multiple-query components. Usually all monadic terms associated with a given variable are evaluated first and all dyadic terms in which the same variable participates are partially evaluated parallely [Palermo, 1972]. This also includes parallel evaluation of logical connectors such as AND existing among the various terms, that always minimizes the size of intermediate query results [Jarke and Schmidt, 1982]. A strategy where aggregate functions and complex sub-queries are computed concurrently, has been proposed by Klug [Klug, 1982]. Parallel processing of query components requires appropriate scheduling strategies for the overall efficient optimization. A few interesting techniques for parallel scheduling for query processing have been proposed by Schmidt [Schmidt, 1979].

[00155] Another strategy that is useful for scheduling parallel optimization is the pipelining of operations that works on the partial output of preceding operations. This is described in [Smith and Chang, 1975, Yao 1979].

[00156] Another method known as the feedback technique combines the tasks of simultaneous evaluation of query components and pipelining, using partial results of a join operation [Clausen, 1980].

[heading-00157] 3.3 Access Plans

[00158] The combination of these building blocks into an efficient and optimal evaluation procedure for an arbitrary standardized, simplified, and ameliorated query expression is discussed below.

[00159] The access plan selection strategies use the transformed and simplified query, the storage structures and access paths, and a simple mathematical cost model to generate an optimal access plan. This is usually achieved by the following procedure:

• [00160] 1. Find all possible logical access plans for evaluating the given query. A logical access plan is defined as a sequence of operations or of intermediate results leading from existing relations to the final result of a query.
• [00161] 2. Obtain details of the physical representation of data such as access paths, statistical information stored in the data-dictionary.
• [00162] 3. Using the mathematical cost model based on the access paths and processing costs, select the cheapest access plan.
  3.3.1 Generation of Access Plans

[00164] The sequence of operations or intermediate results leading from the existing data structures to a query result is known as an access plan for a query. An ideal query optimizer generates an optimal access plan with a minimal optimization effort.

[00165] Two completely different methods were proposed in [Smith and Chang, 1975] and [Yao, 1979]. Smith and Change use a fixed set of query transformation rules. This approach usually results in a single access plan, which need not be optimal. Yao's approach generates all non-dominated access plans that are possible in a given scenario. Obviously generating every single possible access plan becomes prohibitively expensive for complex queries.

[00166] In addition to the above methods, there are other strategies that resort to methods that lie between heuristic selection and detailed generation of alternative access plans. This includes an SQL nested block method based on a hierarchical technique used in System R [Selinger et al., 1979]. In this strategy, in addition to generating and comparing the evaluation plans for each query block, the sequence in which how query blocks are evaluated is also computed. The disadvantage of this method is that as this approach requires a user-specified block structure, the initial query normalization step is pushed into the actual query processing phase [Kim, 1982], INGRES also uses a somewhat similar approach [Wong and Youseffi, 1976].

[heading-00167] 3.3.2 Cost Analysis of Access Plans

[00168] The query optimizer chooses a physical access plan for a given query either on the basis of a set of heuristic rules or on the basis of a mathematical cost model involving the underlying data structures and access methods. Merrett discussed a top-down approach for cost analysis based on the storage structures [Merrett, T. H., 1977]. Though the techniques presented in [Merrett, T. H., 1977] have been significantly improved on since 1977, it is worth mentioning that Merrett's ideas were seminal and initiated the work in the area of cost analysis in relational database systems. In particular, Merrett provides general principles that allow a database analyst either to quickly estimate the costs of a wide variety of alternatives, or to analyze fewer possibilities in depth. He also provides a number of techniques that can be used at any level of the iterative design process.

[00169] A brief review of some of the cost models and their use in the query optimization is given below.

[00170] Even though working storage requirements or CPU costs are considered to be important factors by some researchers, the number of secondary storage accesses or I/O operations is considered to be the most important one in designing a cost model for analyzing any physical access plan. The number of secondary storage accesses is mainly dependent on the size of the operands used in the query, the type of access structures used, and the size of the temporary buffers available in the main memory.

[00171] In the initial stages of the evaluation, the sizes of most of the operands are known, at least approximately. In addition, available index methods for the attribute values involves are also known. But in the later stages of the evaluation, most intermediate relations are the results of preceding operations, and consequently, the cost model estimates their size by using information about the original data structures and any other information available from the DBMS catalogue, such as the selectivity of the operations already performed on them. Unfortunately, there are no generally accepted well defined formulae for estimating the size of intermediate results.

[00172] It is possible to construct a simpler model, using only a few parameters by imposing restrictions on the assumptions about the data. The result size estimate analysis discussed in [Selinger et al., 1979] uses only information already available in the database catalogue. Obviously this requires many assumptions about data and queries to complete the cost model [Astrahan and Chamberlin, 1975]. On the other hand, the result size estimate analysis proposed by Yao assumes that detailed selectivity data is known [Yao, 1979], without stating how this detailed information is obtained.

[00173] In the late 1980s and early 1990s, researchers began to carefully describe and critically analyze all underlying assumptions about database characteristics. The objective was to formally generate valid parameters for the cost model that enable the optimizer to do the following:

[00174] 1. estimate a result size for any relational operation, and

[00175] 2. estimate parameter values for intermediate results based on the previous results and base relations.

[00176] Cost models based on such techniques relate the database state as run time as the result of a random process. This random process is assumed to generate relations from the Cartesian product of the attribute value domains, based on some probability distribution and by invoking certain other general principles such as the functional dependencies of the underlying database schema [Glenbe and Grady, 1982, Richard, 1981]. These assumptions enable one to derive parameters in order to compute the size of any intermediate result of more complex relational operations.

[00177] These assumptions have been critically involved in [Christodoulakis, 1981] and [Montgomery et al., 1983]. They have shown that these assumptions often lead to a bias against direct-access structures in selection plans. However, to date, there has been no practical and simple cost model or formula with more general assumptions, which does not require detailed catalogue information.

[heading-00178] 3.3.3 Selection of Access Plans

[00179] Selection of access plans is often based on either heuristic rules or cost estimates. Some approaches, proposed in the literature, combine heuristic reduction of access plan choices with enumerative cost minimization techniques. A number of experimental studies show that combinatorial analysis significantly improves the database performance.

[00180] Cost estimates can be used in the access plan selection process in two different ways. The first approach estimates the costs of each alternative access plan completely. The major advantage of this approach is that it is possible to make use of techniques like parallelism or feedback in such situations. But, obviously the overall optimization effort is high.

[00181] In the second method, a parallel incremental generation of the cost of strategies is proposed. The main advantage of this method is that it permits whole families of strategies with common parts to be evaluated concurrently. Hence this approach results in a significant reduction in the overall optimization effort. One good example using this approach is the heuristic method proposed by Rosenthal and Reiner [Rosenthal and Reiner, 1982], in which the “optimizer” keeps only the current-optimal way to generate each intermediate result, and discards any other sub-optimal methods.

[00182] A more popular method is the dynamic-programming query optimization strategy, This is actually an extension to the second method, in which, at each level, only the next operation to be performed is determined based on the optimal sub-plans. As in any dynamic programming technique, this method has actual information about all its operands, including intermediate result sizes that are used to update the estimates of the remaining steps. This dynamic approach has two obvious drawbacks. Firstly, it has a potential of getting stuck in local optima if no adequate look ahead is planned. Furthermore, in the more general setting, the method leads to prohibitively high optimization cost.

[heading-00183] 3.4 Query Optimization Using Join Re-Ordering

[heading-00184] 3.4.1 Query Graphs and Join Trees

[00185] Query graph is a commonly used pictorial representation of a relational query. In a query graph, nodes denote the relation names, and edges represent the respective predicates. If a predicate expression, p, references the attributes of two relations, say R_i and R_j, then an edge labeled p is said to exist between the nodes of these two relations. Denoting the edges of the query graph as {p₁, . . . , p_n} and nodes as {R₁, . . . , R_m}, the result of a query graph G=(V, E) is defined as a Cartesian product followed by relational selection: σ_{p1Λp2 . . . Λpn}(R₁x . . . x R_m).

[00186] Instead of using the straight definition of product followed by selection of the query tree stated above, simple Join trees are used to evaluate queries. A join tree is defined as an operator tree whose inner nodes are labeled by the relational join operators and whose leaves are labeled by base relations. The computation of the result of a join tree is always carried out in a computed bottom-up fashion. The nodes of the join trees are usually annotated to reflect the type of join-algorithm used. These generally include algorithms such nested loops, hash, sort merge and so on. It should be noted that some of the binary trees on the relations of the query are not actually join trees since they may involve the use of Cartesian products.

[00187] The query graphs and join trees are two different forms of representing a given query. A query graph merely represents a collection of relations and their corresponding predicate expressions. It does not specify any evaluation order for the expressions involved. On the other hand, a join tree specifies clearly the inputs to each relational operator, and the order in which how they should be evaluated.

[00188] FIG. 6 shows a query graph, and two possible operator trees that solve the query.

[heading-00189] 3.4.2 Join Tree Topologies

[00190] Join trees are classified into two major categories, namely linear join trees and bushy join trees. For every join operator in a join tree, if at least one of the two input relations is a base relation, then the join tree is called linear, otherwise it is called bushy. Using this classification, bushy search space is defined as a set of join trees when there is no restriction on the topology of the trees. Similarly a linear search space is defined as a set of join trees where the topology of the trees is restricted to only linear join trees. The linear search space is actually a subset of the bushy search space. Since join trees do not distinguish between right and left subtrees, they are unordered. Since each of the n−1 internal nodes of an unordered tree of n leaves can have two choices, a total of 2ⁿ⁻¹ ordered trees can be generated from such an unordered tree.

[00191] The number of alternative join trees exponentially increases when considering the various implementation algorithms available for each join operator in the tree. Some of the commonly used join algorithms are hash-join, nested-loop and merge-scan. For example, for a query graph involving n relations where each join has x alternative implementation schemes available, then for each query tree which was previously unordered, one can generate a pool of xⁿ⁻¹ ordered trees.

[heading-00192] 3.4.3 Structured Query Graphs

[00193] When presented with an arbitrary query graph, finding the total number of valid join trees is a computationally intractable problem. On the other hand, when the topology of the query graph is “structured”, it is relatively easy to find the exact number of join trees using standard combinatorial methods [Lanzelotte et al., 1993]. The number of unlabeled binary trees is shown in [Knuth, 1968]to be equal to the Catalan number. Three well known query graph topologies, string, completely connected and star query graphs are discussed below.

[00194] String Query: Both end nodes of a string query have degree 1 and all other n−2 nodes have degree 2 as shown in FIG. 7. String queries are frequently encountered

[00002]

TABLE 2
Number of join trees for structured query graphs.
			Completely
	Search Space	String Query	Connected	Star
	Linear join trees	2n-2	n!	(n-1)!
	Bushy join trees	( 2 ⁢ n - 2 ) ! n ! ⁢ ( n - 1 ) !	( 2 ⁢ n - 2 ) ! ( n - 1 ) !	(n-1)!

in the verification of foreign key relationships and in object-oriented database environments.
Completely Connected Query:

[00197] This is also known as a clique. These type of query graphs are not usually found in day to day operations of a DBMS. The main use of such a graph is as a test case for its large number of evaluation orders. It is clear that the query graph for a completely connected query of n relations, has n nodes of degree n−1. Since every node of this graph is connected to every other node, these graphs are also called complete or n−1 regular graphs. FIG. 8 depicts a clique on four nodes.

[heading-00198] Star Query:

[00199] Online analytical processing (OLAP) applications often use star queries. In the query graph of a star query of n relations, there are n−1 nodes with degree 1 and one central node with degree n−1 as shown in FIG. 9. It is interesting to note that for a star query, all valid join trees involve join operators that have at least one operator as a base relation. Hence in a star query, the number of bushy search space is the same as the linear join tree search space.

[00200] For the three query graph topologies discussed above, namely string, completely connected and star the exact number of unordered linear and bushy join trees is listed in Table 2.

[heading-00201] 3.5 Join Tree Selection Methods

[00202] Optimal join tree selection is a search problem which depends on the three factors, namely the join tree search space, the coat model and the search strategy or search algorithm. The join tree search space contains all valid join trees, both bushy and linear. The cost model is usually a simple mathematical model that annotates a cost to each operator in the tree. The search algorithm is the actual procedure that finds the optimal join tree in the search space using the cost model. Most of the modern-day query optimizers use three different search strategies, namely (a) exhaustive search (b) probabilistic techniques (c) non-exhaustive deterministic algorithms.

[heading-00203] 3.5.1 Exhaustive Search

[00204] Exhaustive search is sometimes efficient when the join tree search spaces are not too large. For most of the relational queries this should be less than ten relations. There are two different exhaustive search techniques commonly in use. These are namely, dynamic programming and transformation-based search methods. Dynamic programming and transformation-based search are also known as the bottom-up and top-down search methods.

[00205] 1. Dynamic Programming: Early database systems such as System R described in [Salinger et al., 1979] and Starburst described in [Hasan and Pirahesh, 1988, Ono and Lohman,1990] used dynamic programming to find optimal join trees or query evaluation plans. This strategy is very simple and easy to comprehend. The dynamic programming algorithm first considers the individual base relations in a bottom-up fashion and adds new relations until all pairs of relations are joined to generate the final result. A table for storing the intermediate result sizes is maintained so that the sequence of the next join operation can be determined based on the cheapest alternative currently known.

[00206] 2. Transformation-based: The Volcano query optimizer and the Cascades described in [Graefe, 1995] query optimizer use the transformation based exhaustive search approach. This strategy works by applying various transformation rules to the initial query tree recursively until no new join trees are generated. These optimizers use an efficient storage structure for storing the information about the partially explored search space, in order to avoid generating the same query trees.

[heading-00207] 3.5.2 Probabilistic Algorithms

[00208] Finding a globally optimal join tree in a very large search space, specially in a bushy search space involving more than 10 relations, is usually a difficult problem. One approach is to use probabilistic algorithms to eliminate the less promising portions of the search space. These algorithms improve the search performance by avoiding the worst join trees during the search process, instead of looking for the best join tree. A number of different probabilistic algorithms such as Iterative Improvement (II) [Swami and Gupta, 1988], Simulated Annealing (SA) [Ioannidis and Wong, 1987]and their variations Toured Simulated Annealing (TSA) [Lanzelotte et al., 1993] and Two Phase Optimization (2PO) [Ioannidis and Kang, 1990] are currently in use for searching large query tree search space. All these algorithms are based on rewriting join trees based on the algebraic properties of the join operator such as commutativity and associativity in order to generate alternative query trees.

[00209] All of the above probabilistic algorithms look for an optimal join tree in the following manner. First, an arbitrary join tree is generated by the algorithm to represent the given query. Then, applying the logical transformation rules, new join trees are generated. For each new join tree, using a simple cost model, the algorithm computes an estimated cost. The new join tree is retained as the current solution, if the cost is found to be below a specified value. The transformation rules are applied again on the current solution to generate new join trees in a recursive manner. This recursive process is carried out until a stopping condition, such as a time limit or level of cost improvement, is met.

[00210] The algorithm TSA finds the optimal join tree by performing simulated annealing repeatedly. Each time the algorithm picks a new query tree as its starting point. The 2PO algorithm combines the features of the II algorithm and the SA algorithm. It first performs II for a given period of time, then using the output from the II phase as its starting query tree, it performs SA until the final globally optimal query tree is obtained.

[heading-00211] 3.5.3 Non-exhaustive Deterministic Algorithm

[00212] An efficient non-exhaustive deterministic algorithm using a block-wise nested-loop join algorithm was first proposed in [Ibaraki and Kameda, 1984]. This algorithm generates optimal linear join trees, especially for acyclic queries. A variant of this algorithm was described in [Boral and Zaniolo, 1986], in which the search strategy employs an arbitrary join algorithm based on the available access paths instead of a nested-loop join algorithm.

[heading-00213] 3.6 Statistical Estimations in Database Systems

[00214] The quantitative properties or statistics that summarize the instances of a database are important for query optimization. In this section the major estimation techniques used to obtain the database statistics that have some commonalities with the present invention are reviewed.

[00215] Query optimization is an NP-hard problem due to the exponential growth of the number of alternative QEPs with the number of relations in the query. Due to this reason, most database systems are forced to make a number assumptions in order to quickly select an optimal QEP. Christodoulakis investigated the relationships of a number of frequently used assumptions and the accuracy of the query optimizer [Christodoulakis, 1983a, Montgomery et al., 1983]. In specific, he considered the following issues in his study:

• [00216] 1. Uniformity of attribute values: Every attribute value in the corresponding value domain has the same frequency.
• [00217] 2. Attribute independence: The data distributions of various attributes in a relation are independent of each other. The value of two attributes (say A and B) are independent if the conditional probability of an A value given a B value is equal to the probability of obtaining the A value by itself.
• [00218] 3. Uniformity of queries: Queries reference all attribute values in a given attribute value domain with equal probabilities.
• [00219] 4. Constant number of records per block: The number of tuples in each file block is the same. Hence the probability of referencing any block is 1/B, where B is the number of blocks.
• [00220] 5. Random placement: The probability of a record in a file appearing in a query is the same, regardless of its location among the different pages of a disk. That is, the probability of referencing any tuple is 1/N, where N is the number of tuples.

[00221] One can easily observe that assumptions 1 and 2 have a direct relationship to the estimates of the sizes of plan operations, thus determine their accuracy. Similarly assumption 3 impacts the size estimate of queries that are associated with a given parameter, as well as the physical database design problems. Assumptions 4 and 5 affect the estimation of logical block accesses for a given attribute value,

[00222] Though these statistical assumptions simplify the factors involved in the estimation of the cost of a QEP, they also decrease accuracy of these estimates. In order to increase the estimation accuracy, some modem query optimizers incorporate more detailed cost models for assumptions 1 and 2. Few optimizers incorporate assumptions 3, 4, and 5 in more detail, since these assumptions are more difficult to analyze.

[00223] Christodoulakis studied the effects of the above assumptions on a number of frequently encountered problems such as the estimation of the (1) number of block accesses for a given number of tuples, (2) number of block accesses for all queries on a given attribute, (3) number of block accesses for queries with multi-attributes, and (4) number of distinct attribute values resulting from a selection operation. Using these studies, he proved that the expected cost of a query estimated using these assumptions is an upper bound on the actual cost of the QEP. For example, he showed that the uniformity and independence assumptions lead to a worst-case estimate for the number of distinct attribute values. He further demonstrated that most commercial database systems using these assumptions are prone to use expensive query evaluation strategies. This indicates that non-uniformity, non-independence, and non random placement that usually exist in a real-world data distribution could be exploited in a query optimizer in order to reduce the system cost. He also argued that optimizers that use these often erroneous assumptions tend to ignore direct access structures because these cost estimates often favor the simpler structures. His investigation in this area was a catalyst in motivating further research in this area for better result size estimation techniques. He also discussed a number of mathematical techniques such as Schur concavity [Marshall and Olkin, 1979] in database performance evaluation,

[00224] The size estimation of select and join queries on a heavily skewed data distribution were thoroughly investigated by Montgomery et al [Montgomery et al., 1983]. In this study, they estimated the result sizes of select and join operations using uniformity assumptions and compared them with the actual result sizes. They also constructed a few models of size estimation using formulae that closely describe the skewed data distributions under study. They reported that the size estimates for the select operations based on the widely used uniformity assumption actually overestimate the actual result size by 200-300%. The size estimates for the join operations were reported to be 200-300% lower than the actual join sizes.

[00225] The local and distributed cost models based on the uniformity assumption that is used for single table sorting and two table joins in R* were experimentally verified and validated in [Mackert and Lohman, 1986a, Mackert and Lohman, 1986b]. They also further reported that the CPU costs are usually a significant portion of the overall, cost for sort operations. In addition, they also found that size estimation is a significant issue in the overall cost, including I/0 and CPU costs. Considering the nested loop join method, they reported that most query optimizers based on uniformity assumption overstate the evaluation cost, when an access structure is used to retrieve the attribute values and when the inner table fits in main memory. This indicates that the cost of evaluating the nested loop join is usually sensitive to parameters such as join cardinality, the outer table's cardinality, and the memory used to maintain the inner table.

[00226] The relationship of join selectivity and the selection of the optimal nesting order involving four and five variable queries were studied by Kumar and Stonebraker [Kumar and Stonebraker, 1987]. A query processor that behaves similarly to the System R optimizer was built. This query processor considered the nested loop and merge scan join algorithms, using only two-way joins. It also considered the availability of any secondary indexes on the inner join table. The sensitivity of a query with respect to changes in the joint selectivity was derived. This was obtained as the ratio between the cost of the optimal evaluation plan and the plan used by the query processor. They found that most optimal evaluation plan under varying selectivities was either the one that minimizes the average cost ratio or the one that minimizes the maximum cost ratio. Using the sensitivity factor as a parameter, they further measured the sensitivity of four and five variable queries under a number of join selectivities. Their experimental results showed that, assuming the query evaluation plan was selected using their criteria, the best query evaluation plan is usually insensitive to changing join selectivities.

[00227] The relationship of the assumption of random placement of tuples to pages and the dependence of multiple attribute values were investigated by Vander Zander et al. [Vander Zander et al., 1986]. A query of the form, “Select the tuples from relation R where R.A=constant” when R is clustered according to another attribute, say B, was used for this type of experiments. They found that whenever there is a high correlation between the attributes A and B, the assumption of random placement of tuples to pages is always violated. This was evident from the skewed pattern of tuple distributions to the pages.

[00228] Recently in [Ioannidis and Christodoulakis, 1991] proved that the worst case errors incurred by the uniformity assumption propagate exponentially as the number of joins in the query increase. As a result, except for very small queries, errors may become extremely high, resulting in inaccurate estimates for result sizes and hence for the execution costs.

[00229] Despite the overwhelming evidence that most of the common assumptions either overestimate or underestimate the true statistics by a wide margin, the query optimization literature abounds with a variety of estimation techniques, most of them discussed in the extensive survey by Mannino, Chu, and Sager [Mannino et al., 1988]. The various estimation techniques can be grouped into four broad classes as follows:

• [00230] 1. Probabilistic counting techniques
• [00231] 2. Sampling based techniques
• [00232] 3. Parametric techniques
• [00233] 4. Non-parametric techniques
  3.6.2 Probabilistic Counting Techniques

[00235] The probabilistic counting techniques are useful for estimating the number of distinct attribute values in the result of projecting a relation over a given subset of attributes. Flajolet and Martin [Flajolet and Martin, 1985] proposed a technique for estimating the number of distinct values in a multi-set, which generates an estimate during a single pass through the data. This technique was extended by Shukla et al for estimating the size of multidimensional projections such as the cube operator [Shukla et al., 1996]. Their experiments have shown that these techniques based on multidimensional projections usually result in more accurate estimates than sampling based techniques. The applicability of these techniques to other operators has not yet been resolved.

[heading-00236] 3.6.2 Sampling based Techniques

[00237] Sampling based techniques are mainly used to compute result estimates during query optimization time. They compute their estimates by collecting and processing random samples of the data The major advantage of these techniques is that since they do not rely on any precomputed information about the data, they are not usually affected by database changes. Another advantage is that they do not require any storage overhead. These techniques also provide a probabilistic guarantee on the accuracy of the estimates. The major disadvantages of these techniques include the disk I/Os, CPU overhead during query optimization and the extra overhead for recomputing the same information since they are not preserved across queries. The sampling based techniques are highly desirable whenever a parameter needs to be estimated once with high accuracy in a dynamic environment. One good example is in the context of a query profiler. A number of different methods on the sampling based techniques have been extensively discussed in the Prior Art literature.

[00238] Traditionally the sampling based size estimation techniques use two distinct models, namely, point space model [Hou et al., 1991] and urn model [Lipton et al., 1990] for result size estimation. These size estimation techniques can be classified into random sampling and systematic sampling.

[00239] The idea behind the random sampling technique is that the tuples are chosen randomly from their set so that every tuple has an equal probability of being chosen. The random sampling techniques are either random sampling with replacement or random sampling without replacement. In random sampling with replacement, a tuple that is drawn randomly is put back into the data set and available for subsequent selections. But, in random sampling without replacement, any selected tuple is not returned to the original data set.

[00240] In systematic sampling technique, all the tuples in a sampled block or page are be used as sampled tuples. This obviously increases efficiency by reducing the number of I/O operations. But its accuracy is highly related to the uniformity of data across blocks. This means, whenever the tuples are clustered, sampled data could become highly biased resulting in increased estimation error [Hou et al., 1991].

[00241] Most of the sampling techniques used in modern-day database systems are based on random sampling with replacement. Some of the widely used techniques are discussed briefly in the following sections.

[heading-00242] 3.6.3 Adaptive Sampling

[00243] Adaptive sampling technique and its variants were proposed in [Lipton et al., 1990]. This technique expresses the stopping condition for sampling in terms of the sum of samples and the amount of sample taken. They provide an asymptotic efficiency of their algorithm and discuss the practicality of their method for estimating the result sizes of select and join operations. Their method provides a bound on the sample size necessary to obtain a desired level of estimation accuracy, providing sanity bounds to handle queries for which the underlying data distribution is skewed.

[heading-00244] 3.8.4 Double Sampling

[00245] In Double sampling technique [Hou et al., 1991], sampling is divided into two phases. In the first phase, x number of tuples are sampled. These samples are used to obtain the estimated mean and variance and to compute the number of samples y to be obtained in the second phase. The number of samples y is computed based on the desired level estimation accuracy, confidence level, and the estimated mean and variance obtained in the first phase. If y>x, then an additional y−x samples are obtained during the second phase of sampling. Otherwise, the number of samples, x, obtained in the first phase is sufficient to provide the desired level of estimation accuracy and confidence level.

[heading-00246] 3.6.5 Sequential Sampling

[00247] Sequential sampling is a random sampling technique for estimating the sizes of query results [Hass and Swami, 1992]. This is a sequential process in which the sampling is topped after a random number of steps based on a stopping criterion. The stopping criterion is usually determined based on the observations obtained from the random samples so far. For a sufficient number of samples, the estimation accuracy is predicted to lie within a certain bound. The method is asymptotically efficient and does not require any ad hoc pilot sampling or any assumptions about the underlying data distributions.

[heading-00248] 3.8.8 Parametric Techniques

[00249] Parametric techniques use a mathematical distribution to approximate the actual data distribution A few popular examples include the uniform distribution, multi-variate normal distribution or Zipf distributions. The parameters used to construct the mathematical distribution are usually obtained from the actual data distributions, and consequently the accuracy of this parametric approximation mainly depends on the similarity between the actual and parameterized distributions. Two major advantages of the parametric technique are (a) their relatively small overhead and (2) small run-time costs. But their downside is that the real-world data hardly conform to any simple mathematical formula. Consequently parametric approximations often result in estimation errors. Another disadvantage of this method is that since the parameters for the mathematical distribution are always precomputed, this technique results in further errors whenever there is a change in the actual data distribution.

[00250] An interesting variant of this approach is the algebraic technique, where the actual data distribution is approximated by a polynomial function. Regression techniques are usually used to obtain the coefficients of this polynomial. Another promising algebraic technique involves adaptively approximating the distribution by a six-degree polynomial, whose coefficients are obtained dynamically based on a query feedback mechanism [Gelenbe and Gardy, 1982]. The main disadvantages in using the above noted algebraic techniques include the difficulties in choosing the degree of the polynomial model and uniformly handling result-size estimates for operators other than simple selection predicates, Some of the positive results obtained in the work of Wei Sun et al [Sun et al., 1993]on algebraic techniques indicate that they have a potential of generating closely matching parametric distributions.

[00251] The uniform distribution is the simplest and applies to all types of variables, from categorical to numerical and from discrete to continuous. For categorical or discrete variables, the uniform distribution provides equal probability for all distinct categories or values. In the absence of any knowledge of the probability distribution of a variable, the uniform distribution is a conservative, minimax assumption. Early query optimizers such as System R relied on the uniformity and independence assumptions. This was primarily due to the small computational overhead and the ease of obtaining the parameters such as maximum and minimum values.

[00252] The use of the uniform distribution assumption has been criticized, however, because many attributes have few occurrences with extreme values. For example, few companies have very large sales, and few employees are very old or very young. The Zipf distribution has been suggested by Fedorowicz [Fedorowicz, 1984, Fedorowicz, 1987] and Samson and Bendell [Samson and Bendell, 1983] for attributes with a skewed distribution such as the occurrence of words in a text.

[00253] Christodoulakis [Christodoulakis, 1983b] demonstrated that many attributes have unimodal distributions that can be approximated by a family of distributions. He proposed a model based on a family of probability density functions, which includes the Pearson types 2 and 7, and the normal distributions. The parameters of the models such as mean, standard variation, and other moments are estimated in one pass and dynamically updated. Christodoulakis demonstrated the superiority of this model over the uniform distribution approach using a set of queries against a population of Canadian engineers.

[00254] Faloutsos [Faloutsos et al., 1996] showed that using multi-fractal distribution and 80-20 law, one better approximates real-world data than with the uniform and Zipf distributions. His method also provides estimates for supersets of a relation, which the uniformity assumption based schemes cannot provide.

[heading-00255] 3.6.7 Non-parametric or Histogram-based Techniques

[00256] In order to avoid the restrictions of particular parametric methods, many researchers have proposed non-parametric methods for estimating a distribution. The oldest and most common of these methods is the histogram. These techniques approximate the underlying data distribution using precomputed histograms. They are probably the most common techniques used in the commercial database systems such as DB2, Informix, Ingres, Microsoft SQL Server, Oracle, Sybase, and Teradata—see Table 3. The essence of the histogram is to divide the range of values of a variable into intervals, or buckets and, by exhaustive scanning or sampling, tabulate frequency counts of the number of observations falling into each bucket. The frequency counts and the bucket boundaries are stored as a distribution table. The distribution tables are used to obtain upper and lower selectivity estimates. Within those bounds, a more precise estimate is then computed by interpolation or other simple techniques. Since the histograms are precomputed, they often incur errors in estimation if the database is updated and hence require regular re-computation. It has been shown

[00002]

TABLE 3
Histograms used in commercial DBMSs.
Vendor	Product	Histogram Type
IBM	DB2-6000 (Client-Server)	Compressed(V, F) Type
IBM	DB2-MVS	Equidepth, Subclass of End-
		Biased(F, F)
Oracle	Oracle7	Equidepth
Sybase	System 11	Equidepth
Tandem	NonStop SQL/MP	Equidepth
NCR	Teradata	Equidepth
Informix	Online Data Server	Equidepth
Microsoft	SQL Server	Equidepth

that significant effort is required to identify the correct form of histograms that incur small errors for all estimation problems.

[00258] Most of the database research on histograms is in the context of simple elementary relational operations such as selections. One of the first works on histograms was by Piatetsky-Shapiro and Connel where they analyzed the effect of histograms on minimizing the error for selection queries [Piatetsky-Shapiro and Connell, 1984]. These histograms involved two distinct classes, namely, equi-width histograms and equi-depth histograms [Kooi, 1980]. One of their major results is that the worst-case and average case errors in both the equality and range selection queries are usually smaller in the equi-depth histograms than the equi-width histograms.

[00259] Extending the work of Kooi, [Muralikrishna and Dewitt, 1988] investigated the use of multi-dimensional equi-depth histograms for result size estimations. Multidimensional attributes are very common in geographical, image and design databases. A typical query with a multidimensional attribute is to find all the objects that overlap a given grid area. By building histograms on multiple attributes together, their techniques were able to capture dependencies between those attributes. They proposed an algorithm to construct equal-height histograms for multidimensional attributes, a storage structure, and two estimation techniques. Their estimation methods are simpler than the single-dimension version because they assume that multidimensional attributes will not have duplicates.

[00260] Many other related works have been done using variable-width histograms for estimating the result size of selection queries, where the buckets are chosen based on various criteria [Kamel and King, 1985, Kooi, 1980, Muthuswamy and Kerschberg, 1985]. A detailed description of the use of histograms inside a query optimizer can be found in Kooi's thesis [Kooi, 1980]. It also deals with the concept of variable-width histograms for query optimization. The survey by Manning, Chu, and Sager [Mannino et al., 1988] provides a list of good references to work in the area of statistics on choosing the appropriate number of buckets in a histogram for sufficient error reduction. Again this work also mainly deals with the context of selection operations.

[00261] Merrett and Otoo [Merrett, T. H., and Otoo, E., 1979] showed how to model a distribution of tuples in a multidimensional space. They derived distributions for the relations that result from applying the relational algebraic operations.

[00262] In their work, a relation was modeled as a multidimensional structure where the dimension was equal to the number of attributes in the relation. They divided each dimension, i, into c_i number of equal width sectors. The values for c_i, 1≦i≦n, are chosen such that the resulting structure can completely fit into the available memory, where n is the dimension of the multidimensional array. Scanning through the relation for each attribute, the cells of the multidimensional structure are filled with integer numbers corresponding to the number of tuples that occupy the respective value ranges of the attributes.

[00263] Denoting the value of the count for a cell (a, b) of relation R(A, B) as d^AB_ab(R), and assuming uniformity of tuples within each cell, they showed that the expected number of tuples within a cell from a projection is, $d_a^A\left(R\left[A\right]\right)=n\left[1-{\left(1-\frac{1}{n}\right)}^{d_a^A\left(R\right)}\right].$

[00264] Using the multidimensional representation, they show that the number of tuples resulting from joining a sector a₁ of R and a₂ of S is equal to, $d_{a_1\bigcap a_2\mathrm{bc}}^{\mathrm{ABC}}\left(Q\right)=\frac{{\mathrm{nd}}_{a_{1}b}^{\mathrm{AB}}\left(R\right)d_{a_{2}c}^{AC}\left(S\right)}{n_1{n}_2},$
where n₁ is the number of values in sector a₁, n₂ is the number of values in sector a₂, n is the overlap between a₁ and a₂, and b and c are the remaining attributes in the respective relations.

[00266] The above value for the join is valid only when the two cells from the relations have overlapping sectors on the joining attribute. The above join estimation depends on the number of overlapping attribute values, n. Since there is no way to compute the value of n, they resort to estimate it based on how the two sectors overlap along the joining attributes. They showed that there are 11 possible ways in which the sectors can overlap. By defining a rule to approximately guess the value for n for each of the 11 possible ways of overlap, they show how to estimate the result size of join from two cells.

[00267] Estimating the result sizes of selection operations using the equi-width histogram is very simple. The histogram bucket where the attribute value corresponding to the search key lies is selected. Then the result size of the selection operation is simply the average number of tuples in that bucket. But the main problem with this simple strategy is that the maximum estimation error is related to the height of the tallest bucket. Consequently a data distribution with widely varying frequency values will result in very high estimation error rate. Another problem associated with the equi-width histogram is that there are no proven statistical method to choose the boundaries of a bucket as this would require some prior knowledge about the underlying data distribution. This invariably has an effect on the estimation accuracy of the selection operations.

[00268] Fortunately there are some statistical techniques that can be used to select the bucket widths or the number of buckets based on the number of tuples in the attribute value domain being mapped. During early days of statistical analysis of data using histograms, a popular rule known as Sturge's rule was used to obtain the number of buckets. The Sturge's rule, based on the binomial distribution, states that the number of buckets for n tuples is equal to 1+log₂n, which is a reasonably accurate value under most circumstances. The modern statistical techniques provide more optimal rules for any given attribute value domain and error rates [Tapia and Thompson, 1978]. It is important to note that the simple Sturges' rule usually yields estimation results which are closer to the modern statistical techniques for up to 500 tuples. The modern statistical literature also provides a number of parameters such as the mean error rate and mean-squared error rate, which are very useful in computing the size of the error within a multiple of a power of the given attribute value domain without any further knowledge of the data distribution. Although the equi-width approach is very simple to implement, its asymptotic accuracy is always lower than the estimation accuracy of the most modern techniques, including the kernel and nearest neighbor techniques [Tapia and Thompson, 1978]. It has been shown in [Tapia and Thompson, 1978] that the asymptotic mean-squared error obtained using the equi-width approach is O(n^−⅔), while that of the more recent methods are O(n^−⅘) or even better.

[00269] In the equi-width. histogram, proper choice of the bucket width usually results in an optimal estimation error rate. Similarly, in the equal-height histogram method, the result size estimation error is directly related to the height of the histogram buckets. A strategy known as the nearest neighbor method in the field of density estimation, in which the bucket height is kept the same over the entire attribute value domain, is optionally used to control the estimation error in the equal-height method by varying the number of buckets. The main problem with this approach is that some prior knowledge about the data distribution is required in order to construct the sector widths so as to guarantee that same number of tuples falling in each bucket. One common approach is to arrange the attribute value in an ascending or descending order, and to then set the bucket boundaries at every k^th attribute value. A less expensive approach would be to employ some sampling techniques to approximately set the bucket boundaries. It has been shown that the estimation accuracy and performance improve asymptotically by allowing buckets to have overlapping attribute value ranges.

[00270] The above technique was further improved in [Moore and Yackel, 1977], by applying the large-n properties. They showed that by allowing some adjustment for the differences between two methods, using the large-n theorem for one method, it is possible to translate it into a large-n theorem for another estimation method without any additional proof.

[00271] Another type of histogram method, often known as variable kernel technique in the density estimation field, uses a partitioning strategy based on criteria other than the equal frequency. Mathematical analysis of the variable kernel technique has been found to be difficult.

[00272] Lecoutre showed how to obtain a value of the cell width for minimizing the integrated mean squared error of the histogram estimate of a multivariate density distribution [Lecoutre, Jean-Pierre, 1985]. By considering a density estimator based on k statistically equivalent blocks, he further proved the L² consistency of this estimator, and described the asymptotic limiting behavior of the integrated mean square error. He also gave a functional form for the optimum k expressed in terms of the sample size and the underlying data distribution.

[00273] A similar technique was proposed by Scott for choosing the bin-width based on the underlying data distribution [Scott, David, 1979]. But his procedure assumes a Gaussian reference standard and requires only the sample size and an estimate of the standard deviation. He also investigated the sensitivity of this procedure using several probability models that violate the Gaussian assumption.

[00274] Using a maximal difference criterion, Christodoulakis [Christodoulakis, 1981] proposed a variable-width histogram, This utilized a uniformity measure for selecting the bucket ranges. This maximal difference criterion brings together attribute values that have a similar ratio of tuples. In other words, the criterion states the maximum and minimum proportions of the attribute values in the bucket must be less than some constant, which is usually based on the individual attribute. He further showed that this criterion reduces the estimation error on all attribute values. This strategy seems most applicable where queries are not uniformly spread over the attribute value domain.

[00275] Another method proposed by Kamel and King [Kamel and King, 1985]is based on pattern recognition to partition the buckets of variable-width distribution tables. In pattern recognition, a frequently encountered problem is to compress the storage space of a given image without distorting its actual appearance. This problem is easily restated in the context of the selectivity estimation problem to partition the data space into nonuniform buckets that reduce the estimation error using an upper bound on storage space. The idea is to partition the attribute domain into equal-width buckets and compute a homogeneity measure for each bucket. The homogeneity is defined as the measure of the non-uniformity or dispersion around the average number of occurrences per value in the cell. The value of homogeneity for a given bucket is computed by a given function or by using sampling techniques.

[00276] A number of multivariate analogs of the equal-width and equal-height methods is found in the density estimation literature. Considering the equi-width case, a two or three dimensional cells of equal area or volume can be partitioned, in the joint attribute value domain. The number of tuples with combined values in each cell is obtainable. Considering the equi-depth case, variable width buckets, each with approximately, say x, nearest neighbors, can be derived, The difficulty in this multiattribute situation is that the shape of the cell must also be selected. A square or a cube is a natural choice, when dealing with the equi-width analog. When the range or variation of one attribute's values is smaller than another's, a rectangular shaped cell is an obvious choice.

[00277] Ioannidis and Christodoulakis proposed optimal histograms for limiting worst-case error propagation in the size of join results [Ioannidis and Christodoulakis, 1992]. They identified two classes of histograms, namely, serial and end-biased histograms that are associated with optimal worst-case error for join operations. End-biased histograms are frequently encountered in modern-day database systems. By considering simple t-clique queries, where queries involve only equi join operations without any function symbols, they showed that the optimal histograms for reducing the worst-case error is always serial. They also further showed that for t-clique queries with a large number of joins, high-biased histograms, which are a subclass of end-biased, are always optimal. The main disadvantage of the serial histograms are that the attribute values need to be sorted with respect to their respective frequencies before being assigned to buckets.

[00278] Ioannidis et al. [Ioannidis and Poosala, 1995] discussed the design issues of various classes of histograms and balancing practicality and optimality of them in the use of query optimization. They also investigated various classes of histograms using different constraints such as V-Optimal, MaxDiff, Compressed, and Spline-based, and sort and source parameters such as Frequency, Spread, and Area. They further provided various sampling techniques for constructing the above histograms and concluded that the V-optimal histogram is the most optimal one for estimating the result sizes of equality-joins and for selection predicates.

[heading-00279] 3.7 Patents

[00280] Many methods of query optimisation for use in data base systems are known. The purpose of research in this area is to improve performance for large database systems. For example, a histogram of the data or of sampled data within the database is often used to estimate sizes of results of operations in order to determine a good approach to follow in processing a complex query.

[00281] In U.S. Pat. Nos. 5,864,841 and 5,664,171 to Agrawal, a method is presented for ordering data within a data set in order to produce a histogram or other data representation thereof. It is important that a method of ordering data exists or the term range has little meaning. A range is often defined as a grouping of elements having a property defining an order thereof. A contiguous range is defined as a grouping between two or more points in an ordered set. Once the ordering is determined, a histogram can be formed from the data The method of ordering the data is repeatable and is therefore repeated when order is unknown.

[00282] In U.S. Pat. No. 5,689,696 to Gibbons et al. a method of generating a high biased histogram is presented. The method comprises the steps of filtering the elements within a data set to eliminate those elements having associated values below a threshold. The histogram is formed from the remaining, unfiltered, elements. Unfortunately, though such a system is advantageous in some query optimisation processes, it is not applicable in a broad range of query optimisation problems. Because of the biasing, some statistical knowledge of search parameters and statistical distribution of data are necessary in order to maximise the benefits derived from such a method when used for query optimisation.

[00283] In U.S. Pat. No. 5,870,752 to Gibbons et al. a method of maintaining buckets or bins within an histogram is presented. The method comprises the steps of splitting a bucket into two adjacent buckets when more than a predetermined number of tuples—aggregate value—results for the bucket. Consider for example the case, when a range of ages from 25 to 29 a bucket is formed. A club has 140 members within that age range, that bucket, and the maximum number of members within any given bucket is 140. Addition of another member results in the bucket being split into two buckets. Unfortunately, though this limits bucket size, it does not provide any additional information relating to a single element within a bucket. In particular, limiting bucket size is an attempt to produce ranges wherein elements are more closely correlated. That said, the additional correlation is not truly present, and within a single range many very different values may be placed.

[00284] As an example, consider the above bucket with 140 members. It is unknown whether one age element, for example 28, has 140 members or zero members. When the bucket is split, it remains unknown whether or not there are any members of 28 years of age. Thus, there may be considerable estimation error using the method disclosed by Gibbons et al.

[00285] Another approach to query optimisation relates to limiting duplicate operations in order to determine a best approach to execute a search query. In U.S. Pat. No. 5,659,728 to Bhargava et al., a method of query optimisation based on uniqueness is proposed.

[00286] In U.S. Pat. Nos. 5,469,568; 5,542,073; and 5,761,653 issued to Schiefer et al., methods for determining join selectivities based on selecting a result for “equivalent” join operations as the largest of possible results is proposed. The methods outlined are intended to improve effectiveness of approximations used during a query optimisation process.

[00287] Clearly, there are advantages to improving the quality of estimates based on which query optimisation is performed. Optimally, each stage of query optimisation is provided with accurate data. Unfortunately, such an approach requires solving each possible operation, which in effect, obviates query optimisation. Therefore, enhancing accuracy of estimates provided to a query optimiser without incurring prohibitive processing costs is essential.

[00288] It is an object of the present invention to provide a method of generating a histogram of data within a data set.

[00289] It is a further object of the invention to provide the histogram with ranges, bins, wherein data elements within the range are associated with values having only a determinable variance from a mean of the values associated with elements within the range, such that each value within the bin is within known tolerances of the mean.

[00290] In accordance with the invention there is provided a method of generating a histogram from data elements and their associated values. First a data set is provided representing a plurality of elements and a value associated with each element, the data set having a property defining an order of the elements therein. At least one range is determined, each of the at least one range having at least an element, a mean of each range equal to the mean of the values associated with the at least an element within said range, and an area of each range equal to the product of the mean of said range and the number of elements within said range, a specific range from the at least a range comprising a plurality of elements from the data set adjacent each other within the defined order, wherein the mean of the specific range is within a predetermined maximum distance from a value associated with an element within the specific range, the predetermined maximum distance independent of the number of elements within the specific range and their associated values. Finally, for each range of the at least a range at least a value is stored relating to the mean and at least data relating to the size and location of the range.

[00291] Prior art histograms provide little or no data as to the content of an element within a range. For example, all tuples within the range may be associated with a same single element, resulting in a data set wherein each common element has an associated value of zero excepting the single element with a value equal to the number of tuples within the range, bin. It is evident, then, that for each estimated value, substantial error exists. This error is equal to the mean for each common element and to the number of tuples minus the mean for the single element.

[00292] Since according to the invention at least a value associated with one element is within a predetermined distance from the mean, it is known when using ranges determined according to the invention that the error is the mean for common elements, at most the predetermined distance for the one element, and at most the number of tuples minus the mean minus (the mean minus the predetermined amount) for the single element. This amount of maximum error is less than that resulting from using prior art histograms. Of course, according to several of the embodiments described herein, the maximum error is further restricted in a known fashion.

[00293] Other prior art methods attempt to limit error based on the associated values and the overall number of tuples within a range. For example, it has been suggested to use Parzen windows with a kernel function such as a Gaussian function, over a histogram to improve the resulting data. Though prior art methods may provide further data relating to the accuracy of a histogram, the data is determined based on histogram contents and/or original data content. Accordingly, computational costs in determining the histogram and/or statistical information relating to estimation accuracy are substantial. This has prevented practical application of these methods. According to the invention, the resulting accuracy of some estimates is based on a predetermined value and as such results in substantially reduced computational requirements. As many databases contain many millions of records, reducing computational requirements for processing each element is extremely advantageous.

[00294] For example according to an embodiment, determining at least a range includes the following steps:

• [00295] (a) using a suitably programmed processor, defining a first bin as a current bin;
• [00296] (b) using the suitably programmed processor, selecting an element and adding it to the current bin as the most recently added element to the current bin;
• [00297] (c) selecting an element from within the data set, the selected element not within a bin and adjacent the most recently added element;
• [00298] (d) determining a mean of the values associated with elements within the bin;
• [00299] (e) when the most recently selected element differs from the mean by an amount less than a predetermined amount, adding the most recently selected element to the current bin as the most recently added element to the current bin and returning the step (c);
• [00300] (f) when the selected element differs from the mean by an amount more than the predetermined amount, creating a new bin as the current bin and adding the selected element to the new bin as the most recently added element to the current bin and returning to step (c); and,
• [00301] (g) providing data relating to each bin including data indicative of a range of elements within each bin as the determined at least a range.

[00302] Such a method results in a last element added to a bin being within a predetermined distance of the mean of the values associated with elements in said bin or range. Typically, each element is close to the mean, though a possibility of increasing or decreasing values within a single bin results in a greater possible maximum error than is typical. When the order of element addition to each bin is known, the maximum error is determinable for each element and is different for some elements. This results in a histogram with increased accuracy and a method of analysing limits on accuracy of data derived from the histogram.

[00303] According to another embodiment, determining at least a range includes the following steps:

• [00304] (a) selecting an element from within the data set;
• [00305] (b) determining a bin with which to associate the element;
• [00306] (c) when the determined bin is empty, adding the element to the bin;
• [00307] (d) when the determined bin is other than empty, determining a mean of the values associated with elements within the determined bin;
• [00308] (e) when the most recently selected element differs from the mean by an amount less than a predetermined amount, adding the most recently selected element to the determined bin and returning to step (a);
• [00309] (f) when the selected element differs from the mean by an amount more than the predetermined amount, adding the selected element to the determined bin and dividing the determined bin into one of two bins and three bins, one of which includes the selected element and returning to step (a); and,
• [00310] (g) providing data relating to each bin including data indicative of a range of elements within the bin.

[00311] According to the above embodiment, it is possible to then merge adjacent bins in accordance with the following steps:

• [00312] determining a first mean of a first selected bin;
• [00313] determining a second mean of a second selected bin adjacent the first selected bin;
• [00314] comparing the first and second means; and,
• [00315] when the means are within a predetermined distance of each other, merging the first selected bin and the second selected bin to form a single merged bin including all the elements of the first selected bin and all the elements of the second selected bin.

[00316] According to yet another embodiment, determining at least a range includes the following steps:

• [00317] (a) using a suitably programmed processor, defining a first bin as a current bin;
• [00318] (b) using the suitably programmed processor, selecting an element and adding it to the current bin as the most recently added element to the current bin;
• [00319] (c) selecting elements adjacent the most recently added element(s);
• [00320] (d) determining a first mean of the values associated with elements within the bin and determining a second mean of the selected elements;
• [00321] (e) when the second mean differs from the first mean by an amount less than a predetermined amount, adding the most recently selected elements to the current bin as the most recently added elements and returning to step (c);
• [00322] (f) when the second mean differs from the first mean by an amount more than the predetermined amount, creating a new bin as the current bin and adding at least one of the selected elements to the new bin as the most recently added element(s) to the current bin and returning to step (c); and,
• [00323] (g) providing data relating to each bin including data indicative of a range of elements within the bin.

[00324] All of the above embodiments have the property that they reduce the variation of the values associated with the elements within a range. In its most simple mathematical form this is achieved by determining the at least a range in terms of the mean of the elements within the current range, which is a function of well known L₁ norm of the elements in the current range. In other embodiments of the invention the at least a range can be computed using other L_k norms. If a function of L_∞ norm of the values within a range is used, the at least a range can be trivially computed using the maximum and minimum values of the current ranges, thus providing an alternate method to limit the variation of the values of the elements in the range. Various other embodiments of the invention are obtained when functions or other L_k norms are used to determine the at least a range. Implementation of these embodiments is achieved using the Generalized positive-k mean and the Generalized negative-k mean as explained presently.

[00325] According to another embodiment, determining at least a range includes the following steps:

• [00326] (a) using a suitably programmed processor, defining a first bin as a current bin;
• [00327] (b) using the suitably programmed processor, selecting an element and adding it to the current bin as the most recently added element to the current bin;
• [00328] (c) selecting an element from within the data set, the selected element not within a bin and adjacent the most recently added element;
• [00329] (d) determining the Generalized positive-2 mean of the current bin as the square-root of the (sum of the squares of the values associated with elements within the bin divided by the number of the elements within the bin);
• [00330] (e) determining the Generalized negative-2 mean of the current bin as the square of the (sum of the square-roots of the values associated with elements within the bin divided by the number of the elements within the bin);
• [00331] (f) when the value associated with the selected element is lower than the said Generalized positive-2 mean, determining a difference between the value associated with the selected element and the said Generalized positive-2 mean, and when the value associated with the selected element is higher than the said Generalized negative-2 mean, determining a difference between the value associated with the selected element and the said Generalized negative-2 mean;
• [00332] (g) when a difference is other than greater than the predetermined amount, adding the selected element to the current bin as the most recently added element to the current bin and returning to step (c);
• [00333] (h) when a difference is greater than the predetermined amount, defining a new bin as the current bin, adding the selected element to the current bin as the most recently added element to the current bin, and returning to step (c); and,
• [00334] (i) providing data relating to each bin including data indicative of a range of elements within each bin as the determined at least a range.

[00335] According to yet another embodiment, determining at least a range includes the following steps:

• [00336] (a) using a suitably programmed processor, defining a first bin as a current bin;
• [00337] (b) using the suitably programmed processor, selecting an element and adding it to the current bin as the most recently added element to the current bin;
• [00338] (c) selecting an element from within the data set, the selected element not within a bin and adjacent the most recently added element;
• [00339] (d) determining the Generalized positive-k mean of the current bin for a predetermined k as the k^th-root of the (sum of the k^th powers of the values associated with elements within the bin divided by the number of the elements within the bin);
• [00340] (e) determining the Generalized negative-k mean of the current bin as the k^th power of the (sum of the k^th-roots of the values associated with elements within the bin divided by the number of the elements within the bin);
• [00341] (f) when the value associated with the selected element is lower than the said Generalized positive-k mean, determining a difference between the value associated with the selected element and the said Generalized positive-k mean, and when the value associated with the selected element is higher than the said Generalized negative-k mean, determining a difference between the value associated with the selected element and the said Generalized negative-k mean;
• [00342] (g) when a difference is other than greater than the predetermined amount, adding the selected element to the current bin as the most recently added element to the current bin and returning to step (c);
• [00343] (h) when a difference is greater than the predetermined amount, defining a new bin as the current bin, adding the selected element to the current bin as the most recently added element to the current bin, and returning to step (c); and,
• [00344] (i) providing data relating to each bin including data indicative of a range of elements within each bin as the determined at least a range.

[00345] The above two embodiments result in a last element being added to a bin, being within a predetermined distance of the mean of the value associated with the elements in the said bin or range, because the Generalized positive-k mean is always greater than the mean and the Generalized negative-k mean is always less than the mean.

[00346] According to yet another embodiment, obtained when the value of k is increased indefinitely in the above embodiment, determining at least a range includes the following steps:

• [00347] (a) using a suitably programmed processor, defining a first bin as a current bin;
• [00348] (b) using the suitably programmed processor, selecting an element and adding it to the current bin as the most recently added element to the current bin;
• [00349] (c) selecting an element from within the data set, the selected element not within a bin and adjacent the most recently added element;
• [00350] (d) determining a current largest value as the largest of the values associated with elements within the bin;
• [00351] (e) determining a current smallest value as the smallest of the values associated with elements within the bin;
• [00352] (f) when the value associated with the selected element is lower than the current largest value, determining a difference between the value associated with the selected element and the current largest value, and when the value associated with the selected element is higher than the current smallest value, determining a difference between the value associated with the selected element and the current smallest value;
• [00353] (g) when a difference is other than greater than the predetermined amount, adding the selected element to the current bin as the most recently added element to the current bin and returning to step (c);
• [00354] (h) when a difference is greater than the predetermined amount, defining a new bin as the current bin, adding the selected element to the current bin as the most recently added element to the current bin, and returning to step (c); and,
• [00355] (i) providing data relating to each bin including data indicative of a range of elements within each bin as the determined at least a range.

[00356] According to yet another embodiment, determining at least a range includes the following steps:

• [00357] (a) selecting a group of elements within the data set and adjacent one another within the ordering;
• [00358] (b) determining a mean of the values associated with each selected element;
• [00359] (c) comparing a value associated with each selected element in the group to the mean value to determine a difference;
• [00360] (d) when a value is different from the mean by more than a predetermined amount, returning to step (a); and,
• [00361] (f) when all values are different from the mean by less than or equal to the predetermined amount, creating a bin including the selected group of elements and returning to step (a).

[00362] Here, the maximum error is bounded by twice the predetermined distance since the difference is on either side. Again, for each element within a range, a same maximum error exists.

[00363] It is also possible to then grow the group according any of the above methods modified as necessary or using the following steps:

• [00364] (f1) selecting an element adjacent the bin including the selected group of elements, the selected element other than an element within a bin;
• [00365] (f2) determining a mean of the values associated with each element within the bin and the selected element; and,
• [00366] (f3) when the value of the selected element differs from the mean by less than or equal to the predetermined amount, adding the selected element to the bin and returning to step (f1).

[00367] Using a histogram formed according to the invention, maximum possible estimation errors are reduced and a quality of estimates derived from the histogram is predictable. Therefore, when a histogram according to the invention is used as a tool for aiding estimation, advantages result. For example, in database query optimisers, it is useful to have estimates of sizes of data sets resulting from a particular operation. Using a histogram according to the invention allows for more accurate estimation and thus is believed to result in better query optimisation.

[00368] Of course, it is also advantageous that when an estimate results in two or more suitable courses of action, analysis of likely error is additional information for use in distinguishing between courses of action.

[00369] A histogram according to the invention is also useful in network routing, actuarial determinations, pattern matching, and open-ended searching of multiple data bases with limited time.

[00370] According to another embodiment of the invention, the histogram is generated using the following steps:

• [00371] (a) providing a data set representing a plurality of elements and a value associated with each element, the data set having a property defining an order of the elements therein;
• [00372] (b) determining a range within the data set, the range comprising a plurality of elements from the data set and adjacent within the order; and,
• [00373] (c) storing a plurality of values indicative of a straight line defining an approximate upper boundary of the values associated with each element within the range, the straight line indicating different values for different elements within the range.

[00374] Preferably, the plurality of values is indicative of a range beginning, a range ending, a value at the range beginning and a value at the range ending.

[00375] Preferably, a range is determined so as to limit variance between values associated with elements in the range and the straight line in a known fashion, the limitation forming further statistical data of the histogram. For example, a best fit straight line is determined so as to limit average error between some values associated with elements in the range and the best fit straight line in a known fashion. Alternatively, a best fit straight line is determined so as to limit least squared error between some values associated with elements in the range and the best fit straight line in a known fashion.

[00376] According to another embodiment of the invention, the histogram is generated using the following steps:

• [00377] (a) providing a data set representing a plurality of elements and a value associated with each element, the data set having a property defining an order of the elements therein;
• [00378] (b) determining at least one range having a length such that the value associated with at least one element within the range is within a predetermined maximum distance of at least one other element within the range; and,
• [00379] (c) for each range storing at least a value related to an estimate of a value associated with an element within the range and at least data relating to the size and location of the range.

[00380] It is an advantage of the present invention that estimating the size of specific data set ranges and of results of certain queries is more accurate.

[00381] For use in query optimisation, an exact measure of worst case accuracy and average case accuracy is determinable which is further useable by the query optimiser in weighing potential avenues. For example, when many approaches have a same estimated cost for the estimates determined from a histogram but different total costs when an average case error analysis is performed, distinguishing between the approaches is straightforward. Similarly a worst case error analysis is possible.

[00382] It is another advantage of the present invention that resulting histograms provide data relating to ranges in which values are somewhat correlated, even if by chance. For example, actuaries rely on data relating to individuals based on a plurality of different elements—sex, age, weight, habits, etc. Usually, age is divided based on certain statistical principles in increments of complete years or five-year periods, and so forth. Using a histogram generation technique according to the invention resulting, age ranges are based on similarities of values associated with elements within the ranges. This is advantageous in determining ranges for which values associated with elements are similar.

[00002]

List of Figures
1	Query Processing Architecture	221
2	An Annotated Query Tree	222
3	Example Relations from Property Tax Assessor's Office	223
4	Two Alternative Query Evaluation Plans	224
5	Equivalent Transformations.	225
6	Query Graph and its Operator Trees.	226
7	A string query.	227
8	A completely connected query on 4 nodes.	228
9	A star query on 5 nodes.	229
10	Equi-width, Equi-depth and Variable-width Histograms.	230
11	An Example of the Rectangular Attribute Cardinality Map	231
12	Comparison of R-ACM and Traditional Histograms. Note in (a), the	232
	sector widths are equal, in (b) the areas of the sectors are equal, in
	(c) the sector widths become smaller whenever there is a significant
	change in the frequencies of the attribute values.
13	Comparison of Equi-width, Equi-depth Histograms and the R-ACM for	233
	Frequency (Probability) Estimation: Each experiment was run 500,000
	times to get the average percentage errors. Estimation errors are given
	for exact match on a random distribution with 100,000 tuples and 1000
	distinct values. For the R-ACM, tolerance value was τ = 3.
14	Frequency Estimation Error vs ACM Variance: The ACM sectors were	234
	partitioned using three different tolerance values and the resulting
	ACM variances were computed for various data distributions. Using
	random selection queries (matches), the errors between the actual and
	the expected frequencies were obtained.
15	Distribution of Values in an ACM Sector	235
16	(a) A decreasing R-ACM sector; (b) An increasing R-ACM sector; (c)	236
	Superimposition of the decreasing and increasing frequency distributions.
17	Estimation of a Range Completely within an R-ACM Sector	237
18	A Random R-ACM Sector	238
19	Estimation of Equality Select Using the R-ACM	239
20	Estimation of Range Select Using the R-ACM	240
21	Estimation of a Range Completely within an R-ACM Sector	241
22	Estimating Result Size of RX=Y S	242
23	Join Estimation Error and the Positions of Attribute Values	243
24	Zipf Distributions for Various z Parameters	244
25	Generation of a Multi-fractal Distribution - First three steps	245
26	An Example for Constructing the Trapezoidal Attribute Cardinality	246
	Map
27	Trapezoidal ACM sector and its corresponding probability mass function	247
28	Average Case Error in T-ACM	248
29	Comparison of Histogram and Trapezoidal ACM	249
30	Comparison of Histogram and the T-ACM for Probability Estimation:	250
	Each experiment was run 100,000 times to get the average percentage of
	errors in the estimated occurrence of the attribute values. Estimation
	errors are given for exact match on a random distribution with 100,000
	tuples and 1000 distinct values. Both histogram and T-ACM were of
	equi-width type with a sector width of 5 and no of sectors equal to 200.
31	Equality Select Using the T-ACM	251
32	Result Estimation of Range Select Using the T-ACM	252
33	Frequency Distributions of Selected Attributes from the U.S. CENSUS.	254
34	Frequency Distributions of Selected Attributes from the NBA Statistics.	255
35	Estimation Error Vs Variance of the R-ACM: U.S. CENSUS Database	256
36	Construction of a T-ACM	257
37	Generation of a (near) Optimal T-ACM	258
38	Minimizing the Average Estimation Error.	259
39	Finding Optimal T-ACM Sectors.	260
40	Optimizing the T-ACM sectors	261
41	Percentage Estimation Error Vs Boundary Frequencies	262
42	Least Squares Estimation Error.	263
43	Optimal Boundary Frequencies: Least Square Error Method.	264
44	Primary Partitioning of an Attribute Value Domain	265
45	Secondary Partitioning of the Value Domain in Sector 3	266
46	Secondary Partitioning of the Value Domain in Sector 3.	267

[00383] In order to estimate data subset sizes for particular elements or ranges of elements, a data set having a property defining an order of the elements therein is provided. Each element has an associated value. As discussed above, a histogram of the data set comprises a plurality of ranges of elements within the data set and a mean value for each range. In order for the term range to have meaning, it is required that elements within the data set have ordering of some sort. That does not mean the elements are sorted or stored in an order, but merely that given three or more elements, a same ordering of those elements is predictably repeatable.

[00384] Within each range are a number of elements each having an associated value. Some of the associated values may be zero indicating no tuples associated with a specific element. That said, even when an associated value is zero, the element exists within its range as predictable from an ordering of the elements.

[00385] The present invention provides a method of determining ranges within an improved histogram, an Attribute Cardinality Map. During the process of determining a range, elements within the range are grouped together. Such a grouping is referred to herein and in the claims that follow as a bin. A bin with no elements grouped therein in an empty bin. Once ranges are determined, elements within a single bin form the elements within a single range. As such, bins act as receptacles for elements during a process of range determination.

[00386] An exemplary embodiment is set out below. The embodiment is selected for ease of implementation and quality of estimation results. Many variations of said embodiment are also possible. Some of these are set out following the exemplary embodiment.

[00387] The traditional histograms, namely equi-width and equi-depth histograms have two major drawbacks. First of all, their fundamental design objective does not address the problem of extreme frequency values within a given bucket. For example, in the equi-width case, all the bucket widths are the same regardless of the frequency distribution of the values. This means large variations between one frequency value to the other is allowed in the same bucket, resulting in higher estimation errors. This problem is somewhat reduced in the equi-depth case. But to avoid the extreme frequency values in a given bucket, a single attribute value may need to be allocated to several consecutive locations in the same bucket. This not only increases the storage requirement but also reduces the efficiency of estimation. The second drawback is that the traditional histograms are usually built at run-time during the query optimization phase using sampling methods. This obviously requires an I/O overhead during the optimization phase and tends to increase the overall optimization time. Moreover, unless sufficiently many samples are taken, the histograms built from the sampled data may not closely reflect the underlying data distribution.

[00388] The present invention uses ACM as a new tool for query result-size estimation to address the above drawbacks in the traditional histograms. Specifically, the R-ACM reduces the estimation errors by disallowing large frequency variations within a single bucket. The T-ACM reduces the estimation errors by using the more accurate trapezoidal-rule of numerical integration. Moreover, as both types of ACMs are catalogue based, they are precomputed, and thus will not incur I/O overhead during run-time.

[heading-00389] 5.1 Rectangular Attribute Cardinality Map

[00390] The Rectangular ACM (R-ACM) of a given attribute, in its simplest form, is a one-dimensional integer array that stores the count of the tuples of a relation corresponding to that attribute, and for some subdivisions for the range of values assumed by that attribute. The R-ACM is, in fact, a modified form of histogram. But unlike the two major forms of histograms, namely, the equi-width histogram, where all the sector widths are equal, and the equi-depth histogram, where the number of tuples in each histogram bucket is equal, the R-ACM has a variable sector width, and varying number of tuples in each sector. The sector widths or subdivisions of the R-ACM are generated according to a rule that aims at minimizing the estimation error within each subdivision.

[00002]

TABLE 4
Notations Used in the Work
Sym-
bol	Explanation
xi	Number of tuples in attribute X for the ith value of X.
E(Xi)	Expected number of tuples in attribute X for the ith value of X.
nj	No of tuples in the jth sector of an ACM.
lj	No of distinct values in the jth sector. (Also known as sector width).
s	Number of sectors in the ACM.
τ	Allowable tolerance for an R-ACM
ξ	Size of a relation.
N	Number of tuples in the relation.

[00391] The R-ACM is either one-dimensional or multi-dimensional depending on the number of attributes being mapped. To introduce the concepts formally, the one-dimensional case is first described.

[00392] Definition 1 A One dimensional Rectangular ACM: Let V={v_i:1≦i≦|V|}, where v_i<v_j when i<j, be the set of values of an attribute X in relation R. Let the value set V be subdivided into s number of sector widths according to the range partitioning rule described below. Then the Rectangular Attribute Cardinality Map of attribute X is an integer array in which the j^th index maps the number of tuples in the j^th value range of the set V for all j, 1<j≦s.

[00393] Rule 1 Range Partitioning Rule: Given a desired tolerance value τ for the R-ACM, the sector widths, l_j, 1≦j≦s, of the R-ACM should be chosen such that for any attribute value X_i, its frequency x_i does not differ from the running mean of the frequency by more than the tolerance value τ, where running mean is the mean of the frequency values examined so far in the current sector.

[00394] For example, consider the frequency set {8, 6, 9, 7, 19, 21, 40} corresponding to the values {X₀, X₁, X₂, X₃, X₄, X₅, X₆} of an attribute X. Using a tolerance value τ=2, the attribute value range is partitioned into the three sectors, {8, 6, 9, 7}, {19, 21}, {40} with sector widths of 4, 2, and 1 respectively.

[heading-00395] 5.1.1 Generating the Rectangular ACM

[00396] Using the range partitioning rule, method Generate_R-ACM partitions the value range of the attribute X into s variable width sectors of the R-ACM.

[00397] The input to the method are the tolerance value τ for the ACM and the actual frequency distribution of the attribute X. The frequency distribution is assumed to be available in an integer array A, which has a total of L entries for each of the L distinct values of X. For simplicity reasons, it is assumed that the attribute values are ordered integers from 0 to L−1. The output of the method is the R-ACM for the given attribute value set.

[00398] Generate_R-ACM generates the R-ACM corresponding to the given frequency value set. Assuming that the frequency distribution of X is already available in array A, the running time of the method Generate_R-ACM is O(L) where L is the number of distinct attribute values.

[00399] The tolerance value, τ, is an input to the above method. The question of how to determine an “optimal” tolerance value for an R-ACM is addressed using adaptive techniques set out below.

[00400] FIG. 11 shows the histogram and the R-ACM of the Age attribute of a relation Emp(SIN, Age, Salary) between Age=30 and Age=49. Note that the actual frequency for every age value is shown in the histogram as shaded rectangles. Whenever the frequency of the current age differs from the frequency of the running mean value for age in the sector by more than the allowed tolerance value τ=8, a new partition is formed. From the ACM, the number of tuples in this relation with ages in the range of 34≦Age≦36 is 130 and the estimate for the number of employees having age=48 is 15/3=5.

[00401] Pseudocode to implement the above method is as follows.

[heading-00402] Method 2 Generate_R-ACM

[00403] Input: tolerance τ, frequency distrib. of X as A[0 . . . L−1]

• [00404] Output: R-ACM
• [00405] begin
  • [00406] Initialize_ACM; /* set all entries in ACM to zero */
  • [00407] current_mean:=A[1]; j:=0;
  • [00408] ACM[j]:=A[1];
  • [00409] for i:=1 to L−1 do /* for every attribute value */
    • [00410] if abs (A[i]−current mean)<τ
      • [00411] ACM[j]:=ACM[j]+A[i];
        • [00412] /* compute the running mean */
      • [00413] current_mean:=(current_mean*i+A[i])/(i+1);
    • [00414] else begin
      • [00415] l_j:=i−1; /* set the sector width */
      • [00416] j++; /* move to next sector */
      • [00417] current_mean:=A[i];
      • [00418] ACM[j]:=A[i];
    • [00419] end;
  • [00420] end;

[00421] End Generate_R-ACM;

[00422] Since the ACM only stores the count of the tuples and not the actual data, it does not incur the usually high I/O cost of having to access the base relations from secondary storages. Secondly, unlike the histogram-based or other parametric and probablistic counting estimation methods, ACM does not use sampling techniques to approximate the data distribution. Each cell of the ACM maintains the actual number of tuples that fall between the boundary values of that cell, and thus, although this leads to an approximation of the density function, there is no approximation of the number of tuples in the data distribution.

[00423] The one-dimensional R-ACM as defined above is easily extended to a multi-dimensional one to map an entire multi-attribute relation. A multi-dimensional ACM is, for example, used to store the multi-dimensional attributes that commonly occur in geographical, image, and design databases.

[heading-00424] 5.1.2 Rationale for the Rectangular ACM

[00425] Without loss of generality, consider an arbitrary continuous frequency function f(x). FIG. 12 shows the histogram partitioning of f(x) under the traditional equi-width, equi-depth methods and the R-ACM method. In the equi-width case, regardless of how steep the frequency changes are in a given sector, the sector widths remain the same across the attribute value range. This means the widely different frequency values of all the different attribute values are assumed to be equal to that of the average sector frequency. Thus there is an obvious loss of accuracy with this method. On the other hand, in the equi-depth case, the area of each histogram sector is the same. This method still has a number of sectors with widely different frequency values and thus suffers from the same problem as the equi-width case. In the R-ACM method, whenever there is a steep frequency change, the corresponding sector widths proportionally decrease or the number of sectors proportionally increases. Hence the actual frequencies of all the attribute values within a sector are kept closer to the average frequency of that sector. This partitioning strategy advantageously increases the estimation accuracy. FIG. 13 shows a comparison of probability estimation errors obtained on all three estimation methods for synthetic data.

[00426] The rationale for partitioning the attribute value range using a tolerance value is to minimize the variance of values in each ACM sector, and thus to minimize the estimation errors. Since variance of an arbitrary attribute value X_k is given as $\mathrm{Var}\left(X_k\right)=E\left[{\left(x_k-\frac{n_j}{l_j}\right)}^2\right],$
forcing the difference between the frequency of a given value and the mean frequency to be less than the tolerance τ, i.e: $x_k-\frac{n_j}{l_J}\le \tau ,$
ensures that the variance of the values falls within the acceptable range. It later becomes clear that minimizing the variance of the individual sectors results in a lower value for the variance of the ACM.

[00429] To demonstrate the relationship between the selection estimation error and the variance of the ACM, an experiment was conducted in which the underlying data distribution was changed and the variance was computed for three different tolerance values. The errors between the estimated and actual size of random matches are plotted against the computed variance of the ACM and shown in FIG. 14.

[heading-00430] 5.1.3 Density Estimation Using Rectangular ACM

[heading-00431] The properties of the R-ACM with regard to density approximation using a one-dimensional Rectangular ACM sector of width l and n tuples are set out below. The following assumption is made to render the analysis feasible.

[heading-00432] Assumption 1 The attribute values within a Rectangular ACM sector are uniformly distributed.

[heading-00433] Rationale: Since the sector widths of the R-ACM are chosen so that the frequency of the values within the sectors do not differ by more than the allowed tolerance, τ, these frequencies are within predetermined limits of each other. The original System R research work relied on the often erroneous assumption that the frequencies of an attribute value are uniformly distributed across the entire attribute value domain. With the adoption of the equi-width and equi-depth histograms in the modern-day database systems, this was improved by making the uniformity assumptions only within histogram buckets. Uniformity assumption within an R-ACM sector is a much weaker assumption than that used in any other prior art histograms, due to its partitioning strategy.

[00434] Using the above uniformity assumption, the probability mass distribution for the R-ACM is derived.

[heading-00435] Lemma 1 The probability mass distribution for the frequencies of the attribute values in an R-ACM is a Binomial distribution with parameters (n, l/1).

[heading-00436] Proof: Since there are l distinct values in the sector, the probability of any of these l values, say X_i, occurring in a random assignment of that value to the sector is equal to l/1. (See FIG. 15).

[00437] Consider an arbitrary permutation of the n tuples in the sector. Suppose the value X_i occurs exactly x_i times. This means all the other (l−1) values must occur a combined total of (n−x_i) times. Since the probability of X_i occurring once is 1/l, the probability of it not occurring is $\left(1-\frac{1}{l}\right).$
Hence the probability of an arbitrary permutation of the n tuples, where the value X_i occurs exactly x_i times and the other values collectively occur n−x_i times is, $\begin{array}{cc}{\left(\frac{1}{l}\right)}^{x_i}{\left(\frac{l-1}{l}\right)}^{n-x_i}.& \left(1\right)\end{array}$

[00439] Clearly, there are $\hspace{1em}\left(\begin{array}{c}n\\ x_i\end{array}\right)$
different permutations of the n tuples in the sector where the above condition is satisfied. Hence the total probability that an arbitrary value X_i occurs exactly x_i times is, $\begin{array}{cc}{p}_{x_i}\left(x_i\right)=\left(\begin{array}{c}n\\ x_i\end{array}\right){\left(\frac{1}{l}\right)}^{x_i}{\left(\frac{l-1}{l}\right)}^{n-x_i}& \left(2\right)\end{array}$
which is exactly the Binomial distribution with parameters $\left(n,\frac{1}{l}\right).$
This proves the lemma.
5.1.4 Maximum Likelihood Estimate Analysis for the Rectangular ACM

[00444] Frequency distribution for a given attribute value in the R-ACM obeys a Binomial distribution. With this as a background, a maximum likelihood estimate for the frequency of an arbitrary attribute value in an R-ACM sector is determined. In classical statistical estimation theory, estimating the parameters such as the mean or other unknown characterizing parameters of the distribution of one or more random variables is usually conducted. Here estimating the value of the occurrence of the random variable, the frequency x_i, which is “inaccessible” is desired. To do this the maximum likelihood estimate is derived, which maximizes the corresponding likelihood function. Indeed the result is both intuitively appealing and quite easy to comprehend.
Theorem 1 For a one-dimensional rectangular ACM, the maximum likelihood estimate of the number of tuples for a given value X_i of attribute X is given by, ${\hat{x}}_{\mathrm{ML}}=\frac{n}{l}$
where n is the number of tuples in the sector containing the value X_i and l is the width of that sector.
Proof: From Lemma 1 it is known that the frequency distribution of a given attribute value in an R-ACM sector is a Binomial distribution. So the probability mass function of the frequency distribution of an attribute value X=X_a in an R-ACM sector can be written as, $f\left(x\right)=\left(\begin{array}{c}n\\ x\end{array}\right){p^x\left(1-p\right)}^{n-x}$
where x is the number of occurrences of X_a. Let $ℒ\left(x\right)=f\left(x\right)=\left(\begin{array}{c}n\\ x\end{array}\right){p^x\left(1-p\right)}^{n-x}.$
L(x) is the traditional likelihood function of the random variable X on the parameter x which is to be maximized. To find out the maximum likelihood estimate for this parameter x and taking natural logarithm on both sides of the likelihood function, $\begin{array}{cc}\begin{array}{c}\ln ℒ\left(x\right)=\ln n!-\ln x!-\ln \left(n-x\right)!+x\ln p+\left(n-x\right)\ln \left(1-p\right)\\ =\ln \Gamma \left(n+1\right)-\ln \Gamma \left(x+1\right)-\ln \Gamma \left(n-x+1\right)+\\ x\ln p+\left(n-x\right)\ln \left(1-p\right)\end{array}& \left(3\right)\end{array}$
where Γ(x) is the Gamma function given by, $\Gamma \left(x\right)={\int }_0^{\infty }{e}^{-t}{t}^{x-1}dt.$
Now using the well known identity, $\Gamma \left(\alpha \right)=\frac{\Gamma \left(\alpha +k+1\right)}{\alpha \left(\alpha +1\right)\dots \left(\alpha +k\right)}$ $\Gamma \left(n-x+1\right)=\frac{\Gamma \left(n+1\right)}{\left(n-x+1\right)\left(n-x+2\right)\dots n}\mathrm{and}$ $\Gamma \left(x+1\right)=\frac{\Gamma \left(n+1\right)}{\left(x+1\right)\left(x+2\right)\dots n}.$

[00452] Thus substituting the above expressions for Γ(n−x+1) and Γ(x+1) in Equation 3, $\begin{array}{c}\ln ℒ\left(x\right)=-\ln \Gamma \left(n+1\right)+x\ln p+\left(n-x\right)\ln \left(1-p\right)+\\ \ln \left(x+1\right)+\ln \left(x+2\right)+\dots +\ln n+\\ \ln \left(n-x+1\right)+\ln \left(n-x+2\right)+\dots +\ln n\end{array}$

[00453] Now differentiating ln L(x) with respect to x, $\frac{d}{dx}\ln ℒ\left(x\right)=\ln p-\ln \left(1-p\right)+\sum _{r=x+1}^{n-x}\frac{1}{r}.$

[00454] Setting $\frac{d\left\{ℒ\left(x\right)\right\}}{dx}=0,$
and noting that $\sum _{r=x+1}^{n-x}\frac{1}{r}\le \ln \left(\frac{n-x}{x}\right),$
{circumflex over (x)}_ML of x is obtained as, $\frac{p\left(n-x\right)}{\left(1-p\right)x}\ge 1.$

[00457] This inequality is solved for x≦np. But, by virtue of the underlying distribution, since the likelihood function monotonically increases until its maximum,
{circumflex over (x)}_ML=np.

[00459] Due to the uniformity assumption within an R-ACM sector, $p=\frac{1}{l}.$
So,
${\hat{x}}_{\mathrm{ML}}=\frac{n}{l}.$
Hence the theorem.

[00463] The maximum likelihood estimate, {circumflex over (x)}_ML=np, derived using the Gamma function above is, most of the time, not an integer. In fact, the maximum likelihood estimate reaches its upper limit of np at integer values only in very special cases. Considering the analogous discrete case, we have the following theorem.
Theorem 2 For a one-dimensional rectangular ACM, the maximum likelihood estimate of the number of tuples for a given value X_i of attribute X falls within the range of, $\frac{\left(n+1\right)}{l}-1\le {\hat{x}}_{\mathrm{ML}}\le \frac{\left(n+1\right)}{l},$
where n is the number of tuples in the sector containing the value X_i and l is the width of that sector.
Proof: The probability mass function $f\left(x\right)=\left(\begin{array}{c}n\\ x\end{array}\right){p^x\left(1-p\right)}^{n-x}$
is a steadily increasing function until it reaches the maximum likelihood value, x={circumflex over (x)}_ML. For any x>{circumflex over (x)}_ML, f(x) is a steadily decreasing function. Hence an integer value for the maximum likelihood estimate is obtained by solving the following two discrete inequalities simultaneously.
f(x)−f((x+1)>0   (4)
f(x)−f((x−1)>0   (5)
From Equation (4), $f\left(x\right)-f\left(x+1\right)>0$ $\left(\begin{array}{c}n\\ x\end{array}\right){p^x\left(1-p\right)}^{n-x}-\left(\begin{array}{c}n\\ x+1\end{array}\right){p^{x+1}\left(1-p\right)}^{n-x-1}>0$ $\frac{n!}{x!\left(n-x\right)!}\left(1-p\right)-\frac{n!}{\left(x+1\right)!\left(n-x-1\right)!}p>0$ $\frac{1-p}{n-x}-\frac{p}{x+1}>0\mathrm{or}x>p\left(n+1\right)-1.$

[00471] Similarly considering Equation (5), by using similar algebraic manipulation, $f\left(x\right)-f\left(x-1\right)>0$ $\left(\begin{array}{c}n\\ x\end{array}\right){p^x\left(1-p\right)}^{n-x}-\left(\begin{array}{c}n\\ x-1\end{array}\right){p^{x-1}\left(1-p\right)}^{n-x-1}>0\mathrm{or}x<p\left(n+1\right).\mathrm{Since}p=\frac{1}{l},\mathrm{the}\mathrm{theorem}\mathrm{follows}.$
5.1.5 Expected Value Analysis for the R-ACM and Self-Join Error Estimate

[00473] The maximum likelihood estimate of the frequency of a given attribute value indicates that the attribute value would have a frequency of {circumflex over (x)}_ML with maximum degree of certainty when compared to the other possible frequency values. But even though the attribute value occurs with the maximum likelihood frequency with high probability, it can also occur with other frequencies with smaller probabilities. Hence in order to find the worst-case and average-case errors for result size estimations, another estimate is obtained which includes all these possible frequency values. One such estimate is the expected value of the frequency of a given attribute value. The Binomial model is used to find the expected value of the frequency of an attribute value as given in the following lemma and to develop a sequence of results regarding the corresponding estimates. Lemma 2 For a one-dimensional rectangular ACM, the expected number of tuples for a given value X_i of attribute X is E(X_i)=n/l, where n is the number of tuples in the sector containing the value X_i and l is the width of that sector.
Proof: From Equation (2), the probability that the value X_i occurs exactly k times is, ${\mathrm{px}}_i\left(k\right)=\left(\begin{array}{c}n\\ k\end{array}\right){\left(\frac{1}{l}\right)}^k{\left(\frac{l-1}{l}\right)}^{n-k}$
which is a Binomial distribution with parameters (n, 1/l). The result follows directly from the fact that the mean of the binomial distribution, Binomial (n, p), is np, where p is the probability of success.

[00476] The above result is very useful in estimating the results of selection and join operations.

[heading-00477] 5.1.6 Estimation Error with Rectangular ACM

[00478] It has been shown that even a small error in the estimation results, when propagated through several intermediate relational operations, can become exponential and be devastating to the performance of a DBMS [Ioannidis and Christodoulakis, 1991].

[00479] The variance of a random variable X measures the spread of dispersion that the values of X can assume and is defined by Var(X)=E{[X−E(X)]²}. It is well known that Var(X)=E(X²)−[E(X)]². Thus the variance of the frequency of the k^th value of the attribute X in the j^th sector is given as, $\mathrm{Var}\left(X_k\right)=E\left[{\left(x_k-\frac{n_j}{l_j}\right)}^2\right]$

[00480] Expanding the right hand side, $\begin{array}{cc}\mathrm{Var}\left(X_k\right)=\sum _{i=0}^{n_j}{x_k^2\left(\frac{1}{l_j}\right)}^i{\left(1-\frac{1}{l_j}\right)}^{n_j-i}-{\left(\frac{n_j}{l_j}\right)}^2& \left(6\right)\end{array}$
Lemma 3 The variance of the frequency of an attribute value X in sector j of an R-ACM is, $\begin{array}{cc}\mathrm{Var}\left(X\right)=\frac{n_j\left(l_j-1\right)}{l_j^2}& \left(7\right)\end{array}$
Proof: It is well known that the variance of a Binomial distribution with parameters (n, p) is np(1−p). Using the property of the Binomial distribution, the expression for the variance given in Equation (6) is reduced to the one given in lemma.
Lemma 4 The sector variance of the j^th rectangular ACM sector is, $\begin{array}{cc}{\mathrm{Var}}_j=\frac{n_j\left(l_j-1\right)}{l_j}& \left(8\right)\end{array}$
Proof: Var(X_k) is same for all k, 1≦k≦l_j,in a given sector. Since the random variables are independent, summing up the variances of all the values in the sector will give an upper bound for the estimation error or variance of the sector. The result follows.

[00485] Similarly, summing up the variances of all the sectors, an expression for the variance of the entire ACM is obtained which is given in the following lemma. Lemma 5 The variance of an R-ACM is given by, $\begin{array}{cc}\mathrm{Var}\left(\mathrm{ACM}\right)=\sum _{i=1}^s{\mathrm{Var}}_i& \left(9\right)\end{array}$
where s in the number of sectors in the ACM.
Proof: The result follows directly from the fact that the variances in each sector are independent, and thus summing up the sector variances yields the variance of the entire ACM.
5.1.7 Error Estimates and Self-Joins

[00489] It is interesting to study the join estimation when a relation is joined with itself. These self-joins frequently occur with 2-way join queries. It is well known that the self-join is a case where the query result size is maximized because the highest occurrences in the joining attributes correspond to the same attribute values. Assuming that the duplicate tuples after the join are not eliminated, the following lemma results.
Lemma 6 The error, ε, resulting from a self-join of relation R on attribute X using a rectangular ACM is given by, $\epsilon =\mathrm{Var}\left(\mathrm{ACM}\right)+\sum _{j=1}^s\left\{\sum _{k=1}^{l_j}{x}_k^2-\frac{n_j^2+n_j{l}_j-n_j}{l_j}\right\}.$
Proof: Since there are $L=\sum _{i=1}^s{l}_j$
values for attribute X, the actual value, ξ and expected value κ of the join size can be estimated as follows. $\xi =\sum _{i=1}^L{x}_i^2=\sum _{j=1}^s\sum _{k=1}^{l_j}{x}_k^2.$
The frequency of an arbitrary attribute value is computed from the R-ACM as the expected value E(x_i), which is the average frequency of the R-ACM sector. Hence the result of self-joining this attribute value is [E(x_i)]². Hence the size of the join computed by the ACM, κ, is, $\begin{array}{c}\kappa =\sum _{i=1}^L{\left[E\left(x_i\right)\right]}^2\\ =\sum _{j=1}^s\sum _{i=1}^{l_j}{\left(\frac{n_j}{l_j}\right)}^2=\sum _{j=1}^s{l_j\left(\frac{n_j}{l_j}\right)}^2.\end{array}$
Hence the error in estimation of the self-join is, $\begin{array}{c}\xi -\kappa =\sum _{j=1}^s\sum _{k=1}^{l_j}{x}_k^2-\sum _{j=1}^s{l_j\left(\frac{n_j}{l_j}\right)}^2\\ =\sum _{j=1}^s{l}_j\left\{\frac{1}{l_j}\sum _{k=1}^{l_j}{x}_k^2-{\left(\frac{n_j}{l_j}\right)}^2\right\}.\end{array}$
But since $\mathrm{Var}\left(\mathrm{ACM}\right)=\sum _{j=1}^s{l}_j{\mathrm{Var}}_j,$
adding and subtracting Var(ACM) from RHS of the above expression results in, $\begin{array}{cc}\begin{array}{c}\xi -\kappa =\sum _{j=1}^s{l}_j{\mathrm{Var}}_j+\sum _{j=1}^s{l}_j\left\{\frac{1}{l_j}\sum _{k=1}^{l_j}{x}_k^2-{\left(\frac{n_j}{l_j}\right)}^2\right\}-\\ \sum _{j=1}^s{l}_j\frac{n_j\left(l_j-1\right)}{l_j^2}\\ =\mathrm{Var}\left(\mathrm{ACM}\right)+\sum _{j=1}^s\left\{\sum _{k=1}^{l_j}{x}_k^2-\frac{n_j^2+n_j{l}_j-n_j}{l_j}\right\}.\end{array}& \left(10\right)\end{array}$

[00497] and the result is proved.

[heading-00498] Observation 1 The error in self-join estimation of a relation from the R-ACM is O(Var(ACM)).

[00499] Experimental results with R-ACM indicate that the error in the self-join estimation is approximately equal to the variance of the ACM since the contribution due to the second term in Equation (10) seems to be less dominant. This agrees well with the results claimed by Ioannidis.
Theorem 3 The variance of a rectangular ACM corresponding to attribute X is, $\begin{array}{cc}\mathrm{Var}\left(\mathrm{ACM}\right)=N-\sum _{j=1}^s\frac{n_j}{l_j}.& \left(11\right)\end{array}$
Proof: From Lemma 5, the variance of an R-ACM is given by $\mathrm{Var}\left(\mathrm{ACM}\right)=\sum _{j=1}^s{\mathrm{Var}}_j,$
where Var_j is the variance of the j^th sector. But from Lemma 4, Var_j=n_j(l_j−1)/l_j. Hence, $\begin{array}{c}\mathrm{Var}\left(\mathrm{ACM}\right)=\sum _{j=1}^s\frac{n_j\left(l_j-1\right)}{l_j}\\ =\sum _{j=1}^s{n}_j-\sum _{j=1}^s\frac{n_j}{l_j}\\ =N-\sum _{j=1}^s\frac{n_j}{l_j}.\end{array}$
Hence the theorem.
5.1.8 Worst-Case Error Analysis for the R-ACM

[00505] As mentioned earlier, forcing a frequency value to be within a given tolerance τ to the current mean ensures that the frequency distribution within an R-ACM sector is very close to uniform. Whenever every frequency value is always consistently smaller or always consistently greater than the current mean by the tolerance value τ, the resulting sectors will be far from uniform. Definition 2 A distribution is said to be “least uniform” if for every attribute value of X_i, the frequency x_i attains the value x_i=μ_i−1−τ, if x_i is decreasing or x_i=μ_i−1+τ if x_i is increasing, where μ_i−1 is the mean of the first (i−1) frequencies. A sector of the former type is called a monotonically decreasing R-ACM sector. Similarly a sector of the latter type is called a monotonically increasing R-ACM sector.

[00506] The motivation for the above definition comes from the following observation. Assume that during the process of constructing an R-ACM sector, the next value x_i is smaller than the current means μ_i−1. If x_i<μ_i−1−τ then, a new sector is generated. Hence the smallest value that x_i can assume is x_i=μ_i−1−τ. The resulting distribution is shown in FIG. 16(a). This is formally given by the following lemma. This lemma is given for the case when the sector is a decreasing R-ACM sector, or in other words, when every frequency value is always smaller than the previous mean. The case for the increasing R-ACM sector is proved in an analogous way. Lemma 7 A decreasing R-ACM sector is “least uniform”, if and only if $x_k=a-\sum _{i=1}^{k-1}\frac{\tau }{i}\mathrm{for}1\le k\le l_j.$
Proof: Note that in this case, least uniformity occurs when the quantity E_S(X)−x_i assumes its largest possible value or when x_i assumes its minimum value, where E_S(X) is the expected value of X in a sector, assuming that the frequency of the first value is x₁=a.

[00508] Basis: x₁=a: Since the current mean is E_S(X)=a, and the sector is a monotonically decreasing R-ACM sector, the minimum possible value for x₂ is obtained from E_S(X)−x₂=τ. This is achieved when x₂=a−τ.

[00509] Inductive hypothesis: Assume the statement is true for n=k. So the sector is the least uniform for the first k values and the frequencies take the following values: $\begin{array}{ccc}{x}_1& =& a\\ x_2& =& a-\tau \\ x_3& =& a-\frac{3\tau }{2}\\ ⋮& ⋮& ⋮\\ x_k& =& a-\sum _{i=1}^{k-1}\frac{\tau }{i}\end{array}$
For n=k+1: The minimum possible value for x_k+1 without creating a new sector is obtained when E_S(X)−x_k+1=τ. This is achieved when x_k+1=E_S(X)−τ. So, $\begin{array}{c}{x}_{k+1}=\frac{x_1+x_2+\dots +x_k}{k}-\tau \\ =a-\frac{\tau +\frac{3\tau }{2}+\dots +\sum _{i=1}^{k-1}\frac{\tau }{i}}{k}-\tau \\ =a-\frac{\left(k-1\right)\tau +\left(k-2\right)\frac{\tau }{2}+\left(k-3\right)\frac{\tau }{3}+\dots +\frac{\tau }{k-1}}{k}-\tau \\ =a-\frac{k\tau \left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{k-1}\right)-\left(k-1\right)\tau }{k}-\tau \\ =a-\sum _{i=1}^k\frac{\tau }{i}\end{array}$
This proves the lemma.
Lemma 8 An increasing R-ACM sector is “least uniform”, if and only if $x_k=a+\sum _{i=1}^{k-1}\frac{\tau }{i}\mathrm{for}1\le k\le l_j.$
Proof: The proof is analogous to that of Lemma 7 and omitted in the interest of brevity.
Theorem 4 If the value X, falls in the j^th sector of an R-ACM, then the number of occurrences of X_i is, $\frac{n_j}{l_j}-\tau \left[\ln \left(\frac{l_j}{i-1}\right)-1\right]\le x_i\le \frac{n_j}{l_j}+\tau \left[\ln \left(\frac{l_j}{i-1}\right)-1\right]$
where n_j and l_j are the number of tuples and the sector width of the j^th sector.
Proof: Consider a sector from an R-ACM. Let the frequency of the first value x₁ be a. Note that the R-ACM sector will become a “skewed” one, if the subsequent values are all smaller or all greater than the previous mean by τ. From Lemma 7 and Lemma 8, it is obvious that such sectors are the “least uniform” ones in an R-ACM, and consequently the largest estimation error occurs in such a “skewed” sector. Assume that the frequency values from x₁ to x_lj decrease monotonically in this manner. In other words, if the mean of the first k values is μ_k, then the next value will take its lowest allowable frequency, μ_k−τ. The resulting distribution is shown in FIG. 16(a). From Lemma 7, the frequency of an arbitrary attribute value X_i is given by, $x_i=a-\sum _{k=1}^{i-1}\frac{\tau }{k}$

[00517] The expected value E(X_i) is the mean frequency for the entire sector. So, $\begin{array}{c}E\left(X_i\right)=\frac{\sum _{k=1}^{l_j}{x}_k}{l_j}\\ =a-\tau \left(1+\frac{1}{2}+\dots +\frac{1}{l_j-1}-\frac{l_j-1}{l_j}\right)\end{array}$

[00518] But the frequency of an arbitrary value X_i is, $x_i=a-\tau \left(1+\frac{1}{2}+\dots +\frac{1}{i-1}\right)$

[00519] So the estimation error is, $x_i-E\left(X_i\right)=\tau \left(\sum _{k=i}^{l_j}\frac{1}{k}-1\right)\le \tau \left[\ln \left(\frac{l_j}{i-1}\right)-1\right]$ $\text{Hence,}{x}_i\ge \frac{n_j}{l_j}-\tau \left[\ln \left(\frac{l_j}{i-1}\right)-1\right]$
Similarly using symmetry, for an R-ACM sector with monotonically increasing frequency value, $x_i\le \frac{n_j}{l_j}+\tau \left[\ln \left(\frac{l_j}{i-1}\right)-1\right].$
The theorem follows. The composite effect of the monotonically decreasing frequency sequence and the monotonically increasing sequence restricts the set of frequency values which the attributes can take. FIG. 16(c) represents the range of likely frequencies when the frequencies in the sector are generated from the frequency of the first attribute value. Note that when the frequencies are generated based on the running mean, the worst case error will be at its maximum at the beginning of the sector and then gradually decrease towards the end of the sector. This is the result of the fact that the sample mean converges to the true mean and the variance tends to zero by the law of large numbers. What is interesting, however, is that by virtue of the fact the next sample deviates from the current mean by at most τ, the error in the deviation is bounded from the mean in a logarithmic manner. If this is not taken into consideration, the above figure can be interpreted erroneously. The following example illustrates the implications of the above theorem.

[00522] Consider an R-ACM sector of width 10 containing 124 tuples, where the R-ACM is partitioned using a tolerance value τ=3. Let us attempt to find the estimated frequency ranges for the attribute values (a) X₃ and (b) X₆.

[00523] (a). The frequency range of X₃ is, $12.4-3\left(\ln 5-1\right)\le x_3\le 12.4+3\left(\ln 5-1\right)$ $10.57\le x_3\le 14.23$

[00524] (b). The frequency range of X₆ is, $12.4-3\left(\ln 2-1\right)\le x_6\le 12.4+3\left(\ln 2-1\right)$ $11.48\le x_6\le 13.32$
Notice that in both the above cases, the possible frequency values from an equi-width or equi-depth histograms are 0≦x≦124, where x=x₃ or x₆. The power of the R-ACM in the estimation is clearly advantageous.
5.1.9 Worst-Case Error in Estimating the Frequency of an Arbitrary Value X_i

[00527] The previous theorem gives an estimate of the number of occurrences of an arbitrary attribute value by considering the worst-case R-ACM sector. So the worst-case error in the above estimate is given by the frequency range that the attribute value can assume. The following theorem provides a worst-case error for this frequency estimation.
Theorem 5 The worst-case error, ε, in estimating the frequency of an arbitrary attribute value X_i in a rectangular ACM is given by, $\epsilon =\tau \left[\ln \left(\frac{l}{i-1}\right)-1\right]$
where τ is the tolerance value used in generating the R-ACM. Proof: It was proved in Theorem 4 that the actual frequency of an attribute value can at most differ from the estimated frequency value $\tau \left[\ln \left(\frac{l}{i-1}\right)-1\right].$
Hence the theorem.
5.1.10 Worst-Case Error in Estimating the Sum of Frequencies in an Attribute Value Range
Consider the three distinct cases when,

• [00533] 1. The attribute value range spans across one R-ACM sector.
• [00534] 2. The attribute value range falls completely within one R-ACM sector.
• [00535] 3. The attribute value range spans across more than one R-ACM sector.

[00536] In the first case, estimation using the R-ACM gives the accurate result (n_j) and there is no estimation error. The estimation error in the second case is shown in the example FIG. 17(a) and is given by the theorem below. The estimation error in the third case can be obtained by noting that it is in fact the combination of the first and second cases.
Theorem 6 An estimate for the worst-case error, ε, in estimating the sum of frequencies of X_i in the attribute value range, X_α≦X_i≦X_β, when both X_α and X_β fall completely within an R-ACM sector is given by, $\epsilon =\ln \left\{l_j^{\left(\beta -\alpha +1\right)\tau }\frac{\left(\beta -1\right)!}{\left(\alpha -2\right)!}\right\}-\left(\beta -\alpha +1\right)\tau$
where β>α.
Proof: Using Theorem 4, the error resulting from this result size estimation is computed by summing up the worst-case error for each of the attribute values in the given value range. Thus the following cumulative error results. $\begin{array}{c}\epsilon =\sum _{i=\alpha }^{\beta }\left\{\tau \ln \left(\frac{l_j}{i-1}\right)-1\right\}\\ =\tau \sum _{i=\alpha }^{\beta }\ln \left(\frac{l_j}{i-1}\right)-\left(\beta -\alpha +1\right)\tau \\ =\ln \left\{l_j^{\left(\beta -\alpha +1\right)\tau }\frac{\left(\beta -1\right)!}{\left(\alpha -2\right)!}\right\}-\left(\beta -\alpha +1\right)\tau .\end{array}$
Hence the theorem follows.
5.1.11 Average Case Error in Estimating the Frequency of an Arbitrary Value X_i

[00542] Average case error occurs in a truly random sector. In a random sector, frequency values do not monotonically increase or decrease as in the least uniform case. Instead, they take on a random value around the mean bounded by the tolerance value. In other words, if the current mean is μ, then the next frequency value is a random variable between μ−τ and μ+τ. Whenever the next frequency value falls outside the range of [μ−τ, μ+τ], then a new sector is generated.

[heading-00543] Theorem 7 The average case error with a rectangular ACM is bounded by 2τ.

[heading-00544] Proof: To compute the average case error, we are required to compute the error at every attribute value and then take its expected value by weighting it with the probability of the corresponding error. However, since the frequency of an attribute value varies only in the range of [μ−τ, μ+τ], the maximum variation the frequency has is 2τ. It follows that the maximum error is always bounded by 2τ, and the result follows.

[heading-00545] 5.1.12 Average Case Error in Estimating the Sum of Frequencies in an Attribute Value Range

[00546] Consider the case when the attribute value range completely falls within an R-ACM sector given by the following theorem. Theorem 8 The average case error with a rectangular ACM in estimating the sum of frequencies in the value range, X_α≦X≦X_β, when both X_α and X_β fall completely within the k^th sector of the R-ACM is given by,
ε=2(β−α+1)τ
where β>α and τ is the tolerance value used to build the R-ACM.
Proof: From Theorem 7, the average-case error bound in estimating the frequency of an arbitrary attribute value X_i is 2τ. Hence considering the errors for the attribute values in the range of X_α≦X≦X_β, the cumulative error is, $\epsilon =\sum _{i=\alpha }^{\beta }2\tau =2\left(\beta -\alpha +1\right)\tau$
and the theorem follows.
5.1.13 Tight Error Bound with R-ACM: A Special Case

[00552] In a random R-ACM sector, almost half of the attribute values tend to have frequency values below the sector mean and the other half above the frequency mean. So it is possible to re-arrange the attribute values in such a random sector so that the frequency values alternatively increase and decrease about the current mean. Considering such a random R-ACM sector where the frequency values alternatively increase and decrease by the tolerance τ about the current mean. For example, the current frequency value x_k is derived from the current mean μ_k−1 by the expression,
x_k=μ_k−1+(−1)^k+1τ.

[00554] The current frequency mean is also given by the following recurrence expression. ${\mu }_k={\mu }_{k-1}+\frac{{\left(-1\right)}^{k+1}\tau }{k}.$

[00555] A random sector with frequency values which alternatively increase and decrease about the current mean is depicted in FIG. 18 and the corresponding frequency and mean values are given in Table 5. Considering the case of such a random sector leads to the following lemma.

[heading-00556] Lemma 9 The estimation error in a rectangular ACM with frequency values which

[00002]

TABLE 5
First few values of xk and μk
k	xk	μk
1	α	α
2	α − τ	α − τ/2
3	α + τ/2	α − τ/6
4	α − 7τ/6	α − 5τ/12
5	α + 7τ/12	α − 13τ/60

alternatively increase and decrease about the current mean is given by, $x_i-E\left(X_i\right)=\tau \left(\sum _{k=2}^i\frac{{\left(-1\right)}^{k+1}}{k}+\ln 2-1\right).$
Proof: The expected value E(X_i) is the mean frequency for the entire sector. So, $\begin{array}{c}E\left(X_i\right)=\frac{\sum _{k=1}^{l_j}{x}_k}{l_j}={\mu }_{l_j}\\ =a+\tau \left\{-\frac{1}{2}+\frac{1}{3}-\dots +\frac{{\left(-1\right)}^{l_j+1}}{l_j}\right\}.\end{array}$
For sufficiently large l_j, the above becomes,
E(X_i)≈a−(1−In2)τ.
But the frequency of an arbitrary value X_i is, $\begin{array}{c}{x}_k={\mu }_{k-1}+{\left(-1\right)}^{k+1}\tau \\ =a+\tau \left\{-\frac{1}{2}+\frac{1}{3}-\dots +\frac{{\left(-1\right)}^{i+1}}{i}\right\}\\ =a+\tau \sum _{k=3}^{i+1}\frac{{\left(-1\right)}^k}{k-1}\end{array}$
Hence the estimation error is, $x_i-E\left(X_i\right)=\tau \left(\sum _{k=2}^i\frac{{\left(-1\right)}^{k+1}}{k}+\ln 2-1\right).$
The lemma follows.

[00564] Note that the above estimation error is always smaller than 0.8069τ and thus is better than the average case error.

[heading-00565] 5.1.14 Size Estimation of Selection Operations Using the R-ACM

[00566] The selection operation is one of the most frequently encountered operations in relational queries. In general, the select operation is denoted by σ_p(R), where p is a Boolean expression or the selection predicate and R is a relation containing the attributes specified in p. The selection predicate p is specified on the relation attributes and is made up of one or more clauses of the form, $\langle \mathrm{Attribute}\rangle \langle \mathrm{comparison}\mathrm{operator}\rangle \langle \mathrm{Constant}\rangle ,\mathrm{or}$ $\langle \mathrm{Attribute1}\rangle \langle \mathrm{comparison}\mathrm{operator}\rangle \langle \mathrm{Attribute2}\rangle .$

[00567] The comparison operator can be any operator in the set, {=, <, ≦, >, ≧, ≠}. The selection predicates can be either range predicates or equality predicates depending upon the comparison operators. Furthermore, the selection clauses can be arbitrarily connected by the Boolean operators, AND, OR, and NOT to form a general selection condition. The comparison operators in the set {=, <, ≦, >, ≧, ≠} apply to attributes whose domains are ordered values, such as numeric or date domains. Domains of strings of characters are considered ordered based on the collating sequences of the characters used in the system under consideration. If the domain of an attribute is a set of unordered values, only the comparison operators in the set {=, ≠} are applied to that attribute.

[00568] In general, the result of a select operation is determined as follows. The selection predicate, p, is applied independently to each tuple t in the relation R. This is done by substituting each occurrence of an attribute A_i in the selection predicate with its value in the tuple t[A_i]. If the condition evaluates to be true, then the tuple t is selected. All the selected tuples appear in the result of the select operation. The relation resulting from the select operation has the same attributes as the relation specified in the selection operation.

[00569] It is assumed that the selection predicates contain only a single clause. First of all, this is done for ease of analysis. Extending the work to any arbitrary number of clauses is straight forward. Finding the estimation for the result sizes of various selection predicates requires finding the estimates, E(σ_X=Xα(R)), E(σ_X<Xα(R)), E(σ_X>Xα(R)), E(σ_X≦Xα(R)), E(σ_X≧Xα(R)) and E(σ_X≠Xα(R)). Using the theoretical results obtained earlier, estimation bounds for each of these six conditions are found. But instead of computing each of these six estimates independently, only the estimation bounds for the estimates E(σ_X≦Xα(R)) and E(σ_X=Xα(R)) are determined. The estimation bounds for the other four selection conditions are obtained from the following relationships between the various selection conditions.

[heading-00570] 5.1.15 Relationships between Selection Conditions

[00571] Understanding the following relationships enables one to obtain the estimation results for every selection condition from the two estimates, E(σ_X≦Xα(R)) and E(σ_X=Xα(R)). These relationships are given in the form of lemmas here. Their proofs are omitted.

[heading-00572] Lemma 10 If N is the total number of tuples for the attribute, then for every X the following conditions hold:
E(σ_X<Xα(R))+E(σ_X=Xα(R))+E(σ_X>Xα(R))=N
E(σ_X≦Xα(R))=E(σ_X<Xα(R))+E(σ_X=Xα(R))
E(σ_X≧Xα(R))=E(σ_X>Xα(R))+E(σ_X=Xα(R))
Lemma 11 If X_min and X_max are the minimum and maximum values for the attribute respectively, then,
E(σ_X>Xmax(R))=0,
E(σ_X<Xmin(R))=0.
Lemma 12 For every X_α and X_β such that X_α<X_β,
E(σ_X<Xα(R))≦E(σ_X<Xβ(R)).
Lemma 13 For every X_α,
E(σ_X=Xα(R))≧0.

[00583] The following corollary gives some further properties, which are inferred from the above lemmas.
Corollary 1 For any arbitrary attribute value X and a given attribute value X_α, $E\left({\sigma }_{X\le X_{\max }}\left(R\right)\right)=N$ $E\left({\sigma }_{X\ge X_{\min }}\left(R\right)\right)=N$ $E\left({\sigma }_{X<X_a}\left(R\right)\right)\le E\left({\sigma }_{X\le X_{\alpha }}\left(R\right)\right).$

[00585] Hence from the above lemmas and corollary, using the estimates E(σ_X=Xα(R)), and E(σ_X≦Xα(R)), the estimates for the other four selection predicates are obtained as follows:
E(σ_X>Xα(R))=N−E(σ_X≦Xα(R))
E(σ_X>Xα(R))=N−E(σ_X≦Xα(R))+E(σ_X=Xα(R))
E(σ_X<Xα(R))=E(σ_X≦Xα(R))−E(σ_X=Xα(R))
E(σ_X≠Xα(R))=N−E(σ_X=Xα(R)).
5.1.16 Result Estimation of Equality Select Using the R-ACM

[00591] For a relational query with an equality select predicate, X=X_α, where X_α is a constant value in the domain of attribute X, the estimate of the result size of the query, σ_X=Xα(R) where the attribute value X_α is in position α of the k^th R-ACM sector is given by the following lemma.
Lemma 14 An estimate obtained by using the expected value analysis for the result of the equality select query, σ_X=Xα(R), using an R-ACM is, $E\left({\sigma }_{X=X_{\alpha }}\left(R\right)\right)=\frac{n_k}{l_k}$
where n_k is the number of tuples in the k^th R-ACM sector and l_k is the number of distinct attribute values (or width) of the k^th sector respectively.
Proof: This result is a direct consequence of Theorem 2.

[00595] Because of the fact that the estimate using the expected value and the maximum likelihood estimate are essentially identical, the estimate is referred to as the maximum likelihood estimate. When estimating the result size of the above query using the R-ACM, obviously associated worst-case and average-case errors are of concern. These errors are shown in FIG. 19(b) and (c).
Lemma 15 If the value X_α falls in the k^th sector of an R-ACM, then the worst-case error in estimating the number of tuples of X_α by using its maximum likelihood estimate is, $\epsilon =\tau \ln \left(\frac{l_k}{\alpha -1}\right)-1$
where n_k and l_k are the number of tuples and the sector width of the k^th sector.
Proof: This is a direct result from Theorem 4.
Lemma 16 The average case error with a rectangular ACM in estimating the equality select query, σ_X=Xα(R) by using its expected value 2τ, where τ is the tolerance value used to build the R-ACM.
Proof: This is a direct result of Theorem 7.
5.1.17 Result Estimation of Range Select Using the R-ACM

[00602] As mentioned earlier, among the various selection predicates, it is sufficient to find the estimate for the range select query σ_X≦Xα(R). With this estimate and the estimate found above for σ_X=Xα(R), the estimates for all other range predicates are obtainable.
Theorem 9 The maximum likelihood estimate for the range select query σ_X≦Xα(R) using the R-ACM is given by, ${𝒮}_{\mathrm{ML}}\left({\sigma }_{X\le X_{\alpha }}\left(R\right)\right)=\sum _{j=1}^{k-1}{n}_j+\frac{z_{\alpha }{n}_k}{l_k}$
where the attribute value X_α is in the k^th sector of the R-ACM and is the z_a^th attribute value in the sector.
Proof: The attribute values which satisfy the query σ_X≦Xα(R) occupy the first k−1 R-ACM sectors and up to and including the z_a^th location of the k^th R-ACM sector. Hence the query result size is found by summing up the number of tuples in the first k−1 sectors of the R-ACM and the maximum likelihood estimate of the tuples for the first z_α attribute values in the k^th sector of the R-ACM. First of all, there is no estimation error in the first k−1 sectors. The maximum likelihood estimate of the tuples for the first z_α attribute values in the k^th sector is found.

[00606] Assuming the frequencies of the first z_α attribute values in the k^th R-ACM sector are x₁, x₂, . . . , x_zα, a likelihood function on these frequencies is obtained by considering their join probability mass functions. But instead, without loss of generality, consider the join probability mass function for the first two attribute values. Due to their uncorrelatedness, the likelihood function is written as, $\begin{array}{c}𝔷\left(x_1,x_2\right)=\left(\begin{array}{c}{n}_k\\ x_1\end{array}\right){p^{x_1}\left(1-p\right)}^{n_k-x_1}\left(\begin{array}{c}{n}_k\\ x_2\end{array}\right){p^{x_2}\left(1-p\right)}^{n_k-x_2}\\ =\left(\begin{array}{c}{n}_k\\ x_1\end{array}\right)\left(\begin{array}{c}{n}_k\\ x_2\end{array}\right){p^{x_1+x_2}\left(1-p\right)}^{2n_k-\left(x_1+x_2\right)}.\end{array}$

[00607] Taking natural logarithm on both sides of the likelihood function, $\begin{array}{c}\ln ℒ\left(x_1,x_2\right)=2\ln n_k!-\ln x_1!-\ln \left(n_k-x_1\right)!-\ln x_2!-\ln \left(n_k-x_2\right)!+\\ \left(x_1+x_2\right)\ln p+\left[2n_k-\left(x_1+x_2\right)\right]\ln \left(1-p\right)\\ =2\ln \Gamma \left(n_k+1\right)-\ln \Gamma \left(x_1+1\right)-\ln \Gamma \left(n_k-x_1+1\right)+-\ln \Gamma \left(x_2+1\right)\\ -\ln \Gamma \left(n_k-x_2+1\right)+\left(x_1+x_2\right)\ln p+\left[2n_k-\left(x_1+x_2\right)\right]\ln \left(1-p\right)\end{array}$

[00608] Now using the well known identity, $\Gamma \left(\alpha \right)=\frac{\Gamma \left(\alpha +k+1\right)}{\alpha \left(\alpha +1\right)\dots \left(\alpha +k\right)}$
and simplifying the above log likelihood function, $\ln ℒ\left(x_1,x_2\right)=-2\ln \Gamma \left(n_k+1\right)+\left(x_1+x_2\right)\ln p+\left[2n_k-\left(x_1+x_2\right)\right]\ln \left(1-p\right)+\ln \left(x_1+1\right)+\ln \left(x_1+2\right)+\dots +\ln n+\ln \left(n_k-x_1+1\right)+\ln \left(n_k-x_1+2\right)+\dots +\ln n\ln \left(x_2+1\right)+\ln \left(x_2+2\right)+\dots +\ln n+\ln \left(n_k-x_2+1\right)+\ln \left(n_k-x_2+2\right)+\dots +\ln n$