qualia_core_db/q42/volume/
postings.rs1use 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
25fn invalid(message: impl Into<String>) -> io::Error {
27 io::Error::new(io::ErrorKind::InvalidData, message.into())
28}
29
30#[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 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 pub fn contains_subject(&self, value: u64) -> bool {
62 self.subjects.binary_search(&value).is_ok()
63 }
64 pub fn contains_predicate(&self, value: u64) -> bool {
66 self.predicates.binary_search(&value).is_ok()
67 }
68 pub fn contains_context(&self, value: u64) -> bool {
70 self.contexts.binary_search(&value).is_ok()
71 }
72
73 pub fn posting_bytes(values: &[u64]) -> usize {
75 2 + encoded_delta_len(values)
76 }
77}
78
79pub 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
89fn 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
108pub 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
122fn 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
166pub 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#[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
230pub(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#[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
284fn sort_unique(values: &mut Vec<u64>) {
286 values.sort_unstable();
287 values.dedup();
288}
289
290fn 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
302fn 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
311fn 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
326fn 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
336fn 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
354fn 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
362fn 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
371fn 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
384pub 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 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(§ion, 2).unwrap();
447 let payload = block_payload(§ion, 1).unwrap();
448 assert!(field_may_contain(payload, 0, 7).unwrap());
449 assert!(!field_may_contain(payload, 0, 1).unwrap());
450 assert!(block_payload(§ion, 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(§ion, 2).is_err());
463 assert!(block_payload(§ion, 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}