Query optimizer system that detects and prevents mutating table violations of database integrity in a query before execution plan generation
First Claim
1. A method for optimizing the execution plan of a query that enforces database integrity in a relational database processing system having a stored database including a plurality of base tables {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of quantifier nodes {Ni } each representing a relational operation, wherein each said quantifier node Ni receives from each of one or more other said quantifier nodes {Nj } a flow of records represented by a directed data-flow arc Aji forming part of a data-flow path and wherein i and j are positive integers, said method comprising the steps of:
- (a) evaluating said query graph G for each said base table Teach to identify common-referencing pairs of said quantifier nodes for which said each base table Teach is the object;
(b) reforming said query graph G to restrict said data-flow path to sequence the execution of each said common-referencing pair of quantifier nodes to produce a query graph GMTI that enforces database integrity during table mutation;
(c) generating a plurality of plans for executing said query graph GMTI ; and
(d) evaluating the execution cost of each said query execution plan and selecting said optimal execution plan.
1 Assignment
0 Petitions
Accused Products
Abstract
An automated system for detecting and preventing mutating table violations of database integrity in a SQL query before generation and selection of an optimal query execution plan (QEP). This system modifies the query graph model (QGM) to restrict the choice of execution plans to those that avoid mutating table integrity (MTI) violations, thereby forcing database integrity during table mutation when executing the optimal QEP. Mutating table integrity violations are detected by evaluating the position in the QGM of each write-node referencing a particular base table with respect to each of the positions of all other read- and write-nodes referencing of the same base table. Every common-referencing node pair is tested for sequencing conflicts and a data-flow dam is inserted in the QGM where necessary to force the completion of the execution of one node before initiating execution of the other common-referencing node. The system of this invention allows processing of all non-cyclic and most cyclic SQL queries known to cause mutating table integrity violations, such as queries having searched and positioned inserts, deletes and updates, and row-level triggers.
164 Citations
20 Claims
-
1. A method for optimizing the execution plan of a query that enforces database integrity in a relational database processing system having a stored database including a plurality of base tables {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of quantifier nodes {Ni } each representing a relational operation, wherein each said quantifier node Ni receives from each of one or more other said quantifier nodes {Nj } a flow of records represented by a directed data-flow arc Aji forming part of a data-flow path and wherein i and j are positive integers, said method comprising the steps of:
-
(a) evaluating said query graph G for each said base table Teach to identify common-referencing pairs of said quantifier nodes for which said each base table Teach is the object; (b) reforming said query graph G to restrict said data-flow path to sequence the execution of each said common-referencing pair of quantifier nodes to produce a query graph GMTI that enforces database integrity during table mutation; (c) generating a plurality of plans for executing said query graph GMTI ; and (d) evaluating the execution cost of each said query execution plan and selecting said optimal execution plan. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A query optimizer system in a relational database processing system having a plurality of base tables {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of quantifier nodes {Ni } each representing a relational operation, wherein each said quantifier node Ni receives from each of one or more other said quantifier nodes {Nj } a flow of records represented by a directed data-flow arc Aji forming part of a data-flow path and wherein i, j are positive integers, said system comprising:
-
base table review means coupled to said data processor for evaluating said query graph G for each said base table Teach to identify common-referencing pairs of said quantifier nodes for which said each base table Teach is the object; data-flow restriction means coupled to said base table referencing means for restricting said data-flow path to sequence the execution of each said common-referencing pair of quantifier nodes to produce a query graph GMTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of plans for executing said query graph GMTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said execution plan. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A database processing system comprising:
-
a data store for storing a plurality of base tables {T}; a data processor coupled to said data store for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of quantifier nodes {Ni } each representing a relational operation, wherein each said quantifier node Ni receives from each of one or more other said quantifier nodes {Nj } a flow of records represented by a directed data-flow arc Aji forming part of a data-flow path and wherein i, j are positive integers; base table review means coupled to said data processor for evaluating said query graph G for each said base table Teach to identify common-referencing pairs of said quantifier nodes for which said each base table Teach is the object; data-flow restriction means coupled to said base table referencing means for restricting said data-flow path to sequence the execution of each said common-referencing pair of quantifier nodes to produce a query graph GMTI that enforces database integrity during table mutation; query plan means coupled to said data-flow restriction means for generating a plurality of plans for executing said query graph GMTI ; and query evaluation means coupled to said query plan means for evaluating the execution cost of each said query execution plan and for selecting an optimal said execution plan. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A computer program product, for use with a relational database processing system having a stored database including a plurality of base tables {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of quantifier nodes {Ni } each representing a relational operation, wherein each said quantifier node Ni receives from each of one or more other said quantifier nodes {Nj } a flow of records represented by a directed data-flow arc Aji forming part of a data-flow path and wherein i and j are positive integers, said computer program product comprising:
-
a recording medium; means recorded on said recording medium, for directing said data processor to evaluate said query graph G for each said base table Teach to identify common-referencing pairs of said quantifier nodes for which said each base table Teach is the object; means recorded on said recording medium, for directing said data processor to reform said query graph G to restrict said data-flow path to sequence the execution of each said common-referencing pair of quantifier nodes to produce a query graph GMTI that enforces database integrity during table mutation; means, recorded on said recording medium, for directing said data processor to generate a plurality of plans for executing said query graph GMTI ; and means, recorded on said recording medium, for directing said data processor to evaluate the execution cost of each said query execution plan and selecting said optimal execution plan. - View Dependent Claims (17, 18, 19, 20)
-
Specification