INFORMIX and Indexing
Support for Data Warehouses

BY PATRICK O'NEIL

The surge of interest in data warehousing signals a new customer emphasis on query performance. The good news is that database parallelism supplies a crucial aspect of data warehouse performance, an area addressed in current releases from most vendors. Indeed utilities for large data warehouses couldn't do without parallelism: a terabyte of data can't even be read from disk using one disk arm at a time in less than a week. A crucial runtime feature, intra-query parallelism (or simply query parallelism), gives a system the ability to execute a single query on a large number of inexpensive CPUs simultaneously. This allows the query optimizer to use all hardware resources effectively, eliminates the risk of losing all query execution when a single processor fails, and permits greatly improved response time for high-priority queries.

But parallelism is only half of the solution for data warehouse performance. Without the best possible indexing techniques, a query optimizer can only employ inefficient access methods to execute complex queries commonly seen in commercial applications. Parallel query execution alone does not solve this problem, since parallel execution with suboptimal index methods simply commits more resources each second to the same inefficient approach. This approach will mean that the customer can achieve needed throughput and response time requirements only at the expense of purchasing additional hardware to run these inefficient algorithms.

Many consider Informix XPS to provide a state-of-the art implementation of database parallelism. With the release of decision support system (DSS) indexing, Informix provides a needed component for optimal data warehouse performance, or indeed for any database application where query performance is crucial. This article starts with an introduction to the basic concepts underlying DSS indexing, such as bitmap indexes and join indexes, and then goes into the detailed syntax of the new Informix indexing features.

RID-LIST AND BITMAP INDEXES

A bitmap index is similar to the traditional row identifier (RID)-list index you have probably been using for years. In simplest terms, either type of index consist of a B-tree that allows the system to look up the value of some column in a table and find all rows that have that column value. But bitmap indexes have important performance advantages in certain regions of behavior. 

We start by defining a RID-list. Each row in a table has an assigned RID, or Row IDentifier, which we can think of as a pointer to the row on disk. A RID normally consists of a disk page number and a slot on the disk page, a specification of the page and position on the page where the record can be found. A set of rows with a given property can be represented by the list of RIDs designating where the rows are positioned, and this is known as a RID-list representation. Most database system have four byte RIDs (although Oracle RIDs are at least six bytes in length), so a list of a million RIDs will normally take up four million bytes of space. RID-lists have traditionally been used in indexes to specify the set of rows associated with each value of some indexed column. If we assume that we are dealing with an index on a department store SALES table of 100 million rows, with a column named department having 40 different values (specifying the department where each sale is made), then each department value will have an associated RID-list with an average of 2.5 million rows. Of course some department values will have fewer associated rows and some more, but no matter how many RIDs are associated with each value, the total number of RIDs in the index will be 100 million, since each row must have exactly one value (see Figure 1).

	Figure 1. Compressed RID-list Index on department, a column of the SALES table 

Given the huge number of RIDs associated with each value in the department index, we don't normally try to bring the RID-list into memory all at once. It is broken up into fragments of several hundred RIDs, which can be placed on successive B-tree leaf nodes. Also, instead of creating index entries of the form (department_value, RID), we note that it is a good deal more space-efficient to specify the department value only once at the head of each RID-list fragment. This is the picture we see in Figure 1. The leaf level of the index needs only about 400 MB of space. The 100 million four byte RIDs become the only important space factor, since the department value lengths are insignificant when amortized over all the RIDs of a fragment. 

We are now ready to introduce the idea of a bitmap. To start, the table on which bitmaps are to be used must have all rows numbered: 0, 1, 2, . . ., N-1. Successively numbered rows will be placed in RID order (physically contiguous on disk) and we need a method to convert from ordinal number to RID and back. Now take a sequence of N bits, and for any set of rows we wish to represent, set bit k to 1 if the row numbered k is in the set, otherwise set bit k to 0. For example, the bitmap:

 (10010100011011010 . . .)

