Evaluation strategy for execution of SQL queries involving recursion and table queues
First Claim
1. A method of executing an SQL query in a computer having a memory, the SQL query being executed by the computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of:
- (a) establishing a table queue for the query in the memory of the computer;
(b) retrieving desired tuples from the relational database stored in the electronic storage device coupled to the computer;
(c) storing the retrieved tuples into the table queue in the memory of the computer;
(d) retrieving the stored tuples from the table queue in the memory of the computer, wherein the retrieved tuples are operated on in accordance with the query;
(e) generating a first end-of-file indication in the memory of the computer when all of the tuples stored in the table queue have been retrieved; and
(f) generating a second end-of-file indication in the memory of the computer after the first end-of-file indication has been generated when all of the desired tuples stored in the relational database have been retrieved.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides an evaluation strategy for the execution of SQL queries involving recursion and table queues in a relational database management system. The table queue is established for the query in the memory of the computer, and tuples are generated by tuple-producing operators in the query for storage into the table queue. As operators of the query read the stored tuples from the table queue, a first end-of-file condition, termed a Temporary End-Of-File, occurs when all of the tuples currently stored in the table queue have been retrieved and control is returned to the operator reading from the table queue. A retry request for additional tuples is generated by the operator through the table queue to the tuple-producing operators. If the tuple-producing operators can generate additional tuples, then these additional tuples are stored into the table queue and control is returned to the operator reading from the table queue in response to the retry request. If the tuple-producing operators cannot generate the additional tuples, then a second end-of-file condition, termed a Permanent End-Of-File, occurs and control is returned to the operator reading from the table queue.
66 Citations
21 Claims
-
1. A method of executing an SQL query in a computer having a memory, the SQL query being executed by the computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) establishing a table queue for the query in the memory of the computer; (b) retrieving desired tuples from the relational database stored in the electronic storage device coupled to the computer; (c) storing the retrieved tuples into the table queue in the memory of the computer; (d) retrieving the stored tuples from the table queue in the memory of the computer, wherein the retrieved tuples are operated on in accordance with the query; (e) generating a first end-of-file indication in the memory of the computer when all of the tuples stored in the table queue have been retrieved; and (f) generating a second end-of-file indication in the memory of the computer after the first end-of-file indication has been generated when all of the desired tuples stored in the relational database have been retrieved. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method of executing an SQL query in a computer having a memory, the SQL query being executed by the computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) performing an operation of the query in the memory of the computer, wherein the operation retrieves tuples from a table queue established in the memory of the computer; (b) receiving an end-of-file indication from the table queue when all of the tuples stored in the table queue have been retrieved by the operation; (c) generating a request for additional tuples from the table queue when the received end-of-file indication is a first occurrence of the end-of-file indication received by the operation, wherein the request results in the additional tuples being retrieved by a tuple producing function performed by the computer and stored into the table queue in accordance with the query; and (d) terminating the operation when the received end-of-file indication is a second occurrence of the end-of-file indication received by the operation.
-
-
7. A method of executing an SQL query in a computer having a memory, the SQL query being executed by the computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) establishing a table queue for the query in the computer; (b) retrieving desired tuples from the relational database and storing the retrieved tuples into the table queue; (d) retrieving the stored tuples from the table queue, wherein the retrieved tuples are operated on in accordance with the query; (e) setting a busy-state indicator in the computer while tuples are being retrieved from the table queue; (f) generating a first end-of-file indication in the computer when all of the tuples stored in the table queue have been retrieved; (g) generating a retry request in the computer in response to the first end-of-file indication to retrieve additional tuples from the table queue; (h) retrieving additional tuples from the relational database after the first end-of-file indication has been generated when all the busy-state indicator is not set, and storing the retrieved tuples into the table queue; and (i) generating a second end-of-file indication in the computer after the first end-of-file indication has been generated when the busy-state indicator is set.
-
-
8. An apparatus for executing an SQL query, comprising:
-
(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database; (b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer; (c) means, performed by the computer, for establishing a table queue for the query in the memory of the computer; (d) means, performed by the computer, for retrieving desired tuples from the relational database stored in the electronic storage device coupled to the computer; (e) means, performed by the computer, for storing the retrieved tuples into the table queue in the memory of the computer; (f) means, performed by the computer, for retrieving the stored tuples from the table queue in the memory of the computer, wherein the retrieved tuples are operated on in accordance with the query; (g) means, performed by the computer, for generating a first end-of-file indication in the memory of the computer when all of the tuples stored in the table queue have been retrieved; and (h) means, performed by the computer, for generating a second end-of-file indication in the memory of the computer after the first end-of-file indication has been generated when all of the desired tuples stored in the relational database have been retrieved. - View Dependent Claims (9, 10, 11, 12)
-
-
13. An apparatus for executing an SQL query, comprising:
-
(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database; (b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer; (c) means, performed by the computer, for performing an operation of the query in the memory of the computer, wherein the operation retrieves tuples from a table queue established in the memory of the computer; (d) means, performed by the computer, for receiving an end-of-file indication from the table queue when all of the tuples stored in the table queue have been retrieved by the operation; (e) means, performed by the computer, for generating a request for additional tuples from the table queue when the received end-of-file indication is a first occurrence of the end-of-file indication received by the operation, wherein the request results in the additional tuples being retrieved by a tuple producing function performed by the computer and stored into the table queue in accordance with the query; and (f) means, performed by the computer, for terminating the operation when the received end-of-file indication is a second occurrence of the end-of-file indication received by the operation.
-
-
14. An apparatus for executing an SQL query, comprising:
-
(a) a computer having a memory and an electronic storage device coupled thereto, the data storage device storing a relational database; (b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the computer; (c) means, performed by the computer, for establishing a table queue for the query; (d) means, performed by the computer, for retrieving desired tuples from the relational database and for storing the retrieved tuples into the table queue; (e) means, performed by the computer, for retrieving the stored tuples from the table queue, wherein the retrieved tuples are operated on in accordance with the query; (f) means, performed by the computer, for setting a busy-state indicator while tuples are being retrieved from the table queue; (g) means, performed by the computer, for generating a first end-of-file indication when all of the tuples stored in the table queue have been retrieved; (h) means, performed by the computer, for generating a retry request in response to the first end-of-file indication to retrieve additional tuples from the table queue; (i) means, performed by the computer, for retrieving additional tuples from the relational database after the first end-of-file indication has been generated when all the busy-state indicator is not set, and for storing the retrieved tuples into the table queue; and (j) means, performed by the computer, for generating a second end-of-file indication after the first end-of-file indication has been generated when the busy-state indicator is set.
-
-
15. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for executing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) establishing a table queue for the query in the memory of the computer; (b) retrieving desired tuples from the relational database stored in the electronic storage device coupled to the computer; (c) storing the retrieved tuples into the table queue in the memory of the computer; (d) retrieving the stored tuples from the table queue in the memory of the computer, wherein the retrieved tuples are operated on in accordance with the query; (e) generating a first end-of-file indication in the memory of the computer when all of the tuples stored in the table queue have been retrieved; and (f) generating a second end-of-file indication in the memory of the computer after the first end-of-file indication has been generated when all of the desired tuples stored in the relational database have been retrieved. - View Dependent Claims (16, 17, 18, 19)
-
-
20. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for executing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) performing an operation of the query in the memory of the computer, wherein the operation retrieves tuples from a table queue established in the memory of the computer; (b) receiving an end-of-file indication from the table queue when all of the tuples stored in the table queue have been retrieved by the operation; (c) generating a request for additional tuples from the table queue when the received end-of-file indication is a first occurrence of the end-of-file indication received by the operation, wherein the request results in the additional tuples being retrieved by a tuple producing function performed by the computer and stored into the table queue in accordance with the query; and (d) terminating the operation when the received end-of-file indication is a second occurrence of the end-of-file indication received by the operation.
-
-
21. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for executing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) establishing a table queue for the query in the computer; (b) retrieving desired tuples from the relational database and storing the retrieved tuples into the table queue; (d) retrieving the stored tuples from the table queue, wherein the retrieved tuples are operated on in accordance with the query; (e) setting a busy-state indicator in the computer while tuples are being retrieved from the table queue; (f) generating a first end-of-file indication in the computer when all of the tuples stored in the table queue have been retrieved; (g) generating a retry request in the computer in response to the first end-of-file indication to retrieve additional tuples from the table queue; (h) retrieving additional tuples from the relational database after the first end-of-file indication has been generated when all the busy-state indicator is not set, and storing the retrieved tuples into the table queue; and (i) generating a second end-of-file indication in the computer after the first end-of-file indication has been generated when the busy-state indicator is set.
-
Specification