Skip to content

Commit 55aa817

Browse files
grgbkrgrgbkr
committed
hidden format and tests
1 parent 584ad3d commit 55aa817

File tree

11 files changed

+618
-88
lines changed

11 files changed

+618
-88
lines changed

‎packages/zero-protocol/src/ast.ts‎

Lines changed: 45 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -69,10 +69,25 @@ export const simpleConditionSchema = v.object({
6969
),
7070
});
7171

72+
export const existsConditionSchema = v.readonlyObject({
73+
type: v.literal('exists'),
74+
});
75+
76+
export const correlatedSubqueryConditionConditionSchema = v.union(
77+
existsConditionSchema,
78+
);
79+
80+
export const correlatedSubqueryConditionSchema = v.readonlyObject({
81+
type: v.literal('subquery'),
82+
related: v.lazy(() => correlatedSubquerySchema),
83+
condition: correlatedSubqueryConditionConditionSchema,
84+
});
85+
7286
export const conditionSchema = v.union(
7387
simpleConditionSchema,
7488
v.lazy(() => conjunctionSchema),
7589
v.lazy(() => disjunctionSchema),
90+
correlatedSubqueryConditionSchema,
7691
);
7792

7893
const conjunctionSchema: v.Type<Conjunction> = v.readonlyObject({
@@ -200,7 +215,11 @@ export type LiteralValue =
200215
* ivm1 supports Conjunctions and Disjunctions.
201216
* We'll support them in the future.
202217
*/
203-
export type Condition = SimpleCondition | Conjunction | Disjunction;
218+
export type Condition =
219+
| SimpleCondition
220+
| Conjunction
221+
| Disjunction
222+
| CorrelatedSubQueryCondition;
204223

205224
export type SimpleCondition = {
206225
type: 'simple';
@@ -230,6 +249,16 @@ export type Disjunction = {
230249
conditions: readonly Condition[];
231250
};
232251

252+
export type CorrelatedSubQueryCondition = {
253+
type: 'subquery';
254+
related: CorrelatedSubQuery;
255+
condition: CorrelatedSubQueryConditionCondition;
256+
};
257+
258+
export type CorrelatedSubQueryConditionCondition = {
259+
type: 'exists';
260+
};
261+
233262
/**
234263
* A parameter is a value that is not known at the time the query is written
235264
* and is resolved at runtime.
@@ -297,7 +326,7 @@ export function normalizeAST(ast: AST): Required<AST> {
297326
}
298327

299328
function sortedWhere(where: Condition): Condition {
300-
if (where.type === 'simple') {
329+
if (where.type === 'simple' || where.type === 'subquery') {
301330
return where;
302331
}
303332
return {
@@ -331,6 +360,19 @@ function cmpCondition(a: Condition, b: Condition): number {
331360
return 1; // Order SimpleConditions first to simplify logic for invalidation filtering.
332361
}
333362

363+
if (a.type === 'subquery') {
364+
if (b.type !== 'subquery') {
365+
return -1; // Order subquery before conjuctions/disjuctions
366+
}
367+
return (
368+
cmpRelated(a.related, b.related) ||
369+
compareUTF8MaybeNull(a.condition.type, b.condition.type)
370+
);
371+
}
372+
if (b.type === 'subquery') {
373+
return -1; // Order subquery before conjuctions/disjuctions
374+
}
375+
334376
const val = compareUTF8MaybeNull(a.type, b.type);
335377
if (val !== 0) {
336378
return val;
@@ -368,7 +410,7 @@ function flattened<T extends Condition>(cond: T | undefined): T | undefined {
368410
if (cond === undefined) {
369411
return undefined;
370412
}
371-
if (cond.type === 'simple') {
413+
if (cond.type === 'simple' || cond.type === 'subquery') {
372414
return cond;
373415
}
374416
const conditions = defined(

‎packages/zql/src/builder/builder.ts‎

Lines changed: 104 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@ import type {
55
AST,
66
Condition,
77
Conjunction,
8+
CorrelatedSubQuery,
9+
CorrelatedSubQueryCondition,
810
Disjunction,
911
LiteralValue,
1012
Ordering,
@@ -14,6 +16,7 @@ import type {
1416
} from '../../../zero-protocol/src/ast.js';
1517
import type {Row} from '../../../zero-protocol/src/data.js';
1618
import type {PrimaryKey} from '../../../zero-protocol/src/primary-key.js';
19+
import {Exists} from '../ivm/exists.js';
1720
import {FanIn} from '../ivm/fan-in.js';
1821
import {FanOut} from '../ivm/fan-out.js';
1922
import {Filter} from '../ivm/filter.js';
@@ -104,15 +107,25 @@ export function bindStaticParameters(
104107
};
105108

106109
function bindCondition(condition: Condition): Condition {
107-
return condition.type === 'simple'
108-
? {
109-
...condition,
110-
value: bindValue(condition.value),
111-
}
112-
: {
113-
...condition,
114-
conditions: condition.conditions.map(bindCondition),
115-
};
110+
if (condition.type === 'simple') {
111+
return {
112+
...condition,
113+
value: bindValue(condition.value),
114+
};
115+
}
116+
if (condition.type === 'subquery') {
117+
return {
118+
...condition,
119+
related: {
120+
...condition.related,
121+
subquery: visit(condition.related.subquery),
122+
},
123+
};
124+
}
125+
return {
126+
...condition,
127+
conditions: condition.conditions.map(bindCondition),
128+
};
116129
}
117130

118131
const bindValue = (value: ValuePosition): LiteralValue => {
@@ -157,8 +170,20 @@ function buildPipelineInternal(
157170
end = new Skip(end, ast.start);
158171
}
159172

173+
const correlatedSubQueryConditions = gatherCorrelatedSubQueryConditions(
174+
ast.where,
175+
);
176+
177+
for (const csqc of correlatedSubQueryConditions) {
178+
let csq = csqc.related;
179+
if (csqc.condition.type === 'exists') {
180+
csq = {...csq, subquery: {...csq.subquery, limit: EXISTS_LIMIT}};
181+
}
182+
end = applyCorrelatedSubQuery(csq, delegate, staticQueryParameters, end);
183+
}
184+
160185
if (ast.where) {
161-
end = applyWhere(end, ast.where, appliedFilters);
186+
end = applyWhere(end, ast.where, appliedFilters, delegate);
162187
}
163188

164189
if (ast.limit) {
@@ -167,28 +192,38 @@ function buildPipelineInternal(
167192

168193
if (ast.related) {
169194
for (const sq of ast.related) {
170-
assert(sq.subquery.alias, 'Subquery must have an alias');
171-
const child = buildPipelineInternal(
172-
sq.subquery,
173-
delegate,
174-
staticQueryParameters,
175-
sq.correlation.childField,
176-
);
177-
end = new Join({
178-
parent: end,
179-
child,
180-
storage: delegate.createStorage(),
181-
parentKey: sq.correlation.parentField,
182-
childKey: sq.correlation.childField,
183-
relationshipName: sq.subquery.alias,
184-
hidden: sq.hidden ?? false,
185-
});
195+
end = applyCorrelatedSubQuery(sq, delegate, staticQueryParameters, end);
186196
}
187197
}
188198

189199
return end;
190200
}
191201

202+
function applyCorrelatedSubQuery(
203+
sq: CorrelatedSubQuery,
204+
delegate: BuilderDelegate,
205+
staticQueryParameters: StaticQueryParameters | undefined,
206+
end: Input,
207+
) {
208+
assert(sq.subquery.alias, 'Subquery must have an alias');
209+
const child = buildPipelineInternal(
210+
sq.subquery,
211+
delegate,
212+
staticQueryParameters,
213+
sq.correlation.childField,
214+
);
215+
end = new Join({
216+
parent: end,
217+
child,
218+
storage: delegate.createStorage(),
219+
parentKey: sq.correlation.parentField,
220+
childKey: sq.correlation.childField,
221+
relationshipName: sq.subquery.alias,
222+
hidden: sq.hidden ?? false,
223+
});
224+
return end;
225+
}
226+
192227
function applyWhere(
193228
input: Input,
194229
condition: Condition,
@@ -197,12 +232,15 @@ function applyWhere(
197232
// Or we do the union of queries approach and retain this `appliedFilters` and `sourceConnect` behavior.
198233
// Downside of that being unbounded memory usage.
199234
appliedFilters: boolean,
235+
delegate: BuilderDelegate,
200236
): Input {
201237
switch (condition.type) {
202238
case 'and':
203-
return applyAnd(input, condition, appliedFilters);
239+
return applyAnd(input, condition, appliedFilters, delegate);
204240
case 'or':
205-
return applyOr(input, condition, appliedFilters);
241+
return applyOr(input, condition, appliedFilters, delegate);
242+
case 'subquery':
243+
return applyCorrelatedSubqueryCondition(input, condition, delegate);
206244
default:
207245
return applySimpleCondition(input, condition, appliedFilters);
208246
}
@@ -212,9 +250,10 @@ function applyAnd(
212250
input: Input,
213251
condition: Conjunction,
214252
appliedFilters: boolean,
253+
delegate: BuilderDelegate,
215254
) {
216255
for (const subCondition of condition.conditions) {
217-
input = applyWhere(input, subCondition, appliedFilters);
256+
input = applyWhere(input, subCondition, appliedFilters, delegate);
218257
}
219258
return input;
220259
}
@@ -223,11 +262,12 @@ function applyOr(
223262
input: Input,
224263
condition: Disjunction,
225264
appliedFilters: boolean,
265+
delegate: BuilderDelegate,
226266
): Input {
227267
const fanOut = new FanOut(input);
228268
const branches: Input[] = [];
229269
for (const subCondition of condition.conditions) {
230-
branches.push(applyWhere(fanOut, subCondition, appliedFilters));
270+
branches.push(applyWhere(fanOut, subCondition, appliedFilters, delegate));
231271
}
232272
assert(branches.length > 0, 'Or condition must have at least one branch');
233273
return new FanIn(fanOut, branches as [Input, ...Input[]]);
@@ -264,3 +304,37 @@ export function assertOrderingIncludesPK(
264304
);
265305
}
266306
}
307+
function applyCorrelatedSubqueryCondition(
308+
input: Input,
309+
condition: CorrelatedSubQueryCondition,
310+
delegate: BuilderDelegate,
311+
): Input {
312+
assert(condition.condition.type === 'exists');
313+
return new Exists(
314+
input,
315+
delegate.createStorage(),
316+
must(condition.related.subquery.alias),
317+
);
318+
}
319+
320+
function gatherCorrelatedSubQueryConditions(condition: Condition | undefined) {
321+
const correlatedSubQueryConditions: CorrelatedSubQueryCondition[] = [];
322+
const gather = (condition: Condition) => {
323+
if (condition.type === 'subquery') {
324+
correlatedSubQueryConditions.push(condition);
325+
return;
326+
}
327+
if (condition.type === 'and' || condition.type === 'or') {
328+
for (const c of condition.conditions) {
329+
gather(c);
330+
}
331+
return;
332+
}
333+
};
334+
if (condition) {
335+
gather(condition);
336+
}
337+
return correlatedSubQueryConditions;
338+
}
339+
340+
const EXISTS_LIMIT = 5;

‎packages/zql/src/ivm/array-view.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ export class ArrayView<V extends View> implements Output, TypedView<V> {
3434

3535
constructor(
3636
input: Input,
37-
format: Format = {singular: false, relationships: {}},
37+
format: Format = {singular: false, hidden: false, relationships: {}},
3838
) {
3939
this.#input = input;
4040
this.#schema = input.getSchema();

0 commit comments

Comments
 (0)