Aggregate predicates and search in a database management system

• US 6,947,934 B1
• Filed: 02/16/2000
• Issued: 09/20/2005
• Est. Priority Date: 02/16/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Weidong, Natsev, Apostol Ivanov, Jou, Michelle Meichiou, Fuh, You-Chin
• Primary Examiner(s): Ali, Mohammad
• Application Number:
  US09/505,165
• Time in Patent Office: 2,043 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 705/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A technique for executing a statement in a computer to manipulate data in a data store connected to the computer. Initially, a statement having an aggregate predicate is received. Then, when evaluating the statement, the aggregate predicate is processed to rank data. Furthermore, evaluating includes performing an extended sort operator with early termination.

Claims

1. A method of executing a statement in a computer to manipulate data in a data store connected to the computer, the method comprising:

receiving a statement having a rank operator for specifying an aggregate predicate; and

when evaluating the statement, processing the aggregate predicate to produce a rank-sorted set of tuples by performing an extended sort on an input stream of tuples using a rank, a group-by list and a scoring expression.

2. The method of claim 1, wherein the aggregate predicate is contained in a search condition.

3. The method of claim 1, wherein the aggregate predicate comprises a numeric-expression.

4. The method of claim 1, wherein the aggregate predicate comprises an ordering indicator.

5. The method of claim 1, wherein the agate predicate comprises a window-specification.

6. The method of claim 1, wherein the aggregate predicate comprises a scalar-expression.

7. The method of claim 1, wherein evaluating comprises performing an extended sort operator.

8. The method of claim 7, wherein the extended sort operator is part of an access plan.

9. The method of claim 7, wherein performing the extended sort operator comprises receiving a stream comprising one or more tuples, a rank, a group by list comprising zero or more groups, and a scoring expression.

10. The method of claim 9, further comprising, for each tuple in the stream, discarding the tuple if its target group is frozen.

11. The method of claim 9, further comprising:

determining a group round radius; and

when the tuple has a different round radius than the group round radius,

setting the group round radius to that round radius; and

if a desired number of tuples have been identified for the group, freezing the group.

12. The method of claim 9, further comprising inserting the tuple into a rank-sorted table based on values in the group by list and scoring expression.

13. The method of claim 9, further comprising, when all tuples in the stream have been processed, freezing the groups that have not already been frozen.

14. An apparatus for executing a statement to manipulate data, comprising:

a computer having a data store connected thereto, wherein the data store stores data; and

one or more computer programs, performed by the computer, for receiving a statement having a rank operator for specifying an aggregate predicate and when evaluating the statement, processing the aggregate predicate to produce a rank-sorted set of tuples by performing an extended sort on an input stream of tuples using a rank, a group-by list and a scoring expression.

15. The apparatus of claim 14, wherein the aggregate predicate is coined in a search condition.

16. The apparatus of claim 14, wherein the aggregate predicate comprises a numeric-expression.

17. The apparatus of claim 14, wherein the aggregate predicate comprises an ordering indicator.

18. The apparatus of claim 14, wherein the aggregate predicate comprises a window-specification.

19. The apparatus of claim 14, wherein the aggregate predicate comprises a scalar-expression.

20. The apparatus of claim 14, wherein the evaluating comprises performing an extended sort operator.

21. The apparatus of claim 20, wherein the extended sort operator is part of an access plan.

22. The apparatus of claim 20, wherein performing the extended sort operator comprises receiving a stream comprising one or more tuples, a rank, a group by list comprising zero or more groups, and a scoring expression.

23. The apparatus of claim 22, further comprising, for each tuple in the stream, discarding the tuple if its target group is frozen.

24. The apparatus of claim 22, further comprising:

determining a group round radius; and

when the tuple has a different round radius than the group round radius,

setting the group round radius to that round radius; and

if a desired number of tuples have been identified for the group, freezing the group.

25. The apparatus of claim 22, further comprising inserting the tuple into a rank-sorted table based on values in the group by list and scoring expression.

26. The apparatus of claim 22, further comprising, when all tuples in the stream have been processed, freezing the groups that have not already been frozen.

27. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for executing a statement in a computer to manipulate data in a data store connected to the computer, comprising:

receiving a statement having a rank operator for specifying an aggregate; and

when evaluating the statement, processing the aggregate predicate to produce a rank-sorted set of tuples by performing an extended sort on an input stream of tuples using a rank, a group-by list and a scoring expression.

28. The article of manufacture of claim 27, wherein the aggregate predicate is contained in a search condition.

29. The article of manufacture of claim 27, wherein the aggregate predicate comprises a numeric-expression.

30. The article of manufacture of claim 27, wherein the aggregate predicate comprises an ordering indicator.

31. The article of manufacture of claim 27, wherein the aggregate pr comprises a window-specification.

32. The article of manufacture of claim 27, wherein the aggregate predicate comprises a scalar-expression.

33. The article of manufacture of claim 27, wherein evaluating comprises performing an extended sort operator.

34. The article of manufacture of claim 33, wherein the extended sort operator is part of an access plan.

35. The article of manufacture of claim 33, wherein performing the extended sort operator comprises receiving a stream comprising one or more tuples, a rank, a group by list comprising zero or more groups, and a scoring expression.

36. The article of manufacture of claim 35, further comprising for each tuple in the steam, discarding the tuple if its target group is frozen.

37. The article of manufacture of claim 35, further comprising:

determining a group round radius; and

when the tuple has a different round radius than the group round radius,

setting the group round radius to that round radius; and

if a desired number of tuples have been identified for the group, freezing the group.

38. The article of manufacture of claim 35, further comprising inserting the tuple into a rank-sorted table based on values in the group by list and scoring expression.

39. The article of manufacture of claim 35, further comprising, when all tuples in the stream have been processed, freezing the groups that have not already been frozen.