Swapnil Gupta, Sreyash Kenkre, Partha Talukdar. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

To address the classical selectivity estimation problem for OLAP queries in relational databases, a radically different approach calledPlanBouquetwas recently proposed in[1], wherein the estimation process is completely abandoned and replaced with a calibrated discovery mechanism. The beneficial outcome of this new construction is that provable guarantees on worst-case performance, measured as Maximum Sub-Optimality (MSO), are obtained thereby facilitating robust query processing. ThePlanBouquetformulation suffers, however, from a systemic drawback—the MSO bound is a function of not only the query, but also the optimizer's behavioral profile over the underlying database platform. As a result, there are adverse consequences: (i) the bound value becomes highly variable, depending on the specifics of the current operating environment, and (ii) it becomes infeasible to compute the value without substantial investments in preprocessing overheads. In this paper, we first presentSpillBound, a new query processing algorithm that retains the core strength of thePlanBouquetdiscovery process, but reduces the bound dependency to only the query. It does so by incorporating plan termination and selectivity monitoring mechanisms in the database engine. Specifically,SpillBounddelivers a worst-case multiplicative bound, of$D^2+3D$, where$D$is simply the number of error-prone predicates in the user query. Consequently, the bound value becomes independent of the optimizer and the database platform, and the guarantee can be issued simply by query inspection. We go on to prove thatSpillBoundis within an$O(D)$factor of thebest possibledeterministic selectivity discovery algorithm in its class. We next devise techniques to bridge this quadratic-to-linear MSO gap by introducing the notion ofcontour alignment, a characterization of the nature of plan structures along theboundariesof the selectivity space. Specifically, we propose a variant ofSpillBound, calledAlignedBound, which exploits the alignment property and provides a guarantee in the range$\mathbf {[2D+2,D^2+3D]}$. Finally, a detailed empirical evaluation over the standard decision-support benchmarks indicates that: (i)SpillBoundprovides markedly superior performance w.r.t. MSO as compared toPlanBouquet, and (ii)AlignedBoundprovides additional benefits for query instances that are challenging forSpillBound, often coming close to the ideal of MSO linearity in$D$. From an absolute perspective,AlignedBoundevaluates virtually all the benchmark queries considered in our study with MSO of around10or lesser. Therefore, in an overall sense,SpillBoundandAlignedBoundoffer a substantive step forward in the long-standing quest for robust query processing.

To address the classical selectivity estimation problem in database systems, a radically different query processing technique called PlanBouquet was proposed in 2014. In this approach, the estimation process is completely abandoned and replaced with a calibrated selectivity discovery mechanism. The beneficial outcome is that provable guarantees are obtained on worst-case execution performance, thereby facilitating robust query processing. An improved version of PlanBouquet, called SpillBound (SB), which significantly accelerates the selectivity discovery process, and provides platform-independent performance guarantees, was presented two years ago.

To address the classical selectivity estimation problem in databases, a radically different approach called PlanBouquet was recently proposed in [3], wherein the estimation process is completely abandoned and replaced with a calibrated discovery mechanism. The beneficial outcome of this new construction is that, for the first time, provable guarantees are obtained on worst-case performance, thereby facilitating robust query processing.

Motivated by scheduling scenarios in large shared computing systems, we study the problem of reusable resource scheduling. In this problem, there are many resources, each specified by a capacity, duration, per-use cost, and an availability window comprising of a release time and a deadline. A resources can be reused multiple times within its availability window with each use being limited by the duration associated with the resource and incurring cost equal to per-use cost. Different uses of a resource have to be non-overlapping. Given a demand profile, the goal is to cover it by scheduling the resources within their availability windows while minimizing their total cost. Reusable resource scheduling is a generalization of the well known interval covering problem. We present approximation algorithms and hardness results for the reusable resource scheduling problem. While the interval cover problem is NP-hard, it can be solved optimally for the special case where all the resources have unit capacities. In contrast, we show that the reusable resource scheduling is NP-hard and APX-hard, even for the case where the resources have unit capacities and unit costs. The approximation algorithms are derived by considering the notion of colored interval coloring, which could be of independent interest.

The problem of ordering a set of entities which contain inherent ties among them arises in many applications. Notion of “bucket order” has emerged as a popular mechanism of ranking in such settings. A bucket order is an ordered partition of the set of entities into “buckets”. There is a total order on the buckets, but the entities within a bucket are treated as tied. In this paper, we focus on discovering bucket order from data captured in the form of user preferences. We consider two settings: one in which the discrepancies in the input preferences are “local” (when collected from experts) and the other in which discrepancies could be arbitrary (when collected from a large population). We present a formal model to capture the setting of local discrepancies and consider the following question: “how many experts need to be queried to discover the underlying bucket order on n entities?”. We prove an upperbound of . In the case of arbitrary discrepancies, we model it as the bucket order problem of discovering a bucket order that best fits the data (captured as pairwise preference statistics). We present a new approach which exploits a connection between the discovery of buckets and the correlation clustering problem. We present empirical evaluation of our algorithms on real and artificially generated datasets.