This whitepaper explains data storage within Adaptive Server Anywhere databases. Reading this whitepaper should help you to understand how the space within the database is used. Adaptive Server Anywhere is designed to store data efficiently, using a small amount of disk space and allowing database operations to be executed relatively quickly. However, there are some things that you can do to reduce the size of your database and to improve its performance. These include storing server files on different drives, choosing a proper page size, and using indexes appropriately. This whitepaper should give you some idea of the effects of these actions so that you can decide how they apply to your particular database.

Except where noted otherwise, this whitepaper refers to features of Adaptive Server Anywhere 8.0.0 and later.

Adaptive Server Anywhere uses four kinds of files when it is running a database. These are the database file, the transaction log, the transaction log mirror, and the temporary file.

Separate files onto different devices to improve performance. Dividing this information into different files has potential performance and recovery benefits for the database server. You can take advantage of these benefits by placing each of these files on a different physical device.

Placing the files on different physical devices improves performance by eliminating the need for disk head movement between the files. Separating the transaction log, the transaction log mirror, and the database file onto different devices has the further benefit of ensuring that media failure will affect only one of these files, allowing for full data recovery. Placing the files on different physical drives also helps prevent file fragmentation.

The information in the database file, the transaction log, and the temporary file is stored on fixed-size areas of disk called pages. The default page size is 2 kb, but pages can also be 1, 4, 8, 16, or 32 kb. All of the pages in the database must be the same size, and this size must be chosen when the database is created.

There are many types of pages used in the database file. These include table pages, index pages, and other pages used to increase performance or to aid in data recovery.

Information in database tables is stored on table pages. Each table has one or more pages assigned to it, and each page is made up of three parts: a header, data rows, and a row offset table. Each table page can storedata from at most one table and at most 255 rows.

• The header stores the object ID of the table that is using that page. It also holds pointers that link the current page to the next and the previous pages for that object.
• The body of the page contains data rows for the object. These data rows contain the actual column data from the table and are stored contiguously on a page.
• The row offset table stores pointers to the starting location for each data row on the page.

Adaptive Server Anywhere creates a bitmap for sufficiently large tables within databases that have at least a 2K page size. Each table’s bitmap reflects the position of each table page in the entire dbspace file. For databases of 2K, 4K, or 8K pages, the server utilizes the bitmap to read large blocks (64K) of table pages instead of single pages at a time, reducing the total number of I/O operations to disk and hence improving performance. Users cannot control the server’s criteria for bitmap creation or usage.

Note that bitmaps, also called page maps, are only available for databases created in version 8.0 and higher. If a database is upgraded from an older version, the database server will not create a bitmap for database tables. Bitmaps are not created for work tables or system tables.

Every new row that is smaller than the page size of the database file is always stored on a single page. If no present page has enough free space for the new row, Adaptive Server Anywhere writes the row to a new page. For example, if the new row requires 600 bytes of space, but only 500 bytes are available on a partially filled page, then Adaptive Server Anywhere places the row on a new page.

To make table pages more contiguous on the disk, Adaptive Server Anywhere allocates table pages as follows:

• For 2 KB pages, table pages are allocated in blocks of 32.
• For 4 KB pages, table pages are allocated in blocks of 16.
• For 8 KB pages and above, table pages are allocated in blocks of 8.

For example in a database with 8 KB pages, when it needs to allocate a page, it allocates eight pages, inserts the page in the block, and then fills up the block with the next seven pages. In addition, it uses a free page bitmap to find contiguous blocks of pages within the dbspace, and performs sequential scans by reading groups of 64 KB, using the bitmap to find relevant pages. This leads to more efficient sequential scans.

Character and binary data types that are larger than 255 characters are called binary large objects, or blobs. These objects are not stored in the table page in their entirety; instead, the page stores the first 255 characters of the object and a pointer to a page where the rest of the object is stored.

Storing blobs separately is more efficient The pages that store the remaining characters of these objects are maintained separately from the table pages. Because blobs take up a lot of space on a page, including them in the table with the rest of the columns would greatly increase the time required to scan the table sequentially. If you were searching sequentially for some data in the table, you would have to scan the blob data even if it was irrelevant to the information you were looking for. Since blob data is stored separately, it does not have to be scanned along with the rest of the table data. There are fewer pages to read, resulting in a more efficient scan.

