Method and system for using materialized views to evaluate queries involving aggregation

• US 5,897,632 A
• Filed: 07/16/1997
• Issued: 04/27/1999
• Est. Priority Date: 08/27/1996
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Dar, Shaul, Jagadish, Hosagrahar Visvesvaraya, Levy, Alon Yitzchak, Srivastava, Divesh
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/895,024
• Time in Patent Office: 650 Days
• Field of Search: 707/1, 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The present invention is a method and system for using materialized views to compute answers to SQL queries with grouping and aggregation. A query is evaluated a using a materialized view. The materialized view is semantically analyzed to determine whether the materialized view is usable in evaluating an input query. The semantic analysis includes determining that the materialized view does not project out any columns needed to evaluate the input query and determining that the view does not discard any tuple that satisfies a condition enforced in the input query. If the view is usable, the input query is rewritten to produce an output query that is multi-set equivalent to the input query and that specifies one or more occurrences of the materialized view as a source of information to be returned by the output query. The output query is then evaluated. The semantic analysis and rewriting may be iterated, with the output query of each iteration being the input query of the next iteration. The output query is evaluated after the last iteration.

Claims

1. A method of evaluating a query in a database system including a materialized view, the method comprising the steps of:

receiving an input query;

semantically analyzing the materialized view to determine whether the materialized view is usable in evaluating the input query;

if the view is usable, rewriting the input query to produce an output query that is multi-set equivalent to the input query, the output query including at least one reference to the materialized view as a source of information to be returned by the output query that was not included in the input query; and

evaluating the output query.

2. The method of claim 1, wherein the semantically analyzing step comprises the steps of:

determining that the materialized view does not project out any columns needed to evaluate the input query; and

determining that the view does not discard any tuple that satisfies a condition enforced in the input query.

3. The method of claim 2, wherein:

the steps of semantically analyzing and rewriting are iterated, with the output query of each iteration being the input query of the next iteration; and

the evaluating step is performed after the last iteration.

4. The method of claim 2, wherein:

there are a plurality of materialized views;

the steps of semantically analyzing and rewriting are iterated at least once for each of the materialized views, with the output query of each iteration being the input query of the next iteration; and

the evaluating step is performed after the last iteration.

5. The method of claim 4, wherein:

the steps of semantically analyzing and rewriting are further iterated for a given one of the materialized views.

6. The method of claim 4, wherein each one of the plurality of materialized views is similar.

7. The method of claim 4, wherein at least one of the plurality of materialized views is different.

8. The method of claim 4, wherein each one of the plurality of materialized views is different.

9. The method of claim 1, wherein the materialized view does not have aggregation.

10. The method of claim 1, wherein the materialized view has aggregation.

11. A system for evaluating a query comprising:

a storage device storing a materialized view;

a receiver operable to receive an input query;

a semantic analyzer operable to analyze the materialized view to determine whether the materialized view is usable in evaluating the input query;

a query rewriting device operable to rewrite the input query to produce an output query that is multi-set equivalent to the input query, the output query including at least one reference to the materialized view as a source of information to be returned by the output query that was not included in the input query, if the view is usable; and

a query evaluator operable to evaluate the output query.

12. The system of claim 11, wherein the semantic analyzer comprises:

a first analysis unit operable to determine that the materialized view does not project out any columns needed to evaluate the input query; and

a second analysis unit operable to determine that the view does not discard any tuple that satisfies a condition enforced in the input query.

13. The system of claim 12, wherein:

the semantic analyzer and query rewriting device are further iteratively operable, with the output query of each iteration coupled to the input query of the next iteration; and

the query evaluator is coupled to the output query of the last iteration.

14. The system of claim 12, wherein:

there are a plurality of materialized views;

the semantic analyzer and query rewriting device are further iteratively operable at least once for each of the materialized views, with the output query of each iteration coupled to the input query of the next iteration; and

the query evaluator is coupled to the output query of the last iteration.

15. The system of claim 14, wherein:

the semantic analyzer and query rewriting device are further iteratively operable for a given one of the materialized views.

16. The system of claim 14, wherein each one of the plurality of materialized views is similar.

17. The system of claim 14, wherein at least one of the plurality of materialized views is different.

18. The system of claim 14, wherein each one of the plurality of materialized views is different.

19. The system of claim 11, wherein the materialized view does not have aggregation.

20. The system of claim 11, wherein the materialized view has aggregation.

21. A computer program storage device, comprising:

a computer readable medium embodying computer program instructions for evaluating a query, including;

computer program instruction means for receiving an input query;

computer program instruction means for semantically analyzing a materialized view to determine whether the materialized view is usable in evaluating the input query;

computer program instruction means for rewriting the input query to produce an output query that is multi-set equivalent to the input query, the output query including at least one reference to the materialized view as a source of information to be returned by the output query that was not included in the input query, if the view is usable; and

computer program instruction means for evaluating the output query.

22. The computer program storage device of claim 21, wherein the computer program instruction means for semantically analyzing the materialized view comprises:

computer program instruction means for determining that the materialized view does not project out any columns needed to evaluate the input query; and

computer program instruction means for determining that the view does not discard any tuple that satisfies a condition enforced in the input query.

23. The computer program storage device of claim 22, further comprising:

computer program instruction means for iteratively operating the computer program instruction means for semantically analyzing the materialized view and the computer program instruction means for rewriting the input query, with the output query of each iteration being the input query of the next iteration; and

wherein

the computer program instruction means for evaluating the output query operates after the last iteration.

24. The computer program storage device of claim 22, wherein there are a plurality of materialized views and the computer program storage device further comprises:

computer program instruction means for iteratively operating the computer program instruction means for semantically analyzing the materialized view and the computer program instruction means for rewriting the input query at least once for each of the materialized views, with the output query of each iteration being the input query of the next iteration; and

wherein

the computer program instruction means for evaluating the output query operates after the last iteration.

25. The computer program storage device of claim 24, wherein:

the computer program instruction means for iteratively operating the computer program instruction means for semantically analyzing the materialized view and the computer program instruction means for rewriting the input query are operable to iterate for a given one of the materialized views.

26. The computer program storage device of claim 24, wherein each one of the plurality of materialized views is similar.

27. The computer program storage device of claim 24, wherein at least one of the plurality of materialized views is different.

28. The computer program storage device of claim 24, wherein each one of the plurality of materialized views is different.

29. The computer program storage device of claim 21, wherein the materialized view does not have aggregation.

30. The computer program storage device of claim 21, wherein the materialized view has aggregation.