US 9,141,648 B1Granted

Management of database blocks

AssigneeParAccel LLC

InventorsAdam Birnbaum, Raymi Dyskant, Scott Graupmann

Life of this patent

Estimating the term…

Loading patent…

Abstract

Data of a columnar database is organized into extents. Each extent occupies contiguous storage on the disk. An extent stores database blocks of a column of a database table. The database system adds new database blocks of a column to the extents assigned to that column. When a request for adding a block to a table is received, the extent for the table and column combination is obtained and the block added to the extent. Prefetching strategies are used to retrieve database blocks in advance of an actual request. The rate of prefetching is determined per column. The rate of prefetching is adjusted based on the number of faults encountered for the column. Database blocks no longer needed in memory are pushed out. When a scan process is reading blocks, as soon as the block has been processed it is scheduled to be pushed out.

Claims20

Dependent claims

A method for storing data in a database, the method comprising:

maintaining a set of extents on a persistent storage device for a columnar database, each extent for storing database blocks in a contiguous portion of the persistent storage device, each extent corresponding to:
a used extent, assigned to a column of a database table and storing database blocks from the column of a database table;
or
a free extent, not assigned to any column, the free extent without any stored database blocks;
receiving information identifying a plurality of tables for loading in the persistent storage device;
determining an order for loading the plurality of tables, the order preferring larger tables for loading before smaller tables;
receiving a database block of a source column of a database table for writing to the persistent storage device;
splitting a used extent for storing the database block if no used extent assigned to the source column has capacity to store the received database block and no free extent has capacity to store the database block, the splitting comprising:
selecting a used extent assigned to another column and dividing the selected used extent into a first used extent assigned to the other column and a second free extent;
and
storing the database block in the second free extent.

8 more elements

A non-transitory computer-readable storage medium storing computer-executable code for storing data in a database, the code, when executed by a computer processor, causing the computer processor to:

maintain a set of extents on a persistent storage device for a columnar database, each extent for storing database blocks in a contiguous portion of the persistent storage device, each extent corresponding to:
a used extent, assigned to a column of a database table and storing database blocks from the column of a database table;
or
a free extent, not assigned to any column, the free extent not storing any database blocks;
receive information identifying a plurality of tables for loading in the persistent storage device;
determine an order for loading the plurality of tables, the order preferring larger tables for loading before smaller tables;
receive a database block of a source column of a database table for writing to the persistent storage device;
split a used extent for storing the database block if no used extent assigned to the source column has capacity to store the received database block and no free extent has capacity to store the database block, the splitting comprising:
selecting a used extent assigned to another column and dividing the selected used extent into a first used extent assigned to the other column and a second free extent;
and
store the database block in the second free extent.

8 more elements

A computer-implemented system for storing data in a database, the system comprising:

a computer processor;
and
a non-transitory computer-readable storage medium storing computer-executable code for storing data in a database, the code, when executed by the computer processor, causing the computer processor to:
maintain a set of extents on a persistent storage device for a columnar database, each extent for storing database blocks in a contiguous portion of the persistent storage device, each extent corresponding to:
a used extent, assigned to a column of a database table and storing database blocks from the column of a database table;
or
a free extent, not assigned to any column, the free extent not storing any database blocks;
receive information identifying a plurality of tables for loading in the persistent storage device;
determine an order for loading the plurality of tables, the order preferring larger tables for loading before smaller tables;
receive a database block of a source column of a database table for writing to the persistent storage device;
split a used extent for storing the database block if no used extent assigned to the source column has capacity to store the received database block and no free extent has capacity to store the database block, the splitting comprising:
selecting a used extent assigned to another column and dividing the selected used extent into a first used extent assigned to the other column and a second free extent;
and
store the database block in the second free extent.

11 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/797,615Filed 12 Mar 2013 · us provisional application
Priority: 5 May 2012
Granted: 22 Sep 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 16/24552
Query execution: database cache management
G06F 16/21
Of structured data, e.g. relational data: design, administration or maintenance of databases
G06F 12/0862
Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches: with prefetch
G06F
Computing and data processing