Method and apparatus for efficiently processing queries in a streaming transaction processing system

• US 7,310,638 B1
• Filed: 10/06/2004
• Issued: 12/18/2007
• Est. Priority Date: 10/06/2004
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Metra Tech
• Inventors: Blair, David A.
• Primary Examiner(s): Vital; Pierre
• Assistant Examiner(s): CHOI, YUK TING
• Application Number:
  US10/959,737
• Time in Patent Office: 1,168 Days
• Field of Search: 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

To efficiently process a parameterized query against a relational database in a streaming transaction processing system, the transaction stream is treated as a sequence of multi-record “chunks” and a single “quasi-batch” query is executed for each chunk. A specific table in the database holds the parameter values obtained from each transaction and the parameters are bound to the rest of the query by using a database join. Another embodiment uses a framework that automates the technique by accepting the parameterized query, identifying inputs and outputs, reading the stream for the parameter values and building the parameter table, converting the parameterized query into an equivalent query that contains a join against the parameter table, performing the equivalent query and inserting the resulting query values into the stream.

Claims

1. A method for efficiently processing transactions in a streaming transaction processing system, wherein each transaction requires execution of a parameterized query having at least one input taken from that transaction against a relational database, the method comprising:

(a) identifying Inputs and outputs of the parameterized query;

(b) creating a parameter table to hold the parameterized query inputs;

(c) converting the parameterized query into an equivalent query that contains a join against the parameter table;

(d) reading parameter values from transactions in the stream and populating the parameter table with input values read from the transactions, and

(e) applying the equivalent query to the relational database to generate a result set; and

(f) inserting output values from the result set into the transactions.

2. The method of claim 1 wherein step (a) comprises:

(a1) lexing the parameterized query to generate a plurality of tokens; and

(a2) parsing the tokens to identify query inputs and query outputs.

3. The method of claim 2 wherein step (b) comprises using an interface to the relational database to create the parameter table based on the identified query inputs.

4. The method of claim 1 wherein step (c) comprises using a set of rules to convert the parameterized query into an equivalent query.

5. The method of claim 4 wherein step (c) comprises:

(c1) modeling the parameterized query as a tree structure;

(c2) specifying a tree grammar that describes the tree structure; and

(c3) selecting at least one rule in the set of rules based on a match between the parameterized query and the tree grammar to convert the parameterized query.

6. The method of claim 1 wherein step (d) comprises populating the parameter table using a bulk insert interface of the relational database.

7. The method of claim 6 wherein the bulk insert interface is not logged.

8. The method of claim 6 wherein the parameter table has a predetermined size and wherein step (d) comprises populating the parameter table until the table becomes filled.

9. The method of claim 8 wherein step (e) comprises executing the equivalent query once each time the parameter table becomes filled.

10. The method of claim 9 further comprising:

(f) clearing the parameter table after the equivalent query has been executed; and

(g) repeating steps (d), (e) and (f) until all transactions have been processed.

11. Apparatus for efficiently processing transactions in a streaming transaction processing system having a memory wherein each

transaction requires execution of a parameterized query having at least one input taken from that transaction against a relational database, the apparatus comprising:

a mechanism that identifies inputs and outputs of the parameterized query;

a table generator that creates a parameter table in the memory to hold the parameterized query inputs;

a transformer that converts the parameterized query into an equivalent query that is in the memory and contains a join against the parameter table;

a mechanism that reads parameter values from transactions in the stream and populates the parameter table with input values read from the transactions; and

a mechanism that applies the equivalent query to the relational database to generate a result set; and

a stream writer that inserts output values from the result set into the transactions.

12. The apparatus of claim 11 wherein the mechanism that identifies inputs and outputs comprises:

a lexer that processes the parameterized query to generate a plurality of tokens; and

a parser that examines the tokens to identify query inputs and query outputs.

