QuickSel: Quick Selectivity Learning with Mixture Models
Yongjoo Park Shucheng Zhong Barzan Mozafari

QuickSel: Quick Selectivity Learning with Mixture Models]QuickSel: Quick Selectivity Learning 
with Mixture Models



These authors contributed equally to this work.









 
University of Illinois at Urbana-Champaign^1 University of Michigan^2

yongjoo@illinois.edu{joezhong,mozafari}@umich.edu 




























Estimating the selectivity of a query is a key step in almost 
any cost-based query optimizer.
Most of today's databases rely on 

histograms or samples 
that are  
    periodically 
    refreshed by re-scanning the data
    as the underlying data changes.
Since frequent scans are costly,
    these statistics are often stale 
    and lead to poor selectivity estimates.
 As an alternative to scans,
query-driven histograms
 have been proposed,
 which refine the histograms
 based on the actual selectivities 
        of the  observed queries.
 Unfortunately, these approaches are either too costly to use 
in practice—i.e., require an exponential number of buckets—or  
      quickly lose their advantage as 
    they observe more queries.





 
 In this paper, we propose a selectivity learning framework, called , 
 which falls into the query-driven paradigm
 but does not use histograms.
 Instead, it builds an internal model of
 the underlying data, which can 
 be refined significantly faster (e.g., only 
 1.9 milliseconds for 300 queries). 
 This fast refinement allows 
 to continuously 
  learn from each query and 
  yield increasingly more accurate selectivity estimates over time.
Unlike query-driven histograms, relies on a mixture model and a new optimization algorithm for training its model.

Our extensive experiments on two real-world datasets
confirm that, given the same target accuracy, is 

34.0×–179.4×
 faster than state-of-the-art query-driven histograms, including ISOMER and STHoles. Further, given the same space budget, is 26.8%–91.8% more accurate than 
periodically-updated histograms and samples, respectively.





Estimating query answers' cardinalities is an essential task for finding an optimal query plan; for modern big data analysis, even small relative improvements in query plans can lead to large savings in absolute time. The most common cardinality estimation techniques are based on precomputed data synopses, such as histograms or samples. In this work, we show we can produce much more precise cardinality estimates by learning a data distribution from thousands of (freely available) past query answers. This result is possible from our new approach that constructs a maximum entropy distribution consistent with past query answers with only O(n^2) space; this is a significant improvement over previous maximum entropy-based methods, which require O(2^n) space. This saving in space complexity also leads to a quicker data distribution learning. Thanks to this computational efficiency, we can use a much larger number of past queries (within a reasonable time-bound); thus, being able to learn a precise data distribution. Our empirical study suggests that our method is not only superior to previous learning-based cardinality estimation methods, but also superior to conventional cardinality estimation techniques, such as histograms and sampling. Also, we demonstrate that a database system using our method gradually improves the quality of its query plans as processing more queries. To the best of our knowledge, we are the first that demonstrates this database system's evolutionary behavior resulting from learning-based cardinality estimations.




[
    Yongjoo Park^1,  Shucheng Zhong^2,  Barzan Mozafari^2
    December 30, 2023
=========================================================



        
the state-of-the-art technique
     on adaptive histograms relies on the maximum entropy principle
     to refine the bucket frequencies based on the observed selectivities 
        of the past queries.






§ INTRODUCTION



Estimating the selectivity of a query—the fraction of input tuples that satisfy the query's predicate—is a fundamental component in cost-based query optimization, 
including  both traditional RDBMSs <cit.> and modern SQL-on-Hadoop engines <cit.>.
The estimated selectivities allow the query optimizer to choose the cheapest access path
or query plan <cit.>.

Today's databases typically rely on histograms <cit.> or samples <cit.> for their selectivity estimation.
These structures need to be populated in advance by performing costly table scans. 
However, as the underlying data changes, 
    they quickly become stale and highly inaccurate.
This is why they need to be updated periodically, creating additional costly operations
    in the database engine
    (e.g., ).[Some database 
    systems <cit.> automatically update their statistics when the number of modified tuples exceeds a threshold.]














To address the shortcoming of  scan-based 
approaches, 
    numerous proposals for query-driven histograms have been introduced,
        which
continuously correct and refine the histograms based on the actual 
selectivities observed after running each  query <cit.>.
 There are two approaches to query-driven histograms.
The first approach <cit.>,
which we call error-feedback histograms,

recursively splits existing buckets (both boundaries and frequencies) for every distinct query 
observed, such that  their error
is  minimized 
for the latest query.

Since the error-feedback histograms do not minimize the (average) error across multiple queries, their estimates tend to be much less accurate.
 

To achieve a higher accuracy, the second approach is to compute the bucket frequencies based on the maximum entropy principle <cit.>.
 However, this approach (which is also the state-of-the-art) requires solving an  optimization problem,
 which quickly becomes prohibitive  
as the number of observed queries (and hence, number of buckets) grows. 
Unfortunately, one cannot simply prune
    the buckets in this approach, 
as it will
    break the underlying assumptions of their optimization algorithm (called iterative scaling,
 see <ref> for details).
Therefore, they  prune the observed queries
instead in order to keep the optimization overhead feasible in practice. 
 However, this also means discarding data that could be used for learning a more accurate distribution.







Our Goal
We aim to develop a new framework for selectivity estimation  that can quickly refine its model 
    after observing each query, thereby
        producing increasingly more accurate
        estimates over time.
We call this new framework selectivity learning.
We particularly focus on designing 
    a low-overhead method that can 
        scale to a large number of observed queries
        without requiring 
        an exponential number of buckets. 
        


Our Model
To overcome the limitations of query-driven histograms, 
we use a mixture model <cit.> to capture the  unknown distribution of the data. 
A mixture model is a probabilistic model 
to approximate an arbitrary probability density function (pdf), say f(x), using a combination of simpler pdfs:

    f(x) = ∑_z=1^m   h(z)   g_z(x)

where 
g_z(x) is the z-th simpler pdf and 
h(z) is its corresponding weight.
The subset of the data 
that follows each of the simpler pdfs is called a subpopulation. 

Since the subpopulations 
are allowed to  
overlap with one another, a mixture model is strictly more expressive
  than histograms.
In fact, it is shown that mixture models can achieve a higher accuracy than histograms <cit.>, which is confirmed by  our empirical study 
(<ref>).


  To the best of our knowledge, 
    we are the first to propose 
        a mixture model for selectivity estimation.[Our mixture model   also differs from kernel density estimation <cit.>, which scans the actual data, rather than analyzing observed queries.]


Challenges
Using a mixture model for selectivity learning requires finding optimal parameter values for h(z) and g_z(x);
 however, this optimization (a.k.a. training) is challenging for two reasons.


First, the training process aims to find  parameters that maximize
the model quality, defined as  
∫ Q(f(x))   dx for some  metric of quality Q  (e.g., entropy).
However, computing this integral is non-trivial
for a mixture model since its subpopulations may overlap in  arbitrary ways.
That is, the combinations of m subpopulations can
create 2^m distinct 
ranges,
each with a potentially different value of f(x).
As a result, naïvely computing the quality of a mixture model quickly becomes  intractable as the number of observed queries grows.


Second, the outer  optimization algorithms
 are often iterative (e.g., iterative scaling, gradient descent), which means they have to repeatedly evaluate the model quality as they search for optimal parameter values. 
 Thus, even when 
 the model quality 
 can be evaluated relatively
 efficiently,
    the overall training/optimization process can be quite costly. 
In addition, the number of the iterations can depend on various factors (e.g., the distribution of data, query workloads, etc.), which makes the overall training time inconsistent and unpredictable. 




Previous Approach
Most previous SL work relies on histograms whose buckets are constructed in a workload-sensitive manner; that is, it determines where to create multidimensional buckets based on the past queries' predicates and then, assigns the weights (to those buckets) in a way that satisfies the observed selectivities for those predicates.
Early work <cit.> proposes bucket/weight splitting rules for these processes; however, its accuracy was relatively low. 
To achieve higher accuracy, recent work <cit.> assigns weights (to buckets) by solving an optimization problem, which pursues two goals simultaneously: (1) consistency with pairs of (predicate, selectivity), and (2) maximum entropy of the estimated distribution. 


Despite their high accuracy, maximum-entropy-based SL methods have two serious limitations. First, the number of the buckets may increase exponentially in the process of creating workload-sensitive buckets

(see <ref>). As a result, the size of the optimization problem also quickly grows to a computationally intractable level. Second, even if one wishes to reduce to bucket counts (thus, the complexity),
buckets cannot be arbitrarily merged or reconstructed because it may make the optimization itself impossible (<ref>). Thus, to reduce the complexity of the optimization problem, the previous work proposes to simply limit the number of (predicate, selectivity) pairs; however, this leads to lower accuracy.

These drawbacks of histogram-based SL are presented in more detail in <ref>.
In this work, we address both problems by employing an alternative model (to histograms), by formulating a new optimization problem, and by solving the optimization problem efficiently.



Challenges
First, finding a new alternative model for SL is challenging due to the sheer number of possible candidates. Basically, any models that can express a probability density function can serve as possible candidates, which includes Bayesian networks, factor graphs, Markov random fields, mixture models, etc.
Among these candidates, we must identify the one that can achieve both high accuracy and efficiency. 
Second, we must propose how to construct the alternative model for SL in a workload-sensitive manner and must formulate an optimization problem for the alternative model.
Third, we must be able to efficiently train the alternative model.
Unlike typical machine learning setting, high efficiency in model training is required for frequent model refinements (preferably after every query).




We propose to use a mixture model for as an alternative to histograms. A mixture model is a probabilistic model that can accurately approximate an arbitrary probability density function (pdf) using a combination of simpler pdfs (e.g., Gaussian distribution) <cit.>.



We call the tuples from each simpler pdf a subpopulation.
Unlike histogram buckets, the subpopulations of a mixture model may overlap with one another, which is the key to its expressiveness.

The potential drawback of using this complex model is the difficulty of training it; however, we devise an efficient approach, as described below.


Our Approach
First, to ensure the efficiency of the model quality evaluation,
we propose a new optimization objective.
Specifically, we find the parameter values that minimize
the L2 distance (or equivalently, mean squared error) 
between the mixture model
 and a uniform distribution, rather than maximizing the entropy of the model (as pursued by previous work <cit.>).
As described above, directly computing the quality of a mixture model involves costly integrations over 2^m distinct ranges. 
However, when minimizing the L2 distance, 
the 2^m integrals can be 

 reduced to 
 only m^2 multiplications, hence greatly reducing the complexity of the model quality evaluation.


 Although minimizing the L2 distance is much more efficient than maximizing the entropy, these
two objectives are closely related
(see our report <cit.> for a discussion).
 
In addition,
 


we adopt a non-conventional variant of mixture models, 
    called a uniform mixture model.
While uniform mixture models 
    have been previously explored in limited settings (with only a few subpopulations) <cit.>, 
    we find that they are quite appropriate  
     in our context as they allow for
      efficient computations of the L2 distance. 
 That is,
with this choice, we can 
evaluate the quality of a model

by only using  min, max, and multiplication operations (<ref>).
Finally, our optimization  can be expressed as a standard 
quadratic program, 
which still requires an iterative procedure.








Therefore, to avoid the costly iterative optimization,
we also devise an analytic solution that can be computed more efficiently.

Specifically,

in addition to the standard reduction 
(i.e., moving some of the
original  constraints to
the objective clause as penalty terms),




we completely relax the positivity constraints for f(x), exploiting the fact that they will be naturally satisfied in the process of approximating the true distribution of the data.
With these modifications, 
we can solve for the solution
analytically by setting
the gradient of the objective function to zero.

This simple transformation speeds up 
the training by 1.5×–17.2×.
In addition, since our analytic solution requires a constant number of operations, the training time is also 
consistent across different 
datasets and workloads.















Using these ideas, we have developed a first prototype of our selectivity learning proposal, called ,
        which allows for extremely fast model refinements.

As summarized in <ref>, differs from—and considerably improves upon—query-driven histograms <cit.>
in terms of both modeling and training

(see <ref> for a detailed comparison). 







the following para is out of place. either move and merge it with where u discussed dynamic histograms or make it a footnote to where we say we re the first to do Mixture model
Finally, we are aware of the selectivity estimation methods <cit.> that rely on a technique called kernel density estimation (KDE). Although KDE itself can be regarded as a special case of a mixture model, their objectives are creating models after database scans; thus, they are fundamentally different from or from  selectivity learning in general
1) not english and completely incomprehensible.
2) what is db scans?? 3) if they re doing sel estimation then
they have the same objective anyways so makes no sense what u re saying (see <ref>).