Index entries are stored on index pages, which are similar to the table pages described above. The main difference between the two types of pages is that the object being stored is a set of index entries rather than a set of data rows. In general, index entries are much smaller than data rows, so index pages usually contain many more entries per page than table pages. Like table pages, each index page can only include information for one index.

Indexes can form a large or a small percentage of the database, depending on the number of indexes created. Since primary and foreign keys are always indexed automatically, most databases contain indexes.

Each connection to the database server has a rollback log. The rollback log is a record of all of the changes that have been made to the database by a connection since the last COMMIT or ROLLBACK statement. This record allows uncommitted changes to be cancelled if a ROLLBACK is issued or in the case of system failure.

The rollback log consists of a linked list of pages that is stored in the database file. Each page contains a list of changes to the database, much like the transaction log. However, unlike the transaction log, which is involved in replication, the rollback log is only available internally to the database server.

Once a transaction has been committed or rolled back, the rollback log is erased and any resulting free pages are available for reuse within the database.

At any given time, the information in the database fileon disk is not guaranteed to be current or consistent with the transaction log. This is because pages are read into the cache and altered but are not immediately written to disk. Dirty pages, or pages that have been changed in the cache, are written to disk only when the cache becomes full or when a checkpoint is issued.

A checkpoint is a point at which all of the dirty pages in the cache are written to disk. After a checkpoint, the database file is up to date and accurately reflects the information in the transaction log. Frequent checkpoints reduce the time needed for data recovery, but this benefit should be balanced with the fact that executing checkpoints takes time. Adaptive Server Anywhere tries to execute checkpoints when there is not a lot of other activity taking place, according to a heuristic based on how long it has been since the last checkpoint and how long recovery would take in the event of a system failure. You can adjust the time between checkpoints using the CHECKPOINT_TIME option, which sets the maximum desired time between checkpoints, in minutes, and the RECOVERY_TIME option, which sets the maximum desired time for recovery in the event of system failure, in minutes.

The database server always executes a checkpoint during database shutdown, so that when the server is restarted, the state of the database file is known, up-to-date, and does not require recovery.

The checkpoint log If a system failure caused the database server to shut down without first executing a checkpoint, the databasefile may not be in a consistent state. That is, some changes that have been made since the last checkpoint may have been written to the database file, while others would not have been written and so would be lost. The database server maintains copies of all of the pages that have been modified since the last checkpoint, and uses these pages to recover from an improper shutdown. These copied pages are called rollback pages, and together they form the checkpoint log.

The checkpoint log is referenced through the free list, a linked list of pages similar to index pages that point to free pages within the database. When the database server requires a new page, it allocates a page from the free list. When a page is allocated as a rollback page, it is marked using a rollback bit to signify that it is part of the checkpoint log.

When the database is started, the checkpoint log is checked to see if it contains any rollback pages. If it does, the database server takes steps to recover from the system failure. It first restores the database file to its state at the last checkpoint by copying all the rollback pages over their corresponding pages in the database file. It then applies changes made since the last checkpoint by reapplying the operations in the transaction log. Finally, it rolls back any uncommitted changes, using the rollback logs. The entire checkpoint log, including all empty checkpoint log pages, is deleted at the end of each session.

As of Adaptive Server Anywhere 8, the checkpoint log is stored in consecutive pages at the end of the database file. This leads to improved performance by allowing sequential scans and multipage writes of the material in the checkpoint log. To gain the benefits of this enhancement on databases created before this release, you must upgrade the database file format by unloading and reloading the database.

Data within the transaction log, transaction log mirror, and temporary files is also stored in pages. These pages are the same size as the pages in the database file.

The transaction log and the transaction log mirror consist essentially of linked lists of pages that store all of the changes that have been made to the database. Each entry in the transaction log holds all of the information necessary to execute the SQL statement for one particularrow change. For example, the entry for a DELETE statement would contain information to accurately identify the row that was deleted.

