1 #!/usr/bin/env python

     2 #

     3 # Copyright 2007 Google Inc.

     4 #

     5 # Licensed under the Apache License, Version 2.0 (the "License");

     6 # you may not use this file except in compliance with the License.

     7 # You may obtain a copy of the License at

     8 #

     9 #     http://www.apache.org/licenses/LICENSE-2.0

    10 #

    11 # Unless required by applicable law or agreed to in writing, software

    12 # distributed under the License is distributed on an "AS IS" BASIS,

    13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

    14 # See the License for the specific language governing permissions and

    15 # limitations under the License.

    16 #

    17 

    18 """Primitives for dealing with datastore indexes.

    19 

    20 Example index.yaml file:

    21 ------------------------

    22 

    23 indexes:

    24 

    25 - kind: Cat

    26   ancestor: no

    27   properties:

    28   - name: name

    29   - name: age

    30     direction: desc

    31 

    32 - kind: Cat

    33   properties:

    34   - name: name

    35     direction: ascending

    36   - name: whiskers

    37     direction: descending

    38 

    39 - kind: Store

    40   ancestor: yes

    41   properties:

    42   - name: business

    43     direction: asc

    44   - name: owner

    45     direction: asc

    46 """

    47 

    48 

    49 

    50 

    51 

    52 from google.appengine.api import validation

    53 from google.appengine.api import yaml_errors

    54 from google.appengine.api import yaml_object

    55 from google.appengine.datastore import datastore_pb

    56 

    57 

    58 class Property(validation.Validated):

    59   """Representation for an individual property of an index.

    60 

    61   Attributes:

    62     name: Name of attribute to sort by.

    63     direction: Direction of sort.

    64   """

    65 

    66   ATTRIBUTES = {

    67       'name': validation.TYPE_STR,

    68       'direction': validation.Options(('asc', ('ascending',)),

    69                                       ('desc', ('descending',)),

    70                                       default='asc'),

    71       }

    72 

    73 

    74 class Index(validation.Validated):

    75   """Individual index definition.

    76 

    77   Order of the properties properties determins a given indixes sort priority.

    78 

    79   Attributes:

    80     kind: Datastore kind that index belongs to.

    81     ancestors: Include ancestors in index.

    82     properties: Properties to sort on.

    83   """

    84 

    85   ATTRIBUTES = {

    86       'kind': validation.TYPE_STR,

    87       'ancestor': validation.Type(bool, default=False),

    88       'properties': validation.Optional(validation.Repeated(Property)),

    89       }

    90 

    91 

    92 class IndexDefinitions(validation.Validated):

    93   """Top level for index definition file.

    94 

    95   Attributes:

    96     indexes: List of Index definitions.

    97   """

    98 

    99   ATTRIBUTES = {

   100       'indexes': validation.Optional(validation.Repeated(Index)),

   101       }

   102 

   103 

   104 def ParseIndexDefinitions(document):

   105   """Parse an individual index definitions document from string or stream.

   106 

   107   Args:

   108     document: Yaml document as a string or file-like stream.

   109 

   110   Raises:

   111     EmptyConfigurationFile when the configuration file is empty.

   112     MultipleConfigurationFile when the configuration file contains more than

   113     one document.

   114 

   115   Returns:

   116     Single parsed yaml file if one is defined, else None.

   117   """

   118   try:

   119     return yaml_object.BuildSingleObject(IndexDefinitions, document)

   120   except yaml_errors.EmptyConfigurationFile:

   121     return None

   122 

   123 

   124 def ParseMultipleIndexDefinitions(document):

   125   """Parse multiple index definitions documents from a string or stream.

   126 

   127   Args:

   128     document: Yaml document as a string or file-like stream.

   129 

   130   Returns:

   131     A list of datstore_index.IndexDefinitions objects, one for each document.

   132   """

   133   return yaml_object.BuildObjects(IndexDefinitions, document)

   134 

   135 

   136 def IndexDefinitionsToKeys(indexes):

   137   """Convert IndexDefinitions to set of keys.

   138 

   139   Args:

   140     indexes: A datastore_index.IndexDefinitions instance, or None.

   141 

   142   Returns:

   143     A set of keys constructed from the argument, each key being a

   144     tuple of the form (kind, ancestor, properties) where properties is

   145     a tuple of (name, direction) pairs, direction being ASCENDING or

   146     DESCENDING (the enums).

   147   """

   148   keyset = set()

   149   if indexes is not None:

   150     if indexes.indexes:

   151       for index in indexes.indexes:

   152         keyset.add(IndexToKey(index))

   153   return keyset

   154 

   155 

   156 def IndexToKey(index):

   157   """Convert Index to key.

   158 

   159   Args:

   160     index: A datastore_index.Index instance (not None!).

   161 

   162   Returns:

   163     A tuple of the form (kind, ancestor, properties) where properties

   164     is a tuple of (name, direction) pairs, direction being ASCENDING

   165     or DESCENDING (the enums).

   166   """

   167   props = []

   168   if index.properties is not None:

   169     for prop in index.properties:

   170       if prop.direction == 'asc':

   171         direction = ASCENDING

   172       else:

   173         direction = DESCENDING

   174       props.append((prop.name, direction))

   175   return index.kind, index.ancestor, tuple(props)

   176 

   177 

   178 

   179 

   180 ASCENDING = datastore_pb.Query_Order.ASCENDING

   181 DESCENDING = datastore_pb.Query_Order.DESCENDING

   182 

   183 EQUALITY_OPERATORS = set((datastore_pb.Query_Filter.EQUAL,

   184                           ))

   185 INEQUALITY_OPERATORS = set((datastore_pb.Query_Filter.LESS_THAN,

   186                             datastore_pb.Query_Filter.LESS_THAN_OR_EQUAL,

   187                             datastore_pb.Query_Filter.GREATER_THAN,

   188                             datastore_pb.Query_Filter.GREATER_THAN_OR_EQUAL,

   189                             ))

   190 EXISTS_OPERATORS = set((datastore_pb.Query_Filter.EXISTS,

   191                         ))

   192 

   193 

   194 def CompositeIndexForQuery(query):

   195   """Return the composite index needed for a query.

   196 

   197   A query is translated into a tuple, as follows:

   198 

   199   - The first item is the kind string, or None if we're not filtering

   200     on kind (see below).

   201 

   202   - The second item is a bool giving whether the query specifies an

   203     ancestor.

   204 

   205   - After that come (property, ASCENDING) pairs for those Filter

   206     entries whose operator is EQUAL or IN.  Since the order of these

   207     doesn't matter, they are sorted by property name to normalize them

   208     in order to avoid duplicates.

   209 

   210   - After that comes at most one (property, ASCENDING) pair for a

   211     Filter entry whose operator is on of the four inequalities.  There

   212     can be at most one of these.

   213 

   214   - After that come all the (property, direction) pairs for the Order

   215     entries, in the order given in the query.  Exceptions: (a) if

   216     there is a Filter entry with an inequality operator that matches

   217     the first Order entry, the first order pair is omitted (or,

   218     equivalently, in this case the inequality pair is omitted); (b) if

   219     an Order entry corresponds to an equality filter, it is ignored

   220     (since there will only ever be one value returned).

   221 

   222   - Finally, if there are Filter entries whose operator is EXISTS, and

   223     whose property names are not already listed, they are added, with

   224     the direction set to ASCENDING.

   225 

   226   This algorithm should consume all Filter and Order entries.

   227 

   228   Additional notes:

   229 

   230   - The low-level implementation allows queries that don't specify a

   231     kind; but the Python API doesn't support this yet.

   232 

   233   - If there's an inequality filter and one or more sort orders, the

   234     first sort order *must* match the inequality filter.

   235 

   236   - The following indexes are always built in and should be suppressed:

   237     - query on kind only;

   238     - query on kind and one filter *or* one order;

   239     - query on ancestor only, without kind (not exposed in Python yet);

   240     - query on kind and equality filters only, no order (with or without

   241       ancestor).

   242 

   243   - While the protocol buffer allows a Filter to contain multiple

   244     properties, we don't use this.  It is only needed for the IN operator

   245     but this is (currently) handled on the client side, so in practice

   246     each Filter is expected to have exactly one property.

   247 

   248   Args:

   249     query: A datastore_pb.Query instance.

   250 

   251   Returns:

   252     None if no composite index is needed for this query.  Otherwise,

   253     a tuple of the form (kind, ancestor, (prop1, prop2, ...), neq) where:

   254       kind: the kind or None;

   255       ancestor: True if this is an ancestor query;

   256       prop1, prop2, ...: tuples of the form (name, direction) where:

   257         name: a property name;

   258         direction: datastore_pb.Query_Order.ASCENDING or ...DESCENDING;

   259       neq: the number of prop tuples corresponding to equality filters.

   260   """

   261   kind = query.kind()

   262   ancestor = query.has_ancestor()

   263   filters = query.filter_list()

   264   orders = query.order_list()

   265 

   266   for filter in filters:

   267     assert filter.op() != datastore_pb.Query_Filter.IN, 'Filter.op()==IN'

   268     nprops = len(filter.property_list())

   269     assert nprops == 1, 'Filter has %s properties, expected 1' % nprops

   270 

   271   if ancestor and not kind and not filters and not orders:

   272     return None

   273 

   274   eq_filters = [f for f in filters if f.op() in EQUALITY_OPERATORS]

   275   ineq_filters = [f for f in filters if f.op() in INEQUALITY_OPERATORS]

   276   exists_filters = [f for f in filters if f.op() in EXISTS_OPERATORS]

   277   assert (len(eq_filters) + len(ineq_filters) +

   278           len(exists_filters)) == len(filters), 'Not all filters used'

   279 

   280   if (kind and eq_filters and not ineq_filters and not exists_filters and

   281       not orders):

   282     return None

   283 

   284   ineq_property = None

   285   if ineq_filters:

   286     ineq_property = ineq_filters[0].property(0).name()

   287     for filter in ineq_filters:

   288       assert filter.property(0).name() == ineq_property

   289 

   290   new_orders = []

   291   for order in orders:

   292     name = order.property()

   293     for filter in eq_filters:

   294       if filter.property(0).name() == name:

   295         break

   296     else:

   297       new_orders.append(order)

   298   orders = new_orders

   299 

   300   props = []

   301 

   302   for f in eq_filters:

   303     prop = f.property(0)

   304     props.append((prop.name(), ASCENDING))

   305 

   306   props.sort()

   307 

   308   if ineq_property:

   309     if orders:

   310       assert ineq_property == orders[0].property()

   311     else:

   312       props.append((ineq_property, ASCENDING))

   313 

   314   for order in orders:

   315     props.append((order.property(), order.direction()))

   316 

   317   for filter in exists_filters:

   318     prop = filter.property(0)

   319     prop_name = prop.name()

   320     for name, direction in props:

   321       if name == prop_name:

   322         break

   323     else:

   324       props.append((prop_name, ASCENDING))

   325 

   326   if (kind and not ancestor and

   327       (not props or (len(props) == 1 and props[0][1] == ASCENDING))):

   328     return None

   329 

   330   unique_names = set(name for name, dir in props)

   331   if len(props) > 1 and len(unique_names) == 1:

   332     return None

   333 

   334   return (kind, ancestor, tuple(props), len(eq_filters))

   335 

   336 

   337 def IndexYamlForQuery(kind, ancestor, props):

   338   """Return the composite index definition YAML needed for a query.

   339 

   340   The arguments are the same as the tuples returned by CompositeIndexForQuery,

   341   without the last neq element.

   342 

   343   Args:

   344     kind: the kind or None

   345     ancestor: True if this is an ancestor query, False otherwise

   346     prop1, prop2, ...: tuples of the form (name, direction) where:

   347         name: a property name;

   348         direction: datastore_pb.Query_Order.ASCENDING or ...DESCENDING;

   349 

   350   Returns:

   351     A string with the YAML for the composite index needed by the query.

   352   """

   353   yaml = []

   354   yaml.append('- kind: %s' % kind)

   355   if ancestor:

   356     yaml.append('  ancestor: yes')

   357   if props:

   358     yaml.append('  properties:')

   359     for name, direction in props:

   360       yaml.append('  - name: %s' % name)

   361       if direction == DESCENDING:

   362         yaml.append('    direction: desc')

   363   return '\n'.join(yaml)