Divide and Conquer: Using Fragmentation for Smarter Data Access

by Hanna Metzger hannam@informix.com.
Tech Notes 1999, Volume 9, Issue 2

Overview

This article contains the following information:

• Introduction
• How to Choose a Fragmentation Method
  • Know Your Data
  • Know Your Queries
• The Role of dbslices in Effective Table Fragmentation
• How Fragmentation Methods Work with Queries
  • Round-Robin Fragmentation
  • Expression-Based Fragmentation
  • Hash Fragmentation
  • Hybrid Fragmentation
• A Simple Example of Hybrid Fragmentation Across dbslices
• An Example with Queries
• Monitoring Table-Fragmentation Efficiency
• Tips for Declaring and Using Dates
• Summary
• About the Authors

Introduction

In almost all database systems, database designers create fragmented tables to overcome the space limits of small disks, eliminate access deadlocks, and balance resource use, such as disk I/O.

Certainly one goal of fragmentation is to balance I/O across multiple disks and maximize throughput. All commercial database servers can improve query and transaction performance with simple fragmentation methods, such as round-robin and expression-based methods. In the IDS with AD and XP Options database server, however, you must fragment tables appropriately for your data and queries so that the database server can best use its built-in intelligence to process queries quickly and efficiently.

If you choose an inappropriate fragmentation method, the database server must scan all table fragments for all queries, which is an inefficient use of parallel-processing power. If you use a fragmentation method that allows the database server to identify table fragments that contain specific rows, query processing immediately becomes more efficient for many queries.

An expression-based fragmentation method provides the information that the database server needs to identify the fragments that contain specific column values. In addition, IDS with AD and XP Options database servers provide other fragmentation methods that can dramatically improve performance in two ways:

• Enhancing parallel processing of queries
• Eliminating table fragments that are not required to satisfy the query, which is called fragment elimination.

The ability of the database server to identify the exact table fragment that contains a specific required row is a related performance improvement as well. The IDS with AD and XP Options database server fragmentation methods and their performance implications are described below.

How to Choose a Fragmentation Method

The kinds of queries that run against the table determine whether enhanced fragment elimination or parallel processing is more important. If most queries are highly selective, accessing relatively few rows, then fragment elimination is more important. If most queries have low selectivity, which results in large table scans, then parallel processing is more important.

For this reason, before you can choose a fragmentation method you must know the data and know the queries that are run against it.

Know Your Data
To find out what kind of information a table contains and make an intelligent prediction about what kind of queries users will run, you must examine the table definition.

For example, suppose you have created the following table that contains date information, such as ship and order dates:

CREATE TABLE orders (
	order_no  integer,
	cust_no  integer,
	store_no  integer
	order_date date,
	ship_date  date,
	status   char(5),
	total_amt  money)
...;

For this table, many queries will probably use dates as filters in the WHERE clause. This prediction suggests that the ship_date and order_date fields are candidates for the fragmentation columns.

If the table is already populated, run the following SQL statement:

UPDATE STATISTICS MEDIUM for TABLE orders(ship_date, order_date);. 

Then use the dbschema -hd command to examine the resulting data distribution information to see how many rows there are for each date. Some date periods might contain more rows than others.

If you find uneven distribution that creates data skew, either you cannot use this column for fragmentation or you must use a fragmentation method, such as a hash or hybrid scheme, that minimizes the effect of the uneven distribution. The fragmentation method that you choose depends on whether your primary fragmentation goal is fragment elimination or parallel-processing improvement. The same principle applies when you examine marketing information tables that have regional information, or other kinds of raw data that might contain more rows for one column value or range of values than for others.

You also need to consider the way in which rows are added to the table and removed from it. For an accounting data table, information might be kept by month on a rolling twelve-month basis. Then at the end of each month, the new month's data is added and the oldest month is removed to an archive. For efficiency, your fragmentation scheme should permit this kind of table modification to occur without rebuilding the entire table or running large delete operations.

If the table contains summary data for each category and each date period contains the same list of categories, data skew is not a problem because each table will have the same number of rows. In this case you have more freedom in choosing a fragmentation method.

Know Your Queries
Examine the queries that are run most often and the queries that take longest to run. Look at the filters in the WHERE clause and use your knowledge of the table definition and the data distribution to figure out whether the query will return only some rows-and if so, approximately how many and based on what column data-or whether it must scan the entire table.

If the filters return relatively few rows, consider fragmenting the table so that the database server needs to scan only the fragments required by the query. Make sure that each fragment is on a separate disk to improve disk I/O for the fragments that are required.

