Systematic approach to query optimization

Details Systematic approach to query optimization Systematic approach to query optimization

2000-09-06

2003-05-20

Jung, David (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06567802

ABSTRACT:

BACKGROUND OF THE INVENTION
Many investigators have studied semantic query optimization for relational systems (e.g., Cheng et al, In
Proceedings of VLDB
, pg 687-698 (September 1999); Grant et al., In
Proceedings of ICDE
(1997); Chakravarthy et al.,
AC Transactions on Database Systems
, 15(2):162-207 (1990), and the references cited therein). The techniques most frequently used, include: index introduction, joint elimination, scan reduction, join introduction, predicate elimination and detection of empty answers (Grant et al., 1997).
Both Tsatlos et al. (In
Proceedings of
20
th
VLDB Conf
., Santiago, Chile (1994)) and Fegaras et al. (In
Proceedings of the
5
th
Int'l Workshop on Database Programming Languages
(DBPL195), Umbria, Italy (1995)) have developed special constructs and types for representing physical structures, but the operations on them that can be used in a query plan (e.g., joins or comprehensions) do not explicitly distinguish them from relations/complex values. Research efforts investigating physical data independence as the central issue or closely related problems, have all recognized physical data independence as an optimization problem, that is how does one rewrite a query Q(&Lgr;) written against a logical schema &Lgr; into an equivalent query plan Q′(&PHgr;) written against a physical schema &PHgr;, given a semantic relationship between &Lgr; and &PHgr;. See, Chaudhuri et al., In
Proceedings of ICDE
, Taipei, Taiwan (1995); Levy et al., In
Proceedings of PODS
(1995); Chen et al., In
Proceedings of the Int'l Conf. on Extending Database Technology
(1994); Yang et al., In
Proceedings of the
13
th
Int'l VLDB Conf
. pg 245-254 (1987)); Keller and Basu, In
Proceedings of the Int'l Conference on Parallel and Distributed Information Systems
, 1994; Levy et al., In
Proceedings of PODS
, 1995; Qian, In
Proceeding ICDE
, pg 48-55, 1996; Rajarman et al., In
Proceedings
14
th
ACM Symposium In Principles of Database System
, pg 105-112 (1995); Fegaras et al., In
Proceedings of the
5
th
Int'l Workshop on Database Programming Languages
(
DBPL
95), Umbria, Italy (1995); Tsatlos et al., (1994); Yang et al., In
Proceedings of the
13
th
Int'l VLDB Conference
, pg 245-254 (1987).
Conventional relational optimization methods (Selinger et al., In
Proceedings of ACM SIGMOD Int'l Conference on Management of Data
, pg 23-34, 1979, Reprinted in
Reading in Database System
, Kaufmann, 1988), such as selection pushing and join reordering, have long relied on ad-hoc heuristics for introducing indexes into a plan. Gmaps (Tsatlos et al., 1994) have been proposed as an alternative, as have studies into object-oriented data independence (Kemper et al., In
Proceedings of ACM SIGMOD Internat'l Conf. on Management of Data
, pg 264-374 (1990), and into distributed, mediator-based systems (Wiederhold,
IEEE Computer
, pg 38-49 (1992) for information integration. However, the previously reported techniques (Chaudhuri et al., 1995; Levy et al., 1995; Qian, 1996; Rajarman et al., 1995) are neither general enough, nor flexible enough, to be adapted to the current problems.
Chase transformation was originally defined for conjunctive (tableau) queries and embedded implicational dependencies. Popa and Tannen (In
Proceedings of ICDT
, Jerusalem, Israel, January 1999) generalized the classical relational tableau chase procedure (Beeri et al.,
Journal of the ACM
31(4):718-741 (1984)) to work for the object-oriented model and dictionaries, and for dependencies that capture a large class of semantic constraints including referential integrity constraints, inverse relationships, nested functional dependencies, etc. Moreover, they have shown that classical tableau minimization (Chandra and Merlin, In Proceedings of 9
th
ACM Symposium on Theory of Computing
, pg 77-90, Boulder, Colo., (1977; Aho et al.,
ACM Transactions on Database Systems
, 4(4):435-454 (1979) can be generalized correspondingly, as chasing with “trivial” (always true) constraints.
Limited use of the chase to path-conjunctive queries and dependencies, presented by Popa and Tannen, 1999, permit the capture of object-oriented queries and queries against Web-like interfaces described by dictionary (finite function) operations. Dictionaries also describe many physical access structures, giving succinct declarative descriptions of query plans, in the same language as the queries. Subsequently, Deutsch et al, in
VLDB
(September 1999), showed that the elements of the implementation mapping (physical access structures, materialized views, etc.) are uniformly captured by the same kind of constraints and that can use the chase (forwards and backwards) to find the solutions of the equation mentioned above.
Although in an earlier manuscript, Jarke et al., In
Proceedings of ACM
-
SIGMOD
, pg 316-325 (1984), described chasing with functional dependencies, tableau minimization and join elimination with referential integrity constraints, surprisingly few experimental results are actually reported in the prior art. Grant et al., (1997) report on join elimination in star queries that are less complex than the present experiments with EC2. Examples of SQO for OO systems appear in Beeri et al.,
Theoretical Computer Science
, 116(1):59-94 (1993); Cherniack. et al., In
Proceedings of
24
th
VLDB Conf
., pg 239-250 (1998); Fegaras et al., 1995); and Grant et al., 1997. A general framework for SQO using rewrite rules that are expressed using OQL appears in the work of Florescu, “Design and implementation of the Flora Object Oriented Query Optimizer,” PhD thesis, Universite of Paris (1996), and Florescu et al.,
Int'l Journal of Cooperative Information Systems
5(4) (1996).
Techniques for using materialized views in query optimization are discussed in the works of Chaudhuri, et al., 1995), both Florescu manuscripts (1996); Tsatalos et al.,
VLDB Journal
5(2):101-118 (1996) and Bello et al., In Proceedings of 24
th
VLDB Conf
, pg 659-664 (1998). Also relevant is the work on join indexes by Valduriez,
ACM Trans. Database Systems
, 12(2):218-452 (1987), and on precomputed access support relations by Kemper et al., In
Proceedings of ACM-SIGMOD Int'l Conf on Management of Data
, pg 364-374 (1990).
However, the problem remains of how to optimize queries aimed at disparate targets, particularly in complex situations. The general problem is forced by data independence, i.e., how to reformulate a query written against a “user”-level schema into a plan that also/only uses physical access structures and materialized views efficiently. The gmap approach (Tsatalos et al., 1996) works with a special case of conjunctive queries (PSJ queries). The core algorithm is exponential, but the restriction to PSJ is used to provide polynomial algorithms for the steps of checking relevance of views and checking a restricted form of query equivalence. However, in light of current findings, there is no measurable practical benefit from all these restrictions.
Moreover, the schemas, views and queries of Chaudhuri et al., 1995; Tsatalos et al., 1996; and Yang et al., 1987, lack significant complexity. Their experiments show that using views is possible, and in the case of Tsatalos et al., 1996, that it can produce faster plans. However, Yang et al. measured only optimization time, and Tsatalos et al. did not separate the cost of the optimization itself. Consequently, they do not offer value that can be compared with time reduction. Although Chaudhuri et al. showed a very good behavior of the optimization time as a function of plans produced, the findings are ineffective because the use of bag semantics restricts variable mappings to isomorphisms, thus greatly reducing the search space.
Deutsch et al. 1999, recently demonstrated the promising potential of the chase and backchase technique (C&B), but raised the natural question: Is this technique practical? This raises two sets of issues that until the present invention remained unanswered in the art:
1. Are these feasible implementation

Affiliated with

Also associated with

Rating

Systematic approach to query optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Systematic approach to query optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systematic approach to query optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3023179