[prev] 20 [next]

Bit-sliced SIMC (cont)

Algorithm for evaluating pmr query using bit-sliced descriptors 

matches = ~0  //all ones
for each bit i set to 1 in desc(q) {
   slice = fetch bit-slice i
   matches = matches & slice
}
for each bit i set to 1 in matches {
   fetch page i
   scan page for matching records
}


Effective because desc(q) typically has less than half bits set to 1