Parallel execution of Duplicate elimination, Projection, and Aggregation operations


How do we perform Duplicate data elimination, Projection, and Aggregation in parallel in parallel database system?


Assume that the table is partitioned and stored in disks D0, D1, …, Dn-1 with processors P0, P1, …, Pn-1. For example, consider the following figure where the table Employee is partitioned used Round-robin partitioning technique.
Figure 1 - Partitioning Employee table


Duplication elimination:

Duplicate elimination is about removing duplicate values or neglecting repeated values that are stored in an attribute for various reasons; For example, in one or all of the following situations we need duplicate elimination;

  • When we would like to count the number of unique values present in a table under a particular attribute.
  • When we need to retrieve the values and present only the unique values of an attribute.
  • When we need to join two tables, etc.
The main approach used for duplicate elimination is by sorting the data on the attribute where in the duplicate values to be removed.
Duplicate elimination can be achieved in the following two ways in parallel database;
1. During parallel sort, if we find any repeated values while partitioning, those can be discarded immediately. (This method is for tables that are not partitioned). For example, in Figure 1, while you partition the data, you send tuples to different partitions based on the partition attribute and conditions. Suppose that we are partitioning on Salary attribute. During the process, if you find any of the repeated values which are already send into a partition, you can discard those values if they repeat. In our example, salary value 5000 occurs in two records. Hence, one can be accepted and the other can be discarded.
2. We can partition the table into many partitions (using range or hash partitioning), and instruct all the processors to sort the data locally and remove the duplicates. (This works only for the data that are hash or range partitioned on the duplicate elimination attribute)

Projection:

Projection means selection of one or more attributes from a table with the records stored in them. This operation can be parallelized as follows;
1. Projection without duplicate elimination: while you read data into various disks during partitioning, you can project the required columns.
2. Projection with duplicate elimination: any of the techniques suggested in Duplicate elimination section above can be used.

Aggregation:

Aggregation operation involves finding the count of records, sum of values stored in an attribute, minimum or maximum value of all the values stored in an attribute, and average value of all the attribute values. This operation basically needs grouping. That is, for example, we can find the sum of salary for all the records of Employee table, or we can find sum of salary with some filter conditions. In the first case, all the records of Employee table come under one group. In the later case, we choose the group based on the conditions included.




Wikipedia

Search results

Followers