Matches = AllOnes(r)
foreach attribute A with index {
   // select ith bit-string for attribute A
   // based on value associated with A in WHERE
   Matches = Matches & Bitmaps[A][i]
}
// Matches contains 1-bit for each matching tuple
foreach i in 0..r {
   if (Matches[i] == 0) continue;
   t = fetchTuple(i)
   Results = Results ∪ {t}
}