State of the Art in Data Warehouses: uses, special techniques, patents, and most relevant competition
   
Dennis Shasha

August, 2000

   
Executive Summary
   
Techniques for aggregating and thereby summarizing large amounts of data probably date back to the Egyptians ("How many cubits of stone have we moved in the past month?") In the last forty years, database management systems have taken over these functions as well as the conceptually simpler functions of recording detailed transactions ("Dave Smith bought 5 pairs of yellow socks at our branch at the Wharf").
   
Since many databases to which one poses aggregating queries change seldom, a wide variety of indexing techniques (e.g., bit vectors and star schemas), table caching techniques (e.g., tables that store aggregate data), and query processing methods (e.g., optimized foreign key joins) have arisen. This paper reviews the principal query processing methods in the literature, and gives references to that literature. Specifically, this paper:
   
1. Outlines some applications of data warehouses to help Lafeyette create a value proposition to customers
   
2. Describes the main algorithms and data structures in the literature with references
   
3. Identifies relevant patents 
   
4. Discusses four significant and typical competitive companies
   
1. Uses of Data Warehouses
   
The information in this section comes from conversations with data warehouse developers and users and a white paper from a Teradata developers conference that was lent to me but of which I no longer have a copy.  So, I have no written reference for this information. Nevertheless, the applications mentioned are real and generalizable.

At an abstract level, here are the principal uses of data warehouses:
   
(i) Companies negotiate better buying terms from their suppliers and enforce high quality deliveries.
   
(ii) Large volume suppliers get information on the sales of their products so they can ship the product and avoid out-of-stock items. Some retailers take advantage of this by paying their suppliers on consignment, i.e., only when the retailer is paid.
   
(iii) Companies identify and reward loyal customers using frequent flier miles for example or by giving special discounts.
   
(iv) Data warehouses form the nucleus for data mining techniques using statistics, neural nets, or association rules. This can help discover fraud, identify good candidates for mortgage loans, or identify prospects for advanced telephone services.  Market basket analysis (what people buy at one time) can help suggest promotions. WalMart for example discovered that people who buy pampers often buy beer, so they moved pampers and beer close together. The result was that sales of both increased (Computer Business Review, October 1996).
   
Here are some industries that use data warehouses. This might suggest some promising customers for Lafeyette.
   
WalMart is the world's most successful retailer. Some indications: a 200,000 square foot WalMart opens every other day; a Barbie Doll is sold at a WalMart every two seconds. Many of WalMart's large volume suppliers, such as Proctor and Gamble, have direct access to the WalMart data warehouse, so they deliver goods to specific stores as needed. WalMart pays such companies for their product only when it is sold. Procter and Gamble ships 40% of its items this way, eliminating paperwork and sales calls on both sides.
   
The WalMart data warehouse is also the source for corporate-wide decisions. Eventually, the company wants to affect price changes globally and instantaneously at its more than 3,000 locations.
  
Data warehouses enable companies to identify hot-selling items. 
(i)	A KMart analyst discovered that bags of multi-colored confetti sold out in certain cities of the southwest US. A store manager in San Antonio informed him that the confetti was being used in Latino communities to fill colored Easter eggs. The buyer authorized stored in other parts of the country to ship their confetti to these stores.
(ii)	 Buttrey Food and Drug discovered that the best selling items in college towns is albacore tuna.
(iii)	Hallmark Cards analysts can ask questions like ``Do people buy Valentines at the last minute?'' ``Do they buy photo albums more on father's day or for graduations?''
   
Warehouses help retailers practice trend merchandising by ``riding the waves of clothing fads'' that begin on either coast and work their way inland. There are also weather-induced clothes buying fashion (e.g., spring clothes sell earlier in Houston than in Minneapolis).
 
Warehouses can help identify a very frustrating source of lost revenue: out-of-stock items. Casino Supermarche recouped several million dollars when they noticed that Coca-Cola was often out-of-stock in many of their stores.
   
