Data Inverted/Bitmap Indexing

Question 1

In querying data

Answer 1

All attributes in the predicate are not PKs or FKs - clearly they are secondary attribute

The simplest solution is to serial read table and apply contrived predicate on each row. Expensive if there’s a lot of data.

How can we use indexes to be more effective than a sequential scan.

Question 2

Solutions to Indexes in queries

Answer 2

Split queries to 2 and merge for common -> success depends on selectiveness

Split queries by column and merge for common -> high selectiveness required.

Question 3

Bitmap

Answer 3

• If an access request is not restricted to one PK attribute, simple direct access methods fail.

Bitmaps are an example of secondary index file structure. Convert search keys to a bit sequence related to a record or attribute instance.

Question 4

Secondary index file structure

Answer 4

Table for relating secondary key field values to a number of master file records that have value. Essential for queries on multiple attributes or sequence of joins.

Question 5

Bitmaps Variety

Answer 5

Fully inverted or Partially inverted indexes

Question 6

Fully inverted index

Answer 6

A file that inverts all the attributes of a data file into bitmap. Some implementations make data file online retention redundant.

Question 7

Partially inverted index

Answer 7

File structure that inverts only a subset of the data file attributes

Question 8

Building a bitmap

Answer 8

Every value in a record’s attribute is represented as a key and the supplementary value in the index is a list of record pointers that hold that value.

• Build by converting search keys into a boolean flag

Question 9

Bitmap Characteristics

Answer 9

• Compact
• Highly sparse
• Accept no unique value

Question 10

Pattern Matching with Bitmaps

Answer 10

efficient. Once read, a bitmap page is unpadded and querying offers huge gains. Inadequate if attribute to invert has many distinct values. Expect rows to have little changes in reference-look-up values

Question 11

Bitmap entries in covered indexes

Answer 11

Index Range Scan of an IOT: Oracle reads root node of index 1 and block in each branch 2+3 to find starting point of the range scan.

As row data is in IOT oracle needs to scan only leaf blocks 4,5,6 until all rows in range have been found.

More leaf blocks than normal index but less block reads overall.

Question 12

IOT meaning

Answer 12

index-organised-tables

Question 13

Queries that can be addressed by bitmaps include

Answer 13

• AND as intersection
• OR as Union
• NOT as compliment
• Minus (A and not B)

Question 14

How to get result bitmap

Answer 14

Each op takes 2 bitmaps of same size and applies the operation on corresponding bits

Question 15

Bitmap enhancements

Answer 15

Compression is possible (on strings of zero) to counter sparsity. Requires decompress on unpadding into RAM, and needs to be compressed before writing to disk.

Question 16

Bitmap Slips

Answer 16

A simple numeric exercise to show how the size of bitmaps (compared to Btrees) deteriorates with the number of distinct values in an attribute to invert

Map number of distinct keys against size of either index.

Question 17

Other file structures that support secondary index demands include:

Answer 17

• Bit pattern indexes
• A collection of B Trees based on sub strings of concatenated key strings
• Advanced data structures like grid files and R-Trees

Question 18

Factors of choosing other file structures:

Answer 18

• Speed/Access requirements
• Volumetric of master file
• Secondary key field size
• Secondary Key field data distribution
• Resilience requirement