PURPOSE
=======
The purpose of this article is to provide an understanding of FREELISTS and FREELIST GROUPS. SCOPE & APPLICATION
===================
This article is intended to be used by DBAs to help understand how FREELISTS and FREELIST GROUP work. FREELISTS and FREELIST GROUPS =============================
The following bulletin is comprised of several parts: 1. Introduction to Oracle data block organization 2. Free List Overview 3. Free List Types 4. Considerations for Optimizing Space Management 5. Algorithms 6. FreeLists in Oracle
1. Introduction:
============= Before going into the details of freelist management one must know how the Oracle data blocks are organized. Every object in an Oracle database which occupies space is associated with a segment. A segment is a set of extents that contains all the data for a specific logical storage structure within a tablespace. There are 4 segment types: o permanent data segment (table, cluster) o index segment o rollback segment o temporary data segment Each segment is made up of smaller storage units called extents. An extent is a storage unit composed of contiguous blocks. Each segment is initially created in the database with at least one extent (controlled by parameter MINEXTENTS). Though empty, the space is reserved. When the initial space is full, a new extent is dynamically allocated. The new extent size is determined by the parameters NEXT and PCTINCREASE. The dynamic allocations stop when the number of extents reaches the value of parameter MAXEXTENTS. The first block of the first extent of each segment is reserved by Oracle to store system information and it is called the segment header. The Segment Header contains : o The Extents Table o The Free Lists descriptors o The High Water Mark (HWM) The HWM marks a limit in the segment where each block below is "in use", and each block above has never been used. The HWM always increases in size; It is reset to "zero" (position to the start of the segment) when a TRUNCATE is issued.
2. Free List Overview
================== Starting with V7.3, it is now possible to create a segment either with a limited number of extents or with an unlimited number of extents. To accommodate this, five new block types are introduced: 14 : Unlimited Rollback Segment Header 15 : Unlimited Deferred Rollback Segment Header 16 : Unlimited Data Segment Header 17 : Unlimited Data Segment Header with FL groups 18 : Extent Map Block For each data segment, Oracle keeps track of blocks having available free space for incoming INSERT or UPDATE. Free Space comes from 2 ways: 1. All blocks beyond the HWM that are allocated but not used. 2. All blocks below the HWM linked in a free list, and candidates to be reused. A Free List is constituted of : o Flag to indicate if the free list is used (1) or unused (0) o DBA of the block head of the Free List Chain, o DBA of the block tail of the Free List Chain. In each Data Block there is a flag to indicate if the block is linked in a Free List chain. If the flag is set the block will also point to the DBA of the next block in the free list chain. A zero value means that the current block is the last block in the chain.
3. Free List Types:
================
The Master Free List or Common Free space pool: =============================================== There is only one for each segment. It is implicitly allocated at segment creation time. For each data segment there is a pool, common for each process, of blocks containing free space available for incoming inserts called the Master free list. Every process has access to this common pool. So, the level of contention increases when several process simultaneously want to insert rows in the same segment. The blocks of initial extents allocated at segment creation time and of the new ones dynamically allocated are linked to the Master free list.
The Process Free Lists: ======================= To reduce contention problems on the Master Free list, another level of free lists is available which is called the Process free lists, Explicitly created when the FREELISTS parameter has been specified in a CREATE/ALTER command. Partitioning the Free Space in multiple free lists is used essentially to improve the performance of OLTP applications with a high degree of concurrent transactions performing inserts or updates requiring new space allocation. Parameter FREELISTS has been added in the STORAGE clause of a CREATE TABLE / CLUSTER or INDEX. Example: CREATE TABLE flg ( . . . .) . . . STORAGE ( ... FREELISTS 10 ...); The number of process freelists must be close to the maximum number of concurrent process performing simultaneously inserts in the segment. It is important to note that this improves the inserts performance, but wastes disk space usage. Each process is mapped to a Process free list by its Oracle PID (Process ID): Process free list entry = (P % NFL) + 1 where P : Oracle PID of the process (index in V$PROCESS), and NFL : Process free lists number as defined by parameter FREELISTS The
Transaction Free Lists: =========================== Implicitly allocated by Oracle as needed. A Transaction Free List is a free list dedicated to one transaction and only one. There are a minimum of 16 transactions free lists per segment, and this number increases as long as it is necessary, until it reaches the limit of the Segment Header block size. A transaction needs to allocate a Tx Free Lists entry when: o It releases space in a block (DELETE or UPDATE) o And if it has not already allocated one.
4. Considerations for Optimizing Space Management: =============================================== The two parameters PCTFREE and PCTUSED of the Storage Clause in a CREATE/ALTER statement, are used to control and optimize space management within a data segment block (table, cluster). PCTFREE specifies the percentage of a data block to be reserved (kept free) for possible updates to rows that already are contained in that block. After a block becomes full, as determined by PCTFREE, Oracle does not consider the block is for the insertion of new rows until the percentage of the block being used falls below the parameter PCTUSED. It is advised that the space calculated as (100% - (PCTFREE + PCTUSED)) be greater than the maximum size of a table row. 5. Algorithms: =========== A block is put on free list if the free space in the block is greater than the space reserved by PCTFREE. Blocks linked in a free list are available for future updates or inserts. A block is unlinked from a free list if the free space in the block is not enough to allow a new row insert, and if the percentage of the used space remains above PCTUSED. A block is relinked to a free list if after DELETE or UPDATE operations, the percentage of the used space falls below PCTUSED. Each time a block is added to a free list, it is linked at the head of the chain. Example: ~~~~~~~~ At time t0 , 2 blocks are on free list : data blocks 1 and 3: FL: B1 -> B3 At time t1, deletions are done on block B2 such as the block has to be relinked to Free list: FL: B2 -> B1 -> B3 A data block is put on Free list only if it is not already linked. Transaction Free List Algorithms: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The Tx free list allocation process starts by scanning all Tx free lists allocated in the segment Header block and checking if a Tx free list entry has not already been allocated to the transaction. Else, it looks for an unused entry or an empty Tx free list belonging to a "committed" transaction. If the search fails, a new entry in the Tx free lists area is allocated. When there is no chance to expand the Tx Free lists area, the unfortunate transaction has to wait for an entry release. The selected entry is determined by (PID % Tx free lists total number). PID is the Oracle process Id. The wait is done by requesting in S mode the TX enqueue held by the transaction T owning the Tx free list entry. The wait will end when T commits. The space freed in a block by a transaction T1 (DELETE or UPDATE) : o is immediately reusable by T1, o will be reusable for other transactions only after T1 commits and when looking for space in this block. Example: ~~~~~~~~ 5.1 Transaction T1 deletes some rows in table T. These operations release some space in block 10 in the segment. The percentage of the remaining used space falls below PCTUSED: block can be reused for incoming inserts, it is put on free list. To do this, Transaction T1 needs to allocate an entry in the Transaction free lists area in the Segment Header block, then links the block 10 in the corresponding free list. 5.2. Transaction T2 wants to insert a new row in table T. The space freed by T1, in block 10, cannot be reused. Assume that T2 does not have a Tx free list allocated in the segment (because T2 has not released space in the segment) 5.2.1 T2 starts walking on its Process Free List (PrFL) looking for a free block. (Let's assume that there are 3 blocks on the PrFL and they don't have enough free space T2 needs.) 5.2.2 The first block fails the check. The block must be exchanged (move to the next block on the list) with another one. This block has to be unlinked from the free list if the used space in the block goes beyond the space defined by PCTUSED or, if the "UNLINK counter" is below a particular threshold. (The default value is 5). The idea behind this is not to keep blocks that fail during free space search at the head of free lists. The UNLINK action is done only if the current block is head of the free list chain. 5.2.3 After all the blocks on the PrFL are checked and no block is found, the block selection in the process free list is stopped 5.2.4 Oracle tries to move blocks from Master free list to Process free list. This operation is called Free Lists Merge. The number of blocks to move is defined by a constant and it is 5. Search will continue from step 5.2.1 Note that at this point Oracle WILL NOT look at the other PrFL even though there might be empty blocks on those lists. This will cause some space to be wasted temporarily. 5.2.5 (Assume that there are no more blocks on the Master Free List) Oracle tries now to get blocks from the other Tx free lists (committed). The Tx free lists entries in the header block are scanned, looking for not empty and "committed" entries. For those entries, ALL the blocks are moved to the Master Free list. Then, only a part (5) of the blocks in Master free list are moved again to process free list. If there are blocks moved from the TxFl to the MsFL, go to step 2.1 5.2.6 (If 2.5 fails) Oracle tries to bump up the HWM. To reduce contention on segment header block, Oracle bumps up the HWM by m blocks at a time. The number m is: 1: if the block does not have to go on free list, 1: if we are on the initial extent (0) and the HWM is <= 4 (small table) min (5, unused blocks in the extent): before 7.2 min (5*(NFL+1), unused blocks in the extent): since 7.2. In the example, we assume HWM is at the end of the extent. 5.2.7 New extent allocation. The new blocks are moved to Master free list. Free block search continues from step 2.4 5.3 Transaction T1 wants now to insert a new row in table T. First, it looks for available space in blocks linked to its transaction free list. The block 10 has available space, and the free space in it is enough to the space required by the new row, block 10 is selected. The percentage of the used space in the block goes up above PCTUSED, the block has to be unlinked from the transaction free list. 6. Freelists Groups: ================= In multi-instances (Oracle Parallel Server), to reduce contention on the segment header block, which contains the free lists descriptors of the segment, it is possible to allocate other special blocks to store free lists descriptors. These groups are called the Free Lists Groups. FREELIST GROUPS is introduced in STORAGE clause of a CREATE TABLE / CLUSTER or INDEX. Example: ~~~~~~~~ CREATE TABLE flg ( . . . .) . . . STORAGE ( ... FREELIST GROUPS 2 FREELISTS 10 ...); Each free list group is associated with a special block called the Free List Block. These blocks will be allocated right after the segment header. So, if and object is created with 2 freelist groups, the first block of the first extent will be the segment header block and the second and third blocks will be the freelist blocks. These blocks store a Master free list (of the group), and as much process free lists as specified by parameter FREELISTS. The rest of the block dedicated to Transactions free lists. In the segment header block of an object with free list groups there is only one free list called The Super Master Free list or the Segment Master free list. The free list groups reduce contention on the segment header block, and reduce inter-instance "pinging", at the cost of excessive disk space consumption. The algorithm to map a Freelist Group, defined on a segment S, to a process P of an instance I, is the following: where: NFB : number of Freelist Groups defined on segment S, P : Oracle PID of the process (from V$PROCESS), I : INSTANCE_NUMBER parameter (if set in INIT.ORA) or parameter THREAD value MAXINST : maximum of instances sharing the same database (MAXINSTANCES parameter of CREATE DATABASE). In a non OPS environment or OPS and Single-Instance environment: Free list group is: (P % NFB) + 1 In a multi-instance environment (OPS): o If NFB <= MAXINST: Free list group is : ((I-1) % NFB) + 1 o If NFB > MAXINST : RANGE = NFB / MAXINST; INITIAL = (RANGE * (I-1)) + 1 REST = NFB - (RANGE * MAXINST) if (I-1) < REST Free list group is : INITIAL + (P % (RANGE+1)) if (I-1) >= REST Free list group is : INITIAL + REST + (P % RANGE) TRUNCATING A TABLE: ~~~~~~~~~~~~~~~~~~~ For the given table and all index associated to it, the TRUNCATE operation does the following tasks: 1. Get exclusive access to the segment header. If the segment header is locked process has to wait its release by requesting a TX lock in Shared mode. 2. Lock the segment header. 3. Flush all blocks belonging to this segment in the buffer cache to disk. 4. Clear all the free lists in the segment header block and in all free list groups blocks (if freelist groups are defined). The before image of all the changes are recorded in the Rollback segment. 5. Truncate the segment: the HWM returns to its initial position (extent 0 and block 0 if table or 1 if index). The before image of the change is recorded in the rollback segment. 6. Trim all the extents beyond MINEXTENTS. 7. If OPS, flush on disk the segment header block and free list groups blocks. NOTE: Performance vs. Space =========================== As can be seen from the algorithms above, using multiple free lists may cause some empty blocks to go unused, causing the segment to extend. If performance is critical, multiple free lists can be used to improve concurrent access, possibly at the expense of additional space used. However, if space is the primary consideration, then a single freelist should be used, leaving FREELISTS=1, without the performance benefits for concurrent transactions
