This
is a motivation for also considering partitioning schemes that favor replication such
as strategies based on the partition and replicate strategy (PRS) of Yu et al. (1989),
which partitions a single relation and replicates all others to process joins without
repartitioning requirements.
Another relevant approach to reduce both the amount of repartitioning and also
of local processing at each node is to apply early-selection strategies. These apply
selection conditions as early as possible to datasets so that much less tuples need
to be processed and exchanged. A bitmap index (Chan & Ioannidis, 1998) contains
one bitmap per possible value of a given attribute (or a coded bitmap with b bits
for 2b possible values); the bitmap consists of one bit (or code) per row to indicate
whether or not that row matches the respective attribute value. Chan and Ioannidis
Efficient and Robust Node-Partitioned Data Warehouses 20
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
(1998) describe and analyze the use of bitmap indexes. When accessing a relation
to answer a query, bitmaps are read and bitwise-operated (e.g., logical AND of
bitmaps) to determine which relation tuples qualify for the query before even reading
the relation itself. All processing and data exchanging is then applied to this
reduced subset of tuples.
Pages:
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400