represents the set containing the rows numbered: 0, 3, 5, 9, 10, 12, 13, 15, . . ., and so on. A bitmap index on SALES for the department column would be a B-tree of the same kind we saw in Figure 1, except that instead of using RID-list fragments on successive leaf pages we would use bitmap fragments (see Figure 2). Each new leaf page would contain a department value, and a bitmap fragment for the series of numbered rows with that department value. Each bitmap requires 100 million bits or 12.5 MB, so successive pages that are filled with bitmap fragments for the same value are the rule rather than the exception.

	Figure 2. Bitmap Index on "department," a column of the SALES table 

Since the department column has 40 values, we would expect bitmaps of the index to have about 1/40 of their bits set to one. We call the fraction of bits set to 1 the density of the bitmap, and note that it is identical to the selectivity of the restriction property. As we explain below, bitmaps with low densities undergo a type of compression, but for now we will consider only high density verbatim bitmaps, which contain all their bits in literal form.

BITMAP INDEX ADVANTAGES

Recall that bitmaps on the SALES table require 12.5 MB. Since there are 40 values for department, the entire bitmap index requires a B-tree leaf level of length 40.12.5 = 500 MB, plus a tiny overhead for department values. This is larger than the 400 MB leaf level we calculated for the RID-list index. To understand this, notice that the average density of a department = :deptvalue bitmap is 1/40, meaning that 40 bits are required to represent each row in the set, whereas with a RID-list, 32 bits (4 bytes) are required. The ratio of bits needed, 40:32, is the same as the total leaf level size ratio 500:400. In this case a bitmap index uses more disk space than a RID-list index.

But the situation changes as we vary the number of values in the index. If we assume the SALES table has an index to recognize the gender of the person making the purchase, there are only two values for such a gender index, M or F. For a bitmap index on gender, only two bitmaps are required, so the leaf level is only about 25 MB in length. A RID-list index on the other hand still requires 400 MB for its leaf level since we still have 100 million rows to represent by RIDs. Thus we see that the (verbatim) bitmap index requires a B-tree size that is proportional to the number of values in the index. But a RID-list index has a B-tree size that is nearly independent of the number of values (at least until the number of different values is so large that space to store values cannot be amortized by duplicate value RIDs). For indexes of less than 32 values we save disk space by using a bitmap index, but this situation reverses when indexes have more than 32 values, so that, on the average, bitmaps in indexes with a large number of key values are sparse.

However, the most important feature of a bitmap index is not disk space savings but the enormously improved CPU speed to perform operations such as AND, OR, NOT, and COUNT on verbatim bitmaps. As an example, assume we have two bitmaps B1 and B2, where B1 represents the property gender = 'M', and B2 represents the property department = 'sports'. We want to AND the two restrictions so that we arrive at the bitmap B3 for rows that have both properties (See Figure 3).

	Figure 3. An example of ANDing two bitmaps 

