Hash, Bitmap, GiST, GIN, BRIN — এক index-এর জুগলবন্দি না

import random, time


class BitmapIndex:
    """value → postings-bitmap (Python big-int); AND/OR/NOT algebra"""

    def __init__(self):
        self.postings = {}                     # value → int (bit i = row i)

    def build(self, column):
        for rid, val in enumerate(column):
            self.postings[val] = self.postings.get(val, 0) | (1 << rid)

    def eq(self, val):
        return self.postings.get(val, 0)

    @staticmethod
    def count(bits):
        return bin(bits).count('1')


if __name__ == '__main__':
    N = 50_000
    random.seed(7)
    region = [random.choice(('asia', 'eu', 'us', 'sa', 'af')) for _ in range(N)]
    status = [random.choice(('new', 'paid', 'ship')) for _ in range(N)]
    ri, si = BitmapIndex(), BitmapIndex()
    t0 = time.perf_counter(); ri.build(region); si.build(status)
    print(f'build 2 indexes over {N:,} rows: {(time.perf_counter() - t0) * 1000:.1f} ms')

    q_and = ri.eq('asia') & si.eq('new')               # AND — word-parallel
    brute = sum(r == 'asia' and s == 'new' for r, s in zip(region, status))
    assert BitmapIndex.count(q_and) == brute
    est = BitmapIndex.count(ri.eq('asia')) * BitmapIndex.count(si.eq('new')) / N
    print(f"asia AND new : exact={brute}  independence-estimate={est:.0f}"
          f"  ({abs(est - brute) / brute * 100:.1f}% error)")

    q_or = ri.eq('asia') | ri.eq('eu')                 # OR
    assert BitmapIndex.count(q_or) == region.count('asia') + region.count('eu')
    q_not = ((1 << N) - 1) ^ si.eq('new')              # NOT — full-mask xor
    assert BitmapIndex.count(q_not) == sum(x != 'new' for x in status)
    print(f"OR asia|eu = {BitmapIndex.count(q_or):,}   "
          f"NOT new = {BitmapIndex.count(q_not):,}")

    t0 = time.perf_counter()
    for _ in range(200):
        BitmapIndex.count(ri.eq('us') & si.eq('paid'))
    bm_us = (time.perf_counter() - t0) / 200 * 1e6
    t0 = time.perf_counter()
    for _ in range(200):
        sum(r == 'us' and s == 'paid' for r, s in zip(region, status))
    bf_ms = (time.perf_counter() - t0) / 200 * 1e3
    print(f"AND-query: bitmap {bm_us:.1f} µs vs row-scan {bf_ms:.2f} ms")

প্রত্যাশিত output (timing machine-ভেদে):

build 2 indexes over 50,000 rows: 52.8 ms
asia AND new : exact=3317  independence-estimate=3347  (0.9% error)
OR asia|eu = 20,052   NOT new = 33,249
AND-query: bitmap 132 µs vs row-scan 3.63 ms

তিনটা পাঠ: ৫০k-row AND-এর উত্তর µs-এ (row-scan-এর ~৩০× দ্রুত); independence- estimate এখানে প্রায় নিখুঁত কারণ columns সত্যিই independent — বাস্তবে correlated columns-এ error দশ-শতাংশ ছাড়ায় (optimizer-এর misestimate-এর উৎস); আর bitmap-approach জেতে যখন predicate-গুলো আগে থেকে indexed — নইলে build-cost একাই scan-কে হারায়।

নিজে বাড়ান: (১) run-length encode (roaring-bitmap ভাবনা) — sparse data-তে memory কত বাঁচে মাপুন; (২) third column যোগ করে correlated pair বানান (status=factory-dependent) — estimate-error বাড়ে দেখুন; (৩) top-k combination search — কোন AND-combination সবচেয়ে selective?