Host options

Bind, Budget, Explain and the context: how a Go host gives a query its values, caps its work, sees where the work went, and stops it. Then pages and tables, sharing a base, and where a parse error is.

A host runs a query with Eval, and passes options to it. This page covers the ones a host uses most. The Go tutorial builds the vocabulary and base they run against, and shows the fourth, Witnesses. Every code block here is a Go Example from docsite/examples/guide/, which go test runs on every build of this site and checks against its // Output: comment.

The examples share a source and a vocabulary, built the same way as in the tutorial, with a deps module of rules:

package guide_test

import (
	"github.com/panyam/jaala/datalog"
	"github.com/panyam/jaala/ns"
	"github.com/panyam/jaala/stdlib"
)

// deps ships the dependency rules as a module. A comment above a member's
// first rule is its doc. _step is private to the module: its own rules can
// call it, and a query can't.
const deps = `
# Everything a package depends on, directly or through others.
depends_on(?a, ?b) :- _step(?a, ?b);
depends_on(?a, ?c) :- depends_on(?a, ?b), _step(?b, ?c);

_step(?a, ?b) :- imports(?a, ?b);
`

// source serves the imports, and a pkg relation whose license column is
// absent where the package states none, which isn't the same as stating "".
func source() *ns.MemSource {
	src := ns.NewMemSource().
		Declare("imports", "from", "to").
		Declare("pkg", "name", "license")
	edges := [][2]string{{"app", "api"}, {"api", "log"}, {"log", "util"}}
	for _, e := range edges {
		src.Add("imports", ns.Tuple{Vals: []ns.Value{ns.S(e[0]), ns.S(e[1])}})
	}
	src.Add("pkg", ns.Tuple{Vals: []ns.Value{ns.S("app"), ns.S("MIT")}})
	src.Add("pkg", ns.Tuple{Vals: []ns.Value{ns.S("api"), ns.Absent()}})
	src.Add("pkg", ns.Tuple{Vals: []ns.Value{ns.S("log"), ns.S("")}})
	src.Add("pkg", ns.Tuple{Vals: []ns.Value{ns.S("util"), ns.S("Apache-2.0")}})
	return src
}

// vocabulary names everything a query can call, with the deps module.
func vocabulary(src ns.Source) (*ns.Vocabulary, error) {
	v, err := ns.NewVocabulary(src)
	if err != nil {
		return nil, err
	}
	if err := v.AddLanguage(datalog.Language); err != nil {
		return nil, err
	}
	if err := stdlib.Register(v); err != nil {
		return nil, err
	}
	err = v.AddModule("deps", datalog.LanguageName, deps, "deps.dl")
	if err != nil {
		return nil, err
	}
	return v, v.Check()
}

`Bind`, `Budget` and the context ¶

package guide_test

import (
	"context"
	"errors"
	"fmt"

	"github.com/panyam/jaala/datalog"
	"github.com/panyam/jaala/ns"
)

func base() *datalog.Base {
	src := source()
	v, err := vocabulary(src)
	if err != nil {
		panic(err)
	}
	b, err := datalog.NewBase(v, src)
	if err != nil {
		panic(err)
	}
	return b
}