Warehouses can identify the effectiveness of advertisements. At  Buttrey Food and Drug, a report can be generated that includes units sold, average cost, retail price, gross margin percentage and dollars realized during an advertisement campaign. Buttrey also uses their warehouse to index competitors' prices against their own.
   
Warehouses can support business-critical ad hoc queries. GUSCO in the UK started a line for petite women. Many catalogues were requested, but few purchases. It turns out that many women wanted to be petite so requested that catalogue, but were no longer petite. GUSCO did a directed ad campaign to women who had bought small sizes (dresses under size 7, shoes under size 5, etc.) They got a 12% response rate.
   
Warehouses help keep tabs on suppliers. At Whirlpool, if a particular motor shows up in the data warehouse as breaking too often, Whirlpool can use that data to renegotiate the supplier's warranty on the part. For example, in the mid-1990s, engineers detected a faulty hose clamp on hundreds of washing machines that had already been sold. The affected customers were identified through the data warehouse Mechanics replaced the clamps before flooding could occur.
   
Warehouses also can improve productivity in the transportation industry. Burlington Northern Santa Fe Railway uses their warehouse to analyze the work habits of all crew members and thus reduce absenteeism. They also do data mining on their warehouse to try to identify the underlying causes of derailments.
   
Warehouses can save money. Another railroad Union Pacific saved 400,000 dollars per month by identifying tax exempt purchases. It saved more by enforcing cash stops on delinquent customers. Boeing uses its data warehouse to track the quality records of its suppliers.
   
Lufthansa uses its warehouse for customer information. Which special routes were Miles and More customers flying? Which agencies fail to promote Lufthansa? How many no-shows were there?
   
American Airlines uses their data warehouse to track how long items are kept in inventory before they are used. If longer than a certain amount of time, then AA slows down purchases of those items. Similarly AA drops leases on telephone lines that it uses infrequently. American Airlines also uses their data warehouse to  centralize the purchase of large volume items, e.g. latex gloves. They charge back vendors for failing to provide what was promised.
   
Finally, AMR SABRE tracks help desk calls in order to improve customer service. A possible next step is a case-based reasoning system (perhaps modeled on the very successful one used at Compaq).
   
The Gold card program was invented by American Airlines in 1982 to give incentives to the relatively small portion of its passengers who account for most of its business: business travelers averaging 13 trips per year. The goal was to reward them for their loyalty without reducing the amount they spent on their business trips. The Gold Card also provides an outlet for direct mail marketers. American sends around 10 million pieces of mail per year. Many companies now give away free miles.
   
The data warehouse is a good place to put bought data. Continental buys data from other people, e.g. it offers promotions to people who live on one coast yet rent cars on the other.
   
In telecommunications, U S WEST uses its data warehouse to identify operational problems. Any item can be drilled down. For example, given installation times by region, a manager can drill down to the installation times by switching area. If one switching area is bad, he or she can drill down by problem type. If one problem type is bad, the reason may be that a switch doesn't support a sold service.
   
Belgacom, the Beligian telecommunications company, mines sales data to discover complementary services to offer, to detect fraud, and to plan network requirements (e.g. which copper to replace by fiber).
   
Sprint uses their data warehouse for marketing. For example, they ran a promotion called "The Most" in which Sprint halved the bill for whomever a customer called the most. They claimed that they wouldn't have been able to do this without their data warehouse.
   
Lucent Technologies Quest: when still part of ATT, Quest helped identify platinum customers as well as potential customers who would be worth enticing. They found it useful to answer questions like: (i) Who is an early adopter of new technology? (For example, heavy internet users might be good candidates for ISDN lines with guaranteed levels of service, for example.) (ii) To whom should I offer a credit card? (They found that phone bill paying habits are an excellent predictor of credit card paying habits.)
   
2. Technology for Data Warehousing
   
