in src/google/appengine/datastore/datastore_index.py [0:0]
def CompositeIndexForQuery(query):
"""Returns the composite index needed for a query.
A query is translated into a tuple, as follows:
- The first item is the kind string, or `None` if we're not filtering
on kind (see below).
- The second item is a bool giving whether the query specifies an
ancestor.
- After that come `(property, ASCENDING)` pairs for those Filter
entries whose operator is `EQUAL` or `IN`. Since the order of these
doesn't matter, they are sorted by property name to normalize them
in order to avoid duplicates.
- After that comes at most one `(property, ASCENDING)` pair for a
Filter entry whose operator is on of the four inequalities. There
can be at most one of these.
- After that come all the `(property, direction)` pairs for the Order
entries, in the order given in the query. Exceptions:
- (a) If there is a Filter entry with an inequality operator that matches
the first Order entry, the first order pair is omitted (or,
equivalently, in this case the inequality pair is omitted).
- (b) If an Order entry corresponds to an equality filter, it is ignored
(since there will only ever be one value returned).
- (c) If there is an equality filter on `__key__` all orders are dropped
(since there will be at most one result returned).
- (d) If there is an order on `__key__` all further orders are dropped
(since keys are unique).
- (e) Orders on `__key__` `ASCENDING` are dropped (since this is supported
natively by the datastore).
- Finally, if there are Filter entries whose operator is `EXISTS`, and
whose property names are not already listed, they are added, with
the direction set to `ASCENDING`.
This algorithm should consume all Filter and Order entries.
Additional notes:
- The low-level implementation allows queries that don't specify a
kind; but the Python `API` doesn't support this yet.
- If there's an inequality filter and one or more sort orders, the
first sort order *must* match the inequality filter.
- The following indexes are always built in and should be suppressed:
- Query on kind only;
- Query on kind and one filter *or* one order;
- Query on ancestor only, without kind (not exposed in Python yet);
- Query on kind and equality filters only, no order (with or without
ancestor).
- While the protocol buffer allows a Filter to contain multiple
properties, we don't use this. It is only needed for the `IN` operator
but this is (currently) handled on the client side, so in practice
each Filter is expected to have exactly one property.
Args:
query: A `datastore_pb.Query` instance.
Returns:
A tuple of the form `(required, kind, ancestor, properties)`.
`required`: Boolean, whether the index is required;
`kind`: The kind or None;
`ancestor`: True if this is an ancestor query;
`properties`: A tuple consisting of:
- The prefix, represented by a set of property names.
- The postfix, represented by a tuple consisting of any number of:
- Sets of property names or `PropertySpec` objects: these
properties can appear in any order.
- Sequences of `PropertySpec` objects: Indicates the properties
must appear in the given order, with the specified direction (if
specified in the `PropertySpec`).
"""
required = True
kind = query.kind
ancestor = query.HasField('ancestor')
filters = query.filter
orders = query.order
for filter in filters:
assert filter.op != datastore_pb.Query.Filter.IN, 'Filter.op==IN'
nprops = len(filter.property)
assert nprops == 1, 'Filter has %s properties, expected 1' % nprops
if filter.op == datastore_pb.Query.Filter.CONTAINED_IN_REGION:
return CompositeIndexForGeoQuery(query)
if not kind:
required = False
exists = list(query.property_name)
exists.extend(query.group_by_property_name)
filters, orders = RemoveNativelySupportedComponents(filters, orders, exists)
eq_filters = [f for f in filters if f.op in EQUALITY_OPERATORS]
ineq_filters = [f for f in filters if f.op in INEQUALITY_OPERATORS]
exists_filters = [f for f in filters if f.op in EXISTS_OPERATORS]
assert (len(eq_filters) + len(ineq_filters) +
len(exists_filters)) == len(filters), 'Not all filters used'
if (kind and not ineq_filters and not exists_filters and
not orders):
names = set(f.property[0].name for f in eq_filters)
if not names.intersection(datastore_types._SPECIAL_PROPERTIES):
required = False
ineq_property = None
if ineq_filters:
for filter in ineq_filters:
if (filter.property[0].name ==
datastore_types._UNAPPLIED_LOG_TIMESTAMP_SPECIAL_PROPERTY):
continue
if not ineq_property:
ineq_property = filter.property[0].name
else:
assert filter.property[0].name == ineq_property
group_by_props = set(query.group_by_property_name)
prefix = frozenset(f.property[0].name for f in eq_filters)
postfix_ordered = [
PropertySpec(name=order.property, direction=order.direction)
for order in orders
]
postfix_group_by = frozenset(f.property[0].name
for f in exists_filters
if f.property[0].name in group_by_props)
postfix_unordered = frozenset(f.property[0].name
for f in exists_filters
if f.property[0].name not in group_by_props)
if ineq_property:
if orders:
assert ineq_property == orders[0].property
else:
postfix_ordered.append(PropertySpec(name=ineq_property))
property_count = (len(prefix) + len(postfix_ordered) + len(postfix_group_by)
+ len(postfix_unordered))
if kind and not ancestor and property_count <= 1:
required = False
if postfix_ordered:
prop = postfix_ordered[0]
if (prop.name == datastore_types.KEY_SPECIAL_PROPERTY and
prop.direction == DESCENDING):
required = True
props = prefix, (tuple(postfix_ordered), postfix_group_by, postfix_unordered)
return required, kind, ancestor, props