Because the transaction log is used during recovery and during replication, it cannot use row IDs to refer to rows that have been modified. Instead, entries in the transaction log must always refer to a row either by primary key value, or, if there is no primary key, by copying the contents of the entire row.

Using a transaction log improves performance Although it may seem that using a transaction log would slow the performance of the database server, in fact the opposite is true. Without a transaction log, Adaptive Server Anywhere must perform a checkpoint at the end of each transaction. Checkpoints are time-consuming as they can involve writing a lot of pages to disk. Using a transaction log involves taking note of every operation, but it requires writing fewer pages to disk. Thus, using a transaction log actually improves performance.

Every update operation is written in the transaction log; however, in order to minimize I/O operations, the transaction log is only written to disk when a COMMIT statement occurs. Therefore, if a transaction log is used, the most recent transaction log pages are written to disk at each COMMIT statement. In contrast, if a transaction log is not used, a COMMIT statement forces a checkpoint. In this case, every page that has been changed in any way since the last COMMIT statement must be written to disk.

The size of the transaction log does not affect performance, because all changes are written to the end of the file, so the transaction log does not usually have to be scanned.

However, you may wish to limit the size of the transaction log in order to conserve disk space. Renaming the transaction log when a backup is performed keeps the transaction log small. You can also manage the growth of the transaction log file by ensuring that all tables have a primary key or a unique index that does not allow NULL. These columns allow the transaction log to identify a row by giving only one value. Without a primary key or a unique, non-NULL index, the transaction log must store a copy of the entire row in order to identify a row uniquely. Copying this extra information can also affect the performance of the database server.

The temporary file contains tables and indexes created by Adaptive Server Anywhere when needed for query processing. These objects are stored on pages identical in structure to the data and index pages within the database file. The temporary file is also used to store prepared statements, cursors, stored procedure definitions, view definitions, the lock table, and user-generated temporary tables.

Adaptive Server Anywhere uses temporary tables to perform operations such as sorts or complex unions that cannot be performed in a single step. For example, if you use a SELECT statement and ORDER BY a column that is not indexed, Adaptive Server Anywhere uses a temporary table to sort the result by the specified column.

Because the temporary file is used in order to solve certain queries, Adaptive Server Anywhere generally uses the temporary file intensively over short periods of time. For example, Adaptive Server Anywhere might use the temporary file to create a temporary table and execute a number of queries using that table, and then not use the temporary file again until the next temporary table is required.

Often, operations that require the use of the temporary file also require the retrieval of large amounts of data from the database file. In order to allow operations to take place in the database file and the temporary file simultaneously, you should place the temporary file on a fast device that is separate from the drive that holds the database file. You can do this by specifying an environment variable. Adaptive Server Anywhere places the temporary file in the location specified by ASTMP; if this variable is not defined, Adaptive Server Anywhere looks next at the variables TMP, TMPDIR, and TEMP, in that order.

The page size for a database can be 1, 2, 4, 8, 16, or 32 kb. The choice of page size can greatly affect the performance of the database and the size of the database file.

When choosing a page size, you should consider the following factors:

• Database server cache size
• Table and row size
• Index fan-out

The advantages and disadvantages of different page sizes depend heavily on the way that you access the data, because of the importance of keeping useful data within the cache.

The cache The cache is an area of memory that holds pages that are currently being read and stores pages that are used frequently. Before information that is stored on disk can be accessed, it must first be read from disk into the cache. Because pages that are already in the cache can be scanned much faster than those that must be retrieved from disk, you should try to maximize the amount of useful information that can be stored in the cache.

Cache page size Like the files used by the database server, the cache is divided into pages. Information is moved between the cache and the disk one page at a time. Cache pages do not have to be the same size as database pages, but they cannot be smaller than the database pages of any database that will be run by the server. Each cache page can hold only one database page, so cache pages should not be made any larger than necessary.

Sequential scans favor large pages It takes approximately the same amount of time to read a page into the cache regardless of the page size. For example, it takes much less time to read one 4 kb page into the cache than it takes to read four 1 kb pages into the cache. Therefore, if you frequently execute commands that require scanning an entire table, it is more efficient to use a large page size, such as 4 kb, which allows you to bring much more of the table into the cache more quickly.