Online-transaction systems (OLTP systems) such as bank teller transactions and airline reservations are optimized for finding a record associated with a specific key, e.g. finding the information about employee 123124. By contrast, data warehouses are optimized for finding sets of records very quickly. The reason is that typical queries are of the form: "find all sales by region and quarter" or "find stores that sell the greatest volume of sportswear per month" or "select the top 5 stores for each product category for the last year". Such queries must access large sets of rows. The query processing challenge is to process these queries without doing a linear scan of all or most of the database. This section discusses the techniques that people have used to attack this problem.
   
There are five main approaches: 
(i) multidimensional arrays, 
(ii) special indexes, 
(iii) table caching, 
(iv) optimized foreign key joins, and  
(v) approximation.
   
(i) Multidimensional arrays (i.e. matrices). 
This strategy consists of implementing the data warehouse as a multidimensional array or matrix. Each dimension corresponds to an attribute of the data. For example, the sales table can be viewed as a matrix with coordinates: store location, product type, customer id, and so on. A particular sale can be identified by specifying all of these attributes. Using matrices is the basic strategy that Hyperion's product (Hyperion used to be called Arbor software having Essbase as its main product) uses.  The strategy works well for small databases or very dense ones. By dense, we mean that the cartesian product of possible values should all be meaningful, e.g., every customer is likely to buy every product  from every store. Since this is rarely true, this scheme must be modified to deal with sparse values. Hyperion does this by defining a notion of sparse attributes and dense ones. So, for example, it might be that every store carries every product (a dense relationship that can be stored in a matrix), but only some of these combinations are valid for any given customer. So, a conventional index would be used whenever customer sales are involved, but a dense one for queries involving store-wide or product-wide sales.
   
(ii) Special indexes. 
Bit-map indexes are an index structure tailored to data warehouses. These indexes have already been used in some commercial products to speed up query processing including Oracle, RedBrick (part of Informix) and Sybase. In its simplest form, a bitmap index on an attribute consists of one vector of bits (i.e., bitmap) per attribute value, where the size of each bitmap is equal to the number of records in the indexed relation.  For example, if the attribute is day-of-week, then there would be seven bitmap vectors for that attribute, one for each day. The bitmap vector corresponding to Monday would have a 1 at position i if record i contains "Monday" in the day-of-week attribute. This single value-based approach is called a Value-List index.  Other techniques associate bit vectors with ranges of values, so there could, for a salary attribute, be a vector for the range 0 to 20,000 Euros, 20,000.01 to 35,000 Euros, and so on. Still others associate each bit vector with a bit value (a 1 or a 0) in a given position. So, if the attribute holds n bit numbers, then there would be 2n bit vectors (position 1, bit value 1; position 1, bit value 0; position 2 bit value 1; ...).
   
The benefit of bit vectors is that it is easy to use multiple bit vectors to answer a single query. Consider a query on several predicates, each of which is indexed. Most conventional database management systems would use just one of the indexes (the one that is most “selective” so returns the fewest rows), though some systems might attempt to intersect the record identifiers of multiple indexes. 
Bitmaps work better, because they are more compact and intersecting several bitmaps is much faster than intersecting several collections of record identifiers. In the best case, the improvement is proportional to the word size of the machine. For example, suppose the word size is 32 bits. Then two bit vectors can be intersected 32 bits at a time. Each set of 32 bits corresponds to 32 record identifiers being intersected. That best case occurs when each predicate is unselective (i.e. many records match each predicate value), but all the predicates together are quite selective. Consider for example the query: "Find people who have brown hair, glasses, ages between 30 and 40, blue eyes, work in the computer industry, live in California, ..." One of the first users of bitmap vectors was the CIA.
   
So, matrices are best when sets of predicates are dense (all, or nearly all, values in the cartesian product are possible), bitmaps are best when predicates are neither dense nor individually selective. An intermediate approach (when there is insufficient density for matrices but many values in the cartesian product are present) is to use multidimensional indexes. Multidimensional indexes such as quadtrees, R-trees and their successors are implemented as variable sized grids on a multidimensional space. The grids are of variable sizes because the population of points differs in different places in a hyperspace. For intuition, consider a map of equi-population rectangles of France. The rectangles would be far more dense in Paris than in the alps. Indexes like this work well for spatial data (where they are used to find the points contained in latitude-longitude quadrants). This alternative is little explored in the commercial arena except for geographical queries, however, because these schemes do not scale well with increasing dimensionality and commercial systems typically have far more than three dimensions.

