Methods and systems for identifying highly contended blocks in a database

A computer system including a database that stores a plurality of files organized as a plurality N of uniquely identified blocks and one or more applications that access selected ones of the blocks, the computer system comprising:

• at least one processor;
• a plurality of processes spawned by said at least one processor for identifying the most frequently accessed blocks in the database, the processes including processing logic for:
• generating a list of the blocks that are accessed by the one or more applications;
• identifying a selectable number K of blocks from the list that account for at least N/K+1 of the accesses, by carrying out the steps of:
• setting a first block of the list as an existing candidate block and setting its count to 1;
• for each subsequent block of the list;
• carrying out:
• a step to increment the count of the existing candidate block if the block is identical to an existing candidate block, or if the block is not identical to an existing candidate block, carrying out one of:
• a step to decrement the count of any existing candidate block having a non-zero count if there are K existing candidate blocks;
• a step to replace an existing candidate block having a zero count with the block if there are K existing candidate blocks, the block becoming an existing candidate block having a count of 1;
• a step to add an existing candidate block and setting the count of the added existing candidate block to 1 if there are fewer than K existing candidate blocks;
• and
• providing all existing candidate blocks having a non-zero count as the K blocks of the list that account for at least N/K+1 of the accesses.

A machine-readable medium having data stored thereon representing sequences of instructions which, when executed by a computing device causes the computing device to identify the most frequently blocks in a database accessed by one or more applications, by carrying out steps including:

• generating a list of the blocks that are accessed by the one or more applications;
• identifying a selectable number K of blocks from the list that account for at least N/K+1 of the accesses, by carrying out the steps of:
• setting a first block of the list as an existing candidate block and setting its count to 1;
• for each subsequent block of the list;
• carrying out:
• a step to increment the count of the existing candidate block if the block is identical to an existing candidate block, or if the block is not identical to an existing candidate block, carrying out one of:
• a step to decrement the count of any existing candidate block having a non-zero count if there are K existing candidate blocks;
• a step to replace an existing candidate block having a zero count with the block if there are K existing candidate blocks, the block becoming an existing candidate block having a count of 1;
• a step to add an existing candidate block and setting the count of the added existing candidate block to 1 if there are fewer than K existing candidate blocks, and
• providing all existing candidate blocks having a non-zero count as the K blocks of the list that account for at least N/K+1 of the accesses.

A computer system suitable for generating a list of K most frequently accessed ones of a plurality of data blocks in a database, comprising:

• at least one processor;
• a plurality of processes spawned by said at least one processor, the processes including processing logic for:
• enabling a selection of the number K;
• building the list of K blocks by storing an identification of and maintaining a running count for up to selected K ones of the plurality of accessed data blocks by iteratively carrying out a single step for each of the plurality of data blocks, the single step being selected from an incrementing step to increment the count, a decrementing step to decrement the count, an adding step to add a data block to the list and to set a count of the added data block and a replacing step to replace an existing data block of the list with a new data block and to set a count of the new data block, and
• providing the list of K most frequently accessed blocks.