// Bind gives a goal variable its value from Go. The answer still has the
// column, filled with the bound value, and binding a variable the goal
// doesn't use is an error rather than a silent no-op.
func Example_bind() {
	b, ctx := base(), context.Background()
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d`)
	rows, err := datalog.SemiNaive{}.Eval(ctx, q, b,
		datalog.Bind(map[datalog.Var][]ns.Value{"p": {ns.S("api")}}))
	for _, r := range rows {
		fmt.Println(r.Bind["p"].S, r.Bind["d"].S)
	}
	_, err = datalog.SemiNaive{}.Eval(ctx, q, b,
		datalog.Bind(map[datalog.Var][]ns.Value{"x": {ns.S("api")}}))
	fmt.Println(err)
	// Output:
	// api log
	// api util
	// query: cannot bind ?x: the goal does not use it
}

// Bound to several values, a variable ranges over them, so one Eval asks
// about every package in the set, and an aggregate counts across all of
// them. api and log both depend on util, and it's counted once.
func Example_bindSet() {
	b, ctx := base(), context.Background()
	set := datalog.Bind(map[datalog.Var][]ns.Value{"p": {ns.S("api"), ns.S("log")}})
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d`)
	rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, set)
	for _, r := range rows {
		fmt.Println(r.Bind["p"].S, r.Bind["d"].S)
	}
	q = datalog.MustParse(`deps.depends_on(?p, ?d) => count(distinct ?d)`)
	rows, _ = datalog.SemiNaive{}.Eval(ctx, q, b, set)
	fmt.Println(rows[0].Bind["count(distinct d)"].S)
	// Output:
	// api log
	// api util
	// log util
	// 2
}

// Budget caps the work one Eval may do, and Work says how much it did, so
// a host can size the budget from what its real queries need.
func Example_budget() {
	b, ctx := base(), context.Background()
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d`)
	rows, err := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Budget(10_000))
	fmt.Println(len(rows), "rows, error:", err)

	_, err = datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Budget(3))
	var over *datalog.BudgetExceeded
	fmt.Println(errors.As(err, &over), "limit", over.Limit)
	// Output:
	// 6 rows, error: <nil>
	// true limit 3
}

// The context reaches every Eval, so a host can stop a query that's taking
// too long, or whose caller went away. The error wraps the context's own.
func Example_cancel() {
	b := base()
	ctx, cancel := context.WithCancel(context.Background())
	cancel()
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d`)
	_, err := datalog.SemiNaive{}.Eval(ctx, q, b)
	fmt.Println(errors.Is(err, context.Canceled))
	// Output:
	// true
}

// Explain fills a report of what an Eval did: each derived relation and
// how it was evaluated, each body in the order it ran, and where the work
// went. Report.String prints all of it; here, the relations and the goal.
func Example_explain() {
	b, ctx := base(), context.Background()
	var r datalog.Report
	q := datalog.MustParse(`deps.depends_on("app", ?d) => ?d`)
	_, err := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Explain(&r))
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, rr := range r.Relations {
		fmt.Println(rr.Relation, rr.How, rr.Adornments, rr.Tuples, "tuples")
	}
	fmt.Println("goal:", r.Goal.Ran)
	for _, l := range r.Goal.Literals {
		fmt.Println(" ", l.Literal, l.Access, "passed", l.Passed)
	}
	// Output:
	// deps._step inlined [] 0 tuples
	// deps.depends_on demand [bf] 3 tuples
	// goal: deps.depends_on/bf("app", ?d)
	//   deps.depends_on/bf("app", ?d) [derived scan] passed 3
}

// A page continues from the last row of the one before it: After takes that
// row, as the host got it, and answers what comes after it in the order by.
// Total says how many rows the whole answer has, so a host can say how many
// a page left out.
func Example_page() {
	b, ctx := base(), context.Background()
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d order by ?p, ?d limit 2`)
	var total int
	page, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Total(&total))
	for _, r := range page {
		fmt.Println(r.Bind["p"].S, r.Bind["d"].S)
	}
	fmt.Println("of", total)
	next, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.After(page[len(page)-1].Bind))
	for _, r := range next {
		fmt.Println(r.Bind["p"].S, r.Bind["d"].S)
	}
	// Output:
	// api log
	// api util
	// of 6
	// app api
	// app log
}

// EvalTable answers as Eval does, as columns and rows of values, without a
// map per row.
func Example_table() {
	b, ctx := base(), context.Background()
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, count(?d) order by count(?d) desc, ?p limit 2`)
	tab, _ := datalog.SemiNaive{}.EvalTable(ctx, q, b)
	fmt.Println(tab.Columns)
	for _, row := range tab.Rows {
		fmt.Println(row[0].S, row[1].S)
	}
	// Output:
	// [p count(d)]
	// app 3
	// api 2
}

