Ingres Database Reference
The format in which data is stored and organized in CA-Ingres databases has an impact on the performance of CA-Ingres systems. These systems need to be efficient in their data retrieval and allow concurrent access to the database. This document addresses issues to be considered in selecting appropriate storage structures to deliver the required retrieval efficiency and concurrency. It is intended for anyone involved in the design, development, support, or administration of a system using CA-Ingres version 6.4.
CA-Ingres databases require a variety of storage structures for tables to provide adequate performance and concurrency. Using and allocating the appropriate structures also allows you to enforce any necessary uniqueness constraints on your data.
The tables in CA-Ingres database are files. These files are organized into pages. Pages are split into three types: index pages, leaf pages, and data pages. Index pages are used in ISAM and BTREE tables. They contain information to allow more direct access to a page. Leaf pages are used in BTREE tables. They contain key values and associated row addresses to allow direct access to data. Data pages are where the rows of data are stored in the table.
When you insert a row of data into a table, its placement is dependent upon the storage structure and the key value if the structure uses a key. Since heap tables do not have a key, the row is allocated to the single data page of the table. For an ISAM, BTREE, or Hash table, the row is directed to a data page determined by the key value. These pages are considered main data pages. Main data pages are those allocated to the table at the time of table creation or modification.
When you insert a new record into a Heap, ISAM, or Hash table and the target page is full, then an overflow page is created, linked to the target page, and the new tuple is placed there. A new overflow page is created each time the current page cannot fit the row to be entered. Overflow pages are linked to each other progressively. A set of linked overflow pages and the leading main page is known as an overflow chain. BTREE tables are dynamic and subject to overflow pages only in extreme circumstances. Complete details of each structure are covered later in this document.
When choosing a storage structure the following two basic questions should be addressed. What is the anticipated insert load on the table? What is the anticipated retrieval load? A table with an anticipated heavy insert load requires a storage structure where insertion of new data is simple and efficient, possibly sacrificing the performance of retrieval against the table. On the other hand, a static table with heavy retrieval for select, update, or delete purposes requires a storage structure which can quickly access specific information from the table.
These two scenarios are quite simple. However, making these decisions can become complex. Often tables have both heavy insertion and retrieval requirements. You may also find it necassary to alter the choice of storage structures as your systems reach different stages of maturity. A new system may have a reasonably high level of input. As it ages the insertion rate may decrease, while the rate of retrieval of data from the database increases.
The word heap accurately describes how data is stored in a table. A single data page is allocated as the main page to the table. All other pages are overflow. Data is inserted into a heap table by adding the record to the end of the heap on the last data page. If there is no room on the last page, a new data page is created. If rows are deleted, the space they occupied is never reused unless they resided on the last page.
An insert into a heap table requires an exclusive page level lock on the page where the data is being inserted (the last page). Updates and deletes take either shared or exclusive table level locks as appropriate.
Tables of only a few (less than three) pages being used for read-only purposes are also ideally suited for heap. For a small table with unique rows, it is more efficient to read a few pages than to access the data through an index. Selects, updates, and deletes involve a scan of the entire table, thereby making heap storage relatively slow for more than a few pages.
Heap storage is ideally suited for single-threaded insert activity. There may be locking issues in a concurrent environment with heavy insert activity on a heap table if many users request exclusive access to a single point of insertion.
When a table is modified to hash, the number of main pages is computed and set. These main pages are often referred to as hash buckets. The buckets have a single main page; once the main page is full extra pages are generated as overflow. In fact, a hash table may be considered as an array of virtual heap tables.
When inserting a new row, the key value is passed to an algorithm. This algorithm operates on the key value and calculates the appropriate hash bucket in which the row is to be placed. The aim of this process is to randomly distribute the data among the hash buckets. Distributing data in this manner is intended to reduce contention among multiple users.
Hash structures allow the fastest access for an exact key retrieval as there are no index pages to be navigated. Any range or partial key search scans the entire table. The reason for this is that an exact value for the entire key must be provided to take advantage of the hashing algorithm.
Overflow pages for a hash table are expensive and performance can be degraded. The number of main data pages is fixed when the table is created or modified. The hash structure is well suited for static table or tables which are growing slowly, provided that the access path used for the table is by an exact value for the key. This point applies to any table being considered for hashing. It does not preclude the hash structure from being used for a dynamic table. In these situations table space can be pre-allocated for growth by modifying the table using a high value for minpages or a low value for the fillfactor. This allows more room in the main pages for additional tuples before overflow pages are required. You should monitor a dynamic table stored as hash on a regular basis for overflow pages.
An ISAM table is built by sorting the data in key order, placing the sorted data into data pages, and constructing an index used to reference the data pages. Data ordered by the key allows for efficient range and partial key searches. The number of main data pages and the index page are fixed when the table is modified. Changes to the distribution of key values are not reflected in the table's index. An ISAM table should never have a monotonically increasing key since all new values are allocated to the same main data page.
For an insert the main page and any linked overflow pages are checked to see if the row will fit. The row will be placed in the first available slot down the overflow chain. If there is no space available in the overflow chain then the data will be inserted on a new overflow page. The tuples are held on data pages, the index pages are navigated to direct queries and inserts to the appropriate data page. Each index entry has one associated main page.
The ISAM structure is ideally suited to static or slowly growing tables with a static range of key values where range or partial key searches are required. Since the number of main pages in an ISAM table is fixed, for growing tables, the growth capacity should be allocated and monitored regularly for overflow. The capacity to grow is achieved by using a low value for fillfactor when modifying the table. This results in fewer tuples on each data page after the modification. It is important to note that this strategy should only be applied when the new key values will be within the minimum and maximum key values on the index.
The BTREE structure is similar to the ISAM structure except that it is dynamic and capable of growth the both in the index and the data. BTREE tables do not have any overflow data pages. BTREE is the most flexible of the four storage structures. As the distribution of data for key columns changes, the index changes accordingly.
A BTREE table has an index similar in construction to the index of an ISAM table. A BTREE index has the added feature of being dynamic. There are three page types. The pages used for the index are called index pages. The index references leaf pages rather than data pages. Leaf pages make up the leaf index. This index has a record containing the key value and the address for each tuple in the table. This address is used to reference the tuple on its data page.
Each leaf page may reference a number of data pages. One of these data pages is known as the associated data page. The associated data page is the data page where the next new tuple for the leaf page will be placed. If the associated data page is full, a new page is allocated, which then becomes the new associated data page. The new tuple is placed there.
The key details for a new tuple may not fit in either the index page or the leaf page. If this is the case, the index or leaf index changes to accommodate the new tuple. If the key value is a duplicate of an existing key value there is no change in the index page; however, an extra record is generated in the leaf page. If there are so many duplicates for a single key value that the leaf records do not fit on a single page, then an overflow page is created. This is the only scenario in which duplicates may appear on a BTREE table.
Because BTREE tables have the scope to grow and change, it is often claimed they require little or no maintenance. This is not the case, however. BTREE tables may require less maintenance since they are unlikely to have overflow pages, but there are a number of issues which must be addressed for a BTREE table in deciding how much maintenance is required. Space is only reused on associated data pages and the leaf pages; it is not reused on the index pages. Heavy delete and insert activity might use space efficiently on the data and leaf pages, but you must be aware of what is happening with the index and how much it may be growing. The distribution of new data across the key column is also relevant since you should remain aware of the balance of your BTREE index.
BTREE tables are well suited for tables which are growing in size. They have all the search capabilities of the ISAM structure in that data is ordered and partial key and range searches can use the index. Data is guaranteed to be returned in key sorted order, removing the need for any explicit sorting. BTREE is ideal for tables where rows are being added to the table and are distributed evenly across the range of existing key values. A BTREE table with a sequential key in a highly concurrent environment with heavy insertion may give performance problems. This is due to the need to continually split the last index page and the concurrent access required to the associated data page.
Secondary indices are used to provide a table with alternative access paths. They are implemented in the database as tables. A secondary index contains columns reflected from the base table as well as an extra column named tidp. This column contains the address of the corresponding tuple on the base table. It is used to direct queries from the secondary index back to the corresponding row in the main table. Since a secondary index is implemented as another table, extra disk space is required. This is part of the overhead involved in using secondary indices.
A major part of index overhead involves internal maintenance to ensure that data in the index corresponds to data in the base table. An insert into the main table also requires an insert into each associated secondary index. Since secondary indices are linked to the main table through the tuple ID, any row relocation also requires an update of the tidp in the secondary indices. Any update of a secondary index column requires an update of the base table and the secondary index. The update of the secondary index is likely to require the tuple to be relocated.
There is also an overhead cost in accessing data by a secondary index. Disk access is required to both the base table and the secondary index. This can be particularly costly in range retrievals or pattern matching. Even though tuples on the index may be on the same page, it could mean accessing several pages on the base table.
Secondary indices are an ideal solution where a table is static and there are multiple access paths required to the data. You should perform an analysis of the benefits and costs of maintaining secondary indices. Is the cost of extra disk I/O worthwhile in supporting a secondary index which is used only by an infrequently run query? This is an example of the type of issue to be addressed when deciding on the creation of secondary indices.
In general, the storage key of the table is the primary key of the entity in the logical data model. Secondary indices are then used for foreign keys by which the table is accessed. This is not a requirement; the ultimate decision on primary and secondary keys should be related to performance.
Secondary indices are useful for access paths where data in the column is unevenly distributed, provided that statistics are kept on the column. With the statistics on the column the optimizer can make better decisions. It decides whether to use the secondary index or to scan the entire table based on the expected number of rows to be returned.
Data can also be stored redundantly in a secondary index. Here is an example of the create index statement which would store a column redundantly:
CREATE INDEX index_name ON table_name (index_key1, index_key2, red_col) WITH KEY = (index_key1, index_key2);
This secondary index will be a table with key columns index_key1, index_key2, and tidp. The extra column red_col is stored in the index as well as the base table. This reduces the amount of disk I/O required to retrieve data when there is no requirement to get data from the main table.
Once storage structures have been selected and implemented, you should implement a rigorous table hygiene process to ensure tables remain clean and access to tables meets performance and concurrency requirements. The distribution of data and access patterns to a table should also be monitored and evaluated on a periodic basis to check on whether or not the storage structure and/or secondary indices should be altered. Changes in data distribution on a table are also a signal that new statistics should be generated using optimizedb.
The choice of appropriate storage structures for tables on CA-Ingres databases is a critical factor in delivering adequate performance and concurrent access to data. It is, however, a single factor. System performance is also dependent on system configuration, database design, transaction semantics, querying techniques, and so on. In planning a system to deliver the expected performance and concurrency each of these areas should be addressed, keeping in mind that they are interdependent tasks.
Ingres Database Reference
To William's Home Page
© William Yuan 2000
Email William