Data_management5.pdf

5.1 STORAGE MEDIA Databases and file systems use a uniform size, called a block, when transferring data between main memory and storage media. Block size is independent of storage media. Storage media are managed by controllers, which convert between blocks and sectors or pages. This conversion is i...

5.1 STORAGE MEDIA Databases and file systems use a uniform size, called a block, when transferring data between main memory and storage media. Block size is independent of storage media. Storage media are managed by controllers, which convert between blocks and sectors or pages. This conversion is internal to the storage device, so the database is unaware of page and sector sizes. Row-oriented storage Most relational databases are optimized for transactional applications, which often read and write individual rows. To minimize block transfers, relational databases usually store an entire row within one block, which is called row-oriented storage. Row-oriented storage performs best when row size is small relative to block size, for two reasons: Improved query performance. When row size is small relative to block size, each block contains many rows. Queries that read and write multiple rows transfer fewer blocks, resulting in better performance. ● Less wasted storage. Row-oriented storage wastes a few bytes per block, since rows do not usually fit evenly into the available space. The wasted space is less than the row size. If row size is small relative to block size, this wasted space is insignificant. Column-oriented storage Some newer relational databases are optimized for analytic applications rather than transactional applications. Analytic applications often read just a few columns from many rows. In this case, column-oriented storage is optimal. In column-oriented storage, also called columnar storage, each block stores values for a single column only. ● Column-oriented storage benefits analytic applications in several ways: Faster data access. More column values are transferred per block, reducing time to access storage media. ● Better data compression. Databases often apply data compression algorithms when storing data. Data compression is usually more effective when all values have the same data type. As a result, more values are stored per block, which reduces storage and access time. With column-oriented storage, reading or writing an entire row requires accessing multiple blocks. Consequently, column-oriented storage is a poor design for most transactional applications. ● 5.2 TABLE STRUCTURES Heap table Row-oriented storage performs better than column-oriented storage for most transactional databases. Consequently, relational databases commonly use row-oriented storage. A table structure is a scheme for organizing rows in blocks on storage media. Databases commonly support four alternative table structures: ● Heap table ● Sorted table ● Hash table ● Table cluster Each table in a database can have a different structure. Databases assign a default structure to all tables. Database administrators can override the default structure to optimize performance for specific queries. In a heap table, no order is imposed on rows. The database maintains a list of blocks assigned to the table, along with the address of the first available space for inserts. If all blocks are full, the database allocates a new block and inserts rows in the new block. Heap tables optimize insert operations. Heap tables are particularly fast for bulk load of many rows, since rows are stored in load order. Heap tables are not optimal for queries that read rows in a specific order, such as a range of primary key values, since rows are scattered randomly across storage media. Sorted table In a sorted table, the database designer identifies a sort column that determines physical row order. The sort column is usually the primary key but can be a non-key column or group of columns. Rows are assigned to blocks according to the value of the sort column. Each block contains all rows with values in a given range. Within each block, rows are located in order of sort column values. Sorted tables are optimal for queries that read data in order of the sort column, such as: ● JOIN on the sort column ● SELECT with range of sort column values in the WHERE clause ● SELECT with ORDER BY the sort column In summary, sorted tables are optimized for read queries at the expense of insert and update operations. Since reads are more frequent than updates and inserts in many databases, sorted tables are often used, usually with the primary key as the sort column. Hash table In a hash table, rows are assigned to buckets. A bucket is a block or group of blocks containing rows. Initially, each bucket has one block. As a table grows, some buckets eventually fill up with rows, and the database allocates additional blocks. New blocks are linked to the initial block, and the bucket becomes a chain of linked blocks. The bucket containing each row is determined by a hash function and a hash key. The hash key is a column or group of columns, usually the primary key. The hash function computes the bucket containing the row from the hash key. Hash functions are designed to scramble row locations and evenly distribute rows across blocks. The modulo function is a simple hash function with four steps: 1. Convert the hash key by interpreting the key's bits as an integer value. 2. Divide the integer by the number of buckets. 3. Interpret the division remainder as the bucket number. 4. Convert the bucket number to the physical address of the block containing the row. A dynamic hash function automatically allocates more blocks to the table, creates additional buckets, and distributes rows across all buckets. With more buckets, fewer rows are assigned to each bucket and, on average, buckets contain fewer linked blocks. Table clusters Table clusters, also called multi-tables, interleave rows of two or more tables in the same storage area. Table clusters have a cluster key, a column that is available in all interleaved tables. The cluster key determines the order in which rows are interleaved. Rows with the same cluster key value are stored together. Usually the cluster key is the primary key of one table and the corresponding foreign key of another, Table clusters are not optimal for many queries and therefore are not commonly used. 5.3 SINGLE LEVEL INDEXES A single-level index is a file containing column values, along with pointers to rows containing the column value. The pointer identifies the block containing the row. In some indexes, the pointer also identifies the exact location of the row within the block. Indexes are created by database designers with the CREATE INDEX command, described elsewhere in this material. An index is usually defined on a single column, but an index can be defined on multiple columns. In a multi-column index, each index entry is a composite of values from all indexed columns. In all other respects, multi-column indexes behave exactly like indexes on a single column. Query processing To execute a SELECT query, the database can perform a table scan or an index scan: A table scan is a database operation that reads table blocks directly, without accessing an index. ● An index scan is a database operation that reads index blocks sequentially, in order to locate the needed table blocks. Hit ratio, also called filter factor or selectivity, is the percentage of table rows selected by a query. When a SELECT query is executed, the database examines the WHERE clause and estimates hit ratio. If hit ratio is high, the database performs a table scan. If hit ratio is low, the query needs only a few table blocks, so a table scan would be inefficient. ● In a binary search, the database repeatedly splits the index in two until it finds the entry containing the search value: 5. The database first compares the search value to an entry in the middle of the index. 6. If the search value is less than the entry value, the search value is in the first half of the index. If not, the search value is in the second half. 7. The database now compares the search value to the entry in the middle of the selected half, to narrow the search to one quarter of the index. 8. The database continues in this manner until it finds the index block containing the search value. Primary and secondary indexes Indexes on a sorted table may be primary or secondary: A primary index, also called a clustering index, is an index on a sort column. A secondary index, also called a nonclustering index, is an index that is not on the sort column. A sorted table can have only one sort column, and therefore only one primary index. Usually, the primary index is on the primary key column(s). In some database systems, the primary index may be created on any column. Tables can have many secondary indexes. All indexes of a heap or hash table are secondary, since heap and hash tables have no sort column. ● ● Indexes may also be dense or sparse: ● ● A dense index contains an entry for every table row. A sparse index contains an entry for every table block. 5.4 MULTI LEVEL INDEXES Multi-level indexes A multi-level index stores column values and row pointers in a hierarchy. The bottom level of the hierarchy is a sorted single-level index. The bottom level is sparse for primary indexes, or dense for secondary indexes. Each level above the bottom is a sparse sorted index to the level below. Since all levels above the bottom are sparse, levels rapidly become smaller. The top level always fits in one block. The number of index entries per block is called the fan-out of a multi-level index. The number of levels in a multi-level index can be computed from fan-out, number of rows, and rows per block Balanced indexes Each path from the top-level block to a bottom-level block is called a branch. Multi-level indexes are called balanced when all branches are the same length and imbalanced when branches are different lengths. B-tree and B+tree indexes The balanced multi-level index described above is called a B+tree. B+tree structure is derived from an earlier approach called a B-tree. The two differ as follows: B+tree. All indexed values appear in the bottom level. Pointers to table blocks appear only in the bottom level. Since some indexed values also appear in higher levels, values are occasionally repeated in the index. ● B-tree. If an indexed value appears in a higher level, the value is not repeated at lower levels. Instead, a pointer to the corresponding table block appears in the higher level along with the value. Although most multi-level indexes are implemented as B+trees, the term B-tree is commonly used and often refers to a B+tree structure. B+tree is commonly written as B+-tree or B+-tree. ● 5.5 OTHER INDEXES Hash indexes The multi-level index is the most commonly used index type. Several additional index types are used less often but supported by many databases: ● Hash index ● Bitmap index ● Logical index ● Function index In a hash index, index entries are assigned to buckets. A bucket is a block or group of blocks containing index entries. Initially, each bucket has one block. As an index grows, some buckets eventually fill up, and additional blocks are allocated and linked to the initial block. Bitmap indexes A bitmap index is a grid of bits: Bitmap indexes contain ones and zeros. 'One' indicates that the table row corresponding to the index row number contains the table value corresponding to the index column number. 'Zero' indicates the row does not contain the value. Logical indexes A single- or multi-level index normally contains pointers to table blocks and is called a physical index. A logical index is a single- or multi-level index in which pointers to table blocks are replaced with primary key values. Logical indexes are always secondary indexes and require a separate primary index on the same table. Logical indexes change only when primary key values are updated, which occurs infrequently. Physical indexes change whenever a row moves to a new block, which occurs in several ways: A row is inserted into a full block. To create space for the new row, the block splits and some rows move to a new block. ● The sort column is updated. When the sort column is updated, the row may move to a new block to maintain sort order. ● The table is reorganized. Occasionally, a database administrator may physically reorganize a table to recover deleted space or order blocks contiguously on magnetic disk. If a table has several indexes, the time required to update physical indexes is significant, and logical indexes are more efficient. ● On read queries, a logical index requires an additional read of the primary index and is slower than a physical index. However, the primary index is often retained in memory, mitigating the cost of the additional read. index entries do not match values in the WHERE clause, so the database cannot use the index to execute the query. To address this problem, some databases support function indexes. In a function index, the database designer specifies a function on the column value. Index entries contain the result of the function applied to column values, rather than the column values. In principle, functions can be used with any index type, including single-level, multi-level, hash, bitmap, and logical indexes. 5.6 TABLESPACES AND PARTITIONS Tablespaces Tablespaces and partitions are supported by most databases but are not specified in the SQL standard. A tablespace is a database object that maps one or more tables to a single file. The CREATE TABLESPACE statement names a tablespace and assigns the tablespace to a file. The CREATE TABLE statement assigns a table to a tablespace. Indexes are stored in the same tablespace as the indexed table. CREATE TABLESPACE TablespaceName [ ADD DATAFILE 'FileName' ]; CREATE TABLE TableName ( ColumnName ColumnDefintion, ... ) [ TABLESPACE TablespaceName ]; By default, most databases automatically create one tablespace for each table, so each table is stored in a separate file. Database administrators can manually create tablespaces and assign one or multiple tables to each tablespace. Database administrators can improve query performance by assigning frequently accessed tables to tablespaces stored on fast storage media. Partitions A partition is a subset of table data. One table has many partitions that do not overlap and, together, contain all table data. A horizontal partition is a subset of table rows. A vertical partition is a subset of table columns. MySQL and most relational databases partition tables horizontally, not vertically. Partitions improve query performance by reducing the amount of data accessed by INSERT, UPDATE, DELETE, and SELECT statements. A shard is similar to a partition. Like a partition, a shard is a subset of table data, usually a subset of rows rather than columns. Unlike partitions, which are stored on different storage devices of a single computer, shards are stored on different computers of a distributed database. Partition types To partition a table, the database administrator specifies a partition expression based on one or more partition columns. The partition expression may be simple, such as the value of a single partition column, or a complex expression based on several partition columns. Rows are assigned to partitions in one of the following ways: ● ● ● A range partition associates each partition with a range of partition expression values. The VALUES LESS THAN keywords specify the upper bound of each range. The MAXVALUE keyword represents the highest column value, and VALUES LESS THAN MAXVALUE specifies the highest range. Each partition is explicitly named by the database administrator. A list partition associates each partition with an explicit list of partition expression values using the VALUES IN keywords. Like a range partition, each partition is explicitly named. A hash partition requires a partition expression with positive integer values. The database administrator specifies the number of partitions, N, and partitions are automatically named p0 through p(N-1). The partition number for each row is computed as: (partition expression value) modulo N. 5.7 PHYSICAL DESIGN MySQL storage engines Logical design specifies tables, columns, and keys. Physical design specifies indexes, table structures, and partitions. Physical design affects query performance but never affects query results. A storage engine or storage manager translates instructions generated by a query processor into low-level commands that access data on storage media. Storage engines support different index and table structures, so physical design is dependent on a specific storage engine. Statement CREATE INDEX Description Create an index DROP INDEX Delete an index SHOW INDEX Show an index Syntax CREATE INDEX IndexName ON TableName (Column1, Column2, ..., ColumnN); DROP INDEX IndexName ON TableName; SHOW INDEX FROM TableName; EXPLAIN statement The EXPLAIN statement generates a result table that describes how a statement is executed by the storage engine. EXPLAIN syntax is simple and uniform in most databases: EXPLAIN statement; The statement can be any SELECT, INSERT, UPDATE, or DELETE statement. Physical design process A database administrator may take a simple approach to physical design for MySQL with InnoDB: 9. Create initial physical design. Create a primary index on primary keys and a secondary index on foreign keys. In MySQL with InnoDB, these indexes are created automatically for all tables. In other databases, this step is necessary for tables larger than roughly 100 kilobytes, but can be omitted for smaller tables. 10. Identify slow queries. The MySQL slow query log is a file that records all long-running queries submitted to the database. Identify slow queries by inspecting the log. Most other relational databases have similar query logs. 11. EXPLAIN slow queries. Run EXPLAIN on each slow query to assess the effectiveness of indexes. A high value for rows and a low value for filtered indicates either a table scan or an ineffective index. 12. Create and drop indexes based on the EXPLAIN result table. Consider creating an index when the rows value is high and the filtered value is low. Consider dropping indexes that are never used. 13. Partition large tables. If some queries are still slow after indexes are created, consider partitions. Partition when slow queries access a small subset of rows of a large table. The partition column should appear in the WHERE clause of slow queries. Often, a range partition is best.