(iii) Table Caching. 
If one doesn't have the luxury to design new indexes on top of a database system (because one is not the implementer of that system) one can pre-compute a large number of anticipated aggregate queries and put them in tables.  For example, if a large retailer frequently asks queries that sum the total sales across multiple stores or multiple products, one may store such information in special tables. The main cost of such a strategy is maintaining these tables in the face of updates. (Disk space is no longer a significant factor.) In the example, every sale of item I at store S would have to update the total product sales table for I and the total store sales tablefor S. So, this strategy is worthwhile if there are few updates between queries. The strategy is not worthwhile if there are many. Redbrick systems uses this strategy in their upcoming release (personal communication of one of the designers) and other vendors have at least considered it.
   
(iv) Optimized Foreign Key Joins.
Most queries in multidimensional tables entail joins between a central ``fact table'' (e.g. sales detail) and a set of dimension tables (e.g. store description, product description, customer description). These are known as “foreign key joins” since the customer identifier in the sales table, for example, is a key of the customer description table. (A key is a value belonging to an attribute such that only one record has that value in the attribute.) One way to accelerate these joins is to create a linkage between fact table records and dimension records. This can be done in three basic ways 
(a)	create an index that holds fact table record identifiers and dimension table record identifiers;
(b)	create bidirectional pointers between fact table records and dimension table rows  -- this is what "object-oriented" databases do
(c)	replace the customer record identifiers in the fact table by offsets into the dimension tables. 
Choice (a) is the most independent of changes in the physical organization of the tables and therefore is best for heavily updated systems, because changes to the dimension table can be reflected in the index to that table alone. Choice (b) is the least flexible to physical reorganization, because reorganizing a dimension table would entail updating the fact table. Choice (c) is a compromise of the two in that certain physical reorganizations can be done to the dimension tables (e.g. changing its position on disk) without changing the fact table.
   
(v) Approximating the Result
Since most people use data warehouses to get strategic aggregate information, many would be happy with a fast approximation as long as it has error bounds. Typical work in this area is the Aqua project at Lucent, led by Viswanath Poosala. That project shows how to estimate aggregate results in data warehouses while giving error bounds. The basic problem is that sampling all tables and then doing aggregates doesn't work in general. For example, if one wants to join R and S on their keys, then taking a 1/10 sample of each will give a size that is 1/100 of the size of the real join if the samples are random. So, one must be more clever. 

The basic idea in Aqua is to take an initial set of tables  R, S, T, ... that are linked by foreign key joins. Suppose  for example that R is the fact table and the others are  dimension tables. Take a sample of R and then perform all these foreign key joins based on the sample giving R', S', T', ... Now, if a query involves R, S, T and includes the foreign key links among these, then the query can be done with great accuracy on R', S', T'. The error can be estimated by considering the result obtained by several partitions of R' and looking at their variance. 
   
3. Some of the Most Relevant Patents
   
In the U.S. alone, query processing is a field in which many patents have appeared. Here I have identified those that are most relevant based on their abstracts. I have not read their bodies since I do not know Lafeyette's strategy so do not know specifically which are very relevant, but these patents and  their references may be good to check for similarities and inspiration.
   
Here is the approach I used.
   
The patent site is www.patents.ibm.com. I typed “query processing” in the search field after specifying the search over the full text. More than 600 patents matched this search. From those, I have selected this highly reduced list of relevant. My criteria for relevance are that I seek patents that give methods for rearranging the order of operations in query processing and for storing tables as a cache, especially for large databases.
   
US5864857: Method for processing multi-dimensional data
   
US5903888: Method and apparatus for using incompatible  types of indexes to process a single query
   