Contributions We make the following contributions:


  * We propose the first 
mixture model-based approach to
 selectivity estimation
(<ref>).

  * 

For training the mixture model, we design a constrained optimization problem
(<ref>). 


  * We show that the proposed optimization problem 
can be reduced (from an exponentially complex one) 
to a quadratic program and present
further optimization strategies for solving it (<ref>).

  * We conduct extensive experiments 
 on two real-world datasets to 
 compare 's performance and state-of-the-art selectivity estimation techniques  (<ref>).





Data analysis with declarative languages is an important feature for both conventional RDMBS <cit.> and modern distributed data analytics systems <cit.>. For those systems, accurate cardinality estimations are crucial for finding an optimal query plan.
A study shows the errors in cardinality estimations caused more than 10× slowdowns for 8% of benchmark queries and more than 100× slowdowns for 5% of benchmark queries, for both open source and commercial database systems <cit.>. These slowdowns are more significant for large-scale data analysis; even a small relative efficiency difference can lead to a big absolute time difference.

In reality, accurate cardinality estimations are hard when (i) correlations exist among attributes or (ii) a query selectivity is low. These conditions make commonly used static cardinality estimation techniques (such as per-attribute histograms <cit.> or sampling based methods <cit.>) inaccurate. In general, high-accuracy estimations demand more histogram bins or more sampled tuples; however, larger numbers of bins and sampled tuples inherently cause larger memory footprints and increased estimation times. Given fixed budgets of space and time, static cardinality estimation techniques are essentially suboptimal unless query workloads are completely uniform over the entire data, or future query workloads are fully known in advance (so, those techniques are optimized for those workloads). We do not make such strong assumptions.


Consistent max-entropy distribution
In this work, we focus on learning-based cardinality estimation (LCE), a class of cardinality estimation techniques that dynamically adjust their performance according to query workloads. For LCE, it is effective to model an underlying data distribution using a maximum entropy distribution consistent with past query answers. The notion of maximum entropy enables us to select the most likely probability distribution given past query answers <cit.>. This approach is principled <cit.> and more accurate compared to other existing approaches <cit.>.

Finding a maximum entropy distribution entails solving an optimization problem. Previous work used a dynamically-constructed histogram for representing an underlying data distribution, and the weights of the histogram bins were optimized by maximizing the entropy of the distribution. The major advantage of using a histogram is the simplicity it brings to the optimization process: the objective function of the optimization problem includes the terms that directly correspond to the histogram bins (see <ref>). This is possible because the bins of a histogram cover disjoint regions (of a cross product of the domains of attributes); that is, there are zero intersections among the bins. The correspondence between the histogram bins and the terms in an objective function also implies that the objective function is only as complicated as the number of the histogram bins.

Since those histogram-based LCE methods represent an underlying data distribution using a histogram obtained by solving an optimization problem, the success of those methods is contingent on the quality of a preprocessing step that generates a bounded number of histogram bins (for efficiency) in a workload-sensitive manner (for high accuracy). However, this process is surprisingly hard. Several approaches we discuss in <ref> fail either because bins overlap or because those methods are not effective for the datasets with many attributes. Existing partitioning methods <cit.> generate O(2^n) bins, where n is the number of past queries; thus, they make the optimization process prohibitively expensive. A graphical model <cit.> is only straightforward for the datasets with discrete attributes. Note that we are not against developing more sophisticated techniques for workload-sensitive bin generations; however, our proposed approach obviates such efforts.


UMM and Contributions
Our work introduces a uniform mixture model (UMM) in place of the histogram for representing an underlying data distribution. With the UMM, representing an underlying data distribution in a workload-sensitive manner becomes straightforward (<ref>). The UMM is a variant of a Gaussian mixture model <cit.>; UMM's probability density is computed as a summation of the probability densities of subpopulations—weighted uniform distributions of different sizes at different locations. This choice of using uniform distributions for the subpopulations make the computations efficient. Also, UMM does not require “zero intersection” in contrast to histogram bins. This high flexibility makes the optimization problem exponentially expensive though: its objective function involves O(2^n) terms, where n is the number of past queries. However, we show we can reduce those terms to only O(n^2) terms using a mathematical trick.


    process box/.style=
        align=center,draw=black,minimum height=7mm,minimum width=10mm,font=,
    ,
    process line/.style=
        draw=black,thick,->,
    




In the query optimization perspective, our approach addresses the O(2^n) complexity of existing partitioning methods (for histogram bins) by transferring the complexity of the bin generation to the optimization problem writing. We depict this concept in <ref>. Due to this “complexity transfer”, the optimization problem writing now generates O(2^n) terms. However, we present a technique that reduces those O(2^n) terms to O(n^2) terms using analytic approximations. This process is possible because there is no materialization (in contrast to the bin generation process). After all, it suffices for a LCE component to compute those O(n^2) terms. This computational efficiency enables our approach to build a precise data distribution by exploiting more query answers compared to previous work. From now on, we call this proposed LCE algorithm—a combination of the UMM and analytic objective function simplifications—.


I should talk about actual error reductions or speedup compared to existing work. I defer those descriptions until experiments are done.


The contribution of this work is as follows:



  * We introduce the uniform mixture model and show that we can obtain a maximum entropy distribution consistent with past query answers with O(n^2) space costs.

  * We show empirically that is superior to previous LCE work and other static cardinality estimation methods.

  * We demonstrate that a database system with gradually improves the quality of its query plans as more queries are processed.










§ PRELIMINARIES



In this section, we first define relevant notations in <ref> and then formally define the problem of query-driven selectivity estimation in <ref>. 

Next, in <ref>, we discuss the drawbacks of   previous approaches.




 §.§ Notations





 <ref> summarizes 
 the notations used throughout this paper.

Set Notations T is a relation that consists of d real-valued columns C_1, …, C_d.[Handling integer and categorical columns is discussed in <ref>.]
The range of values in C_i is [l_i, u_i] and 
the cardinality (i.e., row count) of T is
N=|T|. The tuples in T are denoted by x_1, …, x_N,  where each x_i is a size-d vector that belongs to 
B_0 = [l_1, u_1] ×⋯× [l_d, u_d]. 
Geometrically, B_0 is the area bounded by a hyperrectangle whose bottom-left corner is (l_1, …, l_d) and top-right corner is (u_1, …, u_d). The size of B_0 can thus be computed as |B_0|=(u_1 - l_1) ×⋯× (u_d - l_d).
 

