Browse Prior Art Database

Growing Size of Data Distribution Map without Requiring Data Redistribution

IP.com Disclosure Number: IPCOM000218212D
Publication Date: 2012-May-28
Document File: 7 page(s) / 98K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method to allow the growth in the hash map and alter the hashing function such that no data redistribution is needed. The method includes growing the hash map such that existing rows do not move. It adheres to powers of 2 in the growth 4,096 to 32,768. This growth is done in a fixed number of steps. The method also enhances the hashing function to make use of the 28k new entries, while ensuring they do not change the existing partition mapping.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 27% of the total text.

Page 01 of 7

Growing Size of Data Distribution Map without Requiring Data Redistribution

DB2 is a relational database that incorporates a shared -nothing architecture when a Data Partition Feature (DPF) is enabled. This allows the use of independent computer servers (partitions) to store data and share in the Central Processing Unit (CPU) workload. Data is distributed using a hashing algorithm on each data row 's partitioning keys.

The current hashing algorithm hashes records into a hash map (also known as partition map or distribution map) of 4,096 entries. Each entry in the hash map indicates the target partition of the record . When the number of partitions does not divide evenly into 4,096, then some partitions have one more hash bucket than others do . This is not usually a problem so long as the number of hash buckets in the partitioning map is much larger than the number of partitions in the database . However, as the number of partitions become large the number of hash buckets per partition drops , the difference between n and n+1 buckets becomes significant. For example, at 200 partitions, some partitions will get 20 hash buckets and others will get 21, a difference of 5%. This causes skew in the distribution of the data to the partitions . At 200 partitions, the skew is about 5%, while at 500 partitions the skew is over 12%. This skew worsens as the number of partitions increases. Two serious problems result from this skew:

1. Performance. In a shared-nothing architecture, the system performance is only as fast as the slowest partition. Partitions with x% more data perform (possibly) n% worse.

2. Storage is typically purchased on the assumption that data will distribute evenly across all partitions. Storage is typically the most expensive component in an enterprise warehouse. In the presence of skew, the storage costs are proportionately increased with the data skew as the user is forced to purchase enough storage (or enough Balanced Configuration Units (BCUs)) to support the partitions with the most data. In general, although there may be skew in the data placement, customers are discouraged from purchasing/implementing heterogeneous BCUs (some with more storage and others with less).

Changing the hash map to a larger size (from 4,096 to 32,768 entries) to reduce skew percentage requires a Data Redistribution , which is a complicated and very time-consuming process. The outage based on this process is known to sometimes take day or weeks at a customer's sites. Requiring redistribute when migrating to a new version of DB2 that introduces skew correcting larger partition map is not acceptable.

The disclosed invention allows the growth in the hash map and alters hashing function such that no data redistribution is needed .

The core idea:

1. Grow the hash map such that existing rows do not move. Adhere to powers of 2 in the growth 4,096 to 32,768. This growth is done in a fixed number of steps.

1


Page 02 of 7

2. Enhance the hashing fun...