Adaptive aggregation: improving the performance of grouping and duplicate elimination by avoiding unnecessary disk access

• US 8,352,470 B2
• Filed: 05/23/2008
• Issued: 01/08/2013
• Est. Priority Date: 05/23/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Ying, He, Bin
• Primary Examiner(s): Hwa, Shyue Jiunn
• Assistant Examiner(s): Gurmu, Muluemebet
• Application Number:
  US12/126,831
• Publication Number:
  US 20090292704A1
• Time in Patent Office: 1,691 Days
• Field of Search: 707/737
• US Class Current: 707/737
• 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, comprising:

using an aggregation method, reading blocks of the information from the storage medium into a memory of the computer until the memory is full or until all the information has been read into the memory;

removing duplicates of the blocks as each respective disk block is read into the memory of the computer;

determining a number, k, of blocks to be written back to the storage medium from the memory, wherein k is an estimate of how many blocks need to be written back to the storage medium, based on an estimate of the extent of duplication within the information;

selecting k blocks from the memory, sorting the selected blocks, ranking a group of the selected k blocks based on a number of early aggregation operations done for a group of the selected k blocks with a same value, and writing the sorted blocks with lowest rank as a new sublist to the storage medium;

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

merging the sublists to form an aggregation result; and

outputting partial results of the forming of the aggregation result without writing the partial results to disk.

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 iterating comprises iterating the steps of reading, determining, selecting, sorting, and writing sublists until all the information has been processed.

4. The method of claim 1, wherein k is an estimate of how a lot of blocks need a number of blocks to be written back to the storage medium for each iteration.

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

randomly selecting the blocks from the memory.

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

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

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

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

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

9. 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 until the memory of the database system is full or until all the blocks of the table have been read into the memory of the database system;

determining a number, k, of blocks from the memory to be written from the memory back to the storage medium, wherein k is an estimate of how many blocks from the memory of the database system need to be written back to the storage medium, based on an estimate of the extent of duplication within the memory of the database system;

selecting k of the blocks from the memory, sorting the selected blocks, ranking a group of the selected k blocks based on a total number of early aggregation operations done for a group of the selected k blocks, and accessing the storage medium to write the sorted blocks with the lowest rank 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;

directly outputting to a computer display those blocks from the table that were brought into the memory of the database system for multiple iterations of the reading of the sublists from the computer-accessible storage medium;

sorting the sublists after each of a plurality of instances of the reading of the sublists; and

merging the sublists to form an aggregation result.

10. The system of claim 9, 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)−

i−

1)≠

0, and

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.

11. The system of claim 9, 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)−

i−

1)≠

0, and

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.

12. The system of claim 10, 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(M)−

i−

1)≠

0, and

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.

13. The system of claim 11, 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(M)−

i−

1)≠

0,

and 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.

14. 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, wherein k is an estimate of how many blocks from the memory of the computer need to be written back to the storage medium, based on an estimate of the extent of duplication within the memory of the computer;

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

keep those blocks of the table which have multiple prior aggregations in the memory of the computer until the sorted lowest ranked blocks are written 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;

sort partial results after each of a plurality of instances of the reading of the sublists; and

merge the sublists to form an aggregation result.

15. The product of claim 14, 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.

16. The product of claim 14, 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.

17. The product of claim 14, 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.

18. The product of claim 14, 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.