ADAPTIVE AGGREGATION: IMPROVING THE PERFORMANCE OF GROUPING AND DUPLICATE ELIMINATION BY AVOIDING UNNECESSARY DISK ACCESS

• US 20090292704A1
• Filed: 05/23/2008
• Published: 11/26/2009
• Est. Priority Date: 05/23/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Ying, He, Bin
• Granted Patent: US 8,352,470 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation

Abstract

A method for use with an aggregation operation (e.g., on a relational database table) includes a sorting pass and a merging pass. The sorting pass includes: (a) reading blocks of the table from a storage medium into a memory using an aggregation method until the memory is substantially full or until all the data have been read into the memory; (b) determining a number k of blocks to write back to the storage medium from the memory; (c) selecting k blocks from memory, sorting the k blocks, and then writing the k blocks back to the storage medium as a new sublist; and (d) repeating steps (a), (b), and (c) for any unprocessed tuples in the database table. The merging pass includes: merging all the sublists to form an aggregation result using a merge-sort algorithm.

Claims

1. A computer-implemented method for use with information stored in blocks on a storage medium, the method comprising:

reading blocks of the information from the storage medium into a memory of the computer using an aggregation method;

determining a number, k, of blocks to be written back to the storage medium from the memory;

selecting k blocks from the memory, sorting the selected blocks, and writing the sorted blocks as a new sublist to the storage medium;

iterating the steps of reading, determining, selecting, sorting, and writing sublists; and

merging the sublists to form an aggregation result.

2. The method of claim 1, wherein the aggregation method is an early-aggregation before sort method.

3. The method of claim 1, wherein the step of reading comprises reading blocks until the memory is full or until all the information has been read into the memory.

4. The method of claim 1, wherein the step of iterating comprises iterating the steps of reading, determining, selecting, sorting, and writing sublists until all the information has been processed.

5. The method of claim 1, wherein k is a conservative estimate of how many blocks need to be written back for each iteration.

6. The method of claim 1, wherein k is a conservative estimate of how many blocks need to be written back for each iteration, based on an estimate of the extent of duplication within the information.

7. The method of claim 1, wherein selecting k blocks from the memory comprises:

randomly selecting the blocks from the memory.

8. The method of claim 2, wherein selecting k blocks from the memory comprises:

selecting the blocks from the memory according to how many early-aggregations the blocks participated in during a most recent previous iteration.

9. The method of claim 2, wherein selecting k blocks from the memory comprises:

selecting the blocks from the memory according to how many early-aggregations the blocks participated in during all previous iterations.

10. The method of claim 1, wherein the information comprises tuples in a database.

11. A database system, the database system including a table having tuples, the tuples stored in blocks on a computer-accessible storage medium, the database system executing steps for:

accessing the storage medium to read blocks of the table into a memory of the database system using an early-aggregation method;

determining a number, k, of blocks to be written from the memory back to the storage medium;

selecting k blocks from the memory, sorting the selected blocks, and accessing the storage medium to write the sorted blocks as a sublist;

iterating the processes of reading, determining, selecting, sorting, and writing sublists, wherein the number of accesses to read blocks and write blocks is less than that required to read and write all blocks of the table; and

merging the sublists to form an aggregation result.

12. The system of claim 11, wherein the determining step comprises:

calculating a worst-case estimate of the number, k, of blocks to be written back for each iteration according to a formula;

k=min(B(M),[b/(B(M)−

i−

1)]),

wherein B(M) denotes the number of blocks that can be held in the memory, b denotes the number of blocks remaining to be read from the storage medium at a current iteration and i counts the current iteration.

13. The system of claim 11, wherein the determining step comprises:

calculating an adjusted worst-case estimate of the number, k, of blocks to be written back for each iteration according to a formula;

k=min(B(M),[b/(f×

(B(M)−

i−

1))]),

wherein B(M) denotes the number of blocks that can be held in the memory, b denotes the number of blocks remaining to be read from the storage medium at a current iteration, f denotes an estimate up to the current iteration of the average number of tuples having the same value, and i counts the current iteration.

14. The system of claim 12, wherein:

the number of accesses to read blocks and write blocks is no more than;

B(R)+2×

(Σ

_i=1<sup>N−

1</sup>min(B(M),[b_(i+1)/(B(M)−

i−

1)])+k_N)

wherein B(R) denotes the number of blocks of the table, i counts the iterations, N is the total number of iterations, B(M) denotes the number of blocks that can be held in the memory, and b_(i+1) denotes the number of blocks remaining to be read from the storage medium at the i-th iteration.

15. The system of claim 13, wherein

the number of accesses to read blocks and write blocks is no more than:

B(R)+2×

(Σ

_i=1<sup>N−

1</sup>min(B(M),[b_(i+1)/(f×

(B(M)−

i−

1))])+k_N)

wherein B(R) denotes the number of blocks of the table, i counts the iterations, N is the total number of iterations, B(M) denotes the number of blocks that can be held in the memory, b_(i+1) denotes the number of blocks remaining to be read from the storage medium at the i-th iteration, and f denotes an estimate up to the i-th iteration of the average number of tuples having the same value.

16. A computer program product for use with a relational database table having tuples stored in blocks on a computer-accessible storage medium, the computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

read blocks of the table from the storage medium into a memory of the computer using an early-aggregation before sort method until the memory is full or until all the blocks have been read into the memory;

determine a number, k, of blocks to be written back to the storage medium from the memory;

select k blocks from the memory, sort the selected blocks, and write back the sorted blocks as a sublist to the storage medium;

iterate the steps of reading, determining, selecting, sorting, and writing sublists until each block has been read into the memory, wherein the total number of block reads and writes is less than that required to read and write all blocks of the table; and

merge the sublists to form an aggregation result.

17. The product of claim 16, wherein the determining step comprises:

calculating k based on the number of blocks that can be held in the memory, and the number of blocks remaining to be read from the storage medium at a current iteration.

18. The product of claim 16, wherein the determining step comprises:

calculating k based on the number of blocks that can be held in the memory, the number of blocks remaining to be read from the storage medium at a current iteration, and an estimate up to the current iteration of the average number of tuples having the same value.

19. The product of claim 16, wherein selecting k blocks from the memory comprises:

ranking groups of tuples by the number of early-aggregation operations done for a group of tuples having the same value in a current iteration; and

selecting the blocks from the memory to write back according to which blocks have the lowest ranked tuples.

20. The product of claim 16, wherein selecting k blocks from the memory comprises:

ranking groups of tuples by the number of early-aggregation operations done for a group of tuples having the same value in all previous and current iterations; and

selecting the blocks from the memory to write back according to which blocks have the lowest ranked tuples.