mq-db 0.1.8

Markdown-specialized embedded database with interval-indexed block storage and hierarchical query support
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

# Index Layers

`mq-db` applies three complementary index layers, cheapest-first:

```text
SQL Query
   │
   ▼
Layer 1 — Zone Maps (document skip) ────skip───▶ ✗ irrelevant docs
   │ relevant docs
   ▼
Layer 2 — Interval Index (section scope)
   │ candidate blocks
   ▼
Layer 3 — Secondary Indexes (block lookup)
   │  BitmapIndex · BTreeIndex · HashIndex
   │  (no hint ──▶ Full Scan)
   ▼
Result Rows
```

## Layer 1 — Zone Maps (document-level skip)

Built once per document and stored in the `.mq-db` file. Checked before any block is read.

**Via SQL** — `SqlEngine` derives a skip automatically from the `WHERE` clause, for a single, non-`JOIN`ed `SELECT ... FROM blocks`:

| `WHERE` conjunct | Skips documents where… |
| --- | --- |
| `lang = 'X'` | `code_languages` doesn't contain `X` |
| `depth = N` (`N > 0`) | `N` exceeds `max_heading_depth` |
| `block_type = 'heading' AND content = 'X'` | `heading_contents` has no case-insensitive match for `X` |

**Via the Rust API** — `store.query().documents(|doc| ...)` lets you filter on *any* zone-map field yourself (`heading_slugs`, `frontmatter_keys`, `title`, `tags`, …), not just the patterns `SqlEngine` recognizes automatically.

## Layer 2 — Interval Index (section hierarchy)

Heading hierarchy is encoded as `(pre, post)` pairs via Pre-Post Order (Nested Set) traversal:

```text
# Doc                 pre=0  · post=11
├── ## Section A      pre=2  · post=7
│   ├── Paragraph     pre=3  · post=4
│   └── Code          pre=5  · post=6
└── ## Section B      pre=8  · post=11
    └── Paragraph     pre=9  · post=10
```

`A is_under B` ↔ `B.pre < A.pre AND A.post < B.post` — `O(1)`, no tree traversal. This is exactly what the SQL [`under()`](sql-functions.md) function and the Rust `.under_heading()` query-builder method check.

## Layer 3 — Secondary Indexes (block-level fast lookup)

| Index | Column(s) | Structure | Complexity |
| --- | --- | --- | --- |
| `BitmapIndex` | `block_type` | Inverted list per type | `O(1)` key + `O(k)` iterate |
| `BTreeIndex` | `pre`, `post` | `BTreeMap` | `O(log n)` point, `O(log n + k)` range |
| `HashIndex` | `content`, `lang`, `depth` | `HashMap` | `O(1)` average |

SQL predicate pushdown picks an `IndexHint` based on the shape of the `WHERE` predicate:

| `WHERE` predicate | Index used |
| --- | --- |
| `block_type = '...'` | `BitmapIndex` |
| `pre = N` | `BTreeIndex` (point lookup) |
| `pre BETWEEN N AND M` | `BTreeIndex` (range scan) |
| `content = '...'` | `HashIndex` |
| `lang = '...'` | `HashIndex` |
| `depth = N` | `HashIndex` |
| anything else | Full scan |