// AddUnit names a unit, so arithmetic writes it by name: a host's speed
// is metres over seconds, and an acceleration, which nobody named, comes out
// as that name over seconds.
func Example_units() {
	b, ctx := base(), context.Background()
	if err := b.Vocabulary().AddUnit("speed", "m/s"); err != nil {
		fmt.Println(err)
		return
	}
	q := datalog.MustParse(`imports(?p, _), ?p = "app", ?v = 100m / 4s, ?a = 100m / (4s * 4s) => ?v, ?a`)
	rows, err := datalog.SemiNaive{}.Eval(ctx, q, b)
	if err != nil {
		fmt.Println(err)
		return
	}
	v, a := rows[0].Bind["v"], rows[0].Bind["a"]
	fmt.Println(v.S, v.BaseUnit)
	fmt.Println(a.S, a.BaseUnit)
	// Output:
	// 25 speed
	// 6.25 speed/s
}

// A parse error is a *datalog.ParseError, which says where the piece it's
// about starts, so an editor can put a marker there. Its Error is the
// message alone, the same text with or without the position.
func Example_parseError() {
	_, err := datalog.Parse("imports(?a, ?b)\n=> ?a, nope")
	var pe *datalog.ParseError
	if errors.As(err, &pe) {
		fmt.Printf("line %d, column %d: %v\n", pe.Line, pe.Column, err)
	}
	// Output:
	// line 2, column 8: query: projection column "nope" must be a ?variable or an aggregate
}

Bind gives a goal variable its value from Go, so the query text stays fixed and nobody builds queries out of strings. A bound variable behaves as if its value were written into the goal, and that includes counting as the anchor of a not (see negation). The answer still has the bound column, filled with the value. Binding a variable the goal doesn’t use is an error, since it’s pretty much always a typo, and a typo there would otherwise answer the unbound question without a word.

A variable can be bound to several values too, which is how a host asks one question about a whole selection, such as every package a user ticked. The variable then ranges over the values, as if the goal were joined with a relation holding exactly them, so the answer is the union, and an aggregate like count(distinct ?d) counts across the whole set, which asking once per value can’t do. Demand starts from every value, so a recursive relation is still worked out only for the values asked, and one query costs about what the separate ones would. Each value is checked as a single one is, and an error names the one refused. A variable bound to no values matches nothing: the answer is empty, or the one row an aggregate gives over nothing (a count of 0). A set of one value is the same as binding that value.