Predicates  We use P_i to denote the (selection) predicate   of the i-th query on T. In this paper, a predicate is a 
conjunction[See <ref> for a discussion of disjunctions and negations.]
of one or more constraints.
Each constraint is a range constraint, which can be 
one-sided (e.g., 3≤ C1) or two-sided (e.g.,  -3≤ C1≤ 10). 
This range can be extended to also handle equality constraints on categorical data (see <ref>).
 Each predicate P_i is represented by a hyperrectangle B_i. For example, a constraint “1 ≤ C1 ≤ 3 AND 2 ≤ C2” is represented by a hyperrectangle (1, 3) × (2, u2), where 
 u2 is the upper-bound of C2.
We use P_o to denote an empty predicate, i.e., one that selects all tuples.





Selectivity
The selectivity s_i of P_i is defined as the fraction of the rows of T that satisfy the predicate. That is, s_i = (1/N) ∑_k=1^N I(x_k ∈ B_i),
where I(·) is the indicator function. 
A pair (P_i, s_i) is referred to as an observed query.[This pair is also 
referred to as an assertion by
prior work <cit.>.] Without loss of generality, we assume that n  queries have been observed for T and seek to estimate s_n+1.  
Finally, we use f(x) to denote the joint probability density function of tuple x (that has generated tuples of T).






 






 §.§ Problem Statement




Next, we formally state the problem:





[Query-driven Selectivity Estimation]


Consider a set of n observed queries (P_1, s_1), …,  (P_n, s_n) for T.
By definition, we have the following for each i=1,…,n:

    ∫_x ∈ B_i f(x)   dx = s_i




Then, our goal is to build a model of f(x) that can  estimate the selectivity s_n+1 of a new predicate P_n+1.







Initially, before any query is observed,
    we can conceptually consider a default query (P_0, 1), 
    where all tuples are selected and hence, the 
      selectivity is 1 (i.e., no predicates).








Discrete and Categorical Values
<ref> can be extended 
to support discrete attributes (e.g., integers, characters,
categorical values) and  equality constraints on them, as follows. Without loss of generality, suppose that C_i contains the integers in { 1, 2, …, b_i }. 
 To apply the solution to <ref>, it suffices to (conceptually) 
 treat these integers as real values in [1, b_i + 1] and then convert the original constraints on the integer values into range constraints, as follows.
A constraint of the form “C_i = k” 
will be converted to a range constraint of the form 
k ≤ C_i < k+1. 
 Mathematically, this is equivalent to replacing a probability mass function with a probability density function defined using

dirac delta functions.[A dirac delta function δ(x) outputs ∞ if x = 0 and outputs 0 otherwise while satisfying ∫δ(x)  dx = 1.] 
Then, the summation of the original probability mass function can   be converted to the integration of the probability density function.
String data types (e.g., char, varchar) and their equality constraints can be similarly supported, by conceptually mapping each
string into an integer (preserving their order) and applying the conversion described above for the integer data type. 

 

Supported Queries
Similar to prior work <cit.>, we support  selectivity estimation for 
predicates with conjunctions, negations, and disjunctions of   range and equality constraints on numeric and categorical columns.
We currently do not support  wildcard constraints (e.g., ),  constraints, or  constraints.
 In practice, often a fixed selectivity is used for unsupported predicates,
e.g., 3.125% in Oracle <cit.>.

To simplify our presentation, we focus on conjunctive predicates.
However, negations and disjunctions can also be easily supported.
This is because our algorithm only requires the ability to 
compute the intersection size of pairs of predicates P_i and P_j,
    which can be done
    by converting 
    P_i  P_j into  a disjunctive normal form
    and then using  the inclusion-exclusion principle
            to compute its size.

As in the previous work, 
we focus our presentation on predicates on a single relation.
However, any selectivity estimation technique for a single relation  can be applied to estimating selectivity of a join query whenever the predicates on
the individual relations are independent of the join conditions <cit.>. 



Criteria for Selectivity Learning
This section can be removed.
In solving the problem of selectivity learning (<ref>), we adopt the following general criteria used by adaptive histograms:



  * Consistency: The selectivity estimate must be consistent with the given assertions. That is, if P_n+1 = P_k, then the estimate for s_n+1 must be s_k.

  * Uniformity: Given no extra information, a uniform distribution must be preferred. For example, if we only know that the selectivity for “0 < C_1 < 2” is 0.5, the selectivity estimate for “0 < C_1 ≤ 1” must be 0.25.




The previous work <cit.> pursues uniformity by seeking a maximum entropy distribution. In contrast, pursues uniformity by seeking the distribution closest to the uniform distribution (in terms of mean squared error).

















 §.§ Join Selectivity and Other Data Types



Query-driven selectivity estimation can be generalized in two orthogonal directions: (1) estimating the selectivity of a query including joins and (2) supporting more data types.

Selectivity for JoinSelection
<ref> concerns the selectivity only for a single relation. However, the selectivity of a joined relation can also be computed by combining the selectivity estimates on a single relation and the selectivity of join conditions, under the assumption that the join conditions are independent of the selection predicates placed on individual tables <cit.>. For example, suppose that two predicates P_1 and P_2 are respectively placed on two relations T_1 and T_2, which are inner-joined on T_1.C = T_2.C.
Then, one heuristic rule for the inner-join selectivity is s_join = 1 / max(|distinct(T1.C)|, |distinct(T2.C)|) <cit.>. 
Let s_1 and s_2 be the selectivities of P_1 and P_2, respectively. Then, the number of the tuples of the joined relation can be computed as |T_1| · |T_2| · s_join· s_1 · s_2. This approach can also be applied to the other join selectivity rules <cit.>.






 §.§ Why not Query-driven Histograms



In this section, we briefly describe how query-driven histograms work <cit.>, and then discuss their limitations, which motivate our work.

How Query-driven Histograms Work



To approximate f(x) (defined in <ref>), 
query-driven histograms adjust their bucket boundaries and bucket frequencies according to 
the queries they observe.

Specifically, they first determine bucket boundaries (bucket creation step), 
and then compute their frequencies (training step), as described next.




  * Bucket Creation: Query-driven histograms determine their bucket boundaries based
on the given predicate's ranges <cit.>. If the range of a later predicate overlaps with that of an earlier predicate, they split the bucket(s) created for the earlier one   into two or more buckets in order to ensure that the buckets do not overlap with one another.

<ref> shows an example of this bucket splitting operation.


  * Training: 
After creating the buckets,   query-driven histograms assign frequencies to those buckets.

Early work <cit.> 
determines bucket frequencies in the process of bucket creations. That is, when a bucket is split into two or more, the frequency of the original bucket is also split (or adjusted),
    such that it minimizes the estimation error for the latest observed query.
 
    




However, since this process does not minimize the (average) error across multiple queries, 
    their estimates are much less accurate.
 
 More recent work <cit.> has addressed this limitation by



explicitly solving an optimization problem based on the maximum entropy principle.

That is, they search for   bucket frequencies that maximize the entropy of the distribution while remaining consistent with the actual selectivities observed.



Although using the maximum entropy principle will lead to highly accurate estimates, 
    it still suffers from two key limitations.
 



 
Limitation 1: Exponential Number of Buckets


Since existing buckets may split into multiple ones for each new observed query, 
the number of buckets can potentially grow exponentially as the number of observed queries grows.



For example, in our experiment in <ref>,
    the number of buckets was 22,370 for 100 observed queries, and 318,936 for 300 observed queries. 
Unfortunately, the number of buckets directly affects the training time. 
Specifically, using iterative scaling—the optimization algorithm used by all  previous work <cit.>—
    the cost of each iteration grows linearly with the number of variables (i.e., the number of buckets).
    
    This means that the cost of each iteration can grow exponentially with the number of observed queries.


As stated in <ref>, we address this problem by   employing a mixture model, which can express  a probability distribution more effectively than query-driven histograms.
Specifically, our empirical study in <ref> shows that—using the same number of parameters—a mixture model achieves considerably more accurate estimates than histograms.




Limitation 2: Non-trivial Bucket Merge/Pruning

Gi-ven that query-driven histograms <cit.> quickly 
become infeasible due to their large number of buckets,
    one might consider merging or pruning the buckets in an effort to
    reduce their training times.


However, merging or pruning the histogram buckets violates the assumption used by their optimization algorithms, i.e., iterative scaling.


Specifically, iterative scaling relies on the fact that a bucket is either completely included in a query's predicate range or completely outside of it.[For example, this property is required for the transition from Equation (6) to Equation (7) in <cit.>.] That is, no partial overlap is allowed. This property must hold for each of the n 
 predicates.
However, merging some of the buckets will inevitably cause  partial overlaps 
(between   
predicate  and histogram buckets). 
For interested readers, 
we have included a more detailed explanation of 
 why iterative scaling requires this assumption 
 in  <ref>.








The remedies proposed to addresses this issue still have limitations.
Early work proposes to merges buckets <cit.>; however, this approach leads to heuristic weight update rules, which is known to be less accurate <cit.>.

Recent work proposes to discard most uninformative assertions <cit.>; however, discarding assertions lowers the estimation accuracy.



In contrast, our method () completely avoids the creation of an exponential number of buckets in the first place by introducing an alternative model (<ref>).

The size of our optimization problem (i.e., the number of the variables) is only O(n).
Furthermore, there is a theoretical evidence that our approach can approximate a probability density function more precisely than histograms given the same amount of space budget <cit.>.[The cited work compares histograms and kernel density estimation (KDE); however, KDE is a special case of our approach.]



Drawback 2: Slow training
To simultaneously pursue both uniformity and consistency, recent work <cit.> maximizes the entropy of f(x) while enforcing that the selectivities computed on f(x) are consistent with the given assertions.
This constrained optimization problem is solved using a technique called iterative scaling <cit.>. Iterative scaling gradually updates parameter values (i.e., bucket weights) until convergence. However, as our empirical study in <ref> shows, the convergence speed of iterative scaling is slow, which leads to long training time for SL. In contrast, we show that a much faster optimization technique—quadratic programming—can be used by formulating an optimization problem in a way that directly minimizes the distance between f(x) and the uniform distribution (instead of maximizing the entropy of f(x)). Despite this training speedup, our method also pursues both uniformity and consistency simultaneously. Moreover, minimizing the distance between f(x) and the uniform distribution is closely related to maximizing the entropy of f(x) (<ref>).












