Anna Herlihy, Guillaume Martres, Anastasia Ailamaki et al. · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2024
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 3Open access
Purdue E-pubs, Ihab F. Ilyas, Rahul Shah et al. · 2003
Cited by 0
Farouq Aliyu, Audu Musa Mabu · 2014
Research is the key to success in any society; technology on the other hand is the fastest vehicle to reach it. As such, for speedy development of any society the two have to be coupled, that is why research and internet cannot be separated. Due to the fact that the internet consists of an ever increasing interconnection of hundreds of millions of computers makes it frustrating to search for information. Even though search engines were invented to solve this problem, one needs to know how to query them in order to find the desired information in the shortest possible time. This is why it is necessary to develop a software that can optimize users query before passing it to a search engine in order to increase efficiency in search results. This paper reports in details how one of such software was successfully developed.
Cited by 3
Donna M. Kaminski · 1985
Article Query-processing optimization strategies: feasible vs optimal solutions Share on Author: Donna M. Kaminski Western Michigan University Western Michigan UniversityView Profile Authors Info & Claims ACM '85: Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspectiveOctober 1985 Pages 449–456https://doi.org/10.1145/320435.320565Online:01 October 1985Publication History 0citation244DownloadsMetricsTotal Citations0Total Downloads244Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Cited by 0
Erfan Zamanian Dolati · Repository for Publications and Research Data (ETH Zurich) · 2012
Cited by 0Open access
Nagireddy Karri · International Journal of Artificial Intelligence Data Science and Machine Learning · 2021
The framework for AI-powered query optimization that augments, rather than replaces, a classical cost-based optimizer. The design incorporates three components of learned: (i) a learned cardinality estimator that learns the correlation between joins and predicates; (ii) a neural residual cost corrector that learns cost error at the operator level; and (iii) a reinforcement-learning (RL) planner that focuses on high-leverage transformations of the plan under the constraints of latency and resource cost. The system works in two steps, first, offline training of the system based on past workloads and schema-sensitive synthetic queries, and lastly online adaptation that is done cautiously by using execution feedback (observed row counts, operator run times, spill events). Uncertainty gating is used to enforce safety, time-out-sandboxed trials, and immediate fallback to baseline heuristics. We detail an integration path that keeps optimizer modularity intact (Volcano/Cascades memoization, rule rewrites) while exposing pluggable inference hooks. Compared to a robust cost-based baseline, TPC-H/DS and JOB evaluation indicate a consistent decrease in p95/p99 latency, plan stability and decreased re-optimization, as well as a decrease in the CPU and memory consumption during peak loads. Failure modes out-of-distribution predicates, opaque UDFs and drift and demonstrate how risk can be mitigated using drift detection and canaried fine-tuning. The findings show that AI help produces empirical, trustworthy returns in combination with strong guardrails and observability
Cited by 0Open access
Stéphane Grumbach, Zoé Lacroix, Philippe Rigaux et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2000
Constraint Databases, Edité par G. Kuper, L. Libkin et J. Paradaens
Cited by 2
Nazir, Muhammad Zafar · CERN Document Server (European Organization for Nuclear Research) · 2023
Cited by 0
Priyanka R. Munot, Dipali R. Patil, Kajal P. Pathak · IJARCCE · 2019
Query optimization is the overall process of choosing the most efficient means of executing a SQL statement. The optimizer attempts to generate the best execution plan for a SQL statement. The best execution plan is defined as the plan with the lowest cost among all considered candidate plans. SQL is a nonprocedural language, so the optimizer is free to merge, reorganize, and process in any order. The cost is a number that represents the estimated resource usage for an execution plan. The cost computation accounts for factors of query execution such as I/O, CPU, and communication. To implement query optimization methods such as Heuristic Greedy based optimization, Iterative Improvement based cost optimization and Ant Colony optimization algorithms. Show Comparison of cost, execution time and response time between Heuristic Greedy based optimization; Ant Colony Optimization and Iterative Improvement based cost optimization algorithms
Cited by 1Open access
Neha Singh, Dr Manish Varshney · 2015
In this paper we suggest a method that, given a query presented to a search engine, proposes a list of concerned queries. The concerned queries are founded in antecedently published queries, and can be published by the user to the search engine to tune or redirect the search process. The method proposed is based on a query clustering procedure in which groups of semantically like queries are named. The clustering procedure uses the content of historical preferences of users registered in the query log of the search engine. The method not only discloses the related queries, but also ranks them agreeing to a relevance criterion. Finally, we show with experiments over the query log of a search engine the potency of the method.
Cited by 0
Kevin D. O’Gorman, Amr El Abbadi, Divyakant Agrawal · Software Practice and Experience · 2004
Abstract Multiple concurrent queries occur in many database settings. This paper describes the use of middleware as an optimization tool for such queries. Since common subexpressions derive from common data and the data is usually greatest at the source, the middleware exploits the presence of sharable access patterns to underlying data, especially scans of large portions of tables or indexes, in environments where query queuing or batching is an acceptable approach. The results show that simultaneous queries with such sharable accesses have a tendency to form synchronous groups (teams) which benefit each other through the operation of the disk cache, in effect using it as an implicit pipeline. The middleware exploits this tendency by queuing and scheduling the queries to promote this interaction, using an algorithm designed to promote such teamwork. This is implemented as middleware for use with a commercial database engine. The results include tests using the query mix from the TPC Benchmark ™ R, achieving a speed‐up of 2.34 over the default scheduling provided by one database. Other results show that the success depends on the details of the computing environment. Copyright © 2004 John Wiley & Sons, Ltd.
Cited by 10
Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 2008
Elsevier’s Scopus, the largest abstract and citation database of peer-reviewed literature. Search and access research from the science, technology, medicine, social sciences and arts and humanities fields.
Cited by 0
Hirohisa Seki · 1995
Cited by 0
Remko Troncon, Henk Vandecasteele, Henk V et al. · 2003
In Inductive Logic Programming (ILP), several techniques have been introduced to improve the eciency of query execution. One such technique is query pack execution. A set of queries with a common pre x, as it is generated by the re nement operator of a typical ILP system, can be executed faster after it is converted into a tree structure called a query pack. Query transformations, on the other hand, improve the eciency of executing a single query by transforming it into a dierent form that is more ecient to execute. Combining query packs with query transformations is dicult because a transformation may have a negative eect on the structure of the pack. The once-transformation is one of the most important query transformations and can improve the eciency of query execution by several orders of magnitude. In this work, we extend query pack execution in such a way that it is able to handle queries produced by the once-transformation. We do this in the context of ilProlog, a high performance Prolog system with speci c extensions for supporting ILP systems. We evaluate our approach on both arti cial domains and real world ILP applications.
Cited by 0
Ioannis Atsonios, Olivier Beaumont, Nicolas Hanusse et al. · 2011
Abstract. The view size estimation plays an important role in query optimization. It has been observed that many data follow a power law distribution. In this paper, we consider the balls in bins problem where we place balls into N bins when the bin selection probabilities follow a power law distribution. As a generalization to the coupon collector’s problem, we address the problem of determining the expected number of balls that need to be thrown in order to have at least one ball in each of the N bins. We prove that Θ ( Nα lnN c α N) balls are needed to achieve this where αistheparameterofthepowerlawdistributionandc α N = α−1 α−Nα−1 for α ̸ = 1 and c α N = 1 for α = 1. Next, when fixing the number of balls lnN that are thrown to T, we provide closed form upper and lower bounds on the expected number of bins that have at least one occupant. For n
Cited by 0
Henryk Josiński · 2000
Introduction The multidatabase system (MDBS) approach, as a solution for integrated access to information distributed among diverse data sources, has gained a lot of attention in recent years. The multidatabase system is a database system which integrates pre--existing databases allowing the users to access simultaneously database systems (DBMSs) formulating a global query based on a global schema. The component DBMSs are assumed to be heterogeneous and autonomous. Heterogeneity refers to different user interfaces, data models, query languages, and query optimization strategies [5]. Local autonomy means that each DBMS retains complete control over local data and processing. As result of this, its cost model may not be available to the global query optimizer. When a global query is submitted, it is decomposed into two types of queries [1]: -- subqueries, operating on sharable data items from local databases, -- assembling queries, consisting of,
Cited by 1
Parke Godfrey, Jarek Gryz · 1997
his is possible, and we motivate and sketch an efficient evaluation strategy for discounted queries. Consider the following example. Let the database, DB, contain five base relations: -- Faculty: Name \\Theta Department \\Theta Rank -- Staff: Name \\Theta Department \\Theta Years of Employment -- Ta: Name \\Theta Department -- Life ins: Name \\Theta Insurer \\Theta Monthly premium -- Health plan: Name \\Theta Insurer \\Theta Monthly premium Let there be two views in the DB: an employee relation, via the union of the ta relation and projections from the faculty and staff relations; and a benefits relation, via the union of projections from the<F25.43
Cited by 2
2008
Queries with common sequences of disk accesses can make maximal use of a buffer pool. We developed a middleware to promote the necessary conditions in concurrent query streams, and achieved a speedup of 2.99 in executing a workload derived from the TCP-H benchmark. 1.
Cited by 0
V R L Swamy Vadali · 2001
Query optimization in database systems having non-parametric query metrics cannot be done using dynamic programming approaches. In this thesis, we propose an approach to solve the query optimization problem of complex non-parametric query metric by formulating Ane problems from it. This approach can be applied to other complex non parametric query metrics which are monotonous.
Cited by 0
Yi-Cheng Tu, Mehrad Eslami, Zichen Xu et al. · 2022 IEEE International Conference on Big Data (Big Data) · 2022
Sharing data and computation among concurrent queries has been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of logical foundation for query processing and optimization. In this paper, we present PsiDB, a system model for processing a large number of database queries in a batch. The key idea is to generate a single query expression that returns a global relation containing all the data needed for individual queries. For that, we propose the use of a type of relational operators called <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ψ</mml:mi></mml:math>-operators in combining the individual queries into the global expression. We tackle the algebraic optimization problem in PsiDB by developing equivalence rules to transform concurrent queries with the purpose of revealing query optimization opportunities. Centering around the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ψ</mml:mi></mml:math>-operator, our rules not only cover many optimization techniques adopted in existing batch processing systems, but also revealed new optimization opportunities. Experiments conducted on an early prototype of PsiDB show a performance improvement of up to 36X over a mainstream commercial DBMS.
Cited by 4Open access