If the filters use aggregate expressions on unindexed columns so that all table fragments must be scanned, then you improve parallel processing by fragmenting the table uniformly across all disks and co-servers. The number of scan threads that the database server starts depends on the number of table fragments in dbspaces on each co-server. For large queries that scan all table fragments, limit the number of fragments to between one and three times the number of CPU VPs.

The number of parallel scans is also determined by the number of CPU VPs in your database server configuration. You might begin by creating fragments as a multiple of one or two times the number of CPU VPs. If you see that the CPU VPs can manage more scan threads because your queries do not require them to manage query processing threads-such as join, group, and sort threads-you can increase the number of table fragments per CPU VP.

If you see that many fragments are eliminated for query processing, you can increase the number of table fragments so that the actual number of scanned fragments is in balance with the number of CPU VPs. For example, a table that has 250 fragments of which only 35 are scanned for most queries would perform very well on a system with 16 CPU VPs.

The Role of dbslices in Effective Table Fragmentation

A dbslice is a named set of dbspaces that you can manage as if it were a single object. Dbslices are a significant server management feature for database servers that contain many co-servers and many more disk partitions. You never have to specify a long list of dbspaces when you can refer to the entire set of spaces with a single dbslice name. In addition, dbslices let you design an optimal dbspace layout for table fragments and use it easily when you fragment the tables.

Table fragmentation is only as effective as the arrangement of dbspaces permits it to be. Properly constructed dbslices can help you achieve the two major goals of dbspace layout:

• An optimal number of table fragments per CPU VP

  For the most efficient parallel performance, you want to keep the CPU VPs evenly occupied, but not overburdened. Remember that the CPU VPs run secondary threads for joins, sorts, and other subsidiary processes. A good first approximation is one or two table fragments for each CPU VP. If you turn on SET EXPLAIN to analyze query processing and you see that some fragments are always eliminated when this table is queried, you can increase the number of fragments correspondingly.

  Note that the number of fragments does not limit the size of the table. To provide more space in a table fragment you can always add chunks to dbspaces.

• Balanced disk I/O and maximized throughput

  In general, you should design dbslices to avoid storing more than one table fragment on the same disk. For the best parallel performance, distribute table fragments evenly across all controllers and disks to reduce disk bottlenecks, disk contention, and I/O waits.

How Fragmentation Methods Work with Queries

The standard fragmentation methods work with all Informix database servers. These methods include round-robin fragmentation and expression-based fragmentation. In addition, IDS with AD and XP Options database servers provide two other fragmentation methods: hash fragmentation, which distributes rows into fragments by applying a hash function to the fragmentation columns, and hybrid fragmentation, which combines the hash and expression-based methods.

Round-Robin Fragmentation
Round-robin fragmentation works well if most queries read all or most rows in a table. Round-robin fragmentation distributes rows uniformly across the specified dbspaces for good parallel processing. Nevertheless, because round-robin fragmentation does not provide the database server with any information about the location of rows (i.e. which fragment contains which rows), fragment elimination is not possible for queries that require only a few rows or sets of rows.

As a result, round-robin fragmentation is rarely used in IDS with AD and XP Options database servers.

Expression-Based Fragmentation
Expression-based fragmentation uses an SQL expression to define the location of each table row. This expression provides the database server with information that it needs to eliminate unnecessary table fragments when it processes a query. On the other hand, the expression-based fragmentation method might introduce data skew, which impedes efficient parallel query processing.

Suppose you create the table as follows:

CREATE TABLE sales (
	cust_no integer, billamt money, bill_date integer,...)
	FRAGMENT BY EXPRESSION
	bill_date <= 19980131 AND bill_date >= 19980101 in dbsp1
	bill_date <= 19980228 AND bill_date >= 19980201 in dbsp2
	...
	bill_date <= 19981231 AND bill_date >= 19981201 in dbsp12;

Although expression-based fragmentation might work well for queries reading only some rows in a table and using either exact match or range filters based on the columns used for the fragmentation expression, parallel processing for complete table scans is not optimal if some fragments contain many more rows than others. In addition, because expression-based fragmentation must be specified by dbspace instead of dbslice, this method might produce some dbspace hot spots-where some dbspaces are used more than others, causing I/O wait problems.

The fragmentation method shown for the sales table can eliminate table fragments if a query uses a range expression that requires rows from specified months, as follows:

SELECT * FROM sales
	WHERE bill_date <= 19910331 AND bill_date >=
	19980101

Expression-based fragmentation also allows the database server to identify the table fragment that contains information for a single bill date.

