Browse Prior Art Database

Growing Data Distribution Map Size without Data Redistribution

IP.com Disclosure Number: IPCOM000212708D
Publication Date: 2011-Nov-23
Document File: 5 page(s) / 48K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method applied to DB2* which allows growth in the distribution hash map and alters the hashing function such that no data redistribution is needed. The method grows the hash map such that existing rows do not move, only powers of 2 are used in the growth of 4096 to 32768, and the growth is done in a fixed number of steps. It 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 32% of the total text.

Page 01 of 5

Growing Data Distribution Map Size without Data Redistribution

DB2* is a relational database which incorporates a shared nothing architecture when 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 4096 entries. Each entry in the hash map indicates the target partition of the record. When the number of partitions does not divide evenly into 4096, then some partitions have one more hash buckets than others. 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 becomes larger, the number of hash buckets per partition drops, and the difference between n and n+1 buckets starts to become significant. For example, at 200 partitions some partitions will get 20 hash buckets and others will get 21, at a difference of 5%. This will cause skew in a distribution of the data to the partitions. At 200 partitions the skew is about 5% while at 500 partitions the skew is over 12%. It gets worse and worse as the number of partitions increases.

There are two serious problems that result from this skew:


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


• Cost. Storage is typically purchased on the assumption that data will distribute evenly across all partitions. In the presence of skew, the storage costs are increased proportionately 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.

Changing the hash map to a larger size (from 4096 to 32768 entries) to reduce skew percentage would require a Data Redistribution which is a complicated and very time consuming process. The outage based on this process is known to sometimes take days or weeks at the customer's sites. Requiring redistribution when migrating to a new version of DB2 that introduces skew correcting larger partition map would be a prevent progress.

The disclosed invention allows the growth in the hash map and alters the hashing function such that no data redistribution is needed. The components of the core idea are to utilize a method that:


• Grows the hash map such that existing rows do not move. The process uses only powers of 2 in the growth of 4096 to 32768. This growth is done in a fixed number of steps.


• Enhances the hashing function to make use of the 28k new entries, while ensuring they do not change the existing partition mapping

1


Page 02 of 5

The advantage with this technique to increas...