CSE Roadmap

Specialist tier · about 2 hours · 5 parts

Part 5 of 5 · 3 min read

Exercises

Easy

Easy 1: Name the two Bloom filter answers (15 minutes)

State the two possible answers a Bloom filter can give for a key.

Done when: "definitely not present" and "possibly present" are both correctly named.

Hint

"Definitely not present" and "possibly present."

Easy 2: Name which error type is impossible (15 minutes)

State whether a Bloom filter can produce a false positive, a false negative, or both.

Done when: false positives possible, false negatives impossible, is correctly stated.

Hint

False positives are possible; false negatives are impossible.

Easy 3: Name what a bitmap index suits (15 minutes)

State the kind of column a bitmap index is well-suited for.

Done when: low-cardinality columns, with only a few distinct values, are correctly named.

Hint

Low-cardinality columns, meaning columns with only a small number of distinct possible values.

Medium

Medium 1: Explain why a Bloom filter's "no" can be trusted (25 minutes)

Explain why it is safe to skip checking an SSTable entirely when its Bloom filter answers "definitely not present."

Done when: the explanation correctly notes a Bloom filter never gives a false "definitely not present" for a key that was actually inserted.

Hint

A Bloom filter is built so that a real, inserted key always leaves its bits set, so "definitely not present" can never be wrong.

Medium 2: Explain why shared bits cause false positives (25 minutes)

Explain, using the shared bit array, why a Bloom filter can say "possibly present" for a key that was never inserted.

Done when: the explanation correctly notes that different keys can set overlapping bits, causing an uninserted key's bits to all appear set by coincidence.

Hint

Different keys can happen to set overlapping bits in the shared array, so an uninserted key's bits can appear set purely by coincidence.

Medium 3: Decide between a B+-tree and a bitmap index (25 minutes)

A column holds only three possible values across a hundred million rows. Decide whether a B+-tree or a bitmap index fits this column better, and explain why.

Done when: a bitmap index is chosen, with the explanation correctly citing the small number of distinct values as the reason a B+-tree's structure would be comparatively wasteful.

Hint

A bitmap index, since only three distinct values exist, and a B+-tree's branching structure is built for distinguishing among many more distinct values than that.

Hard

Hard 1: Explain the benefit of checking a Bloom filter before an SSTable (30 minutes)

Explain why checking a Bloom filter first, before reading an SSTable from disk, can meaningfully speed up lookups in an LSM-tree with many SSTables.

Done when: the explanation correctly ties this to avoiding an expensive disk read for every SSTable that definitely does not contain the key, only reading the SSTables the filter cannot rule out.

Hint

Most SSTables can be ruled out instantly via their Bloom filters, so only the few SSTables the filter cannot rule out need an actual disk read.

Hard 2: Explain why false negatives would break correctness (35 minutes)

Explain what would go wrong if a Bloom filter could produce false negatives, in the context of deciding whether to skip an SSTable.

Done when: the explanation correctly notes that a false "definitely not present" would cause a real key to be skipped entirely, silently returning a wrong, incomplete result.

Hint

A real key would be wrongly reported as absent, causing the SSTable holding it to be skipped, and the query would silently return an incomplete, incorrect result.

Hard 3: Explain why a bitmap index does not fit a high-cardinality column (40 minutes)

Explain why a bitmap index is a poor fit for a column such as customer_id, which can take on millions of distinct values.

Done when: the explanation correctly notes that a bitmap index would need one bit-array per distinct value, so millions of distinct values would mean millions of mostly-empty bit-arrays, far less efficient than a B+-tree's structure for this case.

Hint

Millions of distinct values would require millions of separate bit-arrays, most of them nearly all zeros, wasting far more space and work than a B+-tree's tree structure would for the same column.