Skip to main content

qualia_core_db/q42/volume/
postings.rs

1//! Compact per-block S/P/C membership for range pruning.
2//!
3//! Field min/max ranges are a weak first reject: any hash inside a wide interval
4//! still forces a SuperBlock decode. These postings are exact unique hashes,
5//! delta-varint encoded, so a bound subject/predicate/context either is present
6//! or the block is skipped. No false positives, no false negatives.
7//!
8//! A 256-byte Bloom is used only when unique hashes would be *larger* than that
9//! Bloom (measured per field). Blooms have no false negatives; measured FPR is
10//! reported by tests.
11
12use std::io;
13
14use crate::NQuin;
15
16pub const FIELD_POSTINGS_MAGIC: [u8; 4] = *b"PIDX";
17pub const FIELD_POSTINGS_HEADER_BYTES: usize = 16;
18pub const BLOOM_BYTES: usize = 256;
19pub const BLOOM_BITS: usize = BLOOM_BYTES * 8;
20pub const BLOOM_HASHES: usize = 4;
21
22const KIND_POSTINGS: u8 = 0;
23const KIND_BLOOM: u8 = 1;
24
25/// Wraps `message` as an `InvalidData` io error (corrupt section contents).
26fn invalid(message: impl Into<String>) -> io::Error {
27    io::Error::new(io::ErrorKind::InvalidData, message.into())
28}
29
30/// One SuperBlock's compact S/P/C membership.
31#[derive(Clone, Debug, Default, PartialEq, Eq)]
32pub struct BlockFieldPostings {
33    pub subjects: Vec<u64>,
34    pub predicates: Vec<u64>,
35    pub contexts: Vec<u64>,
36}
37
38impl BlockFieldPostings {
39    /// Collects the sorted-unique subject/predicate/context sets from a
40    /// block's quins.
41    pub fn from_quins(quins: &[NQuin]) -> Self {
42        let mut subjects = Vec::with_capacity(quins.len());
43        let mut predicates = Vec::with_capacity(quins.len());
44        let mut contexts = Vec::with_capacity(quins.len());
45        for quin in quins {
46            subjects.push(quin.subject);
47            predicates.push(quin.predicate);
48            contexts.push(quin.context);
49        }
50        sort_unique(&mut subjects);
51        sort_unique(&mut predicates);
52        sort_unique(&mut contexts);
53        Self {
54            subjects,
55            predicates,
56            contexts,
57        }
58    }
59
60    /// Exact membership test on the sorted subject set.
61    pub fn contains_subject(&self, value: u64) -> bool {
62        self.subjects.binary_search(&value).is_ok()
63    }
64    /// Exact membership test on the sorted predicate set.
65    pub fn contains_predicate(&self, value: u64) -> bool {
66        self.predicates.binary_search(&value).is_ok()
67    }
68    /// Exact membership test on the sorted context set.
69    pub fn contains_context(&self, value: u64) -> bool {
70        self.contexts.binary_search(&value).is_ok()
71    }
72
73    /// Encoded size if this field used exact postings.
74    pub fn posting_bytes(values: &[u64]) -> usize {
75        2 + encoded_delta_len(values)
76    }
77}
78
79/// Encode one SuperBlock's three fields. Chooses Bloom when it is strictly
80/// smaller than the exact posting list.
81pub fn encode_block_postings(postings: &BlockFieldPostings) -> Vec<u8> {
82    let mut out = Vec::new();
83    encode_field(&mut out, &postings.subjects);
84    encode_field(&mut out, &postings.predicates);
85    encode_field(&mut out, &postings.contexts);
86    out
87}
88
89/// Writes one field: `KIND_BLOOM` + 32-byte filter when it strictly beats the
90/// posting encoding (>8 values and longer than the bloom), else `KIND_POSTINGS`
91/// + count + delta-varints.
92fn encode_field(out: &mut Vec<u8>, values: &[u64]) {
93    let posting_len = BlockFieldPostings::posting_bytes(values);
94    if values.len() > 8 && posting_len > BLOOM_BYTES + 1 {
95        out.push(KIND_BLOOM);
96        let mut bloom = [0u8; BLOOM_BYTES];
97        for value in values {
98            bloom_insert(&mut bloom, *value);
99        }
100        out.extend_from_slice(&bloom);
101        return;
102    }
103    out.push(KIND_POSTINGS);
104    out.extend_from_slice(&(values.len() as u16).to_le_bytes());
105    encode_deltas(out, values);
106}
107
108/// Decode one SuperBlock payload into caller-owned hash scratch, then test
109/// membership without retaining the payload.
110pub fn field_may_contain(encoded: &[u8], field: usize, value: u64) -> io::Result<bool> {
111    let mut offset = 0usize;
112    for current in 0..3 {
113        let (next, present) = decode_field_contains(encoded, offset, value)?;
114        if current == field {
115            return Ok(present);
116        }
117        offset = next;
118    }
119    Err(invalid("field postings have fewer than three fields"))
120}
121
122/// Tests field membership at `offset`: exact decode for postings (delta
123    /// accumulation with overflow checks), probabilistic test for Bloom.
124    /// Returns `(next_offset, present)`; errors on truncation/unknown kind.
125fn decode_field_contains(encoded: &[u8], offset: usize, value: u64) -> io::Result<(usize, bool)> {
126    let kind = *encoded
127        .get(offset)
128        .ok_or_else(|| invalid("truncated field postings"))?;
129    match kind {
130        KIND_POSTINGS => {
131            if offset + 3 > encoded.len() {
132                return Err(invalid("truncated posting count"));
133            }
134            let count = u16::from_le_bytes([encoded[offset + 1], encoded[offset + 2]]) as usize;
135            let mut cursor = offset + 3;
136            let mut previous = 0u64;
137            let mut found = false;
138            for _ in 0..count {
139                let (delta, used) = decode_varint(&encoded[cursor..])?;
140                previous = previous
141                    .checked_add(delta)
142                    .ok_or_else(|| invalid("posting delta overflow"))?;
143                cursor = cursor
144                    .checked_add(used)
145                    .ok_or_else(|| invalid("posting cursor overflow"))?;
146                if previous == value {
147                    found = true;
148                }
149            }
150            Ok((cursor, found))
151        }
152        KIND_BLOOM => {
153            let end = offset
154                .checked_add(1 + BLOOM_BYTES)
155                .ok_or_else(|| invalid("bloom overflow"))?;
156            if end > encoded.len() {
157                return Err(invalid("truncated bloom filter"));
158            }
159            let bloom = &encoded[offset + 1..end];
160            Ok((end, bloom_may_contain(bloom, value)))
161        }
162        _ => Err(invalid("unknown field-postings kind")),
163    }
164}
165
166/// Encodes all blocks' postings into the PIDX section: a per-block offset
167/// table followed by each block's three-field payload.
168pub fn encode_postings_section(blocks: &[BlockFieldPostings]) -> Vec<u8> {
169    let mut payloads = Vec::with_capacity(blocks.len());
170    let mut offsets = Vec::with_capacity(blocks.len() + 1);
171    let mut cursor = 0u32;
172    offsets.push(0);
173    for block in blocks {
174        let payload = encode_block_postings(block);
175        cursor = cursor
176            .checked_add(payload.len() as u32)
177            .expect("field postings payload exceeds u32");
178        offsets.push(cursor);
179        payloads.push(payload);
180    }
181    let mut out = Vec::new();
182    out.extend_from_slice(&FIELD_POSTINGS_MAGIC);
183    out.extend_from_slice(&1u32.to_le_bytes());
184    out.extend_from_slice(&(blocks.len() as u32).to_le_bytes());
185    out.extend_from_slice(&0u32.to_le_bytes());
186    for offset in &offsets {
187        out.extend_from_slice(&offset.to_le_bytes());
188    }
189    for payload in payloads {
190        out.extend_from_slice(&payload);
191    }
192    out
193}
194
195/// Structural validation of a PIDX section: magic, version, block-count
196/// match, non-truncated offset table, payload-length consistency, and
197/// per-block payload decodability.
198#[cfg(any(not(target_arch = "wasm32"), test))]
199pub fn validate_postings_section(bytes: &[u8], expected_blocks: usize) -> io::Result<()> {
200    if bytes.len() < FIELD_POSTINGS_HEADER_BYTES {
201        return Err(invalid("field postings shorter than header"));
202    }
203    if bytes[0..4] != FIELD_POSTINGS_MAGIC {
204        return Err(invalid("field postings have bad magic"));
205    }
206    if u32::from_le_bytes(bytes[4..8].try_into().unwrap()) != 1 {
207        return Err(invalid("unsupported field postings version"));
208    }
209    let block_count = u32::from_le_bytes(bytes[8..12].try_into().unwrap()) as usize;
210    if block_count != expected_blocks {
211        return Err(invalid("field postings block count mismatch"));
212    }
213    let table_bytes = (block_count + 1)
214        .checked_mul(4)
215        .ok_or_else(|| invalid("field postings table overflow"))?;
216    let header_end = FIELD_POSTINGS_HEADER_BYTES + table_bytes;
217    if bytes.len() < header_end {
218        return Err(invalid("field postings offset table truncated"));
219    }
220    let last = u32::from_le_bytes(bytes[header_end - 4..header_end].try_into().unwrap()) as usize;
221    if bytes.len() != header_end + last {
222        return Err(invalid("field postings payload length mismatch"));
223    }
224    for block_index in 0..block_count {
225        let _ = block_payload(bytes, block_index)?;
226    }
227    Ok(())
228}
229
230/// Absolute byte interval of one SuperBlock's encoded PIDX payload, relative to
231/// the start of a complete PIDX section (header + offset table + payloads).
232pub(crate) fn block_payload_interval(
233    block_count: usize,
234    block_index: usize,
235    table_start: u32,
236    table_end: u32,
237) -> io::Result<(usize, usize)> {
238    if block_index >= block_count {
239        return Err(invalid("field postings block index out of range"));
240    }
241    if table_end < table_start {
242        return Err(invalid("field postings interval inverted"));
243    }
244    let table_bytes = (block_count + 1)
245        .checked_mul(4)
246        .ok_or_else(|| invalid("field postings table overflow"))?;
247    let payload_base = FIELD_POSTINGS_HEADER_BYTES
248        .checked_add(table_bytes)
249        .ok_or_else(|| invalid("field postings payload base overflow"))?;
250    let from = payload_base
251        .checked_add(table_start as usize)
252        .ok_or_else(|| invalid("posting payload start overflow"))?;
253    let to = payload_base
254        .checked_add(table_end as usize)
255        .ok_or_else(|| invalid("posting payload end overflow"))?;
256    Ok((from, to))
257}
258
259/// Slice one SuperBlock's encoded S/P/C membership out of an in-memory PIDX section.
260#[cfg(any(not(target_arch = "wasm32"), test))]
261pub fn block_payload<'a>(bytes: &'a [u8], block_index: usize) -> io::Result<&'a [u8]> {
262    if bytes.len() < FIELD_POSTINGS_HEADER_BYTES {
263        return Err(invalid("field postings shorter than header"));
264    }
265    let block_count = u32::from_le_bytes(bytes[8..12].try_into().unwrap()) as usize;
266    let table = FIELD_POSTINGS_HEADER_BYTES
267        .checked_add(
268            block_index
269                .checked_mul(4)
270                .ok_or_else(|| invalid("field postings table overflow"))?,
271        )
272        .ok_or_else(|| invalid("field postings table overflow"))?;
273    if bytes.len() < table + 8 {
274        return Err(invalid("field postings offset table truncated"));
275    }
276    let start = u32::from_le_bytes(bytes[table..table + 4].try_into().unwrap());
277    let end = u32::from_le_bytes(bytes[table + 4..table + 8].try_into().unwrap());
278    let (from, to) = block_payload_interval(block_count, block_index, start, end)?;
279    bytes
280        .get(from..to)
281        .ok_or_else(|| invalid("field postings payload slice out of range"))
282}
283
284/// Sorts `values` ascending and removes duplicates in place.
285fn sort_unique(values: &mut Vec<u64>) {
286    values.sort_unstable();
287    values.dedup();
288}
289
290/// Total byte length of `values` under delta-varint encoding (caller must
291/// pass sorted input).
292fn encoded_delta_len(values: &[u64]) -> usize {
293    let mut previous = 0u64;
294    let mut len = 0usize;
295    for value in values {
296        len += varint_len(value - previous);
297        previous = *value;
298    }
299    len
300}
301
302/// Appends each `value - previous` as a varint (sorted input assumed).
303fn encode_deltas(out: &mut Vec<u8>, values: &[u64]) {
304    let mut previous = 0u64;
305    for value in values {
306        encode_varint(out, value - previous);
307        previous = *value;
308    }
309}
310
311/// Appends `value` as a LEB128 varint (7 bits per byte, MSB continuation).
312fn encode_varint(out: &mut Vec<u8>, mut value: u64) {
313    loop {
314        let mut byte = (value & 0x7f) as u8;
315        value >>= 7;
316        if value != 0 {
317            byte |= 0x80;
318        }
319        out.push(byte);
320        if value == 0 {
321            return;
322        }
323    }
324}
325
326/// Byte length of `value` under LEB128 varint encoding.
327fn varint_len(mut value: u64) -> usize {
328    let mut len = 1;
329    while value > 0x7f {
330        value >>= 7;
331        len += 1;
332    }
333    len
334}
335
336/// Decodes one LEB128 varint; returns `(value, bytes_used)`. Errors on a
337/// shift exceeding 64 bits or a truncated sequence.
338fn decode_varint(bytes: &[u8]) -> io::Result<(u64, usize)> {
339    let mut value = 0u64;
340    let mut shift = 0u32;
341    for (index, byte) in bytes.iter().copied().enumerate() {
342        if shift >= 64 {
343            return Err(invalid("varint shift overflow"));
344        }
345        value |= u64::from(byte & 0x7f) << shift;
346        if byte & 0x80 == 0 {
347            return Ok((value, index + 1));
348        }
349        shift += 7;
350    }
351    Err(invalid("truncated varint"))
352}
353
354/// Sets the `BLOOM_HASHES` bits for `value` in the 256-bit filter.
355fn bloom_insert(bloom: &mut [u8], value: u64) {
356    for hash in bloom_hashes(value) {
357        let bit = (hash as usize) % BLOOM_BITS;
358        bloom[bit / 8] |= 1 << (bit % 8);
359    }
360}
361
362/// `true` when all of `value`'s hash bits are set — definite non-membership
363/// when `false`, possible membership when `true` (false positives possible).
364fn bloom_may_contain(bloom: &[u8], value: u64) -> bool {
365    bloom_hashes(value).into_iter().all(|hash| {
366        let bit = (hash as usize) % BLOOM_BITS;
367        bloom[bit / 8] & (1 << (bit % 8)) != 0
368    })
369}
370
371/// Four hash functions derived from `value` via two multiply-mix seeds —
372/// cheap double-hashing rather than four independent hashes.
373fn bloom_hashes(value: u64) -> [u64; BLOOM_HASHES] {
374    let mixed = value.wrapping_mul(0x9E37_79B9_7F4A_7C15);
375    let alt = (!value).wrapping_mul(0xBF58_476D_1CE4_E5B9);
376    [
377        mixed,
378        alt,
379        mixed.wrapping_add(alt),
380        mixed ^ alt.rotate_left(17),
381    ]
382}
383
384/// Measured false-positive rate of the Bloom encoding on a synthetic field.
385pub fn measure_bloom_false_positives(values: &[u64], probes: &[u64]) -> (usize, usize) {
386    let mut bloom = [0u8; BLOOM_BYTES];
387    for value in values {
388        bloom_insert(&mut bloom, *value);
389    }
390    let mut false_positives = 0usize;
391    let mut eligible = 0usize;
392    for probe in probes {
393        if values.binary_search(probe).is_ok() {
394            continue;
395        }
396        eligible += 1;
397        if bloom_may_contain(&bloom, *probe) {
398            false_positives += 1;
399        }
400    }
401    (false_positives, eligible)
402}
403
404#[cfg(test)]
405mod tests {
406    use super::*;
407
408    #[test]
409    fn exact_postings_have_no_false_positives() {
410        let quins = [quin(10, 1, 100), quin(20, 1, 101), quin(10, 2, 102)];
411        let postings = BlockFieldPostings::from_quins(&quins);
412        let encoded = encode_block_postings(&postings);
413        assert!(field_may_contain(&encoded, 0, 10).unwrap());
414        assert!(field_may_contain(&encoded, 0, 20).unwrap());
415        assert!(!field_may_contain(&encoded, 0, 99).unwrap());
416        assert!(field_may_contain(&encoded, 1, 2).unwrap());
417        assert!(!field_may_contain(&encoded, 1, 9).unwrap());
418    }
419
420    #[test]
421    fn bloom_is_chosen_when_it_is_smaller_and_has_no_false_negatives() {
422        let values: Vec<u64> = (0..400).map(|i| i * 1_000_003 + 17).collect();
423        let mut encoded = Vec::new();
424        encode_field(&mut encoded, &values);
425        assert_eq!(encoded[0], KIND_BLOOM);
426        for value in &values {
427            assert!(field_may_contain(&encoded, 0, *value).unwrap());
428        }
429        let probes: Vec<u64> = (0..2_000).map(|i| i * 97 + 3).collect();
430        let (fp, eligible) = measure_bloom_false_positives(&values, &probes);
431        assert!(eligible > 0);
432        // 256-byte / 4-hash Bloom on 400 items is compact; FPR must stay usable.
433        assert!(
434            (fp as f64) / (eligible as f64) < 0.35,
435            "bloom FPR too high: {fp}/{eligible}"
436        );
437    }
438
439    #[test]
440    fn section_round_trip_and_validation() {
441        let blocks = vec![
442            BlockFieldPostings::from_quins(&[quin(1, 2, 3)]),
443            BlockFieldPostings::from_quins(&[quin(4, 5, 6), quin(7, 5, 8)]),
444        ];
445        let section = encode_postings_section(&blocks);
446        validate_postings_section(&section, 2).unwrap();
447        let payload = block_payload(&section, 1).unwrap();
448        assert!(field_may_contain(payload, 0, 7).unwrap());
449        assert!(!field_may_contain(payload, 0, 1).unwrap());
450        assert!(block_payload(&section, 2).is_err());
451    }
452
453    #[test]
454    fn inverted_table_interval_is_rejected() {
455        let mut section = encode_postings_section(&[
456            BlockFieldPostings::from_quins(&[quin(1, 2, 3)]),
457            BlockFieldPostings::from_quins(&[quin(4, 5, 6)]),
458        ]);
459        let table = FIELD_POSTINGS_HEADER_BYTES;
460        section[table..table + 4].copy_from_slice(&8u32.to_le_bytes());
461        section[table + 4..table + 8].copy_from_slice(&0u32.to_le_bytes());
462        assert!(validate_postings_section(&section, 2).is_err());
463        assert!(block_payload(&section, 0).is_err());
464    }
465
466    fn quin(subject: u64, predicate: u64, context: u64) -> NQuin {
467        NQuin {
468            subject,
469            predicate,
470            object: 0,
471            context,
472            metadata: 0,
473            parity: 0,
474        }
475    }
476}