A worked query against ProvSQL's own answer #
A left outer join of three departments with three employees, a rank and
an average over each department, and the three rows a total order and
LIMIT 3 keep. ProvSQL computes the provenance of each candidate row on
this instance; everything below is that answer, checked in the kernel.
What it checks is the system's output and not the semantics alone, so a
disagreement is a finding about one of the two and not something to
fit.
What is checked. q1_data gives the six candidate rows; q1_ann and
q2_ann give their annotations as Boolean functions of the six tokens,
compared against ProvSQL's sr_boolexpr at all 64 valuations; and
world_all, world_noA1, world_noB1 give the rows the query returns
in three worlds – both window columns and the LIMIT – by evaluating it
plainly on that world's instance.
The shape is the query's own. The two window columns are two windows
stacked over the join, the second carrying the first one's column
through, and the ORDER BY … LIMIT 3 sits above both, which is where
SQL evaluates it: a window reads its whole partition and not the
truncated relation.
What had to be encoded differently, and why.
- The query is spelled in the core syntax rather than through
AggQueryIn.leftOuterandAggQueryIn.truncate: those carryAggQueryIn.castKind, and a cast along a proof is what the kernel cannot reduce. Writing each projection's columns as a function of the column index keeps the kinds constant by reduction. 𝔹[X]had to be made computable: the library'sDecidableEq (BoolFunc X)isClassical.decEqand there is no linear order onBoolFunc Xat all, so no annotated evaluation over it could be reduced. Both come from the truth table here, as local instances.- Values are numbers: departments
1, 2, 3, names10, 20, 30, identifiers101, 102, 201, salaries as they are. The domain isWithNull ℕ, the nulls being what the padded rows carry.
Agreement. Every row's annotation is ProvSQL's, as a Boolean
function. The one place the two readings are worded differently is the
average of a padded row: ProvSQL prints NaN, which it takes for a
display artefact, and the semantics says null – world_noB1.
The six tokens: dA, dB, dC, a1, a2, b1.
Equations
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
Instances For
Dependency graph
Boolean functions of six variables, computably #
The library's DecidableEq (BoolFunc X) is Classical.decEq, which the
kernel cannot reduce, and there is no linear order on BoolFunc X at all
– so an annotated evaluation over 𝔹[X] cannot be computed. Both come
from the truth table here: a function of six variables is its 64 values,
and a list of booleans is ordered and has decidable equality.
The valuation whose bits are those of k.
Equations
- ProvsqlExample.valOf k i = k.testBit ↑i
Instances For
Dependency graph
The truth table of a Boolean function of the six tokens.
Equations
- ProvsqlExample.table f = List.map (fun (k : ℕ) => f (ProvsqlExample.valOf k)) (List.range 64)
Instances For
Dependency graph
Dependency graph
The order the group and frame sorts read annotations in.
Equations
Instances For
Dependency graph
Equations
Instances For
Dependency graph
Equations
Instances For
Dependency graph
A ↦ 1, B ↦ 2, C ↦ 3; names 10, 20, 30; ids 101, 102, 201.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Instances For
Dependency graph
The query #
dept LEFT JOIN emp ON e.dept = d.dept, spelled in the core syntax
rather than through AggQueryIn.leftOuter: the derived form carries
AggQueryIn.castKind, and a cast along a proof is what the kernel cannot
reduce, so a decide through it is impossible. Writing each projection's
column family as a function of the column index keeps the kinds
constant by reduction, which is what lets the two arms meet and the whole
query evaluate in the kernel.
The five columns are d.dept, d.name, e.id, e.dept, e.salary.
Dependency graph
The identity projection on the five columns, which brings the kinds to the constant form the other arm has.
Equations
Instances For
Dependency graph
The matching pairs.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The two department columns of a join row.
Equations
- ProvsqlExample.firstTwo i = ProjColIn.term (TermGIn.index (Fin.castAdd 3 i) ⋯)
Instances For
Dependency graph
The departments with no employee.
Equations
Instances For
Dependency graph
Padding such a department with three nulls.
Equations
- ProvsqlExample.padTo5 j = ProjColIn.term (Fin.addCases (fun (i : Fin 2) => TermGIn.index i ⋯) (fun (x : Fin 3) => TermGIn.const WithNull.nil) j)
Instances For
Dependency graph
The two window columns, and the ORDER BY … LIMIT 3 over them #
rank() OVER (PARTITION BY d.dept ORDER BY e.salary DESC) and
avg(e.salary) OVER (PARTITION BY d.dept) are two columns of one
SELECT, so they are two windows stacked over the join: the second sits
over a relation that already holds the first one's aggregate column and
carries it through (AggQueryIn.Win reads the regular columns of its
input, ColKind.readTuple). The ORDER BY … LIMIT 3 then sits above
both, which is where SQL evaluates it – a window reads the whole
partition and not the truncated relation.
The truncation is spelled by hand rather than through
AggQueryIn.truncate: that one goes through rank, whose column is
1 + count and whose kinds need AggQueryIn.castKind, and a cast along
a proof is what the kernel cannot reduce. Counting the rows that sort
ahead and keeping ≤ 2 is the same condition as rank ≤ 3, and needs
no cast.
Dependency graph
The counting aggregate: how many rows the frame holds.
Equations
Instances For
Dependency graph
SQL's avg: the mean of the non-null values, null over none.
Equations
- ProvsqlExample.avgAgg = SeqAggFunc.sqlOf fun (l : List ProvsqlExample.V) => WithNull.val ((List.map (fun (x : Option ℕ) => x.getD 0) l).sum / l.length)
Instances For
Dependency graph
rank() OVER (PARTITION BY d.dept ORDER BY e.salary DESC), as the
count of the rows ahead – the rank is one more. Column 5.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The kinds of the relation the second window sits over: five regular columns and the rank count.
Equations
Instances For
Dependency graph
avg(e.salary) OVER (PARTITION BY d.dept) beside it, carrying the
rank column through. Column 6.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
salary DESC NULLS LAST, id ASC, dept ASC.
Equations
- ProvsqlExample.ord3 = ![{ desc := true }, OrderCol.ASC, OrderCol.ASC]
Instances For
Dependency graph
The kinds of the windowed relation: five regular columns and the two window columns.
Instances For
Dependency graph
How many rows sort strictly ahead of a row's peers, over the
windowed relation: rank - 1 in the total order the ORDER BY names.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
LIMIT 3: at most two rows ahead.
Equations
Instances For
Dependency graph
The whole query: the join, the two window columns, the LIMIT, and
the counting column dropped again – the two window columns carried
through by AggQueryIn.dropRank.
Equations
Instances For
Dependency graph
The query's rows, world by world #
Each world is read by evaluating the query plainly on that world's
instance (AnnotatedDatabase.randomWorld), which is SQL on that
sub-instance: the join, both window columns at once, and the three rows
the LIMIT keeps. The rank is 1 + the counting column, as rank
has it.
Every token true.
Equations
Instances For
Dependency graph
a1 absent.
Equations
Instances For
Dependency graph
b1 absent.