Arlen Dean, Zijin Zhang, Stefanus Jasin et al. · arXiv (Cornell University) · 2026
Deploying multiple large language models (LLMs) in parallel to classify an unknown ground-truth label is a common practice, yet the problem of optimally allocating queries across heterogeneous models remains poorly understood. In this paper, we formulate a robust, offline query-planning problem that minimizes total query cost subject to statewise error constraints which guarantee reliability for every possible ground-truth label. We first establish that this problem is NP-hard via a reduction from the minimum-weight set cover problem. To overcome this intractability, we develop a surrogate by combining a union bound decomposition of the multi-class error into pairwise comparisons with Chernoff-type concentration bounds. The resulting surrogate admits a closed-form, multiplicatively separable expression in the query counts and is guaranteed to be feasibility-preserving. We further show that the surrogate is asymptotically tight at the optimization level: the ratio of surrogate-optimal cost to true optimal cost converges to one as error tolerances shrink, with an explicit rate of $O\left(\log\log(1/α_{\min}) / \log(1/α_{\min})\right)$. Finally, we design an asymptotic fully polynomial-time approximation scheme (AFPTAS) that returns a surrogate-feasible query plan within a $(1+\varepsilon)$ factor of the surrogate optimum.
Cited by 0Open access
Jiaqi Chen, Fan Zhang, Lei Zou · 2018
With RDF knowledge base and SPARQL have been widely used, the performance of query engine gets more attention. In the actual complicated application scenarios, query engine may receive intensive query requests with similar structure in a short time, as usual these queries will be evaluated independently. Multi-query optimization evaluation approach can mine feasible common query patterns deeply, choose preferable combination of common query patterns according to the cost model, and reduce the total time consumption by taking advantage of the common query pattern evaluation results. The experiments on LUBM dataset indicate that the total evaluation time of multi-query optimization evaluation approach is shorter than sequential evaluation approach and making the throughput of query engine improve.
Cited by 0
Ke Geng, Supervisor Gill Dobbie · 2008
The objective of my research is to carry out query optimization of XML queries based on the content of the documents. Now eXtensible Markup Language (XML) [1] is widely accepted by website constructors and programmers because of its capability and its flexibility in storing and transferring semistructured data. Query transformation is the method used to improve the query execution time of the database system. Some research has been done with XML query transformation. To date, these works concentrate on the structure of XML documents and little work has been done that takes into account the content of XML documents. With XML documents there is a need to concentrate more on the content because XML is more flexible than other databases and XML documents do not typically have a schema. One of the disadvantages of the flexibility is that the structure of XML documents is inconsistent and unpredictable. Web Ontology Language (OWL) [4] is an ontology language that can formally describe the meaning of terminology used in XML documents. In contrast to other ontology languages, such as RDF (Resource Description Framework) [6], OWL provides more meaningful terms to describe the relationships of elements of the XML document. With these description methods, the elements in XML document can be grouped and described based on the features of their contents. In this research, we will undertake work in the content analysis of XML documents and how the content analysis can help XML query transformation. All the elements in an XML document will be analyzed and classified with their content features using an On Line Analytical Processing (OLAP) [10] system. We choose the OLAP system as the analysis tool because it has two important features: a multidimensional cube can help us to analyze the XML documents from different dimensions and the hierarchy provides a method to classify the elements with their content. The generated groups will be described with their features in an OWL document. With the generated OWL documents, the input XML query can be transformed to a more efficient one, which has the same function as the original query. Currently little work on building OLAP systems for XML databases has been done because of XML’s unpredictable structure. The existing methods, which can present
Cited by 0
NEMIROVSKI, Laurent, GARDY, Danièle · OpenGrey (Institut de l'Information Scientifique et Technique) · 2002
Dans cette thèse, nous avons développé deux outils qui sont des supports pour l'optimisation de requêtes. Le premier cherche à améliorer la précision du modèle de coût. Lors de l'optimisation physique, il est important de savoir évaluer de manière assez précise le nombre de pages mémoires auxquelles il faut accéder lors d'un accès disque. Ce nombre de pages dépend bien évidemment en premier lieu du nombre d'éléments (n-uplets ou objets selon que l'on soit dans un système objet ou relationnel) que l'on cherche. Il dépend également de la répartition de ces éléments. Différents types d'éléments sont stockés dans une base de données. Toutefois, il existe une logique qui les fait coexister dans la même base. En général, il existera donc une corrélation entre les différents types de données stockées dans la base. Pour être précis, il faudra prendre en compte cette corrélation quand nous ferons notre évaluation. Notre modélisation prend en compte tous ces paramètres pour calculer l'évaluation du nombre de pages. Le deuxième outil se situe au niveau de l'optimisation logique. Le schéma est un élément central de la base de données. En effet, il permet entre autre de renseigner l'utilisateur sur le contenu de la base de données. Les bases de données semi-structuréesn'imposent pas un schéma préalablement établi des données. En effet, celles-ci étant intégrées de l'extérieur, on ne peut leur imposer une forme prédéfinie. L'utilisateur n'ayant de schéma pour l'aider à formuler sa question, celle-ci pourra donc être assez évasive ou incomplète. Nous développons dans la deuxième partie de cette thèse une structure qui permet la réécriture d'une requête incomplète dans une forme plus classique.
Cited by 0
Haopu Dong, Zirui Hu, Chenhao Lu et al. · 2025
Cited by 0
HweeHwa Pang, Hongjun Lü, Beng Chin Ooi · Institutional Knowledge (InK) - Institutional Knowledge at Singapore Management University (Singapore Management University) · 1992
Cited by 0
Matthias Jarke, Maurizio Lenzerini, Yannis Vassiliou et al. · 2000
Cited by 13
Andrej Jančič · 2016
In the graduation thesis, I present database, its history of origin, and where it is placed from the perspective of cases of use on the software market. I make a short overview of examples of use from the real world, and shortly research trends of its popularity compared to related products and market as a whole. Based on my own experience, literature, official documentation, and experience of other users, I examine the cases which caused problematic operation of the database. For each of the cases I examine the possibility and advisability of solving the problem with automatic optimisation of queries. I examine the case also historically, since Elasticsearch has in the last year significantly changed. I note that automation of queries is not advisable, since the developers in Elasticsearch solved most of the cases with architectural changes, internal optimisation, and a change of query language, which takes away from the user ambiguity in expressing the queries. I establish that the most important feature of well-functioning cluster is a proper size of shards, which cannot be easily changed. For that, an experimental planning of activities is necessary, which I also describe. In addition to optimum size of shard, there are some bad practices, which I also describe in the thesis; with them we can collapse cluster, and it is important that they are known by the user.
Cited by 0
Rafael Alonso, Sumit Ganguly · 1992
Recently, a number of small yet powerful mobile computers have appeared on the market. Endowed with large disk capacity and network hardware, such systems are capable of holding large amounts of data, as well as of exchanging information with other hosts on a distributed system. These features suggest the need for the design and implementation of a distributed database system for mobile computers. Such mobile database systems present a host of technical challenges. One of them is dealing with the limited battery capacity of current mobile machines. We investigate the possibility of increasing the effective battery life of these computers by selecting energy-efficient query plans during query optimization. In this paper we review the capabilities of mobile computers and describe the power management issues in such systems. We examine the case of database systems on stand-alone mobile computers, and conclude that only a small modification is needed in standard query optimizers. However, ...
Cited by 0
The Clarit System, Natasa Milic-frayling, Chengxiang Zhai et al. · 1998
this report, one CLARITECH linguist, and two non-technical volunteers. The 50 ad-hoc topics were divided up Non-Relevant
Cited by 0
Raghav Kaushik, Jeffrey F. Naughton, Raghu Ramakrishnan et al. · ACM Transactions on Database Systems · 2005
Database systems use precomputed synopses of data to estimate the cost of alternative plans during query optimization. A number of alternative synopsis structures have been proposed, but histograms are by far the most commonly used. While histograms have proved to be very effective in (cost estimation for) single-table selections, queries with joins have long been seen as a challenge; under a model where histograms are maintained for individual tables, a celebrated result of Ioannidis and Christodoulakis [1991] observes that errors propagate exponentially with the number of joins in a query.In this article, we make two main contributions. First, we study the space complexity of using synopses for query optimization from a novel information-theoretic perspective. In particular, we offer evidence in support of histograms for single-table selections, including an analysis over data distributions known to be common in practice, and illustrate their limitations for join queries. Second, for a broad class of common queries involving joins (specifically, all queries involving only key-foreign key joins) we show that the strategy of storing a small precomputed sample of the database yields probabilistic guarantees that are almost space-optimal, which is an important property if these samples are to be used as database statistics. This is the first such optimality result, to our knowledge, and suggests that precomputed samples might be an effective way to circumvent the error propagation problem for queries with key-foreign key joins. We support this result empirically through an experimental study that demonstrates the effectiveness of precomputed samples, and also shows the increasing difference in the effectiveness of samples versus multidimensional histograms as the number of joins in the query grows.
Cited by 9
W. Kim · ACM SIGMOD Record · 1983
No abstract available.
Cited by 0
Dennis Shasha · 1992
Cited by 0
Kraft, Tobias · Fachbereich Informatik (University of Stuttgart) · 2009
Cited by 0
Arlen Dean, Zijin Zhang, Stefanus Jasin et al. · ArXiv.org · 2026
Deploying multiple large language models (LLMs) in parallel to classify an unknown ground-truth label is a common practice, yet the problem of optimally allocating queries across heterogeneous models remains poorly understood. In this paper, we formulate a robust, offline query-planning problem that minimizes total query cost subject to statewise error constraints which guarantee reliability for every possible ground-truth label. We first establish that this problem is NP-hard via a reduction from the minimum-weight set cover problem. To overcome this intractability, we develop a surrogate by combining a union bound decomposition of the multi-class error into pairwise comparisons with Chernoff-type concentration bounds. The resulting surrogate admits a closed-form, multiplicatively separable expression in the query counts and is guaranteed to be feasibility-preserving. We further show that the surrogate is asymptotically tight at the optimization level: the ratio of surrogate-optimal cost to true optimal cost converges to one as error tolerances shrink, with an explicit rate of $O\left(\log\log(1/α_{\min}) / \log(1/α_{\min})\right)$. Finally, we design an asymptotic fully polynomial-time approximation scheme (AFPTAS) that returns a surrogate-feasible query plan within a $(1+\varepsilon)$ factor of the surrogate optimum.
Cited by 0Open access
Buwen Wu, Yongluan Zhou, Hai Jin et al. · 2017
Existing parallel SPARQL query optimizers assume hash-based data partitioning and adopt plan enumeration algorithms with unnecessarily high complexity. Therefore, they cannot easily accommodate other partitioning methods and only consider an unnecessarily limited plan space. To address these problems, we first define a generic RDF data partitioning model to capture the common structure of various state-of-the-art RDF data partitioning methods. Then we propose a query plan enumeration algorithm that not only has an optimal efficiency, but also accommodates different data partitioning methods. Furthermore, based on a solid analysis of the complexity of the plan enumeration algorithm, we propose two new heuristic methods that can consider a much larger plan space than the existing methods, and at the same time can still confine the search space of the algorithm. An autonomous approach is proposed to choose one of the two methods by considering the structure and the size of a complex SPARQL query. We conduct extensive experiments using synthetic and a real-world dataset, which show the superiority of our algorithms in comparing to existing ones.
Cited by 7
Ihab F. Ilyas, Rahul Shah, Walid G. Aref et al. · 2004
Ranking is an important property that needs to be fully supported by current relational query engines. Recently, several rank-join query operators have been proposed based on rank aggregation algorithms. Rank-join operators progressively rank the join results while performing the join operation. The new operators have a direct impact on traditional query processing and optimization.We introduce a rank-aware query optimization framework that fully integrates rank-join operators into relational query engines. The framework is based on extending the System R dynamic programming algorithm in both enumeration and pruning. We define ranking as an interesting property that triggers the generation of rank-aware query plans. Unlike traditional join operators, optimizing for rank-join operators depends on estimating the input cardinality of these operators. We introduce a probabilistic model for estimating the input cardinality, and hence the cost of a rank-join operator. To our knowledge, this paper is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans, although challenging, is key to the full integration of rank-join operators in real-world query processing engines. We experimentally evaluate our framework by modifying the query optimizer of an open-source database management system. The experiments show the validity of our framework and the accuracy of the proposed estimation model.
Cited by 119
Anna Herlihy, Guillaume Martres, Anastasia Ailamaki et al. · arXiv (Cornell University) · 2023
Performance-critical industrial applications, including large-scale program, network, and distributed system analyses, are increasingly reliant on recursive queries for data analysis. Yet traditional relational algebra-based query optimization techniques do not scale well to recursive query processing due to the iterative nature of query evaluation, where relation cardinalities can change unpredictably during the course of a single query execution. To avoid error-prone cardinality estimation, adaptive query processing techniques use runtime information to inform query optimization, but these systems are not optimized for the specific needs of recursive query processing. In this paper, we introduce Adaptive Metaprogramming, an innovative technique that shifts recursive query optimization and code generation from compile-time to runtime using principled metaprogramming, enabling dynamic optimization and re-optimization before and after query execution has begun. We present a custom join-ordering optimization applicable at multiple stages during query compilation and execution. Through Carac, a custom Datalog engine, we evaluate the optimization potential of Adaptive Metaprogramming and show unoptimized recursive query execution time can be improved by three orders of magnitude and hand-optimized queries by 6x.
Cited by 0Open access
Dmitri Korotkevitch · Apress eBooks · 2014
SQL Server Query Processor is perhaps the least visible and least well-known part of SQL Server. It does not expose a large set of the public features, and it allows very limited control in a documented and supported way. It accepts a query as input, compiles and optimizes it generating the execution plan, and executes it.
Cited by 0
Sebastian Maneth, Kim Nguyễn · arXiv (Cornell University) · 2010
Previous work reports about SXSI, a fast XPath engine which executes tree automata over compressed XML indexes. Here, reasons are investigated why SXSI is so fast. It is shown that tree automata can be used as a general framework for fine grained XML query optimization. We define the "relevant nodes" of a query as those nodes that a minimal automaton must touch in order to answer the query. This notion allows to skip many subtrees during execution, and, with the help of particular tree indexes, even allows to skip internal nodes of the tree. We efficiently approximate runs over relevant nodes by means of on-the-fly removal of alternation and non-determinism of (alternating) tree automata. We also introduce many implementation techniques which allows us to efficiently evaluate tree automata, even in the absence of special indexes. Through extensive experiments, we demonstrate the impact of the different optimization techniques.
Cited by 1Open access