The following C program performs an AND of two bitmaps. In the outer While loop, the READFRAGMENT() function reads successive fragments of bitmap1 and bitmap2 into memory resident arrays B1 and B2; both B1 and B2 are overlays, viewing bitmap fragments as n-length arrays of 4 byte integers. The fragments are ANDed in a loop and then the resulting B3 fragment is written out to disk.

	while (READFRAGMENT(bitmap1, B1)
				&& READFRAGMENT(bitmap2, B2)	{
		for (i = 0; i < n; i++)
			B3[i] = B1[i] & B2[i];
		WRITEFRAGMENT(bitmap3, B3);
	}

We require a more cumbersome technique to AND two RID-lists R1 and R2. We need to start with R1 and R2 in ascending order by RID value, then loop through the two RID-lists and perform a merge intersect. This involves two cursors that advance through RIDs of R1 and R2 in a well-thought out way so that the cursor with the smaller RID catches up. When the RID values under the cursors are identical, this RID is placed into list R3. 

The loop to AND bitmaps is much more efficient than the loop to AND RID-lists when the bitmaps are relatively dense. The reason is that the bitmap AND loop will combine 32 bits at a time in a loop that is tremendously fast, whereas the RID-list AND loop must execute several instructions for every RID that is compared. Of course, if we are dealing with RID-lists of only a few dozen rows out of the 100 million rows of SALES, a loop to AND two RID-lists becomes the more efficient approach. The RID-list AND loop is performed faster and faster as the number of RIDs in the list decreases, whereas the time to AND two bitmaps remains the same irrespective of the number of bits set to 1. But down to a density of perhaps 1/100, the algorithm to perform bitmap AND is more efficient than the one for a RID-list. Algorithms with comparable characteristics exist to perform OR, NOT, and COUNT on bitmaps and RID-lists. 

Using uncompressed bitmaps for indexes with thousands of values (and therefore low average density per bitmap) leads to extremely large index sizes. When a bitmap is extremely sparse, bitmap efficiency compares badly with RID-lists not only for CPU reasons, but also because of the need to perform a larger number of disk I/Os. Both problems require us to find some method of compressing bitmaps of low density to achieve disk space savings and at the same time support fast operations for AND, OR, NOT, and COUNT.

One approach that has been taken by MODEL 2042 is to switch representations at different densities, so that as a bitmap fragment becomes more sparse, it simply becomes a RID-list fragment. This is a perfectly feasible approach which has been shown to work well in the Set Query benchmark.3 Other products use special encryption of bitmap patterns designed to save space on disk. The challenge with this approach is that many compression algorithms make it difficult to perform operations such as AND and OR between two compressed bitmaps or between one which is compressed and another that is uncompressed. This difficulty translates to inefficient CPU utilization. The need to find a bitmap compression scheme that supports efficient AND, OR, NOT, and COUNT operations is the most important aspect of bitmap indexing.

JOIN INDEXES

Join operations in SQL queries require the largest proportion of resources of all relational operations. Several general-purpose algorithms (Merge Join, Hash Join, and so on) have been implemented by database vendors to perform joins efficiently. These methods have provided the state of the art in query performance since the original release of relational products. But more recently a new type of special-purpose approach known as join indexing4,5 has offered significant additional acceleration for many queries.

A Join Index provides a means whereby a database system can efficiently translate restrictions on columns of one table to restrictions on another table, through a standard join. We illustrate join indexes using the star join schema of Figure 4. Each row of the SALES table in this schema is an aggregation of sales data for a specific product, a specific customer, and a specific day (this is called the granularity of aggregation1). SALES is the Fact table, and is joined to the three dimension tables, CUSTOMER, PRODUCT, and TIME through foreign key columns cid, pid, and day.

	Figure 4. Star join schema of SALES, CUSTOMER, PRODUCT, and TIME 

Working with this schema, assume the following select statement is a common query in our workload. We want to create useful indexes in advance, so we can execute it efficiently.

	select sum(dollar_sales), sum(unit_sales)
		from SALES s, CUSTOMERS c, PRODUCTS p, TIME t
		where s.cid = c.cid and s.pid = p.pid and s.day = t.day
		and t.month = 'May95' and p.package_type = 'box' 
		and c.gender ='M';

	In this query, the gender column is defined in the CUSTOMER table, but only SALES columns are aggregated; we normally think that the gender restriction on SALES can be performed only after a join. But consider making some preparation in advance, joining all SALES rows with their appropriate CUSTOMER rows (there is only one customer for each sale) and then restricting the SALES rows to those that have male customers. We have selected a set of about half the SALES rows, and this is best represented as a bitmap. Similarly, we can restrict the SALES rows to those that have female customers and create a bitmap for that. Now we create an index on SALES with two values, 'M' and 'F', and provide these two bitmaps for these values. What we have just done is create a gender index on SALES, even though there is no gender column in the SALES table. This index makes it unnecessary to actually perform the join between SALES and CUSTOMER when this query is evaluated. The gender index is what we refer to as a Foreign Column Join Index (or FCJ index). To further reduce the amount of work needed to evaluate the query, we could also create FCJ indexes for p.package_type and t.month on the SALES table. With these, the query optimizer would be able to execute this query using only indexes on the SALES table. The FCJ index is a variant form of the bitmap Join Index introduced recently.4

Instead of creating three FCJ indexes, we could create a Multi-Table Join Index (or MTJ index) that concatenates columns of several tables at once, t.month, p.package_type, and c.gender to create an index on the SALES table. While the ability to restrict columns from several joined tables at once improves the efficiency of the join still more, it turns out that there is a definite loss of flexibility. The usefulness of an MTJ index is severely degraded when one or more columns are changed in the query from the ones in the index. This means that for efficiency reasons, we might need to create new MTJ indexes for every combination of columns of foreign tables that show up in restrictions of the workload. This behavior is what is called a combinatorial explosion. FCJ indexes, on the other hand, are efficiently recombinant, and the number of FCJ indexes grows linearly with the number of foreign columns. For this reason, MTJ indexes are only used in extremely specific situations.

It seems as though we need to create a lot of join indexes to speed up our queries — isn't there something wrong with creating all these indexes? Not really. FCJ Indexes are like the traditional indexes you already use. On a DSS platform with no concurrent updates, there is much less concern with lots of indexes than on OLTP platforms. Join indexes certainly cost something in terms of disk space and initial load time, but they speed up queries. If they don't pay for themselves, you shouldn't use them, but join indexes are the best approach currently known to achieving good run-time performance with reduced hardware costs.

INFORMIX DSS INDEXING

Informix has implemented a state-of-the-art version of bitmaps for DSS indexes.  As explained earlier, the form of compression is the most crucial aspect of such an implementation, since it must be designed both to save disk space for sparse bitmaps, and also to efficiently perform the operations AND, OR, NOT, and COUNT. Informix tested the performance of a number of alternative bitmap compression schemes before settling on the one that provides the best CPU performance. Informix also supports a number of strategies of data partitioning to allow parallel evaluation of bitmap indexes in SQL queries.

The new Informix DSS Index form, known as a Generalized Key Index (or GK index) offers flexible variations on traditional indexing structures with bitmap capabilities. Here is the  Create GK Index syntax.

	create gk index indexname
	on T
		(select as key X.c1 {, Y.c2, . . .}
			from T, X, Y, . . .
			where <restrictions on T, X, Y>)
		);

