Efficient evaluation of queries using translation

• US 7,516,121 B2
• Filed: 09/22/2004
• Issued: 04/07/2009
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Manikutty, Anand, Arora, Vikas, Krishnaprasad, Muralidhar, Liu, Zhen Hua, Kotsovolos, Susan M., Warner, James, Zhang, Hui X.
• Primary Examiner(s): Y; Truong Cam
• Assistant Examiner(s): Hwa; Shyue Jiunn
• Application Number:
  US10/948,523
• Publication Number:
  US 20050289125A1
• Time in Patent Office: 1,658 Days
• Field of Search: 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/8358 Query translation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Techniques are provided for processing a query including receiving the query, where the query specifies certain operations; determining that the query includes a first portion in a first query language and a second portion in a second query language; generating a first in-memory representation for the first portion; generating a second in-memory representation for the second portion; generating a third in-memory representation of the query based on the first in-memory representation and the second in-memory representation; and performing the certain operations based on the third in-memory representation.

Claims

1. A method of processing a query, comprising:

receiving the query, wherein the query specifies operations;

determining that the query comprises a Structured Query Language (SQL) portion that specifies first one or more of said operations in SQL query language and a markup language portion that specifies second one or more of said operations in a markup query language;

wherein the markup query language is one of XQuery query language and XQueryX query language;

wherein, within the query, the markup language portion is embedded into the SQL portion;

generating a first in-memory representation for the SQL portion;

generating a second in-memory representation for the markup language portion;

generating a third in-memory representation of the query based on the first in-memory representation and the second in-memory representation, wherein the third in-memory representation specifies all of said operations; and

performing said operations based on the third in-memory representation;

wherein the first in-memory representation and the third in-memory representation are formatted in a first abstract syntax and the second in-memory representation is formatted in a second abstract syntax, and wherein the step of generating the third in-memory representation comprises;

generating a fourth in-memory representation in the first abstract syntax based on the second in-memory representation; and

generating the third in-memory representation based on the first in-memory representation and the fourth in-memory representation;

wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax; and

wherein the markup language portion comprises a user-defined XQuery function in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating a user-defined PL/SQL function in the first abstract syntax based on the user-defined XQuery function in the second abstract syntax.

2. The method of claim 1 wherein the second in-memory representation comprises one or more in-memory representations of query elements in the second abstract syntax, and wherein generating the fourth in-memory representation comprises:

determining a second set of one or more equivalent in-memory representations of query elements in the first abstract syntax for the one or more in-memory representations of query elements in the second abstract syntax; and

generating the fourth in-memory representation in the first abstract syntax based on the second set of one or more equivalent in-memory representations of query elements in the first abstract syntax.

3. The method of claim 2, wherein each in-memory representation of query elements in the one or more in-memory representations of query elements in the second abstract syntax corresponds to one or more in-memory representation of query elements in the second set of one or more equivalent in-memory representations of query elements in the first abstract syntax.

4. The method of claim 1, wherein one or more of the first in-memory representation, the second in-memory representation, and the third in-memory representation are represented in memory as abstract syntax trees.

5. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery aggregation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL subquery in the first abstract syntax to compute the aggregation, said SQL subquery being generated based on the XQuery aggregation in the second abstract syntax.

6. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises a literal expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL literal in the first abstract syntax based on the literal expression in the second abstract syntax.

7. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery cast expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL cast function and an SQL convert function in the first abstract syntax based on the XQuery cast expression in the second abstract syntax.

8. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises a set expressions in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL UNION, an SQL MINUS, and an SQL INTERSECT in the first abstract syntax based on the set expressions in the second abstract syntax.

9. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery arithmetic expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL arithmetic expression in the first abstract syntax based on the XQuery arithmetic expression in the second abstract syntax.

10. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery comparison in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL comparison in the first abstract syntax based on the XQuery comparison in the second abstract syntax.

11. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery FLWOR order by clause in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL order by clause in the first abstract syntax based on the XQuery FLWOR order by clause in the second abstract syntax.

12. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML logical expressions in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL logical expressions element in the first abstract syntax based on the XML logical expressions in the second abstract syntax.

13. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML FLWOR expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL select expressions element in the first abstract syntax based on the XML FLWOR expression in the second abstract syntax.

14. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML Path expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL path expression in the first abstract syntax based on the XML Path expression in the second abstract syntax.

15. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML if-then-else expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL case—

when expression in the first abstract syntax based on the XML if-then-else expression in the second abstract syntax.

16. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML quantified expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL Exists expression in the first abstract syntax based on the XML quantified expression in the second abstract syntax.

17. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an SQL/XML construction expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL construction expression in the first abstract syntax based on the SQL/XML construction expression in the second abstract syntax.

18. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XML operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL operator in the first abstract syntax based on the XML operator in the second abstract syntax.

19. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery sequence type operation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL type operation in the first abstract syntax based on the XQuery sequence type operation in the second abstract syntax.

20. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery type constructor in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL scalar constructor in the first abstract syntax based on the XQuery type constructor in the second abstract syntax.

21. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery validate operation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL/XML IsValid operation and an SQL/XML Validate operation in the first abstract syntax based on the XQuery validate operation in the second abstract syntax.

22. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises a polymorphic XQuery arithmetic operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of a polymorphic SQL arithmetic operator in the first abstract syntax based on the polymorphic XQuery arithmetic operator in the second abstract syntax.

23. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises a polymorphic XQuery comparison operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of a polymorphic SQL value comparison operator in the first abstract syntax based on the polymorphic XQuery comparison operator in the second abstract syntax.

24. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery function call in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL function call in the first abstract syntax based on the XQuery function call in the second abstract syntax.

25. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an external XQuery function in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an external SQL function in the first abstract syntax based on the external XQuery function in the second abstract syntax.

26. The method of claim 1, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the markup language portion comprises an XQuery module in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating a PL/SQL package in the first abstract syntax based on the XQuery module in the second abstract syntax.

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 1.

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 2.

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 3.

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 4.

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 5.

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 6.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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 17.

44. 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 18.

45. 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 19.

46. 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 20.

47. 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 21.

48. 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 22.

49. 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 23.

50. 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 24.

51. 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 25.

52. 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 26.

53. A method of processing a query, comprising:

receiving the query, wherein the query specifies operations;

determining that the query comprises a first portion that specifies first one or more of the operations in a first query language and a second portion that specifies second one or more of the operations in a second query language;

generating a first in-memory representation for the first portion;

generating a second in-memory representation for the second portion, wherein the second in-memory representation represents at least one query element, supported by the second query language, that is not understood by a query processor for the first query language;

prior to performing any of the operations, generating a third in-memory representation of the query based on the first in-memory representation and a fourth in-memory representation, wherein the third in-memory representation specifies all of the operations, and wherein generating the third in-memory representation comprises;

generating the fourth in-memory representation based on the second in-memory representation, wherein the fourth in-memory representation represents only query elements that are supported by the first query language and understood by a query processor for the first query language; and

performing the operations based on the third in-memory representation;

wherein the first in-memory representation and the third in-memory representation are formatted in an Structure query language (SQL) related abstract syntax or SQL-related abstract syntax and the second in-memory representation is formatted in an XQuery-related abstract syntax, and wherein the fourth in-memory representation is formatted in the SQL-related abstract syntax;

wherein the second portion comprises at least one of;

an XQuery aggregation in the XQuery-related abstract syntax;

a set expression in the XQuery-related abstract syntax;

an XQuery FLWOR order by clause in the XQuery-related abstract syntax;

an XML if-then-else expression in the XQuery-related abstract syntax;

or

an XML quantified expression in the XQuery-related abstract syntax.

54. The method of claim 53, wherein:

the second portion comprises an XQuery aggregation in the XQuery-related abstract syntax; and

the step of generating the fourth in-memory representation comprises generating an SQL subquery in the SQL-related abstract syntax to compute the XQuery aggregation, said SQL subquery being generated based on the XQuery aggregation in the XQuery-related abstract syntax.

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

56. The method of claim 53, wherein:

the second portion comprises a set expression in the XQuery-related abstract syntax; and

the step of generating the fourth in-memory representation comprises generating one of an SQL UNION, an SQL MINUS, and an SQL INTERSECT in the SQL-related abstract syntax based on the set expressions in the XQuery-related abstract syntax.

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

58. The method of claim 53, wherein:

the second portion comprises an XQuery FLWOR order by clause in the XQuery-related abstract syntax; and

the step of generating the fourth in-memory representation comprises generating an SQL order by clause in the SQL-related abstract syntax based on the XQuery FLWOR order by clause in the XQuery-related abstract syntax.

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

60. The method of claim 53, wherein:

the second markup language portion comprises an XML if-then-else expression in the XQuery-related abstract syntax; and

the step of generating the fourth in-memory representation comprises generating an SQL case-when expression in the SQL-related abstract syntax based on the XML if-then-else expression in the XQuery-related abstract syntax.

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

62. The method of claim 53, wherein:

the second portion comprises an XML quantified expression in the XQuery-related abstract syntax; and

the step of generating the fourth in-memory representation comprises generating an SQL Exists expression in the SQL-related abstract syntax based on the XML quantified expression in the XQuery-related abstract syntax.

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

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