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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
use super::{
AggregateExec, EmptyExec, FilterExec, GroupByExec, LegacyFilterExec, ProjectionExec, SliceExec,
SortMergeJoinExec, TableExec, UnionExec,
};
use crate::{
base::{
database::{ColumnField, ColumnRef, LiteralValue, Table, TableEvaluation, TableRef},
map::{IndexMap, IndexSet},
proof::{PlaceholderResult, ProofError},
scalar::Scalar,
},
sql::{
proof::{
FinalRoundBuilder, FirstRoundBuilder, ProofPlan, ProverEvaluate, VerificationBuilder,
},
proof_exprs::{AliasedDynProofExpr, ColumnExpr, DynProofExpr, TableExpr},
AnalyzeResult,
},
};
use alloc::{boxed::Box, vec::Vec};
use bumpalo::Bump;
use serde::{Deserialize, Serialize};
use sqlparser::ast::Ident;
/// The query plan for proving a query
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
#[enum_dispatch::enum_dispatch]
pub enum DynProofPlan {
/// Source [`ProofPlan`] for (sub)queries without table source such as `SELECT "No table here" as msg;`
Empty(EmptyExec),
/// Source [`ProofPlan`] for (sub)queries with table source such as `SELECT col from tab;`
Table(TableExec),
/// Provable expressions for queries of the form
/// ```ignore
/// SELECT <result_expr1>, ..., <result_exprN> FROM <table>
/// ```
Projection(ProjectionExec),
/// Provable expressions for queries of the form
/// ```ignore
/// SELECT <group_by_expr1>, ..., <group_by_exprM>,
/// SUM(<sum_expr1>.0) as <sum_expr1>.1, ..., SUM(<sum_exprN>.0) as <sum_exprN>.1,
/// COUNT(*) as count_alias
/// FROM <table>
/// WHERE <where_clause>
/// GROUP BY <group_by_expr1>, ..., <group_by_exprM>
/// ```
GroupBy(GroupByExec),
/// Provable expressions for queries of the form
/// ```ignore
/// SELECT <group_by_expr1>.expr as <group_by_expr1>.alias, ..., <group_by_exprM>.expr as <group_by_exprM>.alias,
/// SUM(<sum_expr1>.expr) as <sum_expr1>.alias, ..., SUM(<sum_exprN>.expr) as <sum_exprN>.alias,
/// COUNT(*) as <count_alias>
/// FROM <input>
/// WHERE <where_clause>
/// GROUP BY <group_by_expr1>.expr, ..., <group_by_exprM>.expr
/// ```
/// Similar to `GroupBy` but accepts a [`DynProofPlan`] as input
Aggregate(AggregateExec),
/// Provable expressions for queries of the form, where the result is sent in a dense form
/// ```ignore
/// SELECT <result_expr1>, ..., <result_exprN> FROM <table> WHERE <where_clause>
/// ```
LegacyFilter(LegacyFilterExec),
/// Provable expressions for queries of the form, where the result is sent in a dense form
/// ```ignore
/// SELECT <result_expr1>, ..., <result_exprN> FROM <input> WHERE <where_clause>
/// ```
/// Accepts a [`DynProofPlan`] as input
Filter(FilterExec),
/// `ProofPlan` for queries of the form
/// ```ignore
/// <ProofPlan> LIMIT <fetch> [OFFSET <skip>]
/// ```
Slice(SliceExec),
/// `ProofPlan` for queries of the form
/// ```ignore
/// <ProofPlan>
/// UNION ALL
/// <ProofPlan>
/// ...
/// UNION ALL
/// <ProofPlan>
/// ```
Union(UnionExec),
/// `ProofPlan` for queries of the form
/// ```ignore
/// <ProofPlan> INNER JOIN <ProofPlan>
/// ON col1 = col2
/// ```
SortMergeJoin(SortMergeJoinExec),
}
impl DynProofPlan {
/// Creates a new empty plan.
#[must_use]
pub fn new_empty() -> Self {
Self::Empty(EmptyExec::new())
}
/// Creates a new table plan.
#[must_use]
pub fn new_table(table_ref: TableRef, schema: Vec<ColumnField>) -> Self {
Self::Table(TableExec::new(table_ref, schema))
}
/// Creates a new projection plan.
#[must_use]
pub fn new_projection(aliased_results: Vec<AliasedDynProofExpr>, input: DynProofPlan) -> Self {
Self::Projection(ProjectionExec::new(aliased_results, Box::new(input)))
}
/// Creates a new legacy filter plan.
#[must_use]
pub fn new_legacy_filter(
aliased_results: Vec<AliasedDynProofExpr>,
input: TableExpr,
filter_expr: DynProofExpr,
) -> Self {
Self::LegacyFilter(LegacyFilterExec::new(aliased_results, input, filter_expr))
}
/// Creates a new group by plan.
#[must_use]
pub fn try_new_group_by(
group_by_exprs: Vec<ColumnExpr>,
sum_expr: Vec<AliasedDynProofExpr>,
count_alias: Ident,
table: TableExpr,
where_clause: DynProofExpr,
) -> Option<Self> {
GroupByExec::try_new(group_by_exprs, sum_expr, count_alias, table, where_clause)
.map(Self::GroupBy)
}
/// Creates a new aggregate plan.
#[must_use]
pub fn try_new_aggregate(
group_by_exprs: Vec<AliasedDynProofExpr>,
sum_expr: Vec<AliasedDynProofExpr>,
count_alias: Ident,
input: DynProofPlan,
where_clause: DynProofExpr,
) -> Option<Self> {
AggregateExec::try_new(
group_by_exprs,
sum_expr,
count_alias,
Box::new(input),
where_clause,
)
.map(Self::Aggregate)
}
/// Creates a new slice plan.
#[must_use]
pub fn new_slice(input: DynProofPlan, skip: usize, fetch: Option<usize>) -> Self {
Self::Slice(SliceExec::new(Box::new(input), skip, fetch))
}
/// Creates a new union plan.
pub fn try_new_union(inputs: Vec<DynProofPlan>) -> AnalyzeResult<Self> {
UnionExec::try_new(inputs).map(Self::Union)
}
/// Creates a new filter plan.
#[must_use]
pub fn new_filter(
aliased_results: Vec<AliasedDynProofExpr>,
input: DynProofPlan,
filter_expr: DynProofExpr,
) -> Self {
Self::Filter(FilterExec::new(
aliased_results,
Box::new(input),
filter_expr,
))
}
/// Returns the resulting column fields of the plan as column references
pub(crate) fn get_column_result_fields_as_references(&self) -> IndexSet<ColumnRef> {
self.get_column_result_fields()
.into_iter()
.map(|f| ColumnRef::new(TableRef::from_names(None, ""), f.name(), f.data_type()))
.collect()
}
}