# US 2014/0279849 A1 · Hierarchical tablespace space management

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0279849 A1
- Document ID: US20140279849A1
- Status: Published application
- Kind: A1
- Application number: 13/804,197
- Filed: 2013-03-14
- Published: 2014-09-18
- Earliest claimed: 2013-03-14
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Wei Zhang; Sujatha Muthulingam; Amit Ganesh
- Web page: https://patentgrep.com/patent/US20140279849A1

## CPC

- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 12/023: {Free address space management}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/23: Updating
- G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc
- G06F 2212/163: Server or database system
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method, apparatus, and system for hierarchical organization of tablespace free space metadata in a database are provided. The hierarchy is divided into at least two levels: level 1 or L1 bitmap blocks are stored as a shared data structure and map free space in a tablespace, whereas level 2 or L2 bitmap blocks are stored as separate local copies at each database instance and map to the L1 bitmap blocks. This hierarchical organization provides a mechanism for finer grained concurrency control, enabling highly parallel tablespace metadata processing to accommodate the performance requirements of large tablespaces with big data sets. By integrating the hierarchical organization as part of the tablespace stack layer in a database management system (DBMS), implementations can be provided transparently to database end users without demanding any additional administrative, maintenance, or development burdens.

## Claims

### Claim 1

A method, comprising steps of:
storing tablespace metadata describing a tablespace of a database;
receiving, at a first instance of a plurality of database server instances for the database, a request to perform an operation on the tablespace;
updating the tablespace metadata according to the operation;
wherein the tablespace metadata is organized by a hierarchy comprising:
a level 1 (L1) bitmap block level comprising a plurality of L1 bitmap blocks mapping free space of a plurality of allocation units in the tablespace, wherein each of the plurality of L1 bitmap blocks indicates an ownership affinity with one of the plurality of database server instances, and wherein the L1 bitmap block level is stored as a single copy shared by the plurality of database server instances;
a level 2 (L2) bitmap block level comprising a plurality of L2 bitmap blocks mapping to the L1 bitmap block level, wherein each of the plurality of database server instances is assigned to store one of the plurality of L2 bitmap blocks;
wherein the method is performed by one or more computing devices.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of the plurality of L2 bitmap blocks includes the ownership affinity for each mapped L1 bitmap block.

### Claim 3 (depends on 1)

The method of claim 1, wherein each of the plurality of L2 bitmap blocks includes additional free-space metadata for each mapped L1 bitmap block that is self-owned in the respective L2 bitmap block, wherein each mapped L1 bitmap block is self-owned when the ownership affinity of the mapped L1 bitmap block matches an assigned instance for the respective L2 bitmap block.

### Claim 4 (depends on 1)

The method of claim 1, wherein each of the plurality of L1 bitmap blocks maps free space of an allocation stripe having a fixed number of allocation units.

### Claim 5 (depends on 4)

The method of claim 4, wherein each of the plurality of L1 bitmap blocks is stored in a pre-allocated metadata header area of the mapped allocation stripe.

### Claim 6 (depends on 1)

The method of claim 1, wherein each of the plurality of L1 bitmap blocks maps is split into distinct areas.

### Claim 7 (depends on 1)

The method of claim 1, wherein each of the plurality of L1 bitmap blocks maps include a transaction log.

### Claim 8 (depends on 1)

The method of claim 1, wherein the updating of the tablespace metadata is by a tablespace stack layer of a database management system for the database.

### Claim 9 (depends on 1)

The method of claim 1, wherein the plurality of L2 bitmap blocks include a local L2 bitmap block stored at the first instance, wherein the request comprises allocating a new extent in the tablespace, and wherein the updating of the tablespace metadata comprises:
checking, at the first instance, the local L2 bitmap block for a self-owned L1 bitmap block indicating contiguous free space for the new extent, wherein the self-owned L1 bitmap block is self-owned when the ownership affinity of the self-owned L1 bitmap block matches the first instance.

### Claim 10 (depends on 9)

The method of claim 9, wherein the updating of the tablespace metadata further comprises:
allocating the new extent in the self-owned L1 bitmap block in response to finding the self-owned L1 bitmap block;
updating additional free-space metadata in the local L2 bitmap block for the self-owned L1 bitmap block.

### Claim 11 (depends on 9)

The method of claim 9, wherein the updating of the tablespace metadata further comprises:
handshaking with a second instance of the plurality of database server instances to allocate the new extent in a remotely owned L1 bitmap block in response to not finding the self-owned L1 bitmap block, wherein the remotely owned L1 bitmap block is remotely owned when the ownership affinity of the remotely owned L1 bitmap block does not match the first instance;
updating additional free-space metadata in the remote L2 bitmap block for the remotely owned L1 bitmap block.

### Claim 12 (depends on 11)

