///|
priv struct IndexConstraint {
column : Int32
collation : String
op : String
value : Value
}
///|
priv struct IndexRange {
rows : Array[StoredRow]
start : Int32
end : Int32
reverse : Bool
residual : Bool
}
///|
fn index_column(table : Table, expression : Expr, qualifier : String) -> Int32? {
if expression is Collate(e, _) {
return index_column(table, e, qualifier)
}
guard expression is Column(q, name) &&
(q == "" || matches_identifier(q, identifier(qualifier))) else {
return None
}
let key = identifier(name)
for i, column in table.columns {
if matches_identifier(column.name, key) {
return Some(i)
}
}
if !table.without_rowid && ["rowid", "_rowid_", "oid"].contains(key) {
Some(-1)
} else {
None
}
}
///|
fn same_index_column(table : Table, a : Int32, b : Int32) -> Bool {
a == b ||
(
integer_primary(table) >= 0 &&
(
(a == -1 && b == integer_primary(table)) ||
(b == -1 && a == integer_primary(table))
)
)
}
///|
fn index_collation(table : Table, expression : Expr, column : Int32) -> String {
if expression is Collate(_, name) {
identifier(name)
} else if column < 0 {
"binary"
} else {
table.columns[column].collation
}
}
///|
/// ORDER BY resolves output aliases, preserving * expansion priority.
fn index_order_term(
select : Selection,
table : Table,
qualifier : String,
order : Ordering,
) -> IndexField? {
let mut expression = order.expression
let explicit = if expression is Collate(inner, name) {
expression = inner
Some(name)
} else {
None
}
if expression is Column("", name) {
let key = identifier(name)
for projection in select.projections {
if projection.expression is Star(_) {
let found = table.columns.filter(c => matches_identifier(c.name, key))
if !found.is_empty() {
expression = Column(qualifier, found[0].name)
break
}
}
if matches_identifier(projection.label, key) {
expression = projection.expression
break
}
}
}
guard index_column(table, expression, qualifier) is Some(column) else {
return None
}
Some({
column,
collation: explicit
.map(identifier)
.unwrap_or(index_collation(table, expression, column)),
descending: order.descending,
})
}
///|
fn index_value(expression : Expr, params : Array[Value]) -> Value? {
match expression {
Literal(value) => Some(value)
Parameter(i) =>
if i >= 0 && i < params.length() {
Some(params[i])
} else {
None
}
_ => None
}
}
///|
/// Only simple AND comparisons are extracted. Other predicates use the evaluator.
fn index_constraints(
expression : Expr,
table : Table,
qualifier : String,
params : Array[Value],
constraints : Array[IndexConstraint],
) -> Bool {
if expression is Literal(Integer(1L)) {
return true
}
guard expression is Binary(op, left, right) else { return false }
if op == "and" {
return index_constraints(left, table, qualifier, params, constraints) &&
index_constraints(right, table, qualifier, params, constraints)
}
guard ["=", "==", ">", ">=", "<", "<="].contains(op) else { return false }
let (column, collation, operator, bound) = if index_column(
table, left, qualifier,
)
is Some(column) {
(
column,
if right is Collate(_, name) {
identifier(name)
} else {
index_collation(table, left, column)
},
op,
index_value(right, params),
)
} else if index_column(table, right, qualifier) is Some(column) {
(
column,
if left is Collate(_, name) {
identifier(name)
} else {
index_collation(table, right, column)
},
match op {
">" => "<"
">=" => "<="
"<" => ">"
"<=" => ">="
_ => op
},
index_value(left, params),
)
} else {
return false
}
guard bound is Some(value) else { return false }
let affinity = if column < 0 {
"integer"
} else {
affinity_name(table.columns[column].declared)
}
let value = if ["integer", "numeric", "real"].contains(affinity) {
apply_affinity(value, "numeric")
} else if affinity == "text" {
apply_affinity(value, "text")
} else {
value
}
constraints.push({ column, collation, op: operator, value, })
true
}
///|
fn field_constraints(
table : Table,
field : IndexField,
constraints : Array[IndexConstraint],
) -> Array[IndexConstraint] {
constraints.filter(c => {
same_index_column(table, field.column, c.column) &&
field.collation == c.collation
})
}
///|
fn field_fixed(
table : Table,
field : IndexField,
constraints : Array[IndexConstraint],
) -> Bool {
field_constraints(table, field, constraints).any(c => {
c.op == "=" || c.op == "=="
})
}
///|
fn index_order_matches(
table : Table,
fields : Array[IndexField],
orders : Array[IndexField],
constraints : Array[IndexConstraint],
reverse : Bool,
) -> Bool {
let keys = fields + [{ column: -1, collation: "binary", descending: false, }]
let mut position = 0
for order in orders {
// An equality-constrained column is constant in the filtered result.
if field_fixed(table, order, constraints) {
continue
}
while position < keys.length() &&
field_fixed(table, keys[position], constraints) {
position += 1
}
guard position < keys.length() else { return false }
let field = keys[position]
guard same_index_column(table, field.column, order.column) &&
field.collation == order.collation &&
(field.descending != reverse) == order.descending else {
return false
}
position += 1
}
true
}
///|
fn secondary_range(
select : Selection,
context : Evaluation,
table : Table,
qualifier : String,
) -> IndexRange? raise SqlError {
guard !select.orders.is_empty() else { return None }
let orders : Array[IndexField] = []
for order in select.orders {
guard index_order_term(select, table, qualifier, order) is Some(term) else {
return None
}
orders.push(term)
}
let constraints : Array[IndexConstraint] = []
guard index_constraints(
select.predicate,
table,
qualifier,
context.params,
constraints,
) else {
return None
}
for object in context.store.objects {
if object.kind != "index" ||
!matches_identifier(object.table, identifier(table.name)) ||
object.columns.any(n => n == "") {
continue
}
if object.index_predicate is Some(predicate) &&
!index_predicate_implied(predicate, select.predicate) {
continue
}
let fields = index_fields(table, object)
let reverse = if index_order_matches(
table, fields, orders, constraints, false,
) {
false
} else if index_order_matches(table, fields, orders, constraints, true) {
true
} else {
continue
}
if constraints.any(c => c.value is Null) {
return Some({ rows: [], start: 0, end: 0, reverse, residual: false, })
}
let rows = index_rows_for_fields(
context.store,
table,
object.name,
fields,
object.index_predicate,
)
let prefix : Array[Value] = []
let mut start = 0
let mut end = rows.length()
for field in fields {
let bounds = field_constraints(table, field, constraints)
if bounds.is_empty() {
break
}
// NULL is sorted, but never satisfies an ordinary comparison.
if field.descending {
end = end.min(
index_prefix_bound(
context.store,
rows,
fields,
prefix + [Null],
false,
),
)
} else {
start = start.max(
index_prefix_bound(context.store, rows, fields, prefix + [Null], true),
)
}
for c in bounds {
let lower = c.op == ">" || c.op == ">=" || c.op == "=" || c.op == "=="
let upper = c.op == "<" || c.op == "<=" || c.op == "=" || c.op == "=="
if lower {
let n = index_prefix_bound(
context.store,
rows,
fields,
prefix + [c.value],
if field.descending {
c.op != ">"
} else {
c.op == ">"
},
)
if field.descending {
end = end.min(n)
} else {
start = start.max(n)
}
}
if upper {
let n = index_prefix_bound(
context.store,
rows,
fields,
prefix + [c.value],
if field.descending {
c.op == "<"
} else {
c.op != "<"
},
)
if field.descending {
start = start.max(n)
} else {
end = end.min(n)
}
}
}
let equal = bounds.filter(c => c.op == "=" || c.op == "==")
if equal.is_empty() {
break
}
prefix.push(equal[0].value)
}
let residual = fields.length() != 1 ||
constraints.any(c => {
!same_index_column(table, c.column, fields[0].column) ||
c.collation != fields[0].collation
})
return Some({ rows, start, end: end.max(start), reverse, residual, })
}
None
}
///|
/// Deliberately conservative implication: identical conjuncts only.
fn index_predicate_implied(required : Expr, predicate : Expr) -> Bool {
if required is Binary("and", a, b) {
return index_predicate_implied(a, predicate) &&
index_predicate_implied(b, predicate)
}
if @json.to_json(required) == @json.to_json(predicate) {
return true
}
if predicate is Binary("and", a, b) {
return index_predicate_implied(required, a) ||
index_predicate_implied(required, b)
}
false
}