Method for unordered relational database retrieval returning distinct values

• US 7,752,160 B2
• Filed: 07/02/2002
• Issued: 07/06/2010
• Est. Priority Date: 07/12/2001
• Status: Expired due to Term

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lai, Tony Wen Hsun, Zilio, Daniel C., Zuzarte, Calisto Paul, Finlay, Ian R.
• Primary Examiner(s): VO, CECILE H
• Application Number:
  US10/188,569
• Publication Number:
  US 20030014390A1
• Time in Patent Office: 2,926 Days
• Field of Search: 707 1- 7
• US Class Current: 707/792
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The retrieval of distinct tuples in a relational database management system. In response to a request from a consumer process for distinct tuples in a relational database table matching a defined criteria, a distinct operator component sequentially requests tuples from a source component. The source component access the database table and returns a tuple in the sequence to the distinct operator component. The distinct operator component passes each tuple in the sequence to an auxiliary logger. The auxiliary component receives a tuples from the distinct component and determines if it is distinct from other previously received tuples in the sequence to verify its uniqueness to the distinct operator. Tuples that are verified as unique by the auxiliary logger are returned to the consumer process by the distinct operator upon verification.

Claims

1. A method performed by a process in a computer system for providing a set of relational data to a consumer process, the method comprising the steps of:

(a) retrieving from a database table a tuple in a sequence of tuples upon receiving a query from the consumer process requesting distinct tuples;

(b) determining using an auxiliary logger component whether the retrieved tuple is unique in comparison to previously retrieved tuples in the sequence by using a sorted table that stores the unique tuple wherein the retrieved tuple may be returned to the consumer process immediately after the retrieved tuple is determined to be unique without sorting the entire set of tuples and indicating whether the retrieved tuple has been previously received by the auxiliary logger component;

(c) providing using a distinct operator component the consumer process with the retrieved tuple where the tuple is unique and discarding the tuple where the tuple is not unique; and

(d) repeating the above steps until all tuples in the sequence of tuples have been retrieved from the database table,

wherein at least one distinct tuple in the sequence of tuples is provided to the consumer process prior to retrieval of all tuples in the sequence of tuples from the database table.

2. The method of claim 1, wherein the method is performed in a relational database management system comprising

a source component;

the auxiliary logger component being an auxiliary logger component; and

the distinct operator component.

3. The method of claim 2 wherein the consumer process further comprises requesting data from the distinct operator component,

the distinct operator component sequentially requesting a set of tuples from the source component upon receiving a query from the consumer process requesting distinct tuples, and for accepting tuples returned from the source component, for sequentially passing the tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and for passing only verified unique tuples to the consumer process,

the source component for retrieving a tuple in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and,

the auxiliary logger component for sequentially receiving tuples in the set of tuples from the distinct operator component and determining if each sequentially received tuple is distinct from other previously received tuples in the set of tuples to verify the uniqueness of each sequentially received tuple to the distinct operator component.

4. The method of claim 3, further comprising adding the auxiliary logger component including a hash table to each unique sequentially received tuple.

5. The relational database management system of claim 3, in which the auxiliary logger component further includes a sorted data structure to which each unique sequentially received tuple is added.

6. The method of claim 2, wherein instructions for the source component include instructions for retrieving a tuple in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and,

wherein instructions for the auxiliary logger component further includes instructions for sequentially receiving tuples in the set of tuples from the distinct component and for determining if each sequentially received tuple is distinct from other previously received tuples in the set of tuples to verify the uniqueness of each sequentially received tuple to the distinct operator component.

7. The method of claim 1, in which determining if each sequentially received tuple is distinct includes instructions for maintaining a hash table, for verifying uniqueness of tuples using the hash table and for adding each unique sequentially received tuple to the hash table.

8. The method of claim 7, in which the instructions for determining if each sequentially received tuple is distinct further includes instructions for maintaining a sorted data structure, for verifying uniqueness of tuples using the sorted data structure and for adding each unique sequentially received tuple to the sorted data structure.

