ADAPTIVE FILTER INDEX FOR DETERMINING QUERIES AFFECTED BY A DML OPERATION

• US 20100036803A1
• Filed: 12/02/2008
• Published: 02/11/2010
• Est. Priority Date: 08/08/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mullick, Atrayee, Sinha, Bipul, Ganesh, Amit, Gawlick, Dieter, Vemuri, Srinivas S.
• Granted Patent: US 8,185,508 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/24565 Triggers; Constraints

Abstract

Techniques are disclosed for creating and using a filter index in order to identify registered queries whose result sets are likely to have been changed by changes made to tables. The filter index entries are based on filter conditions. The filter conditions are created based on predicates contained in the registered queries. The filter conditions may include exclusive predicates and join predicates. Join predicates that join a table T1 with a table T2 may be instantiated by replacing references to table T2 with values extracted from table T2. Various techniques are described for recognizing situations in which a query can be included in, or excluded from, the set of likely-changed queries, without fully evaluating the filter conditions that correspond to the queries.

Claims

1. A method comprising:

receiving a query that includes a join predicate between a first table and a second table;

generating a virtual clause based on the join predicate;

generating a join source query based on the WHERE CLAUSE of the query;

executing the join source query to obtain a set of one or more values from the second table;

creating a filter condition based on the virtual clause and the one or more values obtained from the join source query;

storing the filter condition in an index in association with an identifier for said query.

2. The method of claim 1 further comprising:

in response to a change made to the first table, performing the steps of

reading the filter condition from the index;

determining whether the change satisfies the filter condition; and

in response to determining that the change satisfies the filter condition, storing data that indicates that said change is likely to have changed a result set of said query.

3. The method of claim 1 further comprising:

generating a reference count for each of the one or more values, wherein the reference count indicates a number of occurrences of each of said one or more values within the result set of said join source query;

after the change, computing a DELTA of the join source query;

based on the DELTA, creating a new reference count for a particular value of the one or more values;

in response to the new reference count being zero, revising the filter condition.

4. The method of claim 1 wherein the step of generating a virtual clause includes:

generating an initial virtual claims;

performing a recursive traversal of a where clause of the query;

when a LEAF node is reached during the traversal, adding a predicate associated with the LEAF node to the emerging virtual clause if the predicate satisfies certain conditions.

17. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

18. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

19. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

20. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

5. A method for identifying queries whose result sets are likely to have been changed by a change to data within a table, comprising:

using a filter index to determine a set of base predicates that are satisfied by the change;

adding, to a list of dependent identifiers, dependent identifiers that are associated with the satisfied base predicates;

based on the list of dependent identifiers adding, to a set of candidate queries, registered queries that correspond to dependent identifiers that have satisfied base predicates; and

using the set of candidate queries to determine which registered queries have result sets that are likely to have been changed by the change to the data within the table.

6. The method of claim 5 further comprising, before adding dependent identifiers to the list of dependent identifiers, performing the steps of:

determining whether the change modified columns that were part of any registered query; and

wherein the step of adding dependent identifiers to the list of dependent identifiers is performed in response to determining that the change modified columns that were part of one or more registered queries.

7. The method of claim 5 wherein the step of adding, to a set of candidate queries, registered queries that correspond to dependent identifiers that have satisfied base predicates includes:

initializing the set of candidate queries to empty;

for each dependent identifier in the list of dependent identifiers, performing the steps of

determining whether the dependent identifier maps to a registered query;

if the dependent identifier maps to a registered query, then adding a query identifier of the registered query to the set of candidate queries; and

if the dependent identifier does not map to a registered query, then (a) evaluating a clause associated with the dependent identifier, and (b) if the clause is satisfied, then adding dependent identifiers corresponding to the clause to the list of independent identifiers.

8. The method of claim 5 further comprising:

inspecting primary key-foreign key constraints involving the table; and

based on the primary key-foreign key constraints, removing one or more queries from the set of candidate queries.

9. The method of claim 5 further comprising:

determining whether a particular query that has been added to the set of queries (a) is a single table query, and (b) is an insert or delete statement; and

if the particular query is a single table query, and is an insert or delete statement, then sending a notification to a subscriber associated with the particular query without further evaluation of the particular query.

10. The method of claim 5 further comprising:

determining whether a particular query that has been added to the set of queries (a) is a single table query, and (b) is an update statement; and

if the particular query is a single table query, and is an update statement, then sending

a notification to a subscriber associated with the particular query, without further evaluation of the particular query, when either the change modifies data in one or more columns in a select list of the particular query;

or

a filter condition associated with the particular query is determined to have transitioned.

11. The method of claim 5 wherein:

the set of queries includes a particular query that specifies a primary key (PK)—

foreign key (FK) join;

the method further comprises;

determining whether every table that is involved in the PK side of the PK-FK join does not have an exclusive predicate involving the table;

responsive to determining that every table that is involved in the PK side of the PK-FK join does not have an exclusive predicate involving the table, sending a notification to a subscriber associated with said particular query without fully evaluating the query.

12. The method of claim 5 wherein

the set of queries includes a particular UPDATE query that specifies a primary key (PK)-foreign key (FK) join;

the method further comprises;

determining whether the table occurs on the PK side of the PK-FK join;

responsive to determining that the table occurs on the PK side of the PK-FK join, marking the particular UPDATE query for further evaluation.

13. The method of claim 5 wherein

the set of queries includes a particular UPDATE query that specifies a primary key (PK)-foreign key (FK) join;

the method further comprises;

determining whether the table occurs only on the FK side of the PK-FK join;

responsive to determining that the table occurs on the FK side of the PK-FK join, determining whether no exclusive predicates are on the PK tables; and

responsive to determining that no exclusive predicates are on the PK tables, then marking the particular UPDATE query for notification.

14. The method of claim 5 further comprising:

identifying a plurality of clauses disjunctively connected within a query;

selecting a single clause, of the plurality of clauses, as a representative clause for said query; and

within said index, associating the query with only said representative clause.

15. The method of claim 14 further comprising dynamically tracking selectivity of said representative clause.

16. The method of claim 15 further comprising

determining whether selectivity of said representative clause satisfies selectivity criteria;

and

responsive to determining that selectivity of said representative clause does not satisfy selectivity criteria, reselecting a different clause, of said plurality of clauses, to be said representative clause for said query.

21. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

22. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

23. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

24. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

25. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

26. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

27. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

28. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

29. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

30. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

31. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

32. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.