US5822747: System and method for optimizing database queries
   
US5819255: System and method for database query optimization
   
US5671403: Iterative dynamic programming system for  query optimization with bounded complexity
   
US5548755: System for optimizing correlated SQL queries in  a relational database using magic decorrelation
   
US5963936: Query processing system that computes GROUPING SETS,  ROLLUP, and CUBE with a reduced number of GROUP BYs in a query graph
   
US5855012: Simplification of SQL queries using generalized inference  propagation and generalized transitive closure
   
US5752017: Method and apparatus for executing complex SQL queries using  projection operations
   
US5724568: Reordering complex SQL queries containing inner and outer join  operations using hypergraphs and required sets
   
US5761657: Global optimization of correlated subqueries and exists predicates
   
US5590324: Optimization of SQL queries using universal quantifiers, set  intersection, and max/min aggregation in the presence of nullable columns
   
US5548754: Optimization of SQL queries using early-out join transformations
   
US5890151: Method and system for performing partial-sum queries on a data cube
   
US5870752: Incremental maintenance of an approximate histogram in  a database system
   
4. Competitive Companies
   
Most small competitors in the data warehousing arena offer a new database management system as their primary product. Customers are wary of such products because databases are the customer enterprises' life blood. A database vendor that is here today and gone tomorrow can render this life blood inaccessible. By contrast, buying hardware is much less of a risk. If a corporation buys a monitor from a vendor that later goes out of business, the only consequence is that the next monitor will have to come from somewhere else -- repairs are not an issue in our throw-away age.
   
Lafeyette is different from these other database vendors in that 
   
(i) it keeps the data in the database of record (say, Oracle)
   
(ii) it doesn't change the user’s access to this database
   
So, a customer can reason as follows: "Even if Lafeyette goes out of business, my data and applications are safe. I may have to buy more hardware or eliminate some queries, but I'm still very much in business."
   
Most companies that start with Lafeyette's philosophy abandon it at least partly, however. They see that they can get so much better performance by offering a new database management system. The temptation -- in the form of energetic technical staff and potential customer demand -- proves too great. So, they end up offering two products. This has happened for example in the case of the company TimesTen www.timesten.com. TimesTen produces a main memory cache for a variety of backend databases. The basic idea used to be that as long as the database resides in main memory (RAM) the queries go to TimesTen. Tables outside of main memory use the normal database. In either case, the database of record remains the backend database (say, Oracle) and TimesTen serves only as a high-speed intermediary. Now, TimesTen offers one product (TimesTen) that loads from Oracle and but runs the TimesTen subset of SQL and is meant to stand alone. They continue to offer another product that uses their technology but automatically keeps the corporate database up to date (FrontTier) -- I don't know how frequently. FrontTier makes TimesTen a direct competitor of Lafeyette for databases up to a few gigabytes in size.
   
The main large player in software-based relational data warehousing is RedBrick, now part of  Informix. Redbrick offers both expressibility and speed. They offer expressibility through extensions to SQL, e.g. year-to-year sales comparisons, running sums, and bucketing (e.g. group products into high sellers, medium sellers, and low sellers).  They offer high speed through optimization for star and snowflake schemas. Recall that a star schema is one in which a large central table called the fact table (e.g. every sale) is linked to a set of dimension tables (e.g. giving detail of the location of the store, the vendor of the product sold etc.). A snowflake schema has several central tables (e.g. in an insurance application, accident reports may be one central table and policy sales may be another). Redbrick offers  two special kinds of indexes (whose details will only be clear when a book comes out that describes them this coming autumn) called  targetindexes and starindexes. Both of these are multitable indexes (meaning they relate data in multiple tables) that mix bit vector and B tree capabilities.
   