§ QUICKSEL: MODEL




This section presents how models the population distribution and estimates the selectivity of a new query. 's model relies on a probabilistic model called a mixture model.
In <ref>, we describe the mixture model employed by . <ref> describes how to estimate the selectivity of a query using the mixture model. 
<ref> describes the details of 's mixture model construction.


















 §.§ Uniform Mixture Model



A mixture model is a probabilistic model that expresses a (complex) probability density function (of the population) as a combination of (simpler) probability density functions (of subpopulations). The population distribution is the one that generates the tuple x of T. The subpopulations are internally managed by to best approximate f(x).

Uniform Mixture Model
uses a type of mixture model, called the uniform mixture model.
The uniform mixture model represents a population distribution f(x) as a weighted summation of multiple uniform distributions, g_z(x) for z = 1, …, m. Specifically,

    f(x) = ∑_z=1^m   h(z)   g_z(x) = ∑_z=1^m   w_z   g_z(x)

where h(z) is a categorical distribution that determines the weight of the z-th subpopulation, and g_z(x) is the probability density function (which is a uniform distribution) for the z-th subpopulation. The support of h(z) is the integers ranging from 1 to m; h(z) = w_z. The support for g_z(x) is represented by a hyperrectangle G_z. Since g_z(x) is a uniform distribution, g_z(x) = 1 / |G_z| if x ∈ G_z and 0 otherwise. The locations of G_z and the values of w_z are determined in the training stage (<ref>). In the remainder of this section (<ref>), we assume that G_z and w_z are given.


Benefit of Uniform Mixture Model
The uniform mixture model was studied early in the statistics community <cit.>; however, recently, a more complex model called the Gaussian mixture model has received more attention <cit.>.[There are other variants of mixture models <cit.>.] The Gaussian mixture model uses a Gaussian distribution for each subpopulation; the smoothness of its probability density function (thus, differentiable) makes the model more appealing when gradients need to be computed. Nevertheless, we intentionally use the uniform mixture model for due to its computational benefit in the training process, as we describe below.

As will be presented in <ref>, 's training involves the computations of the intersection size between two subpopulations, for which the essential operation is evaluating the following integral:

    ∫  g_z1(x)   g_z2(x)   dx

Evaluating the above expression for multivariate Gaussian distributions, e.g., g_z1(x) = exp(  x^⊤Σ^ 1 x ) / √((2 π)^d  |Σ|), requires numerical approximations <cit.>, which are either slow or inaccurate. In contrast, the intersection size between two hyperrectangles can be exactly computed by simple min, max, and multiplication operations.




 §.§ Selectivity Estimation with UMM




For the uniform mixture model, computing the selectivity of a predicate P_i is straightforward:


    ∫_B_i     f(x)   dx
    = ∫_B_i ∑_z=1^m  w_z   g_z(x)   dx
    = ∑_z=1^m   w_z  ∫_B_i  g_z(x)   dx 
       = ∑_z=1^m   w_z  ∫ 1/|G_z|  I(x ∈ G_z ∩ B_i)   dx
    = ∑_z=1^m   w_z  |G_z ∩ B_i|/|G_z|


Recall that both G_z and B_i are represented by hyperrectangles. Thus, their intersection is also a hyperrectangle, and computing its size is straightforward.


The integration, ∫_P_i g_j(x) dx, can only be computed after determining g_j(x).
For the reason we describe will below, uses a hyperrectangle R_j for g_j(x). Specifically, let R_j = (l_1, u_1) ×⋯× (l_d, u_d) where (l_i, u_i) is the range for the i-th dimension. We say x ∈ R_j if x ∈ [l_i, u_i] for all i = 1, …, d. Then, g_j(x) = 1 if x ∈ R_j and 0 otherwise.
Let P_i ∩ R_j be the intersection between P_i and R_j, and let |P_i ∩ R_j| be the size of the intersection. Since ∫_P_i g_j(x) dx = |P_i ∩ R_j| / |R_j|, the selectivity for P_i is simplified to:

    ∫_P_i  f(x)   dx = ∑_j=1^m   w_j  |P_i ∩ R_j|/|R_j|






 §.§ Subpopulations from Observed Queries



We describe 's approach to determining the boundaries of G_z for z = 1, …, m. 

Note that determining G_z is orthogonal to the model training process, which we describe in <ref>; thus, even if one devises an alternative approach to creating G_z, our fast training method is still applicable.



creates m hyperrectangular ranges[The number m of subpopulations is set to min(4 · n, 4,000), by default.] (for the supports of its subpopulations) in a way that satisfies the following simple criterion: if more predicates involve a point x, use a larger number of subpopulations for x.
Unlike query-driven histograms, can easily pursue this goal by exploiting the property of a mixture model: the supports of subpopulations may overlap with one another.

In short, generates multiple points (using predicates) that represent the query workloads and create hyperrectangles that can sufficiently cover those points.

Specifically, we propose two approaches for this:  a sampling-based one and a clustering-based one. The sampling-based approach is faster; the clustering-based approach is more accurate. Each of these is described in more detail below.


Sampling-based
This approach performs the following operations for creating G_z for z = 1, …, m.


  * 

Within each predicate range, generate multiple random points r.
Generating a large number of random points increases the consistency; however, limits the number to 10 since having more than 10 points did not improve accuracy in our preliminary study.

  * Use simple random sampling to reduce the number of points to m, which serves as the centers of G_z for z = 1, …, m.

  * 


The length of the i-th dimension of G_z is set to twice the average of the distances (in the same i-th dimension) to the 10 nearest-neighbor centers.



<ref> illustrates how the subpopulations are created using both (1) highly-overlapping query workloads and (2) scattered query workloads. In both cases, generates random points to represent the distribution of query workloads, which is then used to create G_z (z = 1, …, m), i.e., the supports of subpopulations. 

This sampling-based approach is faster, but it does not ensure the coverage of all random points r. In contrast, the following clustering-based approach ensures that.


Clustering-based

The second approach relies on a clustering algorithm for generating hyperrectangles:


  * Do the same as the sampling-based approach.


  * Cluster r into m groups. (We used K-means++.)


  * For each of m groups, we create the smallest hyperrectangle G_z that covers all the points belonging to the group.


Note that since each r belongs to a cluster and
we have created a hyperrectangle that fully covers each cluster,
the union of the hyperrectangles covers all r.


Our experiments primarily use the sampling-based approach due to its efficiency, but we also compare them empirically in <ref>.




The following section describes how to assign the weights (i.e., h(z) = w_z) of these subpopulations.














 §.§ SELL's Mixture Model



's learning behavior starts from its workload-sensitive generation of the UMM's subpopulations. Formally, generates the supports of those subpopulations in a workload-sensitive manner; and the weights of those subpopulations are optimized according to the given selectivity assertions (see <ref>). Here, we describe how generates those supports. Note that each of those supports are represented by a hyperrectangle defined in the domain of attributes.

Let a dataset has d attributes. The domain of a data item in the dataset is the cross product of the domains of those d attributes, i.e., (min_1, max_1) ×⋯× (min_d, max_d). Similarly, a hyperrectangle B_i is represented by the cross product of d intervals, i.e., (u_i,1,  v_i,1) ×⋯× (u_i,d,  v_i,d).  For instance, the rectangles in <ref> are expressed as (0.4,  0.8) × (0, 1) × (min_3, max_3) ×⋯× (min_d, max_d) and (0, 1) × (0.33,  0.66) × (min_3, max_3) ×⋯× (min_d, max_d), respectively.

The objective of 's subpopulation generation is to be effective for frequently queried ranges and for frequently queried attributes. For this, generates hyperrectangles by dividing each of the range constraints specified in a given selection predicate into k sub-ranges, while using the entire domain for the remaining attributes (i.e., the attributes that are not specified in the selection predicate). For instance, let a selection predicate be a range (u_i,1,  v_i,1) (on the first attribute). Let c = v_i,1 - u_i,1. Then, generates the following k hyperrectangles:


  * (u_i,1,  u_i,1 + c/k) × (min_2,  max_2) ×⋯× (min_d,  max_d)

  * (u_i,1 + c/k,  u_i,1 + 2 · c/k) × (min_2,  max_2) ×⋯× (min_d,  max_d) 

  * this list continues up to

  * (u_i,1 + (k-1)· c/k,  u_i,1 + c) × (min_2,  max_2) ×⋯× (min_d,  max_d) 

<Ref> depicts this idea. On the left subfigure, we visualize the two selection predicates (s_1 and s_2) and the two rectangular ranges selected by those selection predicates, respectively. The first selection predicate, s_1, is on A_1; the second selection predicate, s_2, is on A_2. The right figure shows the hyperrectangles (for the supports of subpopulations) generated by . divides each of the ranges specified in a selection predicate into k sub-intervals (k = 2 in this example). This process generates four (intersecting) hyperrectangles in total:  R_1 and R_2 for s_1; R_3 and R_4 for s_2, as depicted in the right subfigure. In this way, those subpopulations can provide higher resolutions for frequently queried ranges and frequently queried attributes.

Note that this subpopulation generation approach is significantly simpler than the existing partitioning methods <cit.>. This simplicity is only possible because the UMM allows the subpopulations to intersect one another. This approach is unavailable in previous histogram-based LSE methods.








§ QUICKSEL: MODEL TRAINING