This GK index creates a named index on a table T. The Select As Key clause explicitly defines the index key value that can be calculated for any row of T, and the index retrieves the row of table T with this value. The index key can consist of a set of concatenated column values from tables, X, Y, . . ., and the Where clause will specify (among other things) how the rows with columns making up the index key value are joined to the row for which the value is created. No specific order of tables is meant to be implied by the Select list: X.c1 {, Y.c2, . . .}.  It is simply meant to suggest that any table columns can be retrieved in any order, but there might still be only one column retrieved from the table T; we don't require multiple tables in the From clause.

The GK index provides great flexibility for creating new types of indexes. For example here we create the FCJ Index on the SALES table for gender values of the CUSTOMER table.

	create gk index ordersgender
	on SALES
		(select as key c.gender
			from SALES s, CUSTOMER c
			where s.cid = c.cid);

Given this index, the SQL query optimizer will use it in appropriate SQL statements without any need for special intervention from the user. For example, the index will be used for the two variant select statements below. No access to the CUSTOMER table is required in either case.

	select sum(s.dollar_sales) from CUSTOMER c, SALES s
		where s.cid = c.cid and c.gender = 'M';

	select sum(dollar_sales) from SALES
		where cid in (select cid from CUSTOMER
			where c.gender = 'M');

An MTJ Index that concatenates column values from several dimension tables to restrict rows on a central fact table is created in the next SQL statement. With this index, no joins will be required for the select statement using the star schema found on page x.

	create gk index ordersmpg
	on SALES
		(select as key t.month, p.package_type, c.gender
			from SALES s, TIME t, PRODUCT p, CUSTOMER c
			where s.day = t.day and s.pid = p.pid
			and s.cid = c.cid);

VIRTUAL COLUMN INDEXES

The GK index format is flexible enough to support totally new indexing capabilities, such as an index on a virtual column which represents an expression on base columns. Assume in our SALES table that we wished to represent, for each sale, a new virtual column named profit_per_unit, calculated by the formula:

	profit_per_unit = (dollar_sales - dollar_cost)/unit_sales