The method of claim 11, wherein the updating of the tablespace metadata further comprises:
changing the ownership affinity of the remotely owned L1 bitmap block to the first instance in response to comparing an access history of the remotely owned L1 bitmap block to a heat threshold;
updating the local L2 bitmap block and the remote L2 bitmap block to reflect the changing.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
adding a new plurality of allocation units to the tablespace and corresponding new L1 bitmap blocks to the L1 bitmap block level in response to the L2 bitmap block level indicating available free space below a certain threshold.

### Claim 14 (depends on 1)

The method of claim 1, wherein the hierarchy further comprises:
a level 3 (L3) file level comprising filesystem metadata for the tablespace and instance metadata for the plurality of database server instances.

### Claim 15 (depends on 1)

The method of claim 1, wherein a database management system periodically consolidates free space in each of the L1 bitmap blocks.

### Claim 16

A non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, cause performing of:
storing tablespace metadata describing a tablespace of a database;
receiving, at a first instance of a plurality of database server instances for the database, a request to perform an operation on the tablespace;
updating the tablespace metadata according to the operation;
wherein the tablespace metadata is organized by a hierarchy comprising:
a level 1 (L1) bitmap block level comprising a plurality of L1 bitmap blocks mapping free space of a plurality of allocation units in the tablespace, wherein each of the plurality of L1 bitmap blocks indicates an ownership affinity with one of the plurality of database server instances, and wherein the L1 bitmap block level is stored as a single copy shared by the plurality of database server instances;
a level 2 (L2) bitmap block level comprising a plurality of L2 bitmap blocks mapping to the L1 bitmap block level, wherein each of the plurality of database server instances is assigned to store one of the plurality of L2 bitmap blocks.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the plurality of L2 bitmap blocks include a local L2 bitmap block stored at the first instance, wherein the request comprises allocating a new extent in the tablespace, and wherein the updating of the tablespace metadata comprises:
checking, at the first instance, the local L2 bitmap block for a self-owned L1 bitmap block indicating contiguous free space for the new extent, wherein the self-owned L1 bitmap block is self-owned when the ownership affinity of the self-owned L1 bitmap block matches the first instance;
handshaking with a second instance of the plurality of database server instances to allocate the new extent in a remotely owned L1 bitmap block in response to not finding the self-owned L1 bitmap block, wherein the remotely owned L1 bitmap block is remotely owned when the ownership affinity of the remotely owned L1 bitmap block does not match the first instance;
updating additional free-space metadata in the remote L2 bitmap block for the remotely owned L1 bitmap block.

### Claim 18

A database management system comprising one or more computing devices configured to:
store tablespace metadata describing a tablespace of a database;
receive, at a first instance of a plurality of database server instances for the database, a request to perform an operation on the tablespace;
update, by a tablespace stack layer, the tablespace metadata according to the operation;
wherein the tablespace metadata is organized by a hierarchy comprising:
a level 1 (L1) bitmap block level comprising a plurality of L1 bitmap blocks mapping free space of a plurality of allocation units in the tablespace, wherein each of the plurality of L1 bitmap blocks indicates an ownership affinity with one of the plurality of database server instances, and wherein the L1 bitmap block level is stored as a single copy shared by the plurality of database server instances;
a level 2 (L2) bitmap block level comprising a plurality of L2 bitmap blocks mapping to the L1 bitmap block level, wherein each of the plurality of database server instances is assigned to store one of the plurality of L2 bitmap blocks.

### Claim 19 (depends on 18)

The database management system of claim 18, wherein the plurality of L2 bitmap blocks include a local L2 bitmap block stored at the first instance, wherein the request comprises allocating a new extent in the tablespace, and wherein the tablespace stack layer is configured to update the tablespace metadata by:
checking, at the first instance, the local L2 bitmap block for a self-owned L1 bitmap block indicating contiguous free space for the new extent, wherein the self-owned L1 bitmap block is self-owned when the ownership affinity of the self-owned L1 bitmap block matches the first instance;
handshaking with a second instance of the plurality of database server instances to allocate the new extent in a remotely owned L1 bitmap block in response to not finding the self-owned L1 bitmap block, wherein the remotely owned L1 bitmap block is remotely owned when the ownership affinity of the remotely owned L1 bitmap block does not match the first instance;
updating additional free-space metadata in the remote L2 bitmap block for the remotely owned L1 bitmap block.

### Claim 20 (depends on 19)

The database management system of claim 19, wherein the tablespace stack layer is further configured to update the tablespace metadata by:
changing the ownership affinity of the remotely owned L1 bitmap block to the first instance in response to comparing an access history of the remotely owned L1 bitmap block to a heat threshold;
updating the local L2 bitmap block and the remote L2 bitmap block to reflect the changing.
