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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
//! The keyset predicate: [`MongoKeyset`], the `$match` half of a page.
//!
//! # The expansion is FLAT, where the SQL family's is nested
//!
//! ```text
//! order a ASC, b DESC, _id ASC cursor (x, y, z)
//!
//! { $or: [ { a: { $gt: x } },
//! { a: { $eq: x }, b: { $lt: y } },
//! { a: { $eq: x }, b: { $eq: y }, _id: { $gt: z } } ] }
//! ```
//!
//! It is the same predicate [`SqlKeyset`](crate::comparison::sql::SqlKeyset) writes — one branch
//! per tie-break level, each level's ties broken by the level below — with the nesting multiplied
//! out. The two differ in SHAPE and not in meaning, and the shape is a MongoDB fact rather than a
//! taste:
//!
//! - **A top-level `$or` is what the planner can index.** MongoDB's optimizer splits a `$or` whose
//! branches each have an indexed leading field into one index scan per branch and merges them.
//! The nested form — `{$or: [A, {$and: [Eq, {$or: […]}]}]}` — buries every branch past the first
//! inside an `$and`, where those bounds are not derived. So the flat spelling is the one that
//! pages a large collection without a scan.
//! - **A document's keys are unique, so a branch cannot be built by appending.** SQL nests to avoid
//! repeating each level's equality prefix; a BSON branch has to carry its prefix as keys anyway,
//! so nesting would buy nothing back and cost the index bounds above.
//!
//! What the flat form costs is quadratic SIZE in the number of terms — an order of `n` terms writes
//! `n(n+1)/2` field predicates rather than `2n - 1`. That is a page's worth of BSON over an order a
//! client wrote by hand, which is bounded by the columns a record declares.
//!
//! # Nullable fields, and why the table is SHORTER than the SQL one
//!
//! The framework pins `null` BELOW every value, and MongoDB's own BSON ordering already does —
//! `MinKey < Null < Numbers < String < …`, with a MISSING field ordered exactly where a `null` is.
//! So the pin needs no `$sort` clause, and what falls out here is the SQL table with one row made
//! free by TYPE BRACKETING:
//!
//! | term runs | cursor value | documents strictly after it |
//! |---|---|---|
//! | ascending | a value | `{f: {$gt: v}}` — and `null` is EXCLUDED for free, since MongoDB's `$gt` matches only values of the operand's own BSON type, so no `null` and no missing field can answer |
//! | ascending | `null` | `{f: {$ne: null}}` — every value is above every `null`, and `$ne: null` is exactly *present and not null*, because `$eq: null` holds the missing field |
//! | descending | a value | `{$or: [{f: {$lt: v}}, {f: {$eq: null}}]}` — the nulls trail a descending term, so they are after it, and `$eq: null` gathers the missing fields with them |
//! | descending | `null` | NOTHING. The nulls are the last group, so no document is after one |
//!
//! The first row is where the two backends reach one answer by different routes: SQL excludes
//! `NULL` because `NULL > ?` is unknown, and MongoDB excludes it because a comparison operator does
//! not cross BSON types at all. **That same type bracketing is what makes a HETEROGENEOUS field
//! unpageable** — a field holding numbers in some documents and strings in others cannot be walked
//! by `$gt`, because the operand's type decides which documents are even eligible. This crate's
//! columns are typed by the declaration, so the case does not arise from a framework-written
//! document; it is stated because a collection with other writers is where a page would silently
//! stop early.
//!
//! The last row is why a branch can be ABSENT. A disjunction with a branch that admits nothing is
//! the disjunction without it, so the branch is dropped rather than written as a contradiction —
//! and the tie group below it still renders, which is what keeps a page resuming inside a run of
//! nulls.
//!
//! # It is the SQL family's walk, inherited rather than re-measured
//!
//! A keyset that skips or repeats a document is a perfectly good aggregation that answers without
//! an error, so a differential over the rendered BSON cannot see it. What holds this expansion up
//! is that it is the same PREDICATE the SQL family's walk was measured on — twelve rows carrying
//! nulls in the sort field, ties inside a group, and a pair only the id tail separates, paged two
//! at a time both ways against the full ordered scan, exact on SQLite 3.51.0, PostgreSQL 16.14 and
//! 17.10, and MySQL 8.4.11. What is NOT inherited is the two rows above that are MongoDB's own —
//! type bracketing and the missing-field reading — and those are the ones a live walk has to
//! confirm. See [`lane`](super::lane) for where that is recorded.
use ;
use ;
use crate::;
/// MongoDB's document-level DISJUNCTION — the one key this predicate writes at a position that is
/// not a field's.
///
/// Not a [`MongoOperator`] row, for the reason `$and` is not: that vocabulary is the operators a
/// FIELD's key holds, and this one takes a list of whole filter documents instead.
const OR: &str = "$or";
/// One document's position in a written order, as the predicate that finds the documents after it.
///
/// # It is CONSTRUCTED from a checked order and a checked cursor, and there is no other way in
///
/// [`resume`](Self::resume) takes a [`MongoOrder`] — already refused if two terms name one field —
/// and a [`Cursor`], checked against that order's signature, width and nullability there and then.
/// So every refusal this page can make happens BEFORE the type exists, and the lowering below
/// cannot fail: a mismatched cursor is not a predicate that renders wrongly, it is a value nobody is
/// holding.
///
/// # One conjunct, whatever the order holds
///
/// The expansion is one `$or` document, contributed through
/// [`MongoConjunction::and`](crate::comparison::mongo::MongoConjunction::and) — so it joins a
/// `$match` beside a filter's own keys through the accumulator every comparison threads, and a page
/// is *the client's filter AND this* with neither conjunct knowing what the other was.
///
/// Through `and` rather than through the merge, and the reason is the fold: `$or` is a top-level
/// operator taking whole documents, exactly as `$expr` and `$nor` are, and the accumulator's own
/// note is where that distinction lives.
///
/// # `S` is what each term SORTS BY, and its default is the ordinary answer
///
/// `MongoKeyset<'_, V>` is the field keyset and names nothing extra to be one, because
/// [`MongoFields`] is the default. The parameter is where an order whose term reads ANOTHER
/// COLLECTION enters — see [`MongoSubjects`] — and it is a type rather than a runtime branch so
/// that the flat expansion is the same code it was before the seam existed.
/// MongoDB's own always-false predicate, and the `{$or: []}` the server refuses is why it is
/// spelled at all.
///
/// A 5.0 operator, which is this lane's documented server floor — see
/// [`lane`](super::lane). Below that floor the same answer is spelled `{$expr: false}`; the lane
/// does not carry both, because a page that renders one predicate on one server version and another
/// on the next is a page whose text a reader cannot check.
const ALWAYS_FALSE: &str = "$alwaysFalse";
/// `{op: value}` — one operator document, which is what a field's key holds.
/// The EQUALITY leg a branch carries for every level above its own arm.
///
/// `{$eq: null}` where the cursor held nothing, which is the two-state reading the extraction
/// already takes: a document whose field is null and one with no such field are one group here,
/// because they are one group to `$sort` and one group to `$eq`. Writing `$type: "null"` instead
/// would separate them and make this predicate disagree with the very ordering it resumes.
/// ONE impl, and the bounds are the operands' and the subjects': `V: MongoCarrier` is what a stored
/// value costs, exactly as it is for
/// [`MongoScalarComparison`](crate::comparison::mongo::MongoScalarComparison), and `S: MongoSubjects`
/// is what naming the left-hand sides costs.
///
/// It refuses nothing, so [`Backend::Error`](crate::Backend::Error) goes unnamed: what this
/// predicate could have refused was refused at [`MongoKeyset::resume`], where no document had been
/// built.
/// The subjects go unprinted and unbounded: what a `Debug` here is read for is which order is being
/// resumed at which values, and requiring the party that names the fields to be printable would be
/// a bound on every keyset for the sake of one line of output — the standard
/// [`SqlKeyset`](crate::comparison::sql::SqlKeyset)'s own holds.
/// Written out rather than derived, and the reason is `V`: this holds only a `&[Option<V>]`, so the
/// value is [`Clone`] whatever the operand is — where a derive would bound `V: Clone` and make a
/// keyset over a non-clonable operand un-clonable for no reason it could state.
///
/// It asks `S: Clone` where [`Copy`] below asks `S: Copy`, so a subjects party that is one and not
/// the other still travels. [`MongoFields`] is both, so the field keyset is exactly as `Copy` as it
/// was while its three fields were the whole of it.
/// The subjects are compared, and that is not bookkeeping: two keysets over one order and one
/// cursor that name different FIELDS are two different predicates, so leaving them out would be an
/// equality that says the opposite.