The three quantities on the right are actual columns of the SALES table, so the computation is simple for any row in SALES. The Informix create table syntax allows us to create this virtual column for SALES, as in the next SQL statement.

	create table SALES(
		dollar_sales decimal(6,2),
		dollar_cost decimal(6,2)
		unit_sales decimal(6,2),
		. . .
		profit_per_unit virtual(
			 	(dollar_sales - dollar_cost)/unit_sales),
		. . .
		;

An alter table statement could also be used to add a virtual column to an existing table. Now in any select statement, we can refer to this new column as if it were a regular column of SALES. For example, we can retrieve AVG(profit_per_unit) for some restricted set of SALES rows. And the next statement shows how to index the profit column using the GK index.

	create gk index profitx
	on SALES
		(select as key profit_per_unit
			from SALES);

With this virtual column index, we can efficiently evaluate any restriction on profit. For example, we might wish to find all products that make a profit below a given criterion.

	select pid from SALES
		where profit_per_unit < :criterion;

The flexibility built into GK indexes that allows the virtual column index to be created stems from the index’s allowing the Select As Key form. This syntax enables retrieving any standard select element. The virtual column index profitx could instead be created by replacing profit_per_unit with its defining expression.

SELECTIVE INDEX

A selective index is an index that remembers the set of rows selected from a table with a specific where clause set of restrictions. This set of rows, represented by a bitmap (compressed or not), is called a Foundset. Given a selective index, the query optimizer can speed up later queries with that same set of restrictions, and possibly others. For example, we may wish to limit our attention to rows of an EMPLOYEES table that fit a description for "techies".  We create a Selective index of this form next.

	create gk index techies
	on EMPLOYEES
		(select as key 'constant'
			from EMPLOYEES
			where hobby = 'math' and reading = 'Dilbert');

	The 'constant' key value here will never be used in a select statement. This is merely a convention for creating a GK index with a single Foundset bitmap. Once the Foundset has been defined, any select statement that contains the same restriction (as in the example below) will use this index single Foundset bitmap), a single Foundset bitmap  and will save work that would otherwise be needed to combine predicates.

	select name, empid
		from EMPLOYEES
		where hobby = 'math' and reading = 'Dilbert';

There are some other performance capabilities available with Informix XPS that have nothing to do with bitmaps. For example, a Sampled query is a query that takes a statistical sample of the rows to be selected. Users sometimes want to perform a query to get an approximate value for some quantity, a situation where a precise answer is unnecessary. In cases like this, a tremendous amount of effort can be saved by performing a statistical sampling of some large set of rows, rather than accessing every row in the query. We see the Informix syntax in the next statement.

	select SUM(dollar_sales), month
		from 10000 samples of SALES s, TIME t
		where s.day = t.day and t.month >= :month
			and t.month1 <= :month2;
		group by t.month;

Informix contemplates more query performance enhancements for the future. The current release of DSS indexing is an important beginning in an ongoing effort to provide users with innovative solutions for improved cost-performance. 

REFERENCES

1. Kimball, R. The Data Warehouse Toolkit, John Wiley and Sons, 1996.

2. O'Neil, Patrick, "MODEL 204 Architecture and Performance," Second International Workshop on High-Performance Transactions Systems, September 1987, published in Springer-Verlag Lecture Notes in Computer Science 359, 1989, pp. 40-57.

3. O'Neil, Patrick, "The Set Query Benchmark," Chapter 6 in The Benchmark Handbook For Database and Transaction Processing Benchmarks, Jim Gray, Editor, Morgan Kaufmann, 1993.

4. O'Neil, Patrick, and Goetz Graefe, “Multi-Table Joins Through Bitmapped Join Indices,” SIGMOD Record, September, 1995, pp. 8-11.

5. Valduriez, Patrick, “Join Indices”, ACM TODS, Vol. 12, No. 2, June 1987, Pages 218-246.

Patrick O'Neil is a Professor of Computer Science at the University of Massachusetts at Boston. He created the Set Query benchmark, published in the Benchmark Handbook, cited above. Dr. O'Neil has performed database consulting for vendors such as Microsoft, Oracle, Informix, and Sybase, and for user companies such as BGS. CIGNA, and PMSC.  His home page is http://www.cs.umb.edu/~poneil.