kevy_index/advise.rs
1//! The observation half of the auto-declaration loop (the R4b
2//! autodeclare RFC): a refused query IS a complete
3//! declaration specification — the name convention carries the table
4//! and column, the verb and shape carry the kind, the catalog
5//! carries the type. This module is the pure structure both engine
6//! faces share: a bounded log written only on the refusal path, and
7//! the advice renderer that turns its entries into executable
8//! declaration commands. Locking belongs to the caller (the server
9//! wraps it in a mutex, the embedded store in its shard lock) — this
10//! crate stays synchronization-free like the rest of kevy-index.
11
12use crate::catalog::ValType;
13use crate::table::{TableCatalog, TableSpec};
14
15#[path = "advise_usage.rs"]
16mod usage;
17pub use usage::UsageCell;
18
19/// What shape of query was refused — the kind half of the derived
20/// declaration.
21///
22/// ```
23/// use kevy_index::{AdviseLog, AdviseShape};
24/// let mut log = AdviseLog::new();
25/// log.observe(b"t.at", AdviseShape::Range, &[]);
26/// // the shape is half the family key: the same name refused as MATCH is a new family
27/// log.observe(b"t.at", AdviseShape::Match, &[]);
28/// assert_eq!(log.entries().len(), 2);
29/// ```
30#[derive(Debug, Clone, PartialEq, Eq, Hash)]
31#[non_exhaustive]
32pub enum AdviseShape {
33 /// `RANGE`/`EQ` on an undeclared single-column path.
34 ///
35 /// ```
36 /// use kevy_index::{AdviseEntry, AdviseShape};
37 /// # let mut cat = kevy_index::TableCatalog::new();
38 /// # cat.create(kevy_index::parse_table_declare(&[
39 /// # b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
40 /// # b"COLUMN", b"at", b"i64", b"COLUMN", b"body", b"str", b"INDEX", b"at", b"range",
41 /// # ])?)?;
42 /// let a = AdviseEntry::new("t.at", AdviseShape::Range, 1).advice(&cat);
43 /// assert!(a.is_some_and(|a| a.contains("INDEX at range")));
44 /// # Ok::<(), Box<dyn std::error::Error>>(())
45 /// ```
46 Range,
47 /// `WHERE` naming these columns, in clause order, on a name with
48 /// no composite path.
49 ///
50 /// ```
51 /// use kevy_index::{AdviseEntry, AdviseShape};
52 /// # let mut cat = kevy_index::TableCatalog::new();
53 /// # cat.create(kevy_index::parse_table_declare(&[
54 /// # b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
55 /// # b"COLUMN", b"at", b"i64", b"COLUMN", b"body", b"str", b"INDEX", b"at", b"range",
56 /// # ])?)?;
57 /// let shape = AdviseShape::Where(vec![b"body".to_vec(), b"at".to_vec()]);
58 /// let a = AdviseEntry::new("t.by_body", shape, 1).advice(&cat);
59 /// assert!(a.is_some_and(|a| a.contains("ORDERPATH by_body ON body THEN at")));
60 /// # Ok::<(), Box<dyn std::error::Error>>(())
61 /// ```
62 Where(Vec<Vec<u8>>),
63 /// `MATCH` on an undeclared text path.
64 ///
65 /// ```
66 /// use kevy_index::{AdviseEntry, AdviseShape};
67 /// # let mut cat = kevy_index::TableCatalog::new();
68 /// # cat.create(kevy_index::parse_table_declare(&[
69 /// # b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
70 /// # b"COLUMN", b"at", b"i64", b"COLUMN", b"body", b"str", b"INDEX", b"at", b"range",
71 /// # ])?)?;
72 /// let a = AdviseEntry::new("t.body", AdviseShape::Match, 1).advice(&cat);
73 /// assert!(a.is_some_and(|a| a.contains("FIELD body TYPE str KIND text")));
74 /// // only a str column can carry a text index
75 /// assert_eq!(AdviseEntry::new("t.at", AdviseShape::Match, 1).advice(&cat), None);
76 /// # Ok::<(), Box<dyn std::error::Error>>(())
77 /// ```
78 Match,
79 /// A clause naming a field the (existing) path does not store: a
80 /// `FILTER`, or `FIELDS` on a global index, which answers them from
81 /// its stored values.
82 ///
83 /// ```
84 /// use kevy_index::{AdviseEntry, AdviseShape};
85 /// # let mut cat = kevy_index::TableCatalog::new();
86 /// # cat.create(kevy_index::parse_table_declare(&[
87 /// # b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
88 /// # b"COLUMN", b"at", b"i64", b"COLUMN", b"body", b"str", b"INDEX", b"at", b"range",
89 /// # ])?)?;
90 /// let a = AdviseEntry::new("t.at", AdviseShape::Filter(b"body".to_vec()), 1).advice(&cat);
91 /// assert!(a.is_some_and(|a| a.starts_with("add VALUES body (type str)")));
92 /// # Ok::<(), Box<dyn std::error::Error>>(())
93 /// ```
94 Filter(Vec<u8>),
95}
96
97/// One observed refusal family: a (name, shape) pair, how often it
98/// was refused, and the first argv seen (the human-readable sample).
99/// `Clone` so a caller holding the log under a lock can snapshot
100/// entries out and render them lock-free.
101///
102/// ```
103/// use kevy_index::{AdviseEntry, AdviseShape};
104/// let e = AdviseEntry::new("t.at", AdviseShape::Range, 16);
105/// assert_eq!((e.count, e.sample.len()), (16, 0));
106/// ```
107#[derive(Debug, Clone, PartialEq, Eq, Hash)]
108#[non_exhaustive]
109pub struct AdviseEntry {
110 /// The access-path name the query asked for (`<table>.<suffix>`).
111 ///
112 /// ```
113 /// # use kevy_index::{AdviseLog, AdviseShape};
114 /// let mut log = AdviseLog::new();
115 /// log.observe(b"orders.at", AdviseShape::Range, &[]);
116 /// assert_eq!(log.entries()[0].name, b"orders.at");
117 /// ```
118 pub name: Vec<u8>,
119 /// The refused shape.
120 ///
121 /// ```
122 /// # use kevy_index::{AdviseLog, AdviseShape};
123 /// let mut log = AdviseLog::new();
124 /// log.observe(b"orders.body", AdviseShape::Match, &[]);
125 /// assert_eq!(log.entries()[0].shape, AdviseShape::Match);
126 /// ```
127 pub shape: AdviseShape,
128 /// Refusals observed for this family.
129 ///
130 /// ```
131 /// # use kevy_index::{AdviseLog, AdviseShape};
132 /// let mut log = AdviseLog::new();
133 /// log.observe(b"orders.at", AdviseShape::Range, &[]);
134 /// log.observe(b"orders.at", AdviseShape::Range, &[]);
135 /// assert_eq!(log.entries()[0].count, 2);
136 /// ```
137 pub count: u64,
138 /// The first refused argv, verbatim.
139 ///
140 /// ```
141 /// # use kevy_index::{AdviseLog, AdviseShape};
142 /// let mut log = AdviseLog::new();
143 /// let first = [b"RANGE".to_vec(), b"orders.at".to_vec()];
144 /// log.observe(b"orders.at", AdviseShape::Range, &first);
145 /// log.observe(b"orders.at", AdviseShape::Range, &[b"EQ".to_vec()]);
146 /// assert_eq!(log.entries()[0].sample, first, "later argvs only count");
147 /// ```
148 pub sample: Vec<Vec<u8>>,
149}
150
151impl AdviseEntry {
152 /// Render one observed family as the declaration command that would
153 /// have served it — executable verbatim, or `None` when the catalog
154 /// cannot ground it (unknown table / column: the query itself was
155 /// malformed, not under-declared).
156 #[must_use]
157 ///
158 /// ```
159 /// use kevy_index::{AdviseEntry, AdviseShape, TableCatalog, parse_table_declare};
160 /// let mut cat = TableCatalog::new();
161 /// cat.create(parse_table_declare(&[
162 /// b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
163 /// b"COLUMN", b"at", b"i64",
164 /// ])?)?;
165 /// let e = AdviseEntry::new("t.at", AdviseShape::Range, 3);
166 /// assert!(e.advice(&cat).is_some_and(|a| a.contains("INDEX at range")));
167 /// # Ok::<(), Box<dyn std::error::Error>>(())
168 /// ```
169 pub fn advice(&self, cat: &TableCatalog) -> Option<String> {
170 advice_of(self, cat)
171 }
172
173 /// Family `(name, shape)` refused `count` times, with no sample argv.
174 ///
175 /// ```
176 /// use kevy_index::{AdviseEntry, AdviseShape};
177 /// assert_eq!(AdviseEntry::new("t.body", AdviseShape::Match, 1).name, b"t.body");
178 /// ```
179 pub fn new(name: impl Into<Vec<u8>>, shape: AdviseShape, count: u64) -> AdviseEntry {
180 AdviseEntry { name: name.into(), shape, count, sample: Vec::new() }
181 }
182}
183
184/// The bounded refusal log. Insertion-ordered; when full, the entry
185/// with the SMALLEST count makes room (a family that keeps being
186/// refused defends its seat).
187///
188/// ```
189/// use kevy_index::{AdviseLog, AdviseShape};
190/// let mut log = AdviseLog::with_cap(2);
191/// assert_eq!(log.observe(b"t.a", AdviseShape::Range, &[]), 1);
192/// assert_eq!(log.observe(b"t.a", AdviseShape::Range, &[]), 2);
193/// log.observe(b"t.b", AdviseShape::Range, &[]);
194/// // full: the new family evicts the least-refused one, `t.b`
195/// log.observe(b"t.c", AdviseShape::Range, &[]);
196/// let names: Vec<_> = log.entries().iter().map(|e| e.name.clone()).collect();
197/// assert_eq!(names, [b"t.a".to_vec(), b"t.c".to_vec()]);
198/// log.clear();
199/// assert!(log.entries().is_empty());
200/// ```
201#[derive(Debug)]
202pub struct AdviseLog {
203 entries: Vec<AdviseEntry>,
204 cap: usize,
205}
206
207/// [`AdviseLog::new`] — NOT an all-zeroes log: a derived default
208/// would set `cap = 0`, which `with_cap` clamps away for a reason.
209impl Default for AdviseLog {
210 fn default() -> Self {
211 Self::new()
212 }
213}
214
215/// How many refusal families the default log retains.
216///
217/// ```
218/// use kevy_index::{ADVISE_CAP, AdviseLog, AdviseShape};
219/// let mut log = AdviseLog::new();
220/// for i in 0..=ADVISE_CAP {
221/// log.observe(format!("t.c{i}").as_bytes(), AdviseShape::Range, &[]);
222/// }
223/// assert_eq!(log.entries().len(), ADVISE_CAP);
224/// ```
225pub const ADVISE_CAP: usize = 128;
226
227/// Refusals a family must accumulate before the auto loop declares
228/// for it (tables that opted in via `AUTODECLARE <n>`). Empirical
229/// knob, not a derivation.
230///
231/// ```
232/// use kevy_index::{AUTODECLARE_AFTER, AdviseLog, AdviseShape};
233/// let mut log = AdviseLog::new();
234/// let n = (0..AUTODECLARE_AFTER).map(|_| log.observe(b"t.at", AdviseShape::Range, &[])).last();
235/// assert_eq!(n, Some(AUTODECLARE_AFTER), "the refusal that crosses the threshold");
236/// ```
237pub const AUTODECLARE_AFTER: u64 = 16;
238
239pub(crate) fn apply_auto(spec: &mut TableSpec, e: &AdviseEntry) -> Option<Vec<u8>> {
240 if spec.auto_added.len() >= spec.autodeclare {
241 return None;
242 }
243 let dot = e.name.iter().position(|&b| b == b'.')?;
244 let (table, suffix) = (&e.name[..dot], &e.name[dot + 1..]);
245 if table != spec.name {
246 return None;
247 }
248 let entry = auto_entry(spec, &e.name, suffix, &e.shape)?;
249 spec.auto_added.push(entry.clone());
250 Some(entry)
251}
252
253/// [`apply_auto`]'s shape half: mutate the declaration and return the
254/// ledger entry, or `None` when the shape does not ground.
255fn auto_entry(
256 spec: &mut TableSpec,
257 name: &[u8],
258 suffix: &[u8],
259 shape: &AdviseShape,
260) -> Option<Vec<u8>> {
261 match shape {
262 AdviseShape::Range => {
263 spec.column_type(suffix)?;
264 if spec.indexes.iter().any(|ix| ix.column == suffix) {
265 return None;
266 }
267 spec.indexes.push(crate::table::TableIndex {
268 column: suffix.to_vec(),
269 kind: crate::IndexKind::Range,
270 values: Vec::new(),
271 });
272 Some(name.to_vec())
273 }
274 AdviseShape::Where(cols) => {
275 for c in cols {
276 spec.column_type(c)?;
277 }
278 if cols.is_empty() || spec.orderpaths.iter().any(|op| op.name == suffix) {
279 return None;
280 }
281 let on = cols.iter().map(|c| (c.clone(), kevy_text::SortOrder::Asc)).collect();
282 spec.orderpaths.push(crate::table::OrderPath::new(suffix, on));
283 Some(name.to_vec())
284 }
285 AdviseShape::Filter(field) => {
286 spec.column_type(field)?;
287 let ix = spec.indexes.iter_mut().find(|ix| ix.column == suffix)?;
288 if ix.values.iter().any(|v| v == field) {
289 return None;
290 }
291 ix.values.push(field.clone());
292 let mut entry = name.to_vec();
293 entry.push(b'#');
294 entry.extend_from_slice(field);
295 Some(entry)
296 }
297 AdviseShape::Match => None,
298 }
299}
300
301impl AdviseLog {
302 /// An empty log with the default capacity.
303 #[must_use]
304 pub fn new() -> Self {
305 Self::with_cap(ADVISE_CAP)
306 }
307
308 /// An empty log retaining at most `cap` families.
309 #[must_use]
310 pub fn with_cap(cap: usize) -> Self {
311 Self { entries: Vec::new(), cap: cap.max(1) }
312 }
313
314 /// Record one refusal, returning the family's count AFTER this
315 /// observation — the auto loop's threshold input. Families
316 /// deduplicate on (name, shape); a full log evicts its
317 /// least-refused family for a NEW one (an existing family always
318 /// just counts).
319 pub fn observe(&mut self, name: &[u8], shape: AdviseShape, argv: &[Vec<u8>]) -> u64 {
320 if let Some(e) = self.entries.iter_mut().find(|e| e.name == name && e.shape == shape) {
321 e.count += 1;
322 return e.count;
323 }
324 if self.entries.len() >= self.cap {
325 let (weakest, _) = self
326 .entries
327 .iter()
328 .enumerate()
329 .min_by_key(|(_, e)| e.count)
330 .expect("cap >= 1, so a full log is non-empty");
331 self.entries.swap_remove(weakest);
332 }
333 self.entries
334 .push(AdviseEntry { sample: argv.to_vec(), ..AdviseEntry::new(name, shape, 1) });
335 1
336 }
337
338 /// The observed families, most-refused first.
339 #[must_use]
340 pub fn entries(&self) -> Vec<&AdviseEntry> {
341 let mut v: Vec<&AdviseEntry> = self.entries.iter().collect();
342 v.sort_by(|a, b| b.count.cmp(&a.count).then_with(|| a.name.cmp(&b.name)));
343 v
344 }
345
346 /// Forget everything (declarations landed; the slate restarts).
347 pub fn clear(&mut self) {
348 self.entries.clear();
349 }
350}
351
352pub(crate) fn narrow_advice(spec: &TableSpec, margin: Option<i64>) -> Option<String> {
353 let w = spec.window.as_ref()?;
354 let margin = margin?;
355 if w.bucket <= 0 {
356 return None;
357 }
358 let narrow = margin - margin.rem_euclid(w.bucket);
359 if narrow <= 0 {
360 return None;
361 }
362 let new_span = (w.span - narrow).max(w.bucket);
363 if new_span >= w.span {
364 return None;
365 }
366 Some(format!(
367 "WINDOW {} SPAN {} — every observed query kept a margin of {}; SPAN {} still serves them",
368 String::from_utf8_lossy(&w.column),
369 w.span,
370 margin,
371 new_span
372 ))
373}
374
375pub(crate) fn advice_of(e: &AdviseEntry, cat: &TableCatalog) -> Option<String> {
376 let dot = e.name.iter().position(|&b| b == b'.')?;
377 let (table, suffix) = (&e.name[..dot], &e.name[dot + 1..]);
378 let t = cat.get(table)?;
379 let show = |b: &[u8]| String::from_utf8_lossy(b).into_owned();
380 match &e.shape {
381 AdviseShape::Range => {
382 let ty = t.column_type(suffix)?;
383 Some(format!(
384 "TABLE.DECLARE {} … INDEX {} range (column type {})",
385 show(table),
386 show(suffix),
387 ty.tag()
388 ))
389 }
390 AdviseShape::Where(cols) => {
391 for c in cols {
392 t.column_type(c)?;
393 }
394 let list = cols.iter().map(|c| show(c)).collect::<Vec<_>>().join(" THEN ");
395 Some(format!("TABLE.DECLARE {} … ORDERPATH {} ON {}", show(table), show(suffix), list))
396 }
397 AdviseShape::Match => {
398 let ty = t.column_type(suffix)?;
399 (ty == ValType::Str).then(|| {
400 format!(
401 "IDX.CREATE {} ON PREFIX {} FIELD {} TYPE str KIND text",
402 show(&e.name),
403 show(&t.prefix),
404 show(suffix)
405 )
406 })
407 }
408 AdviseShape::Filter(field) => {
409 let ty = t.column_type(field)?;
410 Some(format!(
411 "add VALUES {} (type {}) to the {} declaration",
412 show(field),
413 ty.tag(),
414 show(&e.name)
415 ))
416 }
417 }
418}
419
420impl TableSpec {
421 /// Apply one refused family to the table's declaration — the auto
422 /// half of the loop, shared by both faces so they cannot derive
423 /// different declarations. Returns the ledger entry recorded in
424 /// `auto_added` (`path` or `path#field`); `None` when the budget is
425 /// spent, the shape is not one a table declaration serves (`MATCH`
426 /// stays advise-only — a text index carries knobs the loop must not
427 /// pick), the name does not ground, or it is already declared.
428 ///
429 /// ```
430 /// use kevy_index::{AdviseEntry, AdviseShape, parse_table_declare};
431 /// let mut t = parse_table_declare(&[
432 /// b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
433 /// b"COLUMN", b"at", b"i64", b"AUTODECLARE", b"1",
434 /// ])?;
435 /// let e = AdviseEntry::new("t.at", AdviseShape::Range, 16);
436 /// assert_eq!(t.apply_auto(&e), Some(b"t.at".to_vec()));
437 /// assert_eq!(t.apply_auto(&e), None, "the budget of one is spent");
438 /// # Ok::<(), Box<dyn std::error::Error>>(())
439 /// ```
440 pub fn apply_auto(&mut self, e: &AdviseEntry) -> Option<Vec<u8>> {
441 apply_auto(self, e)
442 }
443
444 /// The window-narrowing advice for one windowed table, given the
445 /// smallest probe margin any query on one of its paths has shown:
446 /// `Some` when every observed query kept more than a bucket of
447 /// margin, so SPAN can shrink by the bucket-aligned amount.
448 /// Advise-only — the window synthesis point; the engine never
449 /// narrows on its own.
450 #[must_use]
451 ///
452 /// ```
453 /// use kevy_index::parse_table_declare;
454 /// let t = parse_table_declare(&[
455 /// b"TABLE.DECLARE", b"t", b"PREFIX", b"t:", b"PK", b"id", b"COLUMN", b"id", b"i64",
456 /// b"COLUMN", b"at", b"i64", b"INDEX", b"at", b"range",
457 /// b"WINDOW", b"at", b"SPAN", b"100", b"BUCKET", b"10",
458 /// ])?;
459 /// assert_eq!(t.narrow_advice(None), None, "no query observed yet");
460 /// assert!(t.narrow_advice(Some(37)).is_some_and(|a| a.contains("SPAN 70")));
461 /// # Ok::<(), Box<dyn std::error::Error>>(())
462 /// ```
463 pub fn narrow_advice(&self, margin: Option<i64>) -> Option<String> {
464 narrow_advice(self, margin)
465 }
466}
467
468#[cfg(test)]
469#[path = "advise_tests.rs"]
470mod tests;