Unfortunately, in the illustrated case the sales table data is not evenly distributed for all months. The months of November and December contain ten or twenty times as many rows as the months of July and August. With this skewed distribution, if a query must scan the entire table-or even different fragments-it is inefficient because the database server can process the query only as fast as it can scan the largest table fragment. The fragments containing data for the months of November and December will hold up processing of the entire query for the following query:

SELECT * FROM sales
	WHERE billamt > 50;

Hash Fragmentation
Hash fragmentation is one of the additional fragmentation methods you can use only in an IDS with AD and XP Options database server. The hash fragmentation method distributes rows into table fragments by applying an internal hash function to the fragmentation columns. It uses the result to distribute the rows into fragments so that they contain approximately the same number of rows. The number of duplicate values in the fragmentation column generally determines how evenly the rows are distributed. If the fragmentation column contains many duplicate values, hash fragmentation might produce data skew.

The hash fragmentation method improves on the round-robin method because the database server can use the hash fragmentation columns to identify the fragment that contains a specific row. If the WHERE clause of the query uses equality expressions on the fragmentation columns, the database server can skip some fragments when it processes the query. Hash fragmentation, however, does not allow the database server to skip fragments when the WHERE clause uses range expressions.

For example, if you have a table of monthly sales data, you might fragment the table by hash on the customer number, as follows:

CREATE TABLE sales (
	cust_no integer, billamt money, bill_date integer,...)
	FRAGMENT BY HASH (cust_no)
	IN dbsp1, dbsp2, dbsp3, ....;

Because there is only one row for each customer number in each month's data, hash fragmentation ensures an approximately uniform distribution of rows across dbspaces, thus improving parallel scan performance for queries like the following query, which requires rows from all fragments:

SELECT * FROM sales
	WHERE billamt > 50;

Hash fragmentation also allows the database server to identify individual customer number rows and access only table fragments that contain them, such as the following query:

SELECT * FROM sales
	WHERE cust_no = 12345 OR cust_no = 56789;

However, since the customer numbers are distributed across many fragments, and not grouped in specific fragments, queries that request a range of customer numbers do not allow the database server to skip fragments. Consider the following query:

SELECT * FROM sales
	WHERE cust_no <= 30000 AND cust_no >= 10000;

For such a query, hash fragmentation requires the database server to scan all table fragments.

Hybrid Fragmentation
Hybrid fragmentation is the second fragmentation method that is unique to IDS with AD and XP Options database servers. Hybrid fragmentation combines the advantages of both hash and expression-based fragmentation to provide fragment elimination for both range and equality expressions in the WHERE clause and to minimize the effect of data skew that might result from expression-based fragmentation alone.

For hybrid fragmentation you create dbslices that contain several dbspaces, evenly distributed across co-servers. In the case of a single co-server database server, you create dbslices that contain several dbspaces evenly distributed across disks.

You need one dbslice for each fragmentation expression. For example, if you use the expression clause of the fragmentation definition to divide accounting data into twelve months, then you need twelve dbslices, one for each month. You can use the same column for the hash distribution into the dbspaces contained in the dbslice, or you can specify a different column to provide fragment elimination on another dimension.

The expression component of the fragmentation scheme allows the database server to eliminate fragments for WHERE clauses that use both range and equality expressions, while the hash component of the fragmentation scheme allows further fragment elimination if the WHERE clause uses equality expressions on the hash column. Even if hash fragments cannot be eliminated, increased parallel processing is possible because table fragments can be scanned by different threads.

The following sections provide hybrid fragmentation examples to illustrate these advantages in more detail.

A Simple Example of Hybrid Fragmentation Across dbslices

This basic example shows how hybrid fragmentation can minimize parallel processing bottlenecks that result from data skew in table fragments and also allow fragment elimination.

Suppose that you have a single table that contains sales information for the twelve months of the fiscal year in several categories (quarter, month, and day) and that you want to store the table across the 16 disks of your single co-server IDS with AD and XP Options database server. Suppose also that your database server has four CPU VPs.

You know that most of your queries require information about the data from a specific quarter. In this case it might seem appropriate to fragment the table by expression into four large dbspaces across the 16 disks, using the quarter column as the fragmentation key. If each quarter's table rows are stored in a single table fragment, then fragments that contain the rows that belong to the quarters not queried can be skipped. This seems like a good idea because it achieves your major fragmentation goal: fragment elimination for quarters that are not required by the query. It also provides some parallel processing if more than one quarter is queried.