9. A relational database management system comprising a source component;

an auxiliary logger component, and a distinct operator, the relational database management system supporting the provision of data from a defined table to a consumer process, the consumer process requesting data from the distinct operator component;

the distinct operator component for sequentially requesting a set of tuples from the source component upon a request from the consumer process, and for accepting tuples returned from the source component, for sequentially passing the tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and for passing only verified unique tuples to the consumer process, the source component for accessing a tuple, in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and the auxiliary logger component for sequentially receiving tuples in the set of tuples from the distinct operator component and determining using an auxiliary component if each sequentially received tuple is distinct from other previously returned tuples in the sequence to verify the uniqueness of each sequentially received tuple to the distinct operator component and indicating whether the retrieved tuple has been previously received by the auxiliary component.

10. The relational database management system of claim 9 in which the auxiliary component includes a hash table to which each unique sequentially received tuple is added.

11. The relational database management system of claim 9 in which the auxiliary component includes a sorted data structure to which each unique sequentially received tuple is added.

12. A computer readable medium containing program instructions for the retrieval of distinct tuples in a relational database management system, the program instructions for providing a distinct operator component, providing a source component, and

providing an auxiliary logger component, wherein the relational database management system supports the provision of data from a defined table to a consumer process, wherein the consumer process requests data from the distinct operator component, wherein the instruction for the distinct operator component further includes instructions for:

sequentially requesting a set of tuples from the source component upon a request from the consumer process, and for accepting tuples returned from the source component sequentially passing the tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and

passing only verified unique tuples to the consumer process, the source component comprising code means for accessing a tuple in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and

wherein the instructions for the auxiliary logger component further includes instructions for sequentially receiving tuples in the set of tuples from the distinct component and for determining using an auxiliary component if each sequentially received tuple is distinct from other previously returned tuples in the sequence to verify the uniqueness of each sequentially received tuple to the distinct operator component and indicating whether the retrieved tuple has been previously received by the auxiliary component.

13. The computer readable medium of claim 12 in which the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a hash table, for verifying uniqueness of tuples using the hash table and for adding each unique sequentially received tuple to the hash table.

14. The computer readable medium of claim 12 in which the instructions for determining if each sequentially received tuple is distinct further includes instructions for maintaining a sorted data structure, for verifying uniqueness of tuples using the sorted data structure and for adding each unique sequentially received tuple to the sorted data structure.

15. A computer readable medium containing program instructions for the retrieval of distinct tuples in a relational database management system, the program instructions for providing a distinct operator component, providing a source component, and

providing an auxiliary logger component, wherein the relational database management system supports the provision of data from a defined table to a consumer process, wherein the consumer process requests data from the distinct operator component, wherein the instruction for the distinct operator component further includes instructions for:

sequentially requesting a set of tuples from the source component upon a request from the consumer process, sequentially passing one or more tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and

passing only verified unique tuples to the consumer process, the source component comprising code means for accessing one or more tuples in the set of tuples from the defined table upon request from the distinct operator component and returning a subset of tuples to the distinct operator component, and wherein the instructions for the auxiliary logger component further including instructions for sequentially receiving a verification set of tuples in the set of tuples from the distinct component and for determining using an auxiliary component if each sequentially received tuple is distinct from other previously returned tuples in the sequence to verify the uniqueness of each sequentially received tuple to the distinct operator component and indicating whether the retrieved tuple has been previously received by the auxiliary component.

16. The computer readable medium of claim 15 wherein the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a hash table and for verifying uniqueness of tuples using the hash table and for adding each unique sequentially received tuple to the hash table.

17. The computer readable medium of claim 15 in which the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a sorted data structure and for verifying uniqueness of tuples using the sorted data structure and for adding each unique sequentially received tuple to the sorted datastructure.