Table 1 shows an SBI on
status and product-category for 5 tuples with two bitmap vectors for status and five
for product-category. These indexes can be interpreted as follows: tuple number 2
Table 1. Example of two simple bitmap indexes
status product-category
Tuple Bs Bb B1 B2 B3 B4 B5
1 1 0 0 1 0 0 0
2 1 0 0 0 0 0 1
3 1 0 0 0 0 1 0
4 0 1 1 0 0 0 0
5 1 0 0 0 1 0 0
Indexing in Data Warehouses 8
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
corresponds to a shipped order (Bs is set) with product-category 5 (B5 is set). To
illustrate query processing with an SBI, consider a simple SQL query that retrieves
all tuples corresponding to shipped orders for product category 5:
SELECT * FROM Inventory WHERE status = ???shipped??? AND product-category = ???5???
In order to evaluate this query using the example SBIs, a query optimizer takes the
bitmaps for ???status = shipped??? and ???product-category = 5??? and performs a logical
AND operation. Tuple 2 in Table 1 is the only tuple in the query answer.
We survey bitmap indexing techniques in the next section. Then we propose a
novel multidimensional indexing technique that precomputes attribute expressions
for data items and stores the results as bit strings. We study performance issues for
this technique and a comparable bitmap index and recommend scenarios where one
may be preferable to the other.
Pages:
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353