Efficient inter-task queue protocol

• US 6,341,302 B1
• Filed: 09/24/1998
• Issued: 01/22/2002
• Est. Priority Date: 09/24/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Inventors: Celis, Pedro
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/160,367
• Time in Patent Office: 1,216 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/107, 711/144, 707/8, 707/9, 710/113, 710/129
• US Class Current: 718/100
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

In a system for executing database queries, a directed graph of logically interconnected tasks represents an execution plan for executing a specified database query. A pair of queues are stored in a computer memory for each pair of interconnected tasks in the directed graph. One of the queues in each pair is a down queue for sending requests from a parent task to a child task, and the other is an up queue for sending replies from the child task to the parent task. Each queue is a circular buffer and includes a head pointer that points to a next location in the queue to be read, and a tail pointer that points to a next location in the queue in which data can be written. Each task checks that a queue is not full before writing data into that queue, and checks that the sibling queue is not empty before reading data from the sibling queue. In addition, a task updates the tail pointer for a queue only after it has written data into the location in the queue to which the tail pointer is updated, to ensure that the other task does not attempt to read that queue location until the new data has been written into it. This queue protocol is sufficient, by itself, to ensure that tasks do not make conflicting use of the queues, despite the fact that the queues are in shared memory and are not protected by a synchronization mechanism.

Claims

1. A system for executing database queries, comprising:

a set of task data structures representing a directed graph of logically interconnected tasks, the directed graph of logically interconnected representing an execution plan for executing at least a portion of a specified database query;

an executor module for executing the tasks represented by the set of task data structures;

a pair of queues for each pair of interconnected tasks represented by the set of task data structures, one of the queues in each pair comprising a down queue for sending requests from a parent task, comprising a first one of the pair of tasks, to a child task, comprising a second one of the pair of tasks, and the other of the queues in each pair for comprising an up queue for sending replies from the child task to the parent task, each reply corresponding to one of the requests;

each of a first subset of the tasks including means for reading requests from a down queue in a respective one of the pairs of queues, for generating a corresponding result and for writing the result as a reply into the up queue in the respective pair of queues;

each of a second subset of the tasks including means for writing requests into a down queue in a respective one of the pairs of queues, for reading a corresponding reply in the up queue in the respective pair of queues;

wherein

each task includes queue fullness checking means for checking that a first respective one of the queues is not full before writing data into the first respective queue, and queue empty checking means for checking that a second respective one of the queues is not empty before reading data from the second respective queue; and

each task writes and reads data to and from respective ones of the queues without first acquiring ownership of a corresponding synchronization mechanism.

2. The system of claim 1, wherein

each queue is a circular buffer and includes a head pointer that points to a next location in the queue to be read, and a tail pointer that points to a next location in the queue in which data can be written;

each queue has an associated size;

each queue is empty when its head pointer is equal to its tail pointer; and

each queue is full when the head pointer is equal to a next location in the queue after the location pointed to by the tail pointer.

3. The system of claim 2, wherein

each task writes data to the respective one of the queues only at the location pointed to by the respect queue'"'"'s tail pointer and increments the tail pointer to point to a next location in the queue only after it has finished writing data into the location in the queue to which the tail pointer points;

each queue'"'"'s tail pointer is updated only by the task that writes data to that queue; and

each queue'"'"'s tail pointer is never decremented to point to an immediately previous location in the queue.

4. The system of claim 1, wherein

a first plurality of the tasks are executed in a first process, and a second plurality of the tasks are executed in a second process;

the tasks include a first interprocess communication task in the first process and a second interprocess communication task in the second process, the first and second interprocess communication tasks exchanging interprocess communication messages so as to communicate requests and replies between a first task in the first process and a second task in the second process;

a first one of the pairs of queues is used for sending requests and replies between the first task and the first interprocess communication task; and

a second one of the pairs of queues is used for sending requests and replies between the second task and the second interprocess communication task; and

first and second interprocess communication tasks and the first and second pairs of queues operate together so as to simulate operation of a single pair of queues for communicating requests and replies between two tasks in a same process.

5. A method of executing database queries, comprising:

storing in a computer memory a set of task data structures representing a directed graph of logically interconnected tasks, the directed graph of logically interconnected representing an execution plan for executing at least a portion of a specified database query;

storing in the computer memory a pair of queues for each pair of interconnected tasks represented by the set of task data structures, one of the queues in each pair comprising a down queue for sending requests from a parent task, comprising a first one of the pair of tasks, to a child task, comprising a second one of the pair of tasks, and the other of the queues in each pair for comprising an up queue for sending replies from the child task to the parent task, each reply corresponding to one of the requests;

executing the tasks represented by the set of task data structures, including;

each of a first subset of the tasks reading requests from a down queue in a respective one of the pairs of queues, generating a corresponding result and writing the result as a reply into the up queue in the respective pair of queues;

each of a second subset of the tasks writing requests into a down queue in a respective one of the pairs of queues, and reading a corresponding reply in the up queue in the respective pair of queues;

wherein

each task checks that a first respective one of the queues is not full before writing data into the first respective queue, and checks that a second respective one of the queues is not empty before reading data from the second respective queue; and

each task writes and reads data to and from respective ones of the queues without first acquiring ownership of a corresponding synchronization mechanism.

6. The method of claim 5, wherein

each queue is a circular buffer and includes a head pointer that points to a next location in the queue to be read, and a tail pointer that points to a next location in the queue in which data can be written;

each queue has an associated size;

each queue is empty when its head pointer is equal to its tail pointer; and

each queue is full when the head pointer is equal to a next location in the queue after the location pointed to by the tail pointer.

7. The method of claim 6, wherein

each task writes data to the respective one of the queues only at the location pointed to by the respect queue'"'"'s tail pointer and increments the tail pointer to point to a next location in the queue only after it has finished writing data into the location in the queue to which the tail pointer points;

each queue'"'"'s tail pointer is updated only by the task that writes data to that queue; and

each queue'"'"'s tail pointer is never decremented to point to an immediately previous location in the queue.

8. The method of claim 5, wherein

a first plurality of the tasks are executed in a first process, and a second plurality of the tasks are executed in a second process;

the tasks include a first interprocess communication task in the first process and a second interprocess communication task in the second process, the first and second interprocess communication tasks exchanging interprocess communication messages so as to communicate requests and replies between a first task in the first process and a second task in the second process;

a first one of the pairs of queues is used for sending requests and replies between the first task and the first interprocess communication task; and

a second one of the pairs of queues is used for sending requests and replies between the second task and the second interprocess communication task; and

first and second interprocess communication tasks and the first and second pairs of queues operate together so as to simulate operation of a single pair of queues for communicating requests and replies between two tasks in a same process.