Large page sizes also provide benefits when writing information to the transaction log and the temporary file. For example, a 4 kb transaction log page can hold more entries than a 1 kb page, and therefore transaction log pages have to be written to disk less often when using larger pages.

Smaller pages may improve performance with a small cache On the other hand, if your typical database commands are more likely to require reading small pieces of data from random locations, using large pages could result in wasted space in the cache. For example, if you use 4 kb pages, you always have to read 4 kb into the cache at a time, even if 1 kb would be adequate.

When a page is read into the cache, another page must usually be written to disk and discarded from the cache in order to make room for the new page. Therefore, if you need to access one row from a random location in your database, and you have 4 kb page sizes, you must discard 4 kb of possibly useful information from the cache in order to access that one row. Using smaller pages allows you to bring small pieces of many different tables into the cache at a time.

You may also want to use smaller database pages if you are running Adaptive Server Anywhere on a machine with limited resources. Small database pages allow a greater number of pages to fit into a smaller cache.

Each table requires at least one table page. Even empty tables have one table page assigned to them. Therefore, if your database consists mostly of tables that can fit on one page, you may want to choose a smaller page size, since larger pages could contain a lot of empty space. However, for a typical database, this is not a concern, because the majority of the database consists of large tables.

Inserted rows that do not fit on an existing page are added to a new page. Therefore, if you are using very large rows, you should be careful not to use a page size that is just under twice the average row size. In this case, almost half of each page is wasted, and you would probably benefit from a different page size.

On the other hand, if your rows are relatively small, you should be careful not to use a page size that is too large. This is because a maximum of 255 rows can be stored on each page, so if the page is too large, the rows do not fill the pages completely. For example, in order for a 32 kb page to be fully used, the average row size would have to be about 125 bytes.

Index fan-out refers to the average number of index entries that can fit on an index page. Clearly, page size can significantly affect index fan-out. This can have a large effect on the performance of queries that use indexes. For more information, please see "Improving index performance" in the section "Improving database performance" in this paper.

The number of rows that fit on a page depends upon the data types stored in those rows. Different data types have different storage requirements.

An index can contain one, two, or more columns. An index on two or more columns is called a composite index. For example, the following statement creates a two-column composite index:

CREATE INDEX name
ON employee (emp_lname, emp_fname)

A composite index is useful if the first column alone does not provide high selectivity. For example, a composite index on emp_lname and emp_fname is
useful when many employees have the same last name. A composite index on emp_id and emp_lname would not be useful because each employee has a
unique ID, so the column emp_lname does not provide any additional selectivity.

Additional columns in an index can allow you to narrow down your search, but having a two-column index is not the same as having two separate indexes. A
composite index is structured like a telephone book, which first sorts people by their last names, and then all the people with the same last name by their first
names. A telephone book is useful if you know the last name, and even more useful if you know both the first name and the last name, but worthless if you only know the first name and not the last name.

When you create composite indexes, you should think carefully about the order of the columns. Composite indexes are useful for doing searches on all the columns in the index or on the first columns only; they are not useful for doing searches on any of the latter columns alone.

Primary keys that have more than one column are always automatically indexed as composite indexes with their columns in the order that they appear in the table definition, not in the order that they are specified in the primary key definition.

The compressed B-tree index type, introduced in Adaptive Server Anywhere 8, substantially improves performance for composite indexes.

Although standard indexes can dramatically improve the performance of statements that search for a specific row or a specific subset of the rows, two rows
appearing sequentially in the index do not necessarily appear on the same page in the database.

However, you can further improve the performance of indexes by creating clustered indexes. Clustered indexes in Adaptive Server Anywhere store the
table rows in approximately the same order as they appear in the corresponding index. Clustered indexes are available in Adaptive Server Anywhere 8.0.2 and
later.

Using the clustered index feature increases the chance that the two rows will appear on the same page in the database. This can lead to performance benefits
by further reducing the number of times each page needs to be read into memory.

For example, in a case where you select two rows that appear sequentially in a clustered index, it is possible that you are retrieving two rows that appear
sequentially on the same page, thus reducing the number of pages to read into memory by half.

