Browse Prior Art Database

Proportional memory allocation algorithm

IP.com Disclosure Number: IPCOM000015366D
Original Publication Date: 2002-Sep-30
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 61K

Publishing Venue

IBM

Abstract

Historically, some database management systems (DBMS) have used a uniform memory allocation policy. This policy allocated memory uniformly across all concurrently executing operators regardless of these operators' actual memory requirements. With the uniform memory allocation policy, the total memory that had to be allocated to a plan to prevent overflow depended on the memory requirements of the single operator that required the most memory. Thus, if one operator required significantly more memory than the others, a great deal of memory might have been wasted simply to prevent the most memory intensive operator from overflowing. The new Proportional Memory Allocation (PMA) algorithm attempts to allocate to each operator the actual amount of memory required by that operator to avoid overflow. With the new algorithm, if one operator requires more memory than another, the server allocates more memory to the operator that can actually use the memory. This strategy increases memory utilization and improves query performance by decreasing the probability of overflow. The various steps in the algorithm are as follows: 1. Computation of Phases The server determines the maximum number of concurrent memory consuming operators in the plan that will execute at any one time and assigns the operators to phases. A phase is a group of adjacent operators that execute and consume memory simultaneously. Each operator belongs to a range of phases starting with the phase during which it is activated and ending with the phase during which it terminates.

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

Page 1 of 3

Proportional memory allocation algorithm

  Historically, some database management systems (DBMS) have used a uniform memory allocation policy. This policy allocated memory uniformly across all concurrently executing operators regardless of these operators' actual memory requirements. With the uniform memory allocation policy, the total memory that had to be allocated to a plan to prevent overflow depended on the memory requirements of the single operator that required the most memory. Thus, if one operator required significantly more memory than the others, a great deal of memory might have been wasted simply to prevent the most memory intensive operator from overflowing.

The new Proportional Memory Allocation (PMA) algorithm attempts to allocate to each operator the actual amount of memory required by that operator to avoid overflow. With the new algorithm, if one operator requires more memory than another, the server allocates more memory to the operator that can actually use the memory. This strategy increases memory utilization and improves query performance by decreasing the probability of overflow.

The various steps in the algorithm are as follows:

1. Computation of Phases The server determines the maximum number of concurrent memory consuming operators in the plan that will execute at any one time and assigns the operators to phases. A phase is a group of adjacent operators that execute and consume memory simultaneously. Each operator belongs to a range of phases starting with the phase during which it is activated and ending with the phase during which it terminates.

2. Computation of Memory Requirements The server calculates the maximum memory requirement (max_op_mem) for each memory consuming operator as well as for each phase of concurrently executing operators. Finally, the per-phase memory requirements computed above are used to determine the maximum memory requirement for the entire plan (max_plan_mem).

    The DBMS Resource Grant Manager (RGM) allocates memory to branches rather than to operators. If one branch has two or more memory consuming operators, the RGM simply divides the memory allocated to the branch equally among the operators. To account for this, the memory requirement of all operators in the same branch is set to the maximum memory required by an operator in the branch.

3. The actual PMA algorithm consists of two main steps:

    a) Initial memory allocation The server computes the actual operator memory (act_op_mem) or the amount of memory actually given to each memory consuming operator as follows:

act_plan_mem = actual memory granted to the query

mem_ratio = act_plan_mem / max_plan_mem

1

Page 2 of 3

act_op_mem = max_op_mem * mem_ratio

     The server computes the actual branch memory or the amount of memory actual given to each branch as follows:

max_br_mem = maximum memory requirement for a branch

= MAX(max_op_mem of operators in branch) * number of operators in branch
act_br_mem = max_br_mem * mem_ratio

         If act_br...