This section describes how to compute the weights w_z of 's subpopulations.
For training its model, finds the model that maximizes uniformity while being consistent with the observed queries. In <ref>, we formulate an optimization problem based on this criteria. 
Next, <ref> presents how to solve the problem efficiently.






 §.§ Training as Optimization



This section formulates an optimization problem for 's training.
Let g_0(x) be the uniform distribution with support B_0; that is, g_0(x) = 1 / |B_0| if x ∈ B_0 and 0 otherwise. aims to find the model f(x), such that the difference between f(x) and g_0(x) is minimized while being consistent with the observed queries.

There are many metrics that can measure the distance between two probability density functions f(x) and g_0(x), such as the earth mover's distance <cit.>, Kullback-Leibler divergence <cit.>, the mean squared error (MSE), the Hellinger distance, and more. Among them, uses MSE (which is equivalent to L2 distance between two distributions) since it enables the reduction of our originally formulated optimization problem (presented shortly; <ref>) to a quadratic programming problem, which can be solved efficiently by many off-the-shelf optimization libraries <cit.>. Also, minimizing MSE between f(x) and g_0(x) is closely related to maximizing the entropy of f(x) <cit.>. 
See <ref> for the explanation of this relationship.

MSE between f(x) and g_0(x) is defined as follows:

    MSE(f(x), g_0(x)) = ∫ ( f(x) - g_0(x) )^2   dx


Recall that the support for g_0(x) is B_0.
Thus, obtains the optimal weights by solving the following problem.




