WAH (word-aligned hybrid), efficient bitmap index compress

WAH(word-aligned hybrid) is very efficent way to compress bitmap index. Of course we have another compression methods, but WAH compressed bitmap can be used to logcial operation without decompression, while other methods requrie decompression before we do any logical operatoin.

Summary of WAH

WAH compression is done in 32bit, both 31 and 30 bits are special meaning like below.

31 bit : Indicates literal(0) or fill(1)
30 bit : fill by(0) or by(1)
29 bit ~ 0 bit : just data bits like unsiged integer

31bit 
🠗  
00xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
 🠕 
30 bit

Example1

There are four 32bit groups and two 32bit are filled by 0

	1st 32bit	2nd 32bit	3rd 32bit	4th 32bit
31-bitgroups	40000380	00000000	00000000	001FFFFF
WAH compressed	40000380	80000002		001FFFFF

Decomposed 0x80000002

Please see to know how 31 and 30 bits are used in WAH

31 bit 1 / 30 bit 0	just 0	just 0	means 2
10000000	00000000	00000000	00000010

31 bit 1, so this 32 bit are fill
30 bit 0, so 32 bit are filed by 0
29 ~ 0 bit, it is 2.

Therefore, two 32bit are filed by 0
https://youtu.be/BsZJ51JoYU0

Very facny explanation of WAH

#References

• https://sdm.lbl.gov/fastbit/compression.html