Budget caps the work one Eval does, counted the same way on every run, so a budget that passes once passes every time. Base.Work reports what a query used, which is how to size a budget from your real queries. It bounds work, not memory. What a query holds grows with its answer rather than its work: a goal keeps one row per distinct answer, or one running total per group for an aggregate, not every combination it found on the way (#120), so a count over a million bindings holds one group. The derived relations a query’s rules produce are held in full, though, and those do grow with the work. So is a relation the source hands over as one slice: it’s all in memory before the budget sees any of it. A source that implements ns.StreamSource hands a relation over one fact at a time instead, and each fact counts against the Budget as it arrives, so a query over a relation bigger than its budget stops having held at most that many facts (#233). Those facts aren’t work: Base.Work and Explain count what the query did with them, and only the budget, and the BudgetExceeded it stops with, adds the read. A read the budget stopped isn’t kept, so the next query reads the relation again. A Federation streams its members in turn, so it stops before the next member’s read even when its members return slices. When the goal is the only reader of a streamed relation (no rule reads it, and the goal reads it once, first), its facts go straight into the answer as they arrive and aren’t kept (#264): a limit without an order by stops the read at its rows, and a count holds its one group rather than the relation. The next query that needs the relation reads it again, unless something else already kept it. A relation the source can look up streams this way only under such a limit, so a repeated question over it still asks the source nothing.

The context reaches every Eval. When it’s cancelled or its deadline passes, the Eval stops at its next check, which comes every 1024 units of work, and returns an error that wraps the context’s own, so errors.Is(err, context.DeadlineExceeded) works. It also reaches a host’s own Go code running inside a query, so that can stop too. A generator gets it as its Gen func’s first argument. A source whose reads take long enough to cancel, one that queries a database say, implements ns.ContextSource: the engine then reads a relation through TuplesContext(ctx, rel) with the query’s context instead of Tuples, and a read that’s cancelled or fails isn’t cached, so the next query needing that relation reads it again under its own context. A read error stops the query, wrapped with the relation’s name. A store that looks up or streams gets the context through those calls too.

Pages, totals and tables ¶

After, Total and EvalTable are for a host showing a big answer a page at a time, such as a viewer listing everything on a net (#194, #195). Example_page and Example_table in the code block above show them.

After takes the last row of the page before, as the host got it, and answers only what comes after it in the query’s order by, as the query’s own after clause would (ordering). With a limit, each page holds only its own rows while it runs, and a page stays put when the facts change between requests. Total fills an int with the number of rows the whole answer has before after, offset and limit, so the page can say how many it left out. Counting needs the whole answer, so a limit without an order by doesn’t stop early when Total is asked for.

EvalTable returns the same answer as Eval, as a Table of columns and rows of values, with each row’s citations, witness and reasons beside it. Eval gives every row a map of its own, which for a small row costs several times its values, so a host serializing a large answer is better off with the table. Table.Row(i) is row i as Eval returns it. Explain’s Report.Held says how many rows (or groups) the goal held at its peak.

Explaining a slow query ¶

Explain fills a Report with what an Eval did, so a slow query shows where its work went rather than one total to bisect by hand (#147). Example_explain in the code block above prints part of it. Report.String prints all of it, and the struct has JSON tags, so a host can log it beside a slow query or return it with an answer.

The report lists each derived relation the query reached, and whether it was evaluated in full, under demand (with how many values were demanded), as a factored walk, inlined into its callers, or reused from what the Base kept from an earlier query. Each comes with its tuples, rounds and work.

It then shows the goal and each rule body in the order it actually ran, after jaala’s rewrites, labelled with the rule as you wrote it. Every literal says how it was read (an index on which arguments, a scan, a generator or a filter), how often solving reached it, how many bindings it passed on, and how many candidates it examined. A literal reached thousands of times is usually the place to look.

Last come the base relations it read, whether the Base already held them, and the indexes it probed, with whether this Eval built them. For a source that looks facts up (facts from stores), each relation also says how many lookups it took, the tuples they fetched, and how many calls were answered again from what an earlier lookup in the same Eval returned. Report.Fetched totals the tuples the source handed this Eval, and Report.Lookups the calls.

Work is what the Eval spent, which is what a Budget caps, so it depends on what ran on the Base before: a query reusing a relation an earlier one kept costs less. Report.Cold is the same query’s cost on a base that kept nothing, which doesn’t move from run to run, so it’s the number to compare two queries or plans by, or to suggest a budget from. When the query reused something, Explain finds it by running the query again on a copy of the base that keeps nothing. That run doesn’t count toward Base.Work, but it does read the source again.

A query that answers nothing gets Report.Empty (#343): the first literal, in the order the body ran, that passed no binding on, and the call that first matched nothing with the values the literals before it had bound, such as edge(?x, "a") matched nothing (first called as edge("b", "a")). When that literal reads one of the program’s own relations and none of its rules derived anything, Because says the same for each of those rules, down to the literal over your data that came up empty. A not that let nothing through, or a comparison that held for none, is named the same way. jaala names the call; saying which values your data does hold there is yours to add. Relation and Args give you the culprit’s atom as written, each argument’s constant or nil for a variable, so you can look up what’s there without parsing the literal’s text, and nl.Pack.Hint is where the frontends ask you for it (#430).

Each call Empty names is then run once more by itself, with only its own constants bound, and Alone records whether that matched anything (#348). matched nothing, even alone means your data holds nothing like it, a wrong value or name; matched nothing here, though it matches alone means it does, and only the values the earlier literals bound found nothing, a wrong join. The probe stops at limit 1, runs under the Eval’s Budget (or 100,000 units of work when there is none) and counts toward neither Report.Work nor Base.Work. Alone stays unset for a not or a comparison, for a probe the budget stopped, and for a relation of your Source’s the Base doesn’t hold (one streamed, or only looked up) unless your Source looks it up and the call has a constant, since that probe would read your store whole.

The report is filled even when the Eval fails, so a query its Budget stopped still shows what spent the budget, and marks the literal it stopped in (LiteralReport.Stopped). Asking for it costs time in proportion to the rules and literals a query runs. Not asking costs nothing measurable, which is why it’s off by default.

A Base pairs a vocabulary with one source’s facts, and caches and indexes what it reads. It’s safe to share between Evals running at the same time, since each Eval keeps its own state. Build one per dataset, and reuse it for every query over that dataset, which mostly comes free once the vocabulary is built at startup.

It also keeps the derived relations a query evaluated in full, so the next query calling the same relation reads it instead of deriving it again (#140). A library member that three workbook tabs all call is derived once. The key is the relation’s rules and everything they read, so a query that sends its own definition of a relation derives its own. A relation derived only for the values one query asked about isn’t kept, since it’s partial. Only SemiNaive uses the cache, and not under Witnesses. Base.LimitDerivedCache sets how many derived tuples the base keeps (about a million by default, and 0 turns it off), dropping the relations used least recently first.

A base’s memory lasts as long as the base. A host that builds a base per request, runs several processes, or wants its own tools to read what a rule derives can also give the base a store with Base.KeepDerivedIn (#220). The store implements ns.DerivedStore, two calls: Derived hands back a relation it holds, and KeepDerived takes one a query evaluated in full. Each relation is filed under an ns.DerivedKey: its name, the text of its rules and everything they read (the same key the base’s memory uses), and the source’s Version. A second base over the same version then reads the relation from the store instead of deriving it, which is what a federation of stores wants when the same rules run against the same members again. The store is read when the base’s memory misses, so LimitDerivedCache(0) leaves it as the only tier. Only a Versioned source’s relations go there, since an unversioned source’s facts have nothing to file them under, and the same evaluators and options use it as use the memory. A store that fails, or hands back tuples of the wrong arity, costs the work of deriving and never changes an answer. SemiNaive.Materialize derives the relations you name in full and keeps them, with everything they read, ahead of any query, and returns the store’s error if it refused one. It also keeps a relation with one rule, which a query would have folded into its caller rather than derived. ns.MemDerivedStore is one held in memory, and its Relation(rel, version) reads a kept relation back as facts.

All of this assumes the source’s facts don’t change while the base is kept. If yours can, have the source implement ns.Versioned, whose Version string changes whenever the facts do. Each Eval reads it first, and when it has moved, the base drops everything it cached and reads the source again. A host that changes facts in place without a version calls Base.Forget instead. A generator whose answers can change while the facts don’t (one reading the clock, say) sets Volatile on its ns.Builtin, and no relation reading it is kept.

Where a parse error is ¶

A query that doesn’t parse returns a *datalog.ParseError, which carries where the piece of text it’s about starts: Line and Column, counted from 1 in characters rather than bytes, and Offset, in bytes from the start (#167). Example_parseError above finds it with errors.As. Error() is the message alone, so a host matching on a message’s words sees the same text it always did. An error from checking a parsed query (Validate, an unknown relation, a wrong arity) is a *datalog.CheckError, which says what it’s about and often how to fix it, and datalog.Locate(text, err) finds where in the text it is, for a ParseError too (asking through a model).

Bind, Budget and the context ¶

Pages, totals and tables ¶

Explaining a slow query ¶

Sharing a base ¶

Where a parse error is ¶

`Bind`, `Budget` and the context ¶