The clustering of indexes in Adaptive Server Anywhere is approximate. While the server attempts to preserve the key order, total clustering is not guaranteed. As well, the clustering degrades over time as more and more rows are inserted into your database.

You can implement clustered indexes using the following statements:

• CREATE TABLE
• ALTER TABLE
• CREATE INDEX
• DECLARE LOCAL TEMPORARY TABLE

Several statements work in conjunction with each other to allow you to maintain and restore the clustering effect:

• The UNLOAD TABLE statement allows you to unload a table in the order of the index key.
• The LOAD TABLE statement inserts rows into the table in the order of the index key.
• The INSERT statement attempts to put new rows on the same table page as the one containing adjacent rows as per the primary key order.
• The REORGANIZE table statement can restore the clustering by rearranging the rows according to the clustering index. On tables where clustering is not specified, tables are ordered using the primary key.

The Optimizer assumes that the table rows are stored in key order and costs index scans accordingly.

Adaptive Server Anywhere supports two types of indexes, and automatically chooses between them depending on the declared width of the indexed columns.
For a total column width that is less than 10 bytes, Adaptive Server Anywhere uses a B-tree index that contains an order-preserving encoding, or hash value,
that represents the indexed data. Hash B-tree indexes are also used when the index key length is longer than one-eighth of the page size for the database or 256 bytes (whichever is lower). For data values whose combined declared length is between these two bounds, Adaptive Server Anywhere uses a compressed B-tree index that stores each key in a compressed form.

Hash B-tree indexes

A hash B-tree index does not store the actual row value(s) from the table. Instead, a hash B-tree index stores an order-preserving encoding of the original data. The number of bytes in each index entry used to store this hash value is termed the hash size, and is automatically chosen by the server based on the declared width of all the indexed columns. The server compares these hashed values as it searches through an index to find a particular row.

When you index a small storage type, such as an integer, the hash value that Adaptive Server Anywhere creates takes approximately the same amount of
space as the original value. For example, the hash value for an integer is 5 bytes in size. If the total hash size is small enough, Adaptive Server Anywhere can tell whether two values are equal, or which one is greater by comparing their hash values. However, it can retrieve the actual value only by reading the row from the corresponding table.

When you index a column containing larger data types, the hash value will often be shorter than the size of the type. For example, if you index a column of string values, the hash value used is at most 9 bytes in length. Consequently, Adaptive Server Anywhere cannot always compare two strings using only the hash values. If the hash values are equal, Adaptive Server Anywhere must retrieve and compare the two actual values from their corresponding rows in the table.

For example, suppose you index the titles of movies, many of which are similar. If you wish to search for a particular title, the index may identify only a set of possible rows. In this case, Adaptive Server Anywhere must retrieve each of the candidate rows and examine the full title.

Compressed B-tree indexes

Compressed B-tree indexes store a compressed form of each indexed value in the index’s internal nodes. To do this, compressed B-tree indexes store the values using Patricia tries, an optimized form of a trie data structure that is augmented with a skip-count to compress its representation. As a result, compressed B-tree indexes offer substantial improvements over hash indexes when the overall data length is reasonably large. More significantly, the compaction algorithm efficiently handles index values that are identical (or nearly so), so that common sub strings within the indexed values have negligible impact on storage requirements and performance. Compressed B-tree indexes are chosen automatically if the sum of the declared width of the indexed columns is between 10 bytes and one-eighth of the database page size, to a maximum of 256 bytes.

Increasing the cache size can dramatically improve database performance. Adaptive Server Anywhere 7.0 uses dynamic cache sizing, which grows the cache if it needs more memory and if it can do so without affecting other applications on the system. This prevents database performance from being hindered because of inadequate cache allocation. However, the cache size is limited by the physical memory. You may even want to consider buying more RAM to allow for a bigger cache.

Disk striping can significantly improve the performance of the database because of improved I/O performance. However, because of the nature of disk striping, the failure of one disk can lead to the corruption of all of the database files. Therefore, the reliability of your database is compromised unless you have RAID above level 0. For this reason, you should be sure to implement a good backup plan along with disk striping.