['s Training]

obtains the optimal parameter  for its model by solving:

    _    ∫_x ∈ B_0 ( f(x) - 1/|B_0|)^2   dx 
    such that    ∫_B_i f(x)   dx = s_i   for  i = 1, …, n 
        f(x) ≥ 0

Here, (<ref>) ensures  f(x) is a proper probability density function.





In principle, there is no particular reason to prefer one to another; however, we use a variant of Kullback-Leibler divergence because it enables the conversion to a quadratic programming <cit.> (<ref>), and thus efficient model training is possible. Also, minimizing our distance metric is closely related to maximizing entropy (<ref>), which is the approach used by several previous works <cit.>.

Specifically, the variant of Kullback-Leibler (KL) divergence we use is expressed as follows:

    ∫  f(x)  log( f(x)/u(x))   dx_KL divergence   ≈∫  f(x)  ( f(x)/u(x) - 1 )   dx_Approximate KL divergence

The left-hand side of the above equation is the standard definition of the KL divergence and the right-hand side is our distance metric. The approximation is made using the first-order Taylor expansion: log x = x - 1.





 §.§ Efficient Optimization



We first describe the challenges in solving <ref>. Then, we describe how to overcome the challenges.

Challenge
Solving <ref> in a naïve way is computationally intractable. For example, consider a mixture model consisting of (only) two subpopulations represented by G_1 and G_2, respectively. Then, ∫_x ∈ B_0 (f(x) - g_0(x))^2  dx is:

    ∫_x ∈ G_1 ∩ G_2( w_1 + w_2/|G_1 ∩ G_2| - g_0(x) )^2   dx 
    
    +    ∫_x ∈ G_1 ∩ G_2( w_1/|G_1 ∩ G_2| - g_0(x) )^2   dx 
    
    +    ∫_x ∈ G_1 ∩ G_2( w_2/| G_1 ∩ G_2| - g_0(x) )^2   dx 
    
    +    ∫_x ∈ G_1 ∩ G_2( 0/| G_1 ∩ G_2| - g_0(x) )^2   dx

Observe that with this approach, we need four separate integrations only for two subpopulations.
In general, the number of integrations is O(2^m), which is O(2^n).
Thus, this direct approach is computationally intractable.


Conversion One: Quadratic Programming
<ref> can be solved efficiently by exploiting the property of the distance metric of our choice (i.e., MSE) and the fact that we use uniform distributions for subpopulations (i.e., UMM). 
The following theorem presents the efficient approach.


















The optimization problem in <ref> can be solved by the following quadratic optimization:

    _     ^⊤ Q 
    such that      A  = ß,   ≽0

where

    (Q)_ij   = |G_i ∩ G_j|/|G_i| |G_j|    
    (A)_ij = |B_i ∩ G_j|/|G_j|

The bendy inequality sign (≽) means that every element of the vector on the left-hand side is equal to or larger than the corresponding element of the vector on the right-hand side.





This theorem can be shown by substituting the definition of 's model (<ref>) into the probability density function f(x) in <ref>.
Note that minimizing (f(x) - g_0(x))^2 is equivalent to minimizing f(x)   (f(x) - 2   g_0(x)), which is also equivalent to minimizing (f(x))^2 since g_0(x) is constant over B_0 and ∫ f(x)   dx = 1.

The integration of (f(x))^2 over B_0 can be converted to a matrix multiplication, as shown below:

    ∫ (f(x))^2    dx 
    
         = ∫[ ∑_z=1^m w_z   I(x ∈ G_z)/|G_z|]^2 
        
        dx 
       = ∫∑_i=1^m ∑_j=1^m w_i w_j/|G_i| |G_j| 
          I(x ∈ G_i)   I(x ∈ G_j)   dx

which can be simplified to

    ∑_i=1^m ∑_j=1^m w_i w_j/|G_i| |G_j|  |G_i ∩ G_j|  
       = [ w_1; w_2;   ⋮; w_m ]^⊤[ |G_1 ∩ G_1|/|G_1| |G_1|                       ⋯ |G_1 ∩ G_m|/|G_1| |G_m|;                       ⋮                                               ⋮; |G_m ∩ G_1|/|G_m| |G_1|                       ⋯ |G_m ∩ G_m|/|G_m| |G_m| ][ w_1; w_2;   ⋮; w_m ]
       = ^⊤ Q


Second, we express the equality constraints in an alternative form. Note that the left-hand side of each equality constraint, i.e., ∫_B_i f(x)   dx, can be expressed as:

    ∫_B_i f(x)   dx 
    = ∫_B_i ∑_j=1^m  w_j/|G_j|  I(x ∈ G_j)   dx 
       = ∑_j=1^m  w_j/|G_j| ∫_B_i I(x ∈ G_j)   dx 
    = ∑_j=1^m  w_j/|G_j|  |B_i ∩ G_j| 
       = [ |B_i ∩ G_1|/|G_1|                 ⋯ |B_i ∩ G_m|/|G_m| ][ w_1;   ⋮; w_m ]

Then, the equality constraints, i.e., ∫_B_i f(x)   dx = s_i for i = 1, …, n, can be expressed as follows:

    [ |B_1 ∩ G_1|/|G_1|                 ⋯ |B_1 ∩ G_m|/|G_m|;                 ⋮                 ⋱                 ⋮; |B_n ∩ G_1|/|G_1|                 ⋯ |B_n ∩ G_m|/|G_m| ][ w_1;   ⋮; w_m ]
       = 
       [ s_1;   ⋮; s_m ]
       ⇒   A  = ß


Finally, ^⊤1 = 1 if and only if ∫ f(x) = 1, and ≽0 for arbitrary G_z if and only if ∫ f(x) ≥ 0.






The implication of the above theorem is significant: we could reduce the problem of O(2^n) complexity to the problem of only O(n^2) complexity.



Conversion Two: Moving Constraints
The quadratic programming problem in <ref> can be solved efficiently by most off-the-shelf optimization libraries; however, we can solve the problem even faster by converting the problem to an alternative form. We first present the alternative problem, then discuss it.





['s QP]

solves this problem alternative to the quadratic programming problem in
<ref>:

    _  ℓ() = ^⊤ Q  + λ  A  - ß^2

where

λ is a large real value (uses λ = 10^6).


In formulating <ref>, two types of conversions are performed: (1) the consistency with the observed queries 
(i.e., A  = ß) is moved into the optimization objective as a penalty term, and (2) the positivity of f(x) is not explicitly specified (by ≽0). These two types of conversions have little impact on the solution for two reasons. First, to guarantee the consistency, a large penalty (i.e., λ = 10^6) is used. Second, the mixture model f(x) is bound to approximate the true distribution, which is always non-negative. We empirically examine the advantage of solving <ref> (instead of solving the problem in <ref> directly) in <ref>.

The solution ^* to <ref> can be obtained in a straightforward way by setting its gradients of the objective (with respect to ) equal to 0:

    ∂ℓ(^*)/∂ 
    = 2   Q  ^* + 2  λ  A^⊤ (A  ^* - ß) = 0
       ⇒^* = ( Q + λ  A^⊤ A )^ 1 λ  A  ß

Observe that ^* is expressed in a closed form; thus, we can obtain ^* analytically instead of using iterative procedures typically required for general quadratic programming.
















§ EXPERIMENT



In this section, we empirically study . 
First, we compare 's end-to-end selectivity estimation quality against query-driven histograms (<ref>). 
Second, we study the efficiency of 's mixture model (<ref>).
Third, we compare 's optimization efficiency to a standard solution (<ref>). 
Fourth, we compare to the methods that rely on periodic database scans (<ref>).
In summary, our results 
show the  following:



  * End-to-end comparison against other query-driven methods:
was 
significantly faster (34.0×–179.4×) for the same accuracy—and produced much more accurate estimates (26.8%–91.8% lower error) for the same time limit—than previous query-driven methods. (<ref>)


  * Comparison against periodic database scans: For the same storage size, 's selectivity estimates were  77.7% and 91.3% more accurate than   scan-based histograms and sampling, respectively.  (<ref>)


  * Impact on PostgreSQL performance:

Using for PostgreSQL makes the system
2.25× faster (median) than the default.
(<ref>)



  * Effectiveness of 's mixture model:
's model produced considerably more accurate estimates than histograms given the same number of parameters. (<ref>)


  * Robustness to workload shifts:

's accuracy quickly recovers after sudden workload shifts.
(<ref>)



  * Optimization efficiency: 's optimization method (<ref>) 
was 1.5×–17.2× faster than solving the standard quadratic programming. (<ref>)

 









 §.§ Experimental Setup


Methods
Our experiments compare to six other selectivity estimation methods.











Query-driven Methods:



  * STHoles <cit.>: This method creates histogram buckets by partitioning existing buckets (as in <ref>). The frequency of an existing bucket is distributed uniformly among the newly created buckets.


  * ISOMER <cit.>: 

This method applies STHoles for histogram bucket creations, but it computes the optimal frequencies of the buckets by finding the maximum entropy distribution.
Among existing query-driven methods, ISOMER produced the highest accuracy in our experiments.


  * ISOMER+QP: This method combines ISOMER's approach for creating histogram buckets and 's quadratic programming (<ref>) for computing the optimal bucket frequencies. 


  * QueryModel <cit.>: 
This method computes the selectivity estimate by a weighted average of the selectivities of observed queries. The weights are determined based on the similarity of the new query and each of the queries observed in the past.




Scan-based Methods:



  * AutoHist: This method creates an equiwidth multidimensional histogram by scanning the data. It also updates its histogram whenever more than 20% of the data changes (this is the default setting with
SQL Server's   option <cit.>).





  * AutoSample: This method relies on a uniform random sample of data to estimate selectivities.
Similar to AutoHist, AutoSample updates its sample whenever more than 10% of the data changes. any citations? any real dbms uses this? Not found yet



We have implemented all methods in Java.







Datasets and Query Sets
We use two real datasets and one synthetic dataset in our
 experiments, as follows:


  * : This dataset contains the vehicle registration records of New York State <cit.>. It contains 11,944,194 rows.
Here, the queries ask for the number of  valid registrations for vehicles produced within a certain date range.
Answering these queries involves predicates on
 three attributes: , , and .
 

  * : This dataset contains the sales records of an online grocery store <cit.>. 
We use their  table, which contains 3.4 million sales records.
Here, the queries ask for the reorder frequency for
orders made during different hours of the day. Answering these queries involves
predicates on
 two attributes:  and .

(In <ref>, we use more attributes (up to ten).)


 

  * : We also generated a synthetic dataset using a bivariate dimensional normal distribution. 
We varied this dataset to study our method under workload shifts,
different degrees of correlation between the attributes, and more. 
Here, the queries count the number of points that lie within a randomly generated rectangle.


For each dataset, we measured the estimation quality   using   100 test queries
not used for training.


The ranges for selection predicates (in queries) were generated randomly within a feasible region; the ranges of different queries may or may not overlap.



Environment
All our experiments were performed on      EC2  instances, with 16-core Intel Xeon 2.5GHz and 64 GB of memory running Ubuntu 16.04.



Metrics

We use
the root mean square (RMS) error:



    RMS error = 
        (
            1/t∑_i=1^t
            (true_sel - est_sel)^2
        )^1/2

where t is the number of test queries. We report the RMS errors in percentage (by treating both true_sel and est_sel as percentages).


















 

When reporting training time, we include the time required for refining a model using an additional observed query,
which itself includes the time to store the query and run the necessary optimization routines.










 §.§ Selectivity Estimation Quality



In this section, we compare the end-to-end selectivity estimation quality of 
versus query-driven histograms. 



We have summarized the main results in <ref>.
The table reports that, for both and dataset, was significantly faster for the same accuracy, and significantly more accurate for the same time limit.


Specifically, we gradually increased the number of observed queries provided to each method from 10 to 1,000. 
For each number of observed queries, 
we measured the estimation error and training time of each method using 100 test queries.

 These results are reported 
in <ref>. 
Given the same number of observed queries,  
's training was significantly faster
 (<ref>),
 while still achieving comparable 
estimation errors 
(<ref>).
We also studied the relationship between errors and training times in <ref>, confirming 
's superior efficiency (STHoles, ISOMER+QP, and QueryModel are
omitted 
in these figures due to their poor performance). 
In summary, was able to quickly learn
from a large
 number of observed queries (i.e., shorter training time)
    and produce highly accurate models.





 §.§ Comparison to Scan-based Methods





We also compared to two automatically-updating scan-based methods, AutoHist and AutoSample,
which incorporate SQL Server's automatic updating rule into equiwidth multidimensional histograms and samples, respectively. Since both methods incur an up-front cost for obtaining
their statistics, they should produce relatively more accurate estimates initially (before seeing new queries).
In contrast, the accuracy of 's estimates 
    should quickly improve as new queries are observed.

To verify this empirically, 
    we first generated a dataset (1 million tuples) with correlation 0. We then inserted 200K new tuples generated from a distribution with a different correlation 
    after processing   200 queries, and repeated this process. 
    In other words, after processing the first 100 queries, we inserted new data with correlation 0.1; after processing the next 100 queries, we inserted new data with correlation 0.2; and continued this process until a total of 1000 queries were processed. 
    We performed this process for each method under comparison. 
    adjusted
     its model each time after observing 100 queries.
    
    AutoHist and AutoSample updated their statistics after each batch of
    data insertion. 
    and AutoHist both used 100 parameters (# of subpopulations for the mixture model and # of buckets for histograms); 
    AutoSample used a sample of 100 tuples.







<ref> shows the error of each method. 
As expected, AutoHist produced more accurate estimates initially.
However, as more queries were processed, 
    the error of drastically decreased. 
 In contrast, the errors of AutoSample and AutoHist 
    did not improve with more queries, as they only depend on the frequency 
    at which a new scan (or sampling) is performed. 
  After processing only 100 queries (i.e., initial update), 
produced more accurate estimates than both AutoHist and AutoSample.  On average (including the first 100 queries), 

was 71.4% and 89.8% more accurate than AutoHist and AutoSample, respectively. This is consistent with the previously reported observations that
    query-driven methods yield better accuracy than
        scan-based ones <cit.>.
(The reason why query-driven proposals have not  been widely adopted
to date is due to their prohibitive cost; see <ref>).

In addition, <ref> compares the update times of the three methods.
By avoiding scans, 's query-driven updates were 525× and 243× faster than AutoHist and AutoSample, respectively.


Finally, we studied how the performance of those methods changed as we increased the data dimension (i.e., the number of attributes appearing in selection predicates). First, using the dataset,
we designed each query to target a random subset of dimensions (N/2) as increasing the dimension N from 2 to 10. 
In all test cases (<ref> left), ’s accuracy was consistent, showing its ability to scale to high-dimensional data. Also in this experiment, performed significantly better than, or comparably to, histograms and sampling. 
We could also obtain a similar result using the dataset (<ref> right).
This consistent performance across different data dimensions is primarily due to how is designed; that is, its estimation only depends on how much queries overlap with one another.
















 §.§ Impact on Query Performance




This section examines 's impact on query performance. That is, we test if 's more accurate
selectivity estimates can lead to improved query performance for actual database systems (i.e., shorter latency).

To measure the actual query latencies, we used PostgreSQL ver. 10 with a third-party extension, called  <cit.>.
Using this extension, we enforced our own estimates (for PostgreSQL's query optimization) in place of the default ones.
We compared PostgreSQL Default (i.e., no hint) and —to measure the latencies of the following join query in processing the dataset:

[
    basicstyle=,
    xleftmargin=10pt
]
select count(*)
from S inner join T on S.tid = T.tid
       inner join U on T.uid = U.uid
where (range_filter_on_T)
  and (range_filter_on_S);




where the joins keys for the tables , , and  were in the PK-FK relationship, as described by the schema (of ).

<ref> shows the speedups could achieve in comparison to PostgreSQL Default. Note that does not improve any underlying I/O or computation speed; its speedups are purely from helping PostgreSQL's query optimizer choose a more optimal plan based on improved selectivity estimates. Even so, could bring 2.25× median speedup, with 3.47× max speedup. In the worst case, PostgreSQL with was almost identical to PostgreSQL Default (i.e., 0.98× speedup).







 §.§ 's Model Effectiveness



In this section, we  compare the effectiveness of 's model 
to that of models used in the previous work.

Specifically, the effectiveness is assessed by
(1) how the model size—its number of parameters—grows as the number of observed queries grows, 
and (2)
how quickly its error decreases as its number of  parameters grows.  

Here, we use 's default setting whereby   its number of parameters increases linearly with the number of observed queries, deferring the analysis of its non-default setting to <ref>.










<ref> reports the relationship between the number of observed queries and the number of model parameters.   
As discussed in <ref>, the number of buckets (hence, parameters) of ISOMER increased quickly as the number of observed queries grew. 
STHoles was able to keep the number of its parameters small due to its bucket merging technique; however, this had a negative impact on its accuracy.
 Here, used the least number of model parameters. For instance, when 100 queries were observed for , had 10× fewer parameters than STHoles and 56× fewer parameters than ISOMER.

 We also studied the relationship between  the 
 number of model parameters and the error.
 The lower the error (for the same number of model parameters), the more effective the model.



 <ref> shows the result. 
Given the same number of model parameters, produced significantly more accurate estimates. Equivalently, produced the same quality estimates with much fewer model parameters. 

























 §.§ Robustness to Workload Shifts




In this section, we test QuickSel’s performance under significant workload shifts.
That is, after observing a certain number of queries (i.e., 100 queries) around a certain region of data, the query workload suddenly jumps to a novel region.  This pattern repeats several times. 


<ref> shows the result. Here, we could observe the following pattern. QuickSel’s error increased significantly right after each jump (i.e., at query sequence #100 and at #200), producing 1.5×-3.6× higher RMS errors compared to histograms. However, QuickSel’s error dropped quickly, achieving 12×-378× lower RMS errors than histograms. This was possible due to QuickSel’s faster adaptation.







 §.§ Internal Mechanisms




In this section, we empirically study (1) the effect of 's optimization (presented in <ref>), 
and (2) two alternative mechanisms for generating subpopulations
(presented in <ref>).


Optimization Efficiency
To study 's optimization efficiency,
    we compared two approaches for solving the quadratic problem 
    defined in <ref>:
solving the original QP without 
    any modifications versus solving our modified 
version (<ref>).
We used the  
library for the former and used   (a linear algebra library) for the latter. 
Both libraries use multiple cores for parallel processing. 

<ref> shows
the time taken by   each optimization
approach. The second approach (<ref>)
was increasingly more 
efficient as the number of observed queries grew.
For example, it was 8.36× faster when the number of observed queries reached 1,000.
This is thanks to the modified problem 
having an analytical solution, while the original
problem required an iterative gradient descent 
solution.



Subpopulation Generation

We empirically studied the two subpopulation generation approaches (i.e., the sampling-based approach and the clustering-based approach, <ref>) in terms of their scalability to high-dimensional data.
Specifically, we compared their estimation accuracies and computational overhead using the dataset (with its dimension set to 2–10).

<ref> reports the results. As shown in <ref>(a), the clustering-based approach obtained impressive accuracy in comparison to the sampling-based one. However, as shown in <ref>(b), the clustering-based approach produced higher overhead (i.e., longer training times),
which is an example of the natural tradeoff between cost and accuracy.






 §.§ QuickSel's Robustness



Remove this section
 
We further studied how 's accuracy is affected by data distribution, query workloads, number of  model parameters, and number of columns in the schema.


Data Correlation
To study how 's accuracy changes based on 
different degrees of correlations in the data,
    we used  our workload,
    generating values with different correlations between columns.
    
    In each case, trained its model using 100 observed queries; the error was measured using the 
    other 100 queries (not used for training).
 As shown in <ref>, 
    the errors remained almost identical across
        all different degrees of correlation.
     
    
    
    
    
    
    
    
    



Workload Shifts
We also studied  's accuracy 
under situations where the 
query workload shifts over time. 
Here, we generated the  dataset
with

correlation 0.5.
We generated  queries with different predicates,
    with each predicate being a different rectangle in the 2-dimensional 
    space.[The purpose of this scenario
     is to 
        simulate a workload shift;
        we study high-dimensional data and 
        complex queries in <ref>.]
We simulated three scenarios of workload shifts
    by modifying these rectangular predicates. 
First, we created a random-shift workload by choosing random rectangles in the space. We also created a sliding-shift workload by gradually moving the rectangles from the left-tail of the normal
        distribution towards the right-tail.
Third, we created a no-shift workload by using the same rectangle for all queries.

 
In each scenario, we first trained on the first 10 observed queries (i.e., sequence numbers: 1–10) and   measured the accuracy on the next 10 observed queries (i.e., sequence numbers: 11–20). 
Then, we trained on the first 20 observed queries (i.e., sequence numbers: 1–20) and measured the accuracy using the next 10 observed queries (i.e., their sequence numbers: 21–30). We kept increasing the number of observed queries until we reached 
    1,000 observed queries for training.
    
The results are plotted in <ref>. 
As expected, the errors were highest under random-shift. However, the error still decreased as observed more queries; after 100 queries, the relative error was only 1.2% for the random shift-workload. The errors were lower in general for the other workloads.




Model Parameter Count
To study the relationship between 's 
number of parameters and  its accuracy, 
  we disabled 's default setting
  (i.e., # of model params = 4 × # of observed queries).
Instead, we manually controlled its number of parameters.





 
<ref> shows the results for a dataset with correlation 0.5. 
As expected, the errors were relatively higher when the number of model parameters was extremely small (i.e., 10). 
However, as soon as the number of model parameters reached 50, the errors
    were drastically reduced.




Data Dimension
Lastly, we studied the effect of data dimension
(i.e., number of columns) on error. 

Here, we generated the datasets using   multivariate normal distributions with different dimensions. 
For each dataset, 
we used three methods—AutoHist, AutoSample, and —to produce selectivity estimates for the predicates on all dimensions.
AutoHist used 1000 buckets, AutoSample used 1000 sampled rows, and used 1000 observed queries.

<ref> shows the result. The error of AutoHist increased quickly as the dimensions increased, which is a well-known problem of multidimensional histograms.
 In contrast, the errors of AutoSample and were not as sensitive to the number of dimensions of the data.
 The robustness of is due to the fact
that its internal model only depends on the intersection sizes of the query predicates (not on their dimensions).
Among these methods,  was the most accurate.












 §.§ 's Optimization Efficiency




To study the 's optimization efficiency,
    we compared two approaches for solving the quadratic problem 
    defined in <ref>:
solving the original QP without 
    any modifications versus solving our modified 
version (<ref>).
We used the  
library for the former and used   (a linear algebra library) for the latter. 
Both libraries use multiple cores for parallel processing. 

<ref> shows
the time taken by   each optimization
approach. The second approach (<ref>)
was increasingly more 
efficient as the number of observed queries grew.
For example, it was 8.36× faster when the number of observed queries reached 1,000.
This is thanks to the modified problem 
having an analytical solution, while the original
problem required an iterative gradient descent 
solution.














§ CONNECTION: MSE AND ENTROPY




The max-entropy query-driven histograms optimize their parameters (i.e., bucket frequencies) by searching for the parameter values that maximize the entropy of the distribution f(x). We show that this approach is approximately equivalent to 's optimization objective, i.e., minimizing the mean squared error (MSE) of f(x) from a uniform distribution. The entropy of the probability density function is defined as ∫ f(x)  log( f(x) )   dx. Thus, maximizing the entropy is equivalent to minimizing ∫ f(x)  log( f(x) )   dx, which is related to minimizing MSE as follows:

    ∫ f(x) log( f(x) )   dx
         ≈∫ f(x)  (f(x) - 1)   dx 
       = ∫ (f(x))^2   dx

since ∫ f(x)   dx = 1 by definition. We used the first-order Taylor expansion to approximate log(x) with x - 1. Note that, when the constraint ∫ f(x)  dx = 1 is considered, f(x) = 1/|R_0| is the common solution to both the entropy maximization and minimizing MSE.







 §.§ Integration with Existing DBMS



Frame this as a challenge

In this paper, we study the query-driven selectivity estimation (<ref>) as a standalone problem, which is not tied to any specific DBMS.
However, any query-driven selectivity estimation technique  
(including ours)
    can be integrated into a DBMS using much of their 
    existing infrastructure.


Most DBMS systems contain the module that computes actual selectivities, the module that computes selectivity estimates, and the API to store metadata in its system catalog.
For example, Spark already collects actual selectivities
in the  class <cit.>.
Although Spark currently reports this selectivity  only at query time, it can be modified to also store the observed selectivities in its metastore (which is equivalent to a DB's system catalog).
The produced selectivity estimates can then be used in
the  class.
Prior work uses a similar integration strategy but for IBM DB2 <cit.> and Microsoft SQL Server <cit.>.





§ RELATED WORK





There is   extensive  work on 
selectivity estimation due to its importance for query optimization.
In this section, we review both scan-based  (<ref>) and query-driven methods
(<ref>).
belongs to the latter category.


We have summarized the related work in <ref>.








 §.§ Database Scan-based Estimation


 
As explained in <ref>,
we use the term scan-based methods to refer to 
    techniques that directly inspect the data (or part of it) for collecting their statistics. 
These approaches differ from query-based methods which 
rely only on the actual selectivities of the observed queries.


Scan-based Histograms
These approaches approximate the joint distribution by     
  periodically scanning the data. There has been
  much work on how to efficiently express the joint distribution of multidimensional data <cit.>.


 There is also some work on  histograms 
 for special types of data, such as XML <cit.>, spatial data <cit.>, graph <cit.>, string <cit.>; or for privacy <cit.>.



Sampling
Sampling-based methods rely on a sample of data for estimating its joint distribution <cit.>. However, drawing a new random sample 
    requires a table-scan or random retrieval of tuples,
        both of which are costly operations and hence,
        are only performed periodically.
    

Machine Learning Models
Here, we first describe Kernel density estimation (KDE); then, describe its difference from mixture models (MM), which we employ for .
 KDE is a technique that translates randomly sampled data points into a distribution <cit.>.


 In the context of selectivity estimation, KDE has been
used as an alternative  to histograms <cit.>.
The similarity between KDE and mixture models (which we employ for ) is that they both express a probability density function as a summation of some basis functions.
However, KDE and MM (mixture models) are fundamentally different. KDE relies on independent and identically distributed samples, and hence lends itself to  
scan-based selectivity estimation. 
In contrast, 
    MM does not require any
    sampling and can thus be used in
        query-driven selectivity estimation (where sampling is not practical).
 


Similarly,
probabilistic graphical models <cit.>,
neural networks <cit.>,
and tree-based ensembles <cit.>
have been used for selectivity estimation.
Unlike histograms, these approaches can  capture
column correlations more succinctly.
However, applicability of these models for query-driven selectivity estimation has not been explored and remains unclear.

More recently,


sketching <cit.> and
probe executions <cit.> have been proposed, 
which differ from ours in that they build their models directly using the data
 (not query results).
Similar to histograms, using the data requires
    either periodic updates or higher query processing overhead. avoids both of these shortcomings
with its query-driven MM.





 §.§ Query-driven Estimation

 


Query-driven techniques create their histogram buckets adaptively according to the queries they observe in the workload. These can be further 
categorized into two techniques based on  how they compute their bucket frequencies: error-feedback histograms and max-entropy histograms.

Error-feedback Histograms Error-feedback histograms <cit.>  adjust bucket frequencies in consideration of the errors made by old bucket frequencies. 
 They differ in how they create histogram buckets according to the observed queries.
For example, STHoles <cit.> splits existing buckets with the predicate range of the new query.

 
 SASH <cit.> uses 
a space-efficient multidimensional histogram, called MHIST <cit.>, but determines its bucket frequencies with an error-feedback mechanism.

 
 QueryModel <cit.> 
 treats the observed queries themselves as conceptual histogram buckets and determines the distances among those buckets based on the similarities among the queries' predicates.




Max-Entropy Histograms
Max-entropy histograms <cit.> find a maximum entropy distribution  consistent with the observed queries. 


Unfortunately, these methods generally suffer from the exponential growth in their number of buckets as 
the number of observed queries grows (as discussed in <ref>).
avoids this problem by relying on mixture models.






Fitting Parametric Functions
Adaptive selectivity estimation <cit.> fits a parametric function (e.g., linear, polynomial) 
to the observed queries. 
This approach is more applicable when we know the data distribution  a priori, which is not assumed by .





Self-tuning Databases
Query-driven histograms have also been studied in the context of self-tuning databases <cit.>.

IBM's LEO <cit.> corrects  errors in any stage of query execution based on the observed queries.
Microsoft's AutoAdmin <cit.> focuses on automatic physical design, self-tuning histograms, and monitoring infrastructure. Part of this effort is ST-histogram <cit.> and STHoles <cit.> (see <ref>).
DBL <cit.> and IDEA <cit.> exploit the answers to past queries for more accurate approximate query processing.
 QueryBot 5000 <cit.> forecasts the future queries,
whereas OtterTune <cit.> 
and index <cit.>
use machine learning for automatic physical design and 
building secondary indices, respectively.






 §.§ Estimation in Commercial DBMS





 Oracle 12c uses both sampling <cit.> and scan-based histograms <cit.> for selectivity estimation. It also reuses the selectivity of an observed query if the same query is issued again <cit.>.
PostgreSQL <cit.>, IBM <cit.>, MariaDB <cit.>, and SQL Server <cit.> all rely on scan-based histograms for selectivity estimation.
In particular, SQL Server offers an option   whereby histograms are updated automatically when more than a certain percentage of tuples have been updated (20% by default).
  Hive <cit.> and   Spark <cit.> use cost-based optimizers based on the range and number of distinct values in each column. This approach can be regarded as a simple form of histograms where each bucket is a distinct value and bucket frequencies are uniform.
  


Approximate Query Processing
Approximate Query Processing (AQP) systems produce error-bounded approximate answers to (mostly) aggregate queries. Sampling-based AQP <cit.> is one of the most popular approaches; its underlying technique is similar to the sampling technique used for selectivity estimation in that it typically relies on the statistical property, such as the law of large numbers, the central limit theorem, etc. However, AQP systems typically rely on samples rather than assertions.

We are aware that the previous work called database learning (DBL) <cit.> relies on a model to improve the quality of AQP answers; the model is built from the answers to past queries. However, database learning does not employ mixture models; it relies on maximum entropy principle for constructing its model.















§ CONCLUSION AND FUTURE WORK


The prohibitive cost of 
query-driven selectivity estimation techniques 
    has greatly limited their adoption by DBMS vendors, which for the most part still rely on scan-based histograms and samples that are periodically updated
    and are otherwise stale.
In this paper, we proposed a new framework, called selectivity learning
or , which learns from every query to continuously refine its internal model of the underlying data, and therefore produce increasingly more accurate selectivity estimates over time. 
differs from previous query-driven selectivity estimation techniques by (i) not using histograms
and (ii) enabling extremely fast refinements using its mixture model.
We formally showed that
 the training cost of our mixture model   can be reduced from exponential   to only quadratic complexity (<ref>).


















Supporting Complex Joins

When modeling the selectivity of join queries,
even state-of-the-art modes  <cit.>
take a relatively simple approach:
conceptually prejoining corresponding tables,
and constructing a joint probability distribution over each join pattern.
We plan to similarly extend our current formulation of to model the  selectivity of general joins.
however,
since there may be O(2^N) join patterns given N tables,
this approach soon becomes infeasible.
    Instead, we think we need a combination of sampling
    and models. Unlike many models, sampling is 
    more robust to curse of dimensionality (i.e., 
    we can more easily handle many tables with a large number
    of columns); however,
    unlike models, sampling is less efficient in capturing
    the data distribution (as shown in our experiments).
    By combining these two, however, we will be able
    to achieve accurate estimation even for high-dimensional data.

















§ ACKNOWLEDGEMENT


This material is based upon work supported by the National Science Foundation under Grant No. 1629397 and the Michigan Institute for Data Science (MIDAS) PODS.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.




ACM-Reference-Format




  





















§ ANALYSIS OF ITERATIVE SCALING





The previous work uses an algorithm called iterative scaling to optimize the bucket frequencies. In this section, we analyze why using the approach is non-trivial when some buckets are merged or pruned.
Specifically, we show that the approach becomes non-trivial if a histogram bucket may partially overlap with a predicate range, rather than being completely within or outside of the predicate range.

Selectivity Estimation with Histograms
First, we describe how histograms can be used for selectivity estimation. This description is needed to present iterative scaling itself.
Let G_z for z = 1, …, m denote the boundary of z-th bucket. 
w_z is the frequency of the z-th bucket.
Then, the histogram approximates the distribution of data as follows:

    f(x) = w_j/|G_j|    for  G_j  such that  x ∈ G_j

For a query's predicate P_i, its selectivity can be computed as follows:

    s_i = ∑_j=1^m |B_i ∩ G_j|/|G_j|  = ß

One can observe that the above expression is akin to selectivity estimation formula with a mixture model (<ref>), which is natural since mixture models can be regarded as a generalization of histograms.


Optimization with Maximum Entropy Principle
To optimize the bucket frequencies, the previous work employs the maximum entropy principle.
When the maximum entropy principle is used, one can optimize the bucket frequencies by solving the following problem.

[Training with Max Entropy Principle]

    _     ∫  f(x)  log(f(x))   dx 
    such that      A   = ß

where A is a n-by-m matrix; its (i,j)-th entry is defined as

    (A)_i,j = |B_i ∩ G_j|/|G_j|.

ß is a size-n column vector; its i-th entry is the observed selectivity of the i-th query.


If a histogram bucket is completely included within a predicate range, A_i,j takes 1; if a histogram bucket is completely outside a predicate range, A_i,j takes 0. If a histogram bucket partially overlaps with a predicate range, A_i,j takes a value between 0 and 1.

For histograms, the integral in the above problem can be directly simplified as follows:

    ∫  f(x)  log(f(x))   dx 
    
        
    
       = ∑_i=1^m  ∫_x ∈ G_i w_i/|G_i|log( w_i/|G_i|)
         dx  
       = ∑_i=1^m   w_i  log( w_i/|G_i|)



Iterative Scaling
Iterative Scaling solves the above problem by updating model parameters in a sequential order; that is, it updates w_1 as using fixed values for other parameters, it updates w_2 as using fixed values for other parameters, and so on. This iteration (i.e., updating all w_1 through w_m) continues until those parameter values converge. In this process, the important part is the formula for the updates.

To derive this update rule, the previous work uses the Lagrangian method, as follows. In the following derivation, we suppose a slightly more general setting; that is, we allow possible partial overlaps. We first define L:

    L(, ) = ∑_j=1^m w_j 
      log( w_j/|G_j|)
      - ^⊤ (A  - ß)

where  is a size-m column vector containing m Lagrangian multipliers, i.e.,  = (λ_1, …, λ_m)^⊤.

At optimal solutions, the derivative of L with respect to  and λ must be zero. 
Let the column vectors of A be denoted by a_1, …, a_m; that is, A = [a_1, …, a_m].
Then,

    ∂ L/∂ w_j
    = log(w_j) + 1 - log(|G_j|) - a_j^⊤ = 0


Let z_i = exp(λ_i). Then,

    log( w_j/|G_j|) = a_j^⊤ - 1  
          for  j = 1, …, m 
    ⇒     w_j/|G_j| = 1/eexp( a_j^⊤) 
            for  j = 1, …, m 
    ⇒      w_j = |G_j|/e∏_i=1^n exp( A_i,j λ_i )
            for  j = 1, …, m 
    ⇒      w_j = |G_j|/e∏_i=1^n z_i^A_i,j    for  j = 1, …, m


From the constraint that ∑_j=1^m A_i,j w_j = s_i for i = 1, …, n,

    ∑_j=1^m A_i,j|G_j|/e∏_i=1^n z_i^A_i,j = s_i


Let's assume that A_i,j always takes either 0 or 1 (the condition used in the previous work); then, the above expression can be simplified to produce an analytic update rule. Let C_i be an index set such that C_i = { k | A_i,k = 1, k = 1, …, m }. Also, let D_j \ i = { k | A_k,j = 1, k = 1, …, n, k  i }. Then,

    ∑_j=1^m A_i,j|G_j|/e∏_i=1^n z_i^A_i,j = s_i 
    ⇒     ∑_j ∈ C_i|G_j|/e  z_i ∏_k ∈ D_i \ j z_k = s_i 
    ⇒     
      z_i = s_i/∑_j ∈ C_i |G_j| / e ∏_k ∈ D_i \ j z_k

Using the above equation, the previous work continues to update z_i for i = 1, …, n until convergence. Once those values are obtained, the bucket frequencies can be obtained by <ref>.

However, without the assumption that A_i,j always takes either 0 or 1,
obtaining the update equation (<ref>) from <ref> is non-trivial.







