lib/sql/src/statement/access.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sql = @import("../root.zig");
3 const ast_mod = @import("ast.zig");
4 const execute_mod = @import("execute.zig");
5 const predicate_mod = @import("predicate.zig");
6 const key = sql.key;
7 const relation_mod = sql.relation;
8 const page = sql.page;
9 const catalog_mod = sql.catalog;
10 const plan = sql.plan;
11 const row = sql.row;
12 const tree = sql.tree;
13 const version = sql.version;
14
15 const Allocator = std.mem.Allocator;
16
17 pub const AccessCost = struct {
18 table_scan: usize = 0,
19 index_scan: usize = 0,
20 estimated_rows: usize = 0,
21 from_stats: bool = false,
22 from_distribution: bool = false,
23 };
24
25 pub const SelectAccess = union(enum) {
26 rowid: predicate_mod.RowidPredicate,
27 index: predicate_mod.IndexedPredicate,
28 covering: usize,
29 scan: ?predicate_mod.ScannedPredicate,
30 };
31
32 pub fn coveringIndex(
33 select: ast_mod.Select,
34 relation: *const plan.PreparedRelation,
35 fields: []const execute_mod.ProjectedColumn,
36 ) ?usize {
37 if (select.order.len == 0) return null;
38 const handle = &relation.handle;
39 const stats = relation.relationStats();
40 const table_cost = if (stats) |relation_stats| tableScanCost(relation_stats.table) else 0;
41 var best: ?usize = null;
42 var best_cost: usize = std.math.maxInt(usize);
43 var best_width: usize = std.math.maxInt(usize);
44 for (handle.specs, 0..) |spec, slot| {
45 if (!indexCoversProjection(handle, slot, fields)) continue;
46 var binary_projection = true;
47 for (fields) |field| switch (field) {
48 .rowid => {},
49 .field => |column_index| {
50 if (handle.definitions[column_index].column.collation != .binary) {
51 binary_projection = false;
52 break;
53 }
54 },
55 };
56 if (!binary_projection) continue;
57 if (!indexCoversOrder(handle, slot, select.order)) continue;
58 var covered = true;
59 var offset: usize = 0;
60 while (offset < predicate_mod.selectPredicateCount(select)) : (offset += 1) {
61 const predicate = predicate_mod.selectPredicateAt(select, offset);
62 if (!indexCoversPredicate(handle, slot, predicate) or
63 !indexCoversColumn(handle, slot, predicate.column))
64 {
65 covered = false;
66 break;
67 }
68 }
69 if (!covered) continue;
70 const cost = if (stats) |relation_stats| cost: {
71 const index_stats = indexStatsForRoot(relation_stats, spec.root_page) orelse continue;
72 const summary = index_stats.summary;
73 break :cost summaryPageCost(summary) +| summary.entries;
74 } else 0;
75 if (stats != null and cost >= table_cost) continue;
76 if (best == null or cost < best_cost or
77 (cost == best_cost and spec.fields.len < best_width))
78 {
79 best = slot;
80 best_cost = cost;
81 best_width = spec.fields.len;
82 }
83 }
84 return best;
85 }
86
87 pub fn indexCoversOrder(
88 handle: *const catalog_mod.RelationHandle,
89 index_slot: usize,
90 order: []const ast_mod.OrderKey,
91 ) bool {
92 for (order) |order_key| {
93 if (!indexCoversColumn(handle, index_slot, order_key.column)) return false;
94 }
95 return true;
96 }
97
98 fn indexCoversColumn(
99 handle: *const catalog_mod.RelationHandle,
100 index_slot: usize,
101 column: ast_mod.PredicateColumn,
102 ) bool {
103 return switch (column) {
104 .rowid => true,
105 .field => |name| covered: {
106 const field = columnIndex(handle.definitions, name) orelse return false;
107 const position = fieldPosition(
108 handle.specs[index_slot].fields,
109 field,
110 ) orelse return false;
111 break :covered handle.definitions[field].column.collation == .binary and
112 handle.specs[index_slot].columns[position].collation == .binary;
113 },
114 };
115 }
116
117 pub fn runtimeSelectAccess(select: ast_mod.Select, relation: *const plan.PreparedRelation, fields: []const execute_mod.ProjectedColumn, values: []const row.Value) ast_mod.Error!SelectAccess {
118 return try execute_mod.prepareSelectAccess(select, relation, fields, values);
119 }
120
121 pub fn predicateIndex(
122 select: ast_mod.Select,
123 relation: *const plan.PreparedRelation,
124 fields: []const execute_mod.ProjectedColumn,
125 values: ?[]const row.Value,
126 ) ?predicate_mod.IndexedPredicate {
127 const handle = &relation.handle;
128 if (relation.relationStats()) |relation_stats| return costedPredicateIndex(select, handle, relation_stats, fields, values);
129 return fallbackPredicateIndex(select, handle);
130 }
131
132 pub fn fallbackPredicateIndex(select: ast_mod.Select, handle: *const catalog_mod.RelationHandle) ?predicate_mod.IndexedPredicate {
133 var best: ?predicate_mod.IndexedPredicate = null;
134 var best_width: usize = std.math.maxInt(usize);
135 for (handle.specs, 0..) |spec, slot| {
136 const candidate = indexPredicateForSpec(select, handle, spec, slot) orelse continue;
137 if (best == null or betterIndexedPredicate(candidate, spec.fields.len, best.?, best_width)) {
138 best = candidate;
139 best_width = spec.fields.len;
140 }
141 }
142 return best;
143 }
144
145 pub fn costedPredicateIndex(
146 select: ast_mod.Select,
147 handle: *const catalog_mod.RelationHandle,
148 stats: *const catalog_mod.RelationStats,
149 fields: []const execute_mod.ProjectedColumn,
150 values: ?[]const row.Value,
151 ) ?predicate_mod.IndexedPredicate {
152 const table_cost = tableScanCost(stats.table);
153 var best: ?predicate_mod.IndexedPredicate = null;
154 var best_width: usize = std.math.maxInt(usize);
155 for (handle.specs, 0..) |spec, slot| {
156 var candidate = indexPredicateForSpec(select, handle, spec, slot) orelse continue;
157 const index_stats = indexStatsForRoot(stats, spec.root_page) orelse continue;
158 const covered = indexCoversSelect(handle, slot, fields, select);
159 candidate.cost = indexAccessCostForCandidate(table_cost, index_stats, spec, candidate, select, values, covered);
160 if (best == null or betterIndexedPredicate(candidate, spec.fields.len, best.?, best_width)) {
161 best = candidate;
162 best_width = spec.fields.len;
163 }
164 }
165 if (best) |choice| {
166 if (choice.cost.index_scan < table_cost) return choice;
167 }
168 return null;
169 }
170
171 pub fn indexPredicateForSpec(select: ast_mod.Select, handle: *const catalog_mod.RelationHandle, spec: relation_mod.IndexSpec, slot: usize) ?predicate_mod.IndexedPredicate {
172 if (spec.fields.len == 0) return null;
173 var candidate = predicate_mod.IndexedPredicate{
174 .field = spec.fields[0],
175 .index_slot = slot,
176 .predicate_index = 0,
177 .operator = .eq,
178 };
179 var prefix_count: usize = 0;
180 while (prefix_count < spec.fields.len and prefix_count < relation_mod.max_index_fields) : (prefix_count += 1) {
181 const field = spec.fields[prefix_count];
182 if (spec.columns[prefix_count].collation != handle.definitions[field].column.collation) break;
183 const predicate_index = equalityPredicateIndex(select, handle, field) orelse break;
184 candidate.prefix_fields[prefix_count] = field;
185 candidate.prefix_predicates[prefix_count] = predicate_index;
186 }
187 if (prefix_count < spec.fields.len and prefix_count < relation_mod.max_index_fields) {
188 const field = spec.fields[prefix_count];
189 if (spec.columns[prefix_count].collation == handle.definitions[field].column.collation) {
190 if (rangePredicateIndex(select, handle, field)) |predicate_index| {
191 const predicate = predicate_mod.selectPredicateAt(select, predicate_index);
192 candidate.field = field;
193 candidate.predicate_index = predicate_index;
194 candidate.operator = predicate.operator;
195 candidate.equality_count = prefix_count;
196 candidate.prefix_count = prefix_count + 1;
197 candidate.prefix_fields[prefix_count] = field;
198 candidate.prefix_predicates[prefix_count] = predicate_index;
199 return candidate;
200 }
201 }
202 }
203 if (prefix_count > 0) {
204 candidate.field = candidate.prefix_fields[0];
205 candidate.predicate_index = candidate.prefix_predicates[0];
206 candidate.operator = .eq;
207 candidate.equality_count = prefix_count;
208 candidate.prefix_count = prefix_count;
209 return candidate;
210 }
211 return null;
212 }
213
214 pub fn equalityPredicateIndex(select: ast_mod.Select, handle: *const catalog_mod.RelationHandle, field: usize) ?usize {
215 var offset: usize = 0;
216 while (offset < predicate_mod.selectPredicateCount(select)) : (offset += 1) {
217 const predicate = predicate_mod.selectPredicateAt(select, offset);
218 if (predicate.operator != .eq) continue;
219 if (predicate_mod.predicateField(handle, predicate) == field) return offset;
220 }
221 return null;
222 }
223
224 pub fn rangePredicateIndex(select: ast_mod.Select, handle: *const catalog_mod.RelationHandle, field: usize) ?usize {
225 var offset: usize = 0;
226 while (offset < predicate_mod.selectPredicateCount(select)) : (offset += 1) {
227 const predicate = predicate_mod.selectPredicateAt(select, offset);
228 if (predicate.operator == .eq) continue;
229 if (predicate_mod.predicateField(handle, predicate) == field) return offset;
230 }
231 return null;
232 }
233
234 pub fn betterIndexedPredicate(left: predicate_mod.IndexedPredicate, left_width: usize, right: predicate_mod.IndexedPredicate, right_width: usize) bool {
235 if (left.cost.from_stats or right.cost.from_stats) {
236 if (left.cost.index_scan != right.cost.index_scan) return left.cost.index_scan < right.cost.index_scan;
237 }
238 if (left.prefix_count != right.prefix_count) return left.prefix_count > right.prefix_count;
239 return left_width < right_width;
240 }
241
242 pub fn scanCost(stats: ?*const catalog_mod.RelationStats) AccessCost {
243 if (stats) |relation_stats| {
244 const table_cost = tableScanCost(relation_stats.table);
245 return .{
246 .table_scan = table_cost,
247 .from_stats = true,
248 };
249 }
250 return .{};
251 }
252
253 pub fn indexAccessCostForCandidate(
254 table_cost: usize,
255 index_stats: *const catalog_mod.IndexStats,
256 spec: relation_mod.IndexSpec,
257 candidate: predicate_mod.IndexedPredicate,
258 select: ast_mod.Select,
259 values: ?[]const row.Value,
260 covered: bool,
261 ) AccessCost {
262 if (candidate.operator != .eq and candidate.equality_count > 0) {
263 if (rangePrefixEstimate(index_stats, spec, candidate, select, values)) |estimate| {
264 return indexAccessCostFromRows(table_cost, index_stats.summary, estimate.rows, covered, estimate.from_distribution);
265 }
266 }
267 if (candidate.operator == .eq and candidate.prefix_count > 1) {
268 if (equalityPrefixEstimate(index_stats, spec, candidate, select, values)) |estimate| {
269 return indexAccessCostFromRows(table_cost, index_stats.summary, estimate.rows, covered, estimate.from_distribution);
270 }
271 }
272 var cost = indexAccessCost(
273 table_cost,
274 index_stats,
275 spec,
276 candidate.operator,
277 predicate_mod.predicateExpression(select, candidate.predicate_index, values),
278 covered,
279 );
280 if (candidate.operator != .eq or candidate.prefix_count <= 1) return cost;
281 var rows = cost.estimated_rows;
282 var offset: usize = 1;
283 while (offset < candidate.prefix_count) : (offset += 1) {
284 rows = if (rows <= 1) rows else @max(@as(usize, 1), rows / 4);
285 }
286 const summary = index_stats.summary;
287 var index_cost = summaryPageCost(summary) +| rows;
288 if (!covered) index_cost +|= rows;
289 cost.index_scan = index_cost;
290 cost.estimated_rows = rows;
291 return cost;
292 }
293
294 pub fn indexAccessCostFromRows(table_cost: usize, summary: tree.Summary, rows: usize, covered: bool, from_distribution: bool) AccessCost {
295 var index_cost = summaryPageCost(summary) +| rows;
296 if (!covered) index_cost +|= rows;
297 return .{
298 .table_scan = table_cost,
299 .index_scan = index_cost,
300 .estimated_rows = rows,
301 .from_stats = true,
302 .from_distribution = from_distribution,
303 };
304 }
305
306 pub fn indexAccessCost(
307 table_cost: usize,
308 index_stats: *const catalog_mod.IndexStats,
309 spec: relation_mod.IndexSpec,
310 operator: ast_mod.PredicateOperator,
311 value: ast_mod.Expression,
312 covered: bool,
313 ) AccessCost {
314 const estimate = estimatedRows(index_stats, spec, operator, value);
315 const rows = estimate.rows;
316 const summary = index_stats.summary;
317 var index_cost = summaryPageCost(summary) +| rows;
318 if (!covered) index_cost +|= rows;
319 return .{
320 .table_scan = table_cost,
321 .index_scan = index_cost,
322 .estimated_rows = rows,
323 .from_stats = true,
324 .from_distribution = estimate.from_distribution,
325 };
326 }
327
328 pub fn tableScanCost(summary: tree.Summary) usize {
329 return summaryPageCost(summary) +| summary.entries;
330 }
331
332 pub fn summaryPageCost(summary: tree.Summary) usize {
333 return summary.branch_pages +| summary.leaf_pages +| summary.overflow_pages;
334 }
335
336 pub const RowEstimate = struct {
337 rows: usize,
338 from_distribution: bool = false,
339 };
340
341 pub fn estimatedRows(index_stats: *const catalog_mod.IndexStats, spec: relation_mod.IndexSpec, operator: ast_mod.PredicateOperator, value: ast_mod.Expression) RowEstimate {
342 const entries = index_stats.summary.entries;
343 if (entries == 0) return .{ .rows = 0 };
344 if (predicate_mod.literalValue(value)) |literal| {
345 if (sampleEstimate(index_stats.distribution, spec, operator, literal, entries)) |estimate| return estimate;
346 }
347 if (index_stats.distribution.distinct_values != 0 and operator == .eq) {
348 return .{
349 .rows = @max(@as(usize, 1), entries / index_stats.distribution.distinct_values),
350 .from_distribution = true,
351 };
352 }
353 return .{
354 .rows = switch (operator) {
355 .eq => @max(@as(usize, 1), entries / 16),
356 .lt, .lte, .gt, .gte => @max(@as(usize, 1), entries / 2),
357 },
358 };
359 }
360
361 pub fn equalityPrefixEstimate(
362 index_stats: *const catalog_mod.IndexStats,
363 spec: relation_mod.IndexSpec,
364 candidate: predicate_mod.IndexedPredicate,
365 select: ast_mod.Select,
366 values: ?[]const row.Value,
367 ) ?RowEstimate {
368 const entries = index_stats.summary.entries;
369 const prefix = distributionPrefix(index_stats.distribution, candidate.prefix_count) orelse return null;
370 var prefix_values_buffer: [relation_mod.max_index_fields]row.Value = undefined;
371 if (predicate_mod.literalPrefixValues(&prefix_values_buffer, select, candidate, candidate.prefix_count, values)) |prefix_values| {
372 if (sampleEstimatePrefix(prefix, spec, .eq, prefix_values, entries)) |estimate| return estimate;
373 }
374 if (prefix.distinct_values == 0) return null;
375 return .{
376 .rows = @max(@as(usize, 1), entries / prefix.distinct_values),
377 .from_distribution = true,
378 };
379 }
380
381 pub fn rangePrefixEstimate(
382 index_stats: *const catalog_mod.IndexStats,
383 spec: relation_mod.IndexSpec,
384 candidate: predicate_mod.IndexedPredicate,
385 select: ast_mod.Select,
386 values: ?[]const row.Value,
387 ) ?RowEstimate {
388 const entries = index_stats.summary.entries;
389 const equality_prefix = distributionPrefix(index_stats.distribution, candidate.equality_count) orelse return null;
390 var equality_values_buffer: [relation_mod.max_index_fields]row.Value = undefined;
391 if (predicate_mod.literalPrefixValues(&equality_values_buffer, select, candidate, candidate.equality_count, values)) |equality_values| {
392 if (sampleRankPrefix(equality_prefix, spec, equality_values, entries)) |equality_rank| {
393 if (equality_rank.equal_count != 0) {
394 var range_values_buffer: [relation_mod.max_index_fields]row.Value = undefined;
395 if (predicate_mod.literalPrefixValues(&range_values_buffer, select, candidate, candidate.prefix_count, values)) |range_values| {
396 if (distributionPrefix(index_stats.distribution, candidate.prefix_count)) |range_prefix| {
397 if (sampleRankPrefix(range_prefix, spec, range_values, entries)) |range_rank| {
398 return .{
399 .rows = rangeRowsWithinEquality(candidate.operator, equality_rank, range_rank),
400 .from_distribution = true,
401 };
402 }
403 }
404 }
405 return .{
406 .rows = halfRows(equality_rank.equal_count),
407 .from_distribution = true,
408 };
409 }
410 if (equality_rank.estimated_equal != 0) {
411 return .{
412 .rows = halfRows(equality_rank.estimated_equal),
413 .from_distribution = true,
414 };
415 }
416 }
417 }
418 if (equality_prefix.distinct_values == 0) return null;
419 return .{
420 .rows = halfRows(@max(@as(usize, 1), entries / equality_prefix.distinct_values)),
421 .from_distribution = true,
422 };
423 }
424
425 pub fn rangeRowsWithinEquality(operator: ast_mod.PredicateOperator, equality_rank: SampleRank, range_rank: SampleRank) usize {
426 const group_start = equality_rank.less_than;
427 const group_end = group_start +| equality_rank.equal_count;
428 const bound_after = range_rank.less_than +| range_rank.equal_count;
429 return @min(equality_rank.equal_count, switch (operator) {
430 .eq => equality_rank.equal_count,
431 .lt => range_rank.less_than -| group_start,
432 .lte => bound_after -| group_start,
433 .gt => group_end -| bound_after,
434 .gte => group_end -| range_rank.less_than,
435 });
436 }
437
438 pub fn halfRows(rows: usize) usize {
439 return if (rows <= 1) rows else @max(@as(usize, 1), rows / 2);
440 }
441
442 pub fn distributionPrefix(distribution: catalog_mod.IndexDistribution, field_count: usize) ?catalog_mod.IndexPrefixDistribution {
443 if (field_count == 0) return null;
444 for (distribution.prefixes) |prefix| {
445 if (prefix.field_count == field_count) return prefix;
446 }
447 if (field_count == 1 and (distribution.samples.len != 0 or distribution.distinct_values != 0)) {
448 return .{
449 .field_count = 1,
450 .distinct_values = distribution.distinct_values,
451 .max_equal = distribution.max_equal,
452 .samples = distribution.samples,
453 .sample_keys = distribution.sample_keys,
454 };
455 }
456 return null;
457 }
458
459 pub fn sampleEstimate(distribution: catalog_mod.IndexDistribution, spec: relation_mod.IndexSpec, operator: ast_mod.PredicateOperator, value: row.Value, entries: usize) ?RowEstimate {
460 const prefix = distributionPrefix(distribution, 1) orelse return null;
461 const values = [_]row.Value{value};
462 return sampleEstimatePrefix(prefix, spec, operator, &values, entries);
463 }
464
465 pub fn sampleEstimatePrefix(prefix: catalog_mod.IndexPrefixDistribution, spec: relation_mod.IndexSpec, operator: ast_mod.PredicateOperator, values: []const row.Value, entries: usize) ?RowEstimate {
466 const rank = sampleRankPrefix(prefix, spec, values, entries) orelse return null;
467 return .{
468 .rows = switch (operator) {
469 .eq => if (rank.equal_count != 0)
470 rank.equal_count
471 else if (rank.estimated_equal != 0)
472 rank.estimated_equal
473 else if (prefix.distinct_values != 0)
474 @max(@as(usize, 1), entries / prefix.distinct_values)
475 else
476 @max(@as(usize, 1), entries / 16),
477 .lt => rank.less_than,
478 .lte => rank.less_than +| rank.equal_count,
479 .gt => entries -| (rank.less_than +| rank.equal_count),
480 .gte => entries -| rank.less_than,
481 },
482 .from_distribution = true,
483 };
484 }
485
486 pub fn sampleRankPrefix(prefix: catalog_mod.IndexPrefixDistribution, spec: relation_mod.IndexSpec, values: []const row.Value, entries: usize) ?SampleRank {
487 if (prefix.samples.len == 0) return null;
488 var key_buffer: [page.size]u8 = undefined;
489 const encoded = key.encodeIndexPrefix(&key_buffer, values, spec.columns) catch return null;
490 return sampleRank(prefix.samples, encoded, entries, prefix.distinct_values);
491 }
492
493 pub const SampleRank = struct {
494 less_than: usize,
495 equal_count: usize,
496 estimated_equal: usize = 0,
497 };
498
499 pub fn sampleRank(samples: []const catalog_mod.IndexSample, encoded: []const u8, entries: usize, distinct_values: usize) SampleRank {
500 var previous: ?catalog_mod.IndexSample = null;
501 for (samples) |sample| {
502 switch (std.mem.order(u8, sample.key, encoded)) {
503 .eq => return .{
504 .less_than = sample.less_than,
505 .equal_count = sample.equal_count,
506 .estimated_equal = sample.equal_count,
507 },
508 .gt => {
509 if (previous) |before| {
510 const previous_row_end = before.less_than +| before.equal_count;
511 const previous_distinct_end = before.less_distinct +| 1;
512 return .{
513 .less_than = (previous_row_end + sample.less_than) / 2,
514 .equal_count = 0,
515 .estimated_equal = localEqualEstimate(previous_row_end, previous_distinct_end, sample.less_than, sample.less_distinct),
516 };
517 }
518 return .{
519 .less_than = 0,
520 .equal_count = 0,
521 .estimated_equal = localEqualEstimate(0, 0, sample.less_than, sample.less_distinct),
522 };
523 },
524 .lt => previous = sample,
525 }
526 }
527 if (previous) |before| {
528 const previous_row_end = before.less_than +| before.equal_count;
529 const previous_distinct_end = before.less_distinct +| 1;
530 return .{
531 .less_than = entries,
532 .equal_count = 0,
533 .estimated_equal = localEqualEstimate(previous_row_end, previous_distinct_end, entries, distinct_values),
534 };
535 }
536 return .{
537 .less_than = entries,
538 .equal_count = 0,
539 };
540 }
541
542 pub fn localEqualEstimate(row_start: usize, distinct_start: usize, row_end: usize, distinct_end: usize) usize {
543 const row_gap = row_end -| row_start;
544 const distinct_gap = distinct_end -| distinct_start;
545 if (row_gap == 0 or distinct_gap == 0) return 0;
546 return @max(@as(usize, 1), row_gap / distinct_gap);
547 }
548
549 pub fn indexStatsForRoot(stats: *const catalog_mod.RelationStats, root_page: u32) ?*const catalog_mod.IndexStats {
550 for (stats.indexes) |*index_stats| {
551 if (index_stats.root_page == root_page) return index_stats;
552 }
553 return null;
554 }
555
556 pub fn indexCoversSelect(handle: *const catalog_mod.RelationHandle, index_slot: usize, fields: []const execute_mod.ProjectedColumn, select: ast_mod.Select) bool {
557 if (!indexCoversProjection(handle, index_slot, fields)) return false;
558 var offset: usize = 0;
559 while (offset < predicate_mod.selectPredicateCount(select)) : (offset += 1) {
560 if (!indexCoversPredicate(handle, index_slot, predicate_mod.selectPredicateAt(select, offset))) return false;
561 }
562 return true;
563 }
564
565 pub fn indexCoversPredicates(handle: *const catalog_mod.RelationHandle, index_slot: usize, fields: []const execute_mod.ProjectedColumn, predicates: []const ast_mod.Predicate) bool {
566 if (!indexCoversProjection(handle, index_slot, fields)) return false;
567 for (predicates) |predicate| {
568 if (!indexCoversPredicate(handle, index_slot, predicate)) return false;
569 }
570 return true;
571 }
572
573 pub fn indexCoversPredicate(handle: *const catalog_mod.RelationHandle, index_slot: usize, predicate: ast_mod.Predicate) bool {
574 return switch (predicate.column) {
575 .rowid => true,
576 .field => |name| covered: {
577 const field = columnIndex(handle.definitions, name) orelse return false;
578 const spec = handle.specs[index_slot];
579 const position = fieldPosition(spec.fields, field) orelse return false;
580 break :covered spec.columns[position].collation == handle.definitions[field].column.collation;
581 },
582 };
583 }
584
585 pub fn indexCoversProjection(handle: *const catalog_mod.RelationHandle, index_slot: usize, fields: []const execute_mod.ProjectedColumn) bool {
586 if (fields.len == 0) return false;
587 const spec = handle.specs[index_slot];
588 for (fields) |field| switch (field) {
589 .rowid => {},
590 .field => |index| {
591 const position = fieldPosition(spec.fields, index) orelse return false;
592 if (spec.columns[position].collation != .binary) return false;
593 },
594 };
595 return true;
596 }
597
598 pub fn fieldPosition(fields: []const usize, field: usize) ?usize {
599 for (fields, 0..) |candidate, position| {
600 if (candidate == field) return position;
601 }
602 return null;
603 }
604
605 pub fn columnIndex(definitions: []const catalog_mod.ColumnDefinition, name: []const u8) ?usize {
606 for (definitions, 0..) |definition, index| {
607 if (std.ascii.eqlIgnoreCase(definition.name, name)) return index;
608 }
609 return null;
610 }
611
612 test "sample estimates use local distinct density" {
613 var key0_buffer: [page.size]u8 = undefined;
614 var key10_buffer: [page.size]u8 = undefined;
615 var key20_buffer: [page.size]u8 = undefined;
616 const key0 = try key.encodeIndexPrefix(&key0_buffer, &.{.{ .integer = 0 }}, &.{});
617 const key10 = try key.encodeIndexPrefix(&key10_buffer, &.{.{ .integer = 10 }}, &.{});
618 const key20 = try key.encodeIndexPrefix(&key20_buffer, &.{.{ .integer = 20 }}, &.{});
619 var samples = [_]catalog_mod.IndexSample{
620 .{
621 .key = key0,
622 .less_than = 0,
623 .equal_count = 1,
624 .less_distinct = 0,
625 },
626 .{
627 .key = key10,
628 .less_than = 100,
629 .equal_count = 10,
630 .less_distinct = 10,
631 },
632 .{
633 .key = key20,
634 .less_than = 121,
635 .equal_count = 1,
636 .less_distinct = 20,
637 },
638 };
639 const prefix = catalog_mod.IndexPrefixDistribution{
640 .field_count = 1,
641 .distinct_values = 21,
642 .max_equal = 10,
643 .samples = samples[0..],
644 };
645 const spec = relation_mod.IndexSpec{
646 .root_page = 0,
647 .fields = &.{0},
648 };
649
650 const dense = sampleEstimatePrefix(prefix, spec, .eq, &.{.{ .integer = 5 }}, 122).?;
651 const sparse = sampleEstimatePrefix(prefix, spec, .eq, &.{.{ .integer = 15 }}, 122).?;
652
653 try std.testing.expectEqual(@as(usize, 11), dense.rows);
654 try std.testing.expectEqual(@as(usize, 1), sparse.rows);
655 try std.testing.expect(dense.rows > sparse.rows);
656 }