Split elimination in mapreduce systems

• US 10,691,646 B2
• Filed: 03/05/2018
• Issued: 06/23/2020
• Est. Priority Date: 02/06/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eltabakh, Mohamed, Haas, Peter J., Ozcan, Fatma, Pirahesh, Mir Hamid, Sismanis, John (Yannis), Vondrak, Jan
• Primary Examiner(s): Bromell, Alexandria Y
• Application Number:
  US15/912,410
• Publication Number:
  US 20180196828A1
• Time in Patent Office: 841 Days
• Field of Search: 707719
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

Embodiments of the present invention relate to elimination of blocks such as splits in distributed processing systems such as MapReduce systems using the Hadoop Distributed Filing System (HDFS). In one embodiment, a method of and computer program product for optimizing queries in distributed processing systems are provided. A query is received. The query includes at least one predicate. The query refers to data. The data includes a plurality of records. Each record comprises a plurality of values in a plurality of attributes. Each record is located in at least one of a plurality of blocks of a distributed file system. Each block has a unique identifier. For each block of the distributed file system, at least one value cluster is determined for an attribute of the plurality of attributes. Each value cluster has a range. The predicate of the query is compared with the at least one value cluster of each block. The query is executed against only those blocks where the predicate is met by at least one value cluster.

Claims

1. A method comprising:

receiving a query comprising at least one predicate, the query referring to data comprising a plurality of records, each record comprising a plurality of values in a plurality of attributes and each record being located in at least one of a plurality of blocks of a distributed file system, each block having a unique identifier;

determining a block count indicating the number of blocks in which each of the values of the data appear;

determining a record count indicating the number of instances of each of the values in each of the attributes;

based on the block count, determining a profit value associated with copying each of the values of the data to a materialized view;

based on the record count, determining a cost value associated with copying each of the values of the data to a materialized view;

selecting a predetermined number of values such that the profit to cost ratio is maximal for the predetermined number of values;

providing a materialized view comprising the predetermined number of values;

determining whether the query is applicable to the materialized view;

wherein the query comprises more than one predicate and determining whether the query is applicable to the materialized view comprises;

determining whether the predicates comprise a conjunction of a predicate met by one of the values of the materialized view;

executing the query against the materialized view if it is applicable to the materialized view.

2. The method of claim 1, wherein determining the profit value further comprises weighting the profit value based on a historical frequency of queries returning each of the values.

3. The method of claim 1, wherein the query comprises exactly one predicate and determining whether the query is applicable to the materialized view comprises:

determining whether the predicate is met by one of the values of the materialized view.

4. The method of claim 1, wherein:

determining the block count comprises;

traversing each of the plurality of blocks;

maintaining a data structure comprising at most a first predetermined number of values with a highest profit to cost ratio; and

determining the record count comprises;

traversing the data structure.

5. The method of claim 4, wherein the data structure is a sorted list.

6. The method of claim 4, wherein the data structure is a heap.

7. A computer program product for optimizing queries in distributed processing systems, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

receiving a query comprising at least one predicate, the query referring to data comprising a plurality of records, each record comprising a plurality of values in a plurality of attributes and each record being located in at least one of a plurality of blocks of a distributed file system, each block having a unique identifier;

determining a block count indicating the number of blocks in which each of the values of the data appear;

determining a record count indicating the number of instances of each of the values in each of the attributes;

based on the block count, determining a profit value associated with copying each of the values of the data to a materialized view;

based on the record count, determining a cost value associated with copying each of the values of the data to a materialized view;

selecting a predetermined number of values such that the profit to cost ratio is maximal for the predetermined number of values;

providing a materialized view comprising the predetermined number of values;

determining whether the query is applicable to the materialized view;

wherein the query comprises more than one predicate and determining whether the query is applicable to the materialized view comprises;

determining whether the predicates comprise a conjunction of a predicate met by one of the values of the materialized view;

executing the query against the materialized view if it is applicable to the materialized view.

8. The computer program product of claim 7, wherein determining the profit value further comprises weighting the profit value based on a historical frequency of queries returning each of the values.

9. The computer program product of claim 7, wherein the query comprises exactly one predicate and determining whether the query is applicable to the materialized view comprises:

determining whether the predicate is met by one of the values of the materialized view.

10. The computer program product of claim 7, wherein:

determining the block count comprises;

traversing each of the plurality of blocks;

maintaining a data structure comprising at most a first predetermined number of values with a highest profit to cost ratio; and

determining the record count comprises;

traversing the data structure.

11. The computer program product of claim 10, wherein the data structure is a sorted list.

12. The computer program product of claim 10, wherein the data structure is a heap.