Adaptive filter index for determining queries affected by a DML operation

• US 8,185,508 B2
• Filed: 12/02/2008
• Issued: 05/22/2012
• Est. Priority Date: 08/08/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Vemuri, Srinivas S., Mullick, Atrayee, Sinha, Bipul, Ganesh, Amit, Gawlick, Dieter
• Primary Examiner(s): Nguyen, Cam-Linh
• Application Number:
  US12/326,822
• Publication Number:
  US 20100036803A1
• Time in Patent Office: 1,267 Days
• Field of Search: 707688-690, 707694-696, 707/700, 707/702, 707/713, 707/736, 707/739, 707/758, 707/760, 707/769, 707/773
• US Class Current: 707/702
• 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 for identifying registered queries whose result sets were actually 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;

determining that a particular set of registered queries correspond to the set of base predicates that are satisfied by the change;

wherein the particular set of registered queries includes at least one registered query whose result set was not actually changed by the change;

adding, to a set of candidate queries, the particular set of registered queries that correspond to the set of base predicates; and

using the set of candidate queries to determine which registered queries have result sets that were actually changed by the change to the data within the table;

wherein using the set of candidate queries includes determining that the result set of the at least one registered query was not actually changed by the change;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 further comprising,

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

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.

3. The method of claim 2 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.

4. The method of claim 1 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.

5. The method of claim 1 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.

6. The method of claim 1 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.

7. The method of claim 1 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.

8. The method of claim 1 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.

9. The method of claim 1 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.

10. The method of claim 1 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.

11. The method of claim 10 further comprising dynamically tracking selectivity of said representative clause.

12. The method of claim 11 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.

13. The method of Claim 1, further comprising:

storing a filter condition in the filter index in association with an identifier for a query;

wherein the filter condition is created by performing the steps of;

receiving the 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, and

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

14. The method of claim 13 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 made to the first table 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.

15. The method of claim 13 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;

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.

16. The method of claim 13 wherein the step of generating a virtual clause includes:

generating an initial virtual clause;

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 an emerging virtual clause if the predicate satisfies certain conditions.

17. A non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform

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

determining that a particular set of registered queries correspond to the set of base predicates that are satisfied by the change;

wherein the particular set of registered queries includes at least one registered query whose result set was not actually changed by the change;

,

adding, to a set of candidate queries, the particular set of registered queries that correspond to the set of base predicates; and

using the set of candidate queries to determine which registered queries have result sets that were actually changed by the change to the data within the table;

wherein using the set of candidate queries includes determining that the result set of the at least one registered query was not actually changed by the change.

18. The non-transitory computer-readable medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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

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.

19. The non-transitory computer-readable medium of claim 18, 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.

20. The non-transitory computer-readable medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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.

21. The non-transitory computer-readable medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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.

22. The non-transitory computer-readable medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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.

23. The non-transitory computer-readable medium of claim 17, wherein:

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

the non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform;

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.

24. The non-transitory computer-readable medium of claim 17, wherein:

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

the non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform;

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.

25. The non-transitory computer-readable storage medium of claim 17 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. wherein:

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

the non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform;

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.

26. The non-transitory computer-readable storage medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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.

27. The non-transitory computer-readable storage medium of claim 26 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

dynamically tracking selectivity of said representative clause.

28. The non-transitory computer-readable storage medium of claim 27 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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.

29. The non-transitory computer-readable medium of claim 17 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

storing a filter condition in the filter index in association with an identifier for a query;

wherein the filter condition is created by performing the steps of;

receiving the 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, and

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

30. The non-transitory computer-readable medium of claim 29 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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 made to the first table 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.

31. The non-transitory computer-readable medium of claim 29 storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to further perform

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;

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.

32. The non-transitory computer-readable medium of claim 29, wherein the step of generating a virtual clause includes:

generating an initial virtual clause;

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 an emerging virtual clause if the predicate satisfies certain conditions.