Unfortunately, your sales data is not evenly distributed. When you fragment the table by quarter, you find that the first quarter fragment contains more than three times as many rows as the third quarter fragment, while the second and fourth quarter fragments contain about three-fourths as many rows as the first quarter fragment (Figure 1). Not only is this inefficient use of dbspace, but it also creates significant data skew when more than one quarter is queried.

Your row distribution will look like this:

Figure 1: Data skew in quarterly sales row distribution.

You find that even if you fragment the table by month, data is still significantly skewed.

Hybrid fragmentation can improve parallel processing by using dbslices to combine expression-based fragmentation with hash fragmentation.

First you create four horizontal dbslices by striping the dbspaces across the disks so that each dbslice contains one dbspace on each disk. You then fragment the table by expression so that the data for each quarter is stored in a separate dbslice. You also fragment the table by hash so that within each dbslice the data for a single quarter is spread evenly across the disks into dbspaces determined by a hash function applied to the prod_code column data. To create the fragmented table, use the following SQL statement:

CREATE TABLE sales (quarter integer, month integer, day integer, year integer, prod_code
integer, tot_amt decimal...)
	FRAGMENT BY HYBRID (HASH (prod_code))
		EXPRESSION quarter = 1 IN dbsl1
				quarter = 2 IN dbsl2
				quarter = 3 IN dbsl3
				quarter = 4 IN dbsl4;

With hybrid fragmentation, row distribution looks like this:

Figure 2: Hybrid fragmentation example.

This fragmentation method meets both fragmentation goals:

• Fragment elimination

  If a query requires data from only a single quarter or a single month, only the fragments that contain the rows for the quarter or the quarter that includes that month are scanned.

  If queries use one or more specific product codes as a filter, only table fragments that contain that product code are scanned.

• Improved parallel processing

  Although data skew is not eliminated-the first quarter dbslice obviously contains more table rows than the other dbslices-no parallel processing bottlenecks exist for a query that requires data for a single quarter. This is true because the rows for each quarter are distributed more or less uniformly across all disks and each dbspace can be scanned by a separate scan thread.

An Example with Queries

The following real-world example shows how fragment elimination can be effective for specific queries.

In this example, the orders table is fragmented to store order information for all stores in twelve dbslices, one dbslice for each month. Each dbslice contains the same number of dbspaces, evenly distributed across disks. For each month, there is one table fragment for each CPU VP on the co-server node where the fragment is stored. Thus for a single co-server database server with four CPU VPs, each dbslice would contain four dbspaces. Within each dbslice, the month's order information is fragmented by hash on the region number associated with the order. The entire table, then, is stored in 48 fragments on the four-CPU VP single co-server database server. The table definition statement is as follows:

CREATE OPERATIONAL TABLE orders (
	order_date integer,
	store_no smallint,
	region smallint,
	class integer,
	total_sales decimal (10,2),
	cost decimal (10,2),
	units decimal (10,2)
	)
	FRAGMENT BY HYBRID (region)
	EXPRESSION
		order_date <= 19980131 AND order_date >= 19980101,
		order_date <= 19980228 AND order_date >= 19980201,
		. . .
		order_date <= 19981231 AND order_date >= 19981201;

Data rows are distributed as shown in the following figure:

Figure 3: Hybrid fragmentation of the orders table.

For the following query, the database server scans only four table fragments, or 1/12 of the data:

SELECT MIN(total_sales) FROM orders WHERE
		order_date <= 19980131 AND order_date >= 19980101;

For the following query, the database server scans only one table fragment, or 1/48 of the data:

SELECT total_sales, store_no FROM orders WHERE
		order_date <= 19980131 AND order_date >= 19910101
		AND region = 100;

Although the following query scans fragments from all twelve months, it scans only twelve fragments, or 1/4 of the data, because it can identify the fragments that contain the required region:

SELECT order_date, total_sales, store_no FROM orders WHERE
		region = 100
		ORDER BY order_date;

Note: Query performance might also be improved by the use of indexes. Specifically, indexes can improve performance for queries that use non-fragmentation or non-key columns in the WHERE clause. Sometimes an index alone can be scanned to provide the required information to satisfy a query. The subject of indexes, however, deserves an article of its own that discusses when to create an index, what columns to use, whether to fragment the index and how to fragment it, and so on.

Monitoring Table-Fragmentation Efficiency

Before you put a fragmentation scheme into effect in a production database, test it in an appropriately configured testbed system to make sure that the scheme meets your fragmentation goals. Test your fragmentation methods carefully. After you create a production database system, it is difficult to change the fragmentation method. Although you can easily add fragments, changing the fragmentation method requires you to drop the table, redefine it, and reload the data.