Having said all this, I should point out that Microsoft SQL Server seems to be winning the TPCH benchmarks for 100 gigabytes or less. Informix (and Redbrick) come into their own at 300 gigabytes. As a side note, IBM seems to have the best hardware (http://www.tpc.org/new_result/h-ttperf.idc).
   
There are two other data warehouse that should be mentioned simply because of their market share.
   
Teradata produces huge systems holding several terabytes and built on special parallel hardware for very large customers such as Walmart, Delta, Royal Bank of Canada, large hospitals, the express mail services and so on. Their basic strategy is to partition their data horizontally (so the rows of each table are partitioned across many different sites). This permits them to divide the work of processing queries across many sites. Their current strategy is to support what they call ``Active Data Warehouses'' wherein their large databases are queried for day-to-day decisions. For example, consider a frequent flier on an airline X who encounters two late flights in two weeks. An active data warehouse will contact that customer and offer him perks, because data mining on the data warehouse reveals that customers having bad experiences in a short period of time are at risk of switching to another airline.
   
Arbor software, now part of Hyperion, presents a non-relational implementation that stores multi-dimensional data as a multi-dimensional matrix (this is called MOLAP in contrast to relational approaches that are called  ROLAP). As discussed above, the difficulty is that this matrix could be sparse, so Hyperion  uses a B-tree style index for sparse attributes. The system is for small databases and basically provides an extension to Excel. 

Conclusion

Most of the techniques used by other vendors (except for table caching) involve changing the underlying database management system and/or the query processing engine. A technique that sits on top of a database management system is far more portable and therefore can have wider impact.

A small database company serving large data warehouses is entirely viable if it can offer high speed while leaving applications and the backend database intact. It is much harder to sell a new interface and a new storage system, because the customer’s perceived risk is too great. 

Technology References
   
General: Nick Kotidas, accompanying this document and  available in postscript, presents a very nice review.
   
Indexing
   
[1 bitmaps] Sybase IQ Indexes. In Sybase IQ Administration Guide,  Sybase IQ Collection.
   
[2 bitmaps] C.Y. Chan and Y .E. Ioannidis. Bitmap Index Design and Evaluation. ACM SIGMOD 1998.
   
[3 general source] S. Chaudhuri and U. Dayal. An Overview of Data Warehousing and OLAP Technology. ACM SIGMOD Record , 26(1):65-74, March 1997. 
   
[4 general indexing] Sunita Sarawagi. Indexing OLAP Data.  Data Engineering Bulletin 1996.
   
[5 spatial database index] A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 47-57, Boston, MA, June 1984.
   
[6 spatial database index with fast insertions] Cubetree -- a set of compressed R trees that permits fast insertions http://www.cs.umd.edu/~nick/projects/cubetree.html
   
[7 matrix-based indexing] Robert J. Earle. Arbor software corp oration, U.S. patent # 5359724, Oct 1994.
   
[8 sparse multiple index] T. Johnson and D. Shasha.  Some Approaches to Index Design for Cube Forests Issue: Supporting On-line Analytical Processing (editor: Daniel Barbara) March 1997  issue of the IEEE Data Engineering Bulletin http://www.research.microsoft.com/research/db/debull/ 

   
Table Caching [1] V. Harinarayan, A. Rajaraman, and J.D. Ullman.  Implementing data cubes efficiently In Proc. of the ACM SIGMOD, June 1996.
   
[2 optimal algorithm for selecting cached tables given updates]  Nick Rousopoulos and Yannis Kotidas Dynamat http://www.cs.umd.edu/~nick/papers/DynaMat.html
   
redbrick and oracle reference for multitable indexes from vldb98
   
Optimized Foreign Key Join
   
[1 offset approach to foregn keys] KDB product. http://www.kx.com
   
[2 direct pointer approach to foreign keys] http://www.exceloncorp.com/
   
Competition References
   
[1] TimesTen. http://www.timesten.com
   
[2] Redbrick Software. http://www.informix.com/redbrick
   
[3] Benchmark Results. http://www.tpc.org/new_result/h-ttperf.idc
   
[4] Teradata software. http://www.teradata.com/
   
[5] Arbor software now called Hyperion. http://www.hyperion.com/