13. The apparatus of claim 12 wherein the table generator comprises a mechanism that uses an interface to the relational database to create the parameter table based on the identified query inputs.

14. The apparatus of claim 11 wherein the transformer comprises a rule-based mechanism that uses a set of rules to convert the parameterized query into an equivalent query.

15. The apparatus of claim 14 wherein the rule-based mechanism comprises:

means for modeling the parameterized query as a tree structure;

means for specifying a tree grammar that describes the tree structure; and

means for selecting at least one rule in the set of rules based on a match between the parameterized query and the tree grammar to convert the parameterized query.

16. The apparatus of claim 11 wherein the mechanism that populates the parameter table comprises means for populating the parameter table using a bulk insert interface of the relational database.

17. The apparatus of claim 16 wherein the bulk insert interface is not logged.

18. The apparatus of claim 16 wherein the parameter table has a predetermined size and wherein the mechanism for populating the parameter table comprises means for populating the parameter table until the table becomes filled.

19. The apparatus of claim 18 wherein the mechanism that applies the equivalent query to the relational database comprises means for executing the equivalent query once each time the parameter table becomes filled.

20. The apparatus of claim 19 further comprising:

means for clearing the parameter table after the equivalent query has been executed; and

processing transactions with the transformer, the mechanism that populates the parameter table with input values read from the transactions and the mechanism that applies the equivalent query to the relational database to until all transactions have been processed.

21. Apparatus for efficiently processing transactions in a streaming transaction processing system having a memory wherein each transaction requires execution of a parameterized query having at least one input taken from that transaction against a relational database, the apparatus comprising:

means for Identifying Inputs and outputs of the parameterized query,

means for creating a parameter table in the memory to hold the parameterized query inputs;

means for converting the parameterized query into an equivalent query that is In the memory and contains a join against the parameter table;

means for reading parameter values from transactions in the stream and populates the parameter table with input values read from the transactions; and

means for applying the equivalent query to the relational database to generate a result set; and

means for inserting output values from the result set Into the transactions.

22. The apparatus of claim 21 wherein the means for identifying inputs and outputs comprises:

means for processing the parameterized query to generate a plurality of tokens; and

means for examining the tokens to identify query inputs and query outputs.

23. The apparatus of claim 22 wherein the means for creating the parameter table comprises means for using an interface to the relational database to create the parameter table based on the identified query inputs.

24. The apparatus of claim 21 wherein the means for converting the parameterized query comprises means for using a set of rules to convert the parameterized query into an equivalent query.

25. A pipelined system for efficiently processing transactions in a streaming transaction processing system having a memory wherein each transaction requires execution of a parameterized query having at least one input taken from that transaction against a relational database, the system comprising:

a plurality of processing stages;

a pipeline controller that determines the order of execution of the pipeline stages;

wherein at least one pipeline stage includes;

a mechanism that identifies inputs and outputs of the parameterized query;

a table generator that creates a parameter table in the memory to hold the parameterized query inputs;

a transformer that converts the parameterized query into an equivalent query that is in the memory and contains a join against the parameter table;

a mechanism that reads parameter values from transactions in the stream and populates the parameter table with input values read from the transactions;

a mechanism that applies the equivalent query to the relational database to generate a result set; and

a mechanism that inserts output values from the result set into the transactions.

26. A computer program product for efficiently processing transactions in a streaming transaction processing system, wherein each transaction requires execution of a parameterized query having at least one input taken from that transaction against a relational database, the computer program product comprising a tangible computer usable medium having computer readable program code thereon, including:

program code for identifying inputs and outputs of the parameterized query;

program code for creating a parameter table to hold the parameterized query inputs;

program code for converting the parameterized query into an equivalent query that contains a join against the parameter table;

program code for reading parameter values from transactions in the stream and populates the parameter table with input values read from the transactions;

program code for applying the equivalent query to the relational database to generate a result set; and

program code for inserting output values from the result set into the transactions.