To test the fragmentation scheme, you run a set of typical queries against the table and monitor query performance. To monitor query performance, enter the SET EXPLAIN ON statement before the query runs and examine the output that is produced. You can also enter some of the onstat utility commands to get information while the query is running.

For example, suppose that you run the following query against the orders fact table introduced in the previous section:

SELECT prod.vendor
FROM orders, stores, product
WHERE (orders.order_date = 19980613 
	OR orders.order_date = 19980514 
	AND (orders.store_no in(1400))
	AND stores.store_no = orders.store_no
	AND product.class = orders.class
GROUP BY product.vendor
ORDER BY product.vendor

The orders fact/dimension database contains several dimension tables, among them a stores table that is hash-fragmented on the store_no column, and a product table that is fragmented by hash on the vendor column into a dbslice with four dbspaces. The stores table also has an index on the store_no column.

The sqexplain.out file produced when you turn on SET EXPLAIN contains the following output. This sample output shows only relevant information about fragment elimination when the orders table is scanned to display data for two days, one day in May and the other day in June, and the other threads that must be run by the CPU VPs.

Temporary Files Required For: Order By Group By

1) informix.loc: INDEX PATH

  (1) Index Keys: orders  (Key-Only) (Parallel, fragments: ALL)
    Lower Index Filter: informix..store_no = 1400

2) informix.sales: SEQUENTIAL SCAN (Parallel, fragments: 5.0, 5.1, 5.2, 5.3, 6.0, 6.1,
   6.2, 6.3)

  Filters: (((informix.orders.order_date >= 19980613 AND informix.orders.order_date <=
   19980613 ) OR (informix.orders.order_date >= 19980514 AND informix.orders.order_date
   <= 19980514 ) AND informix.orders.store_no IN (1400 )) 

DYNAMIC HASH JOIN (Build Outer) 
  Dynamic Hash Filters: informix.region.store_no = informix.orders.store_no 

3) informix.prod: SEQUENTIAL SCAN (Parallel, fragments: ALL)

DYNAMIC HASH JOIN (Build Outer) 
  Dynamic Hash Filters: informix.orders.class = informix.prod.class
# of Secondary Threads = 38

XMP Query Plan
oper	segid	brid	width 
------------------------------
scan	 5	 0	 1
scan	 6	 0	 8
hjoin	 4	 0	 4
scan	 7	 0	 4
hjoin	 3	 0	 4
group	3	0	4
group	2	0	4
sort	  1	  0	  4

In the XMP Query Plan section, the width column shows the number of threads for each SQL operator, including scan, hash join, group, and sort.

The remainder of the sqexplain.out information, not included here, displays details about how the database server is executing the query plan.

You can also get this information from the output of some onstat utility commands. First get the query_id number from onstat -g rgm output. Then get detailed information from other onstat utility commands, which are available only while the query is running:

• For detailed information about SQL operators running the query, use onstat -g xmp.
• For information about activity on each co-server, run onstat -g xqs query_id.
• For information about the plan itself, run onstat -g xqp query_id.

While the query runs, you can also get information about the scan threads by running onstat -g ath. You might see something like this output, which shows what all threads, including the CPU VP threads, are doing and how many CPU VP threads are scanning fragments.

Tips for Declaring and Using Dates:

• Declare dates as integer data types in year-month-day order as shown in the sales table creation and query example below. For example, use the integer 19990101 for January 1, 1999.

  When a date is declared as a date data type the database server must convert it to an integer before it can perform operations on the data. Declaring the date as an integer eliminates this step and speeds up transaction and query processing.

• Enter date ranges (and other range expressions) with the most restrictive part first as shown in the examples.

  In most cases, this counter-intuitive method of entering range statements reduces the number of expression evaluations that must be evaluated. In a logical AND operation, if the first clause is false, then the expression to the right of the AND for the fragment is not evaluated.

Summary

In this article we have explained why appropriate fragmentation methods are vital to efficient performance of IDS with AD and XP Options database servers. We have also provided general guidelines with examples to help you decide on the best fragmentation method for your data and queries, and shown how to monitor queries to find out if your fragmentation method is meeting your goals.

In the next article we will show how appropriate fragmentation methods make it fast and easy to scrub and load data and update tables by adding and removing table fragments.

About the Author

This article has been written by an IDS with AD and XP Options team that consists of Hanna Metzger, a senior technical writer at Informix, and a group of software engineers who work on the database server development. We have benefited greatly from the advice and real-world examples and information provided by Informix field support and data warehouse experts. Hanna may be reached at mailto:hannam@informix.com.