Sign in

1. Products
2. Google Cloud Platform
3. Google Cloud Datastore

Google Cloud Datastore

Feedback on this document

Datastore Indexes

Every Datastore query computes its results using one or more indexes, tables containing entities in a sequence specified by the index's properties and, optionally, the entity's ancestors. The indexes are updated incrementally to reflect any changes the application makes to its entities, so that the correct results of all queries are immediately available with no further computation needed.

The Datastore predefines a simple index on each property of an entity. You can define further custom indexes in an index configuration file

Note: The index-based query mechanism supports a wide range of queries and is suitable for most applications. However, it does not support some kinds of query common in other database technologies: in particular, joins and aggregate queries aren't supported within the Datastore query engine. See the Datastore Queries page for limitations on Datastore queries.

Contents

1. Index definition and structure
2. Index configuration
3. Indexes and properties
   1. Properties with mixed value types
   2. Unindexed properties
4. Index limits

Index definition and structure

An index is defined on a list of properties of a given entity kind , with a corresponding order (ascending or descending) for each property. For use with ancestor queries, the index may also optionally include an entity's ancestors.

An index table contains a column for every property named in the index's definition. Each row of the table represents an entity in the Datastore that is a potential result for queries based on the index. An entity is included in the index only if it has an indexed value set for every property used in the index; if the index definition refers to a property for which the entity has no value, that entity will not appear in the index and hence will never be returned as a result for any query based on the index.

The rows of an index table are sorted first by ancestor and then by property values, in the order specified in the index definition. The perfect index for a query, which allows the query to be executed most efficiently, is defined on the following properties, in order:

1. Properties used in equality filters
2. Property used in an inequality filter (of which there can be no more than one )
3. Properties used in sort orders

This ensures that all results for every possible execution of the query appear in consecutive rows of the table. The Datastore executes a query using a perfect index by the following steps:

1. Identifies the index corresponding to the query's kind, filter properties, filter operators, and sort orders.
2. Scans from the beginning of the index to the first entity that meets all of the query's filter conditions.
3. Continues scanning the index, returning each entity in turn, until it
   • encounters an entity that does not meet the filter conditions, or
   • reaches the end of the index, or
   • has collected the maximum number of results requested by the query.

For example, consider the following query:

datastore.runQuery({
  query: {
    kinds: [{ name: 'Person' }],
    filter: {
      compositeFilter: {
        operator: 'AND',
        filters: [{
          propertyFilter: {
            property: { name: 'lastName' },
            operator: 'EQUAL',
            value: { stringValue: 'Smith' }
          }
        }, {
          propertyFilter: {
            property: { name: 'height' },
            operator: 'LESS_THAN',
            value: { integerValue: 72 }
          }
        }]
      }
    },
    order: [{ property: { name: 'height' }, direction: 'DESCENDING' }]
  }
}).execute(callback);

query = datastore.Query()

query.kind.add().name = 'Person'

composite_filter = query.filter.composite_filter
composite_filter.operator = datastore.CompositeFilter.AND

last_name_filter = composite_filter.filter.add().property_filter
last_name_filter.property.name = 'last_name'
last_name_filter.operator = datastore.PropertyFilter.EQUAL
last_name_filter.value.string_value = 'Smith'

height_filter = composite_filter.filter.add().property_filter
height_filter.property.name = 'height'
height_filter.operator = datastore.PropertyFilter.LESS_THAN
height_filter.value.integer_value = 72

order = query.order.add()
order.property.name = 'height'
order.direction = datastore.PropertyOrder.DESCENDING

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Person");
query.setFilter(makeFilter(
    makeFilter("lastName", PropertyFilter.Operator.EQUAL, makeValue("Smith")).build(),
    makeFilter("height", PropertyFilter.Operator.LESS_THAN, makeValue(72)).build()));
query.addOrder(makeOrder("height", PropertyOrder.Direction.DESCENDING));

The perfect index for this query is a table of keys for entities of kind Person , with columns for the values of the last_name and height properties. The index is sorted first in ascending order by last_name and then in descending order by height .

Two queries of the same form but with different filter values use the same index. For example, the following query uses the same index as the one above:

datastore.runQuery({
  query: {
    kinds: [{ name: 'Person' }],
    filter: {
      compositeFilter: {
        operator: 'AND',
        filters: [{
          propertyFilter: {
            property: { name: 'lastName' },
            operator: 'EQUAL',
            value: { stringValue: 'Smith' }
          }
        }, {
          propertyFilter: {
            property: { name: 'height' },
            operator: 'LESS_THAN',
            value: { integerValue: 63 }
          }
        }]
      }
    },
    order: [{ property: { name: 'height' }, direction: 'DESCENDING' }]
  }
}).execute(callback);

query = datastore.Query()

query.kind.add().name = 'Person'

composite_filter = query.filter.composite_filter
composite_filter.operator = datastore.CompositeFilter.AND

last_name_filter = composite_filter.filter.add().property_filter
last_name_filter.property.name = 'last_name'
last_name_filter.operator = datastore.PropertyFilter.EQUAL
last_name_filter.value.string_value = 'Jones'

height_filter = composite_filter.filter.add().property_filter
height_filter.property.name = 'height'
height_filter.operator = datastore.PropertyFilter.LESS_THAN
height_filter.value.integer_value = 63

order = query.order.add()
order.property.name = 'height'
order.direction = datastore.PropertyOrder.DESCENDING

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Person");
query.setFilter(makeFilter(
    makeFilter("lastName", PropertyFilter.Operator.EQUAL, makeValue("Jones")).build(),
    makeFilter("height", PropertyFilter.Operator.LESS_THAN, makeValue(63)).build()));
query.addOrder(makeOrder("height", PropertyOrder.Direction.DESCENDING));

The following two queries also use the same index, despite their different forms:

datastore.runQuery({
  query: {
    kinds: [{ name: 'Person' }],
    filter: {
      compositeFilter: {
        operator: 'AND',
        filters: [{
          propertyFilter: {
            property: { name: 'firstName' },
            operator: 'EQUAL',
            value: { stringValue: 'Friedkin' }
          }
        }, {
          propertyFilter: {
            property: { name: 'lastName' },
            operator: 'EQUAL',
            value: { stringValue: 'Damian' }
          }
        }]
      }
    },
    order: [{ property: { name: 'height' }, direction: 'ASCENDING' }]
  }
}).execute(callback);

query = datastore.Query()

query.kind.add().name = 'Person'

composite_filter = query.filter.composite_filter
composite_filter.operator = datastore.CompositeFilter.AND

last_name_filter = composite_filter.filter.add().property_filter
last_name_filter.property.name = 'last_name'
last_name_filter.operator = datastore.PropertyFilter.EQUAL
last_name_filter.value.string_value = 'Friedkin'

first_name_filter = composite_filter.filter.add().property_filter
first_name_filter.property.name = 'first_name'
first_name_filter.operator = datastore.PropertyFilter.EQUAL
first_name_filter.value.string_value = 'Damian'

order = query.order.add()
order.property.name = 'height'
order.direction = datastore.PropertyOrder.ASCENDING

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Person");
query.setFilter(makeFilter(
    makeFilter("lastName", PropertyFilter.Operator.EQUAL, makeValue("Friedkin")).build(),
    makeFilter("firstName", PropertyFilter.Operator.EQUAL, makeValue("Damian")).build()));
query.addOrder(makeOrder("height", PropertyOrder.Direction.ASCENDING));

and

datastore.runQuery({
  query: {
    kinds: [{ name: 'Person' }],
    filter: {
      propertyFilter: {
        property: { name: 'lastName' },
        operator: 'EQUAL',
        value: { stringValue: 'Blair' }
      }
    },
    order: [{ property: { name: 'firstName' }, direction: 'ASCENDING' },
            { property: { name: 'height' }, direction: 'ASCENDING' }]
  }
}).execute(callback);

query = datastore.Query()

query.kind.add().name = 'Person'

last_name_filter = query.filter.property_filter
last_name_filter.property.name = 'last_name'
last_name_filter.operator = datastore.PropertyFilter.EQUAL
last_name_filter.value.string_value = 'Blair'

first_name_order = query.order.add()
first_name_order.property.name = 'first_name'
first_name_order.direction = datastore.PropertyOrder.ASCENDING

height_order = query.order.add()
height_order.property.name = 'height'
height_order.direction = datastore.PropertyOrder.ASCENDING

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Person");
query.setFilter(
    makeFilter("lastName", PropertyFilter.Operator.EQUAL, makeValue("Blair")).build());
query.addOrder(makeOrder("firstName", PropertyOrder.Direction.ASCENDING));
query.addOrder(makeOrder("height", PropertyOrder.Direction.ASCENDING));

Index configuration

By default, the Datastore automatically predefines an index for each property of each entity kind. These predefined indexes are sufficient to perform many simple queries, such as equality-only queries and simple inequality queries. For all other queries, the application must define the indexes it needs in an index configuration file named datastore-indexes.xml . If the application tries to perform a query that cannot be executed with the available indexes (either predefined or specified in the index configuration file), the query will fail.

The Datastore builds automatic indexes for queries of the following forms:

• Kindless queries using only ancestor and key filters
• Queries using only ancestor and equality filters
• Queries using only inequality filters (which are limited to a single property )
• Queries using only ancestor filters, equality filters on properties, and inequality filters on keys
• Queries with no filters and only one sort order on a property, either ascending or descending

Other forms of query require their indexes to be specified in the index configuration file, including:

• Queries with ancestor and inequality filters
• Queries with one or more inequality filters on a property and one or more equality filters on other properties
• Queries with a sort order on keys in descending order
• Queries with multiple sort orders

Indexes and properties

Here are a few special considerations to keep in mind about indexes and how they relate to the properties of entities in the Datastore:

Properties with mixed value types

When two entities have properties of the same name but different value types, an index of the property sorts the entities first by value type and then by a secondary ordering appropriate to each type. For example, if two entities each have a property named age , one with an integer value and one with a string value, the entity with the integer value always precedes the one with the string value when sorted by the age property, regardless of the property values themselves.

This is especially worth noting in the case of integers and floating-point numbers, which are treated as separate types by the Datastore. Because all integers are sorted before all floats, a property with the integer value 38 is sorted before one with the floating-point value 37.5 .

Unindexed properties

If you know you will never have to filter or sort on a particular property, you can tell the Datastore not to maintain index entries for that property by setting the property's indexed value to False . This lowers the cost of running your application by decreasing the number of Datastore writes it has to perform. An entity with an unindexed property behaves as if the property were not set: queries with a filter or sort order on the unindexed property will never match that entity.

In the following snippet, Lucy's age property has its indexed value set to False , which means that property will not be indexed.

// parent entity key path.
var acmeGroup = { kind: 'Company', name: 'Acme' };
datastore.commit({
  mutation: {
    upsert: [{
      // parent entity.
      key: { path: [acmeGroup] },
    }, {
      // child entity.
      key: { path: [acmeGroup, { kind: 'Person', name: 'Tom' }] },
      properties: {
        name: { stringValue: 'Tom' },
        age: { integerValue: 32 }
      }
    }, {
      // child entity with unindexed age property.
      key: { path: [acmeGroup, { kind: 'Person', name: 'Lucy' }] },
      properties: {
        name: { stringValue: 'Tom' },
        age: { integerValue: 29, indexed: false }
      }
    }]
  },
  mode: 'NON_TRANSACTIONAL'
}).execute(function(err, result) {
  datastore.runQuery({
    query: {
      kinds: [{ name: 'Person' }],
      filter: {
        compositeFilter: {
          operator: 'AND',
          filters: [{
            propertyFilter: {
              property: { name: '__key__' },
              operator: 'HAS_ANCESTOR',
              value: { keyValue: { path: [acmeGroup] } }
            }
          }, {
            propertyFilter: {
              property: { name: 'age' },
              operator: 'GREATER_THAN',
              value: { integerValue: 25 }
            }
          }]
        }
      }
    }
  }).execute(function(err, result) {
    // returns tom but not lucy, because her age property is unindexed.
    console.assert(!err, err);
    callback(err, result.batch.entityResults);
  });
});

acme_key = datastore.Key()
path_element = acme_key.path_element.add()
path_element.kind = 'Company'
path_element.name = 'Acme'

# Make tom a child of acme_key
tom = datastore.Entity()
tom.key.path_element.extend(acme_key.path_element)
tom.key.path_element.add().kind = 'Person'

name_property = tom.property.add()
name_property.name = 'name'
name_property.value.string_value = 'Tom'

age_property = tom.property.add()
age_property.name = 'age'
age_value = age_property.value
age_value.integer_value = 32

req = datastore.CommitRequest()
req.mode = datastore.CommitRequest.NON_TRANSACTIONAL
req.mutation.insert_auto_id.extend([tom])
self.datastore.commit(req)

# Make lucy a child of acme_key
lucy = datastore.Entity()
tom.key.path_element.extend(acme_key.path_element)
lucy.key.path_element.add().kind = 'Person'

name_property = lucy.property.add()
name_property.name = 'name'
name_property.value.string_value = 'Lucy'

age_property = lucy.property.add()
age_property.name = 'age'
age_value = age_property.value
age_value.integer_value = 29
age_value.indexed = False

req = datastore.CommitRequest()
req.mode = datastore.CommitRequest.NON_TRANSACTIONAL
req.mutation.insert_auto_id.extend([lucy])
self.datastore.commit(req)

run_query = datastore.RunQueryRequest()
query = run_query.query
query.kind.add().name = 'Person'
query.filter.composite_filter.operator = datastore.CompositeFilter.AND

ancestor_filter = query.filter.composite_filter.filter.add().property_filter
ancestor_filter.property.name = '__key__'
ancestor_filter.operator = datastore.PropertyFilter.HAS_ANCESTOR
ancestor_filter.value.key_value.CopyFrom(acme_key)

age_filter = query.filter.composite_filter.filter.add().property_filter
age_filter.property.name = 'age'
age_filter.operator = datastore.PropertyFilter.GREATER_THAN
age_filter.value.integer_value = 25

# Returns tom but not lucy, because her age is unindexed
resp = self.datastore.run_query(run_query)

Key acmeKey = makeKey("Company", "Acme").build();
Entity.Builder tom = Entity.newBuilder();

// Make tom a child of acmeKey
tom.setKey(makeKey("Company", "Acme", "Person", "Tom"));
tom.addProperty(makeProperty("name", makeValue("Tom")));
tom.addProperty(makeProperty("age", makeValue(32)));
CommitRequest commitRequest = CommitRequest.newBuilder()
    .setMode(CommitRequest.Mode.NON_TRANSACTIONAL)
    .setMutation(Mutation.newBuilder().addInsert(tom))
    .build();
datastore.commit(commitRequest);

Entity.Builder lucy = Entity.newBuilder();
// Make lucy a child of acmeKey
lucy.setKey(makeKey("Company", "Acme", "Person", "Lucy"));
lucy.addProperty(makeProperty("name", makeValue("Lucy")));
lucy.addProperty(makeProperty("age", makeValue(32).setIndexed(false)));
commitRequest = CommitRequest.newBuilder()
    .setMode(CommitRequest.Mode.NON_TRANSACTIONAL)
    .setMutation(Mutation.newBuilder().addInsert(lucy))
    .build();
datastore.commit(commitRequest);

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Person");
query.setFilter(makeFilter(
    makeFilter("__key__", PropertyFilter.Operator.HAS_ANCESTOR, makeValue(acmeKey)).build(),
    makeFilter("age", PropertyFilter.Operator.GREATER_THAN, makeValue(25)).build()));
// Returns tom but not lucy, because her age is unindexed
RunQueryRequest.Builder queryRequest = RunQueryRequest.newBuilder();
queryRequest.setQuery(query);
RunQueryResponse queryResponse = datastore.runQuery(queryRequest.build());

You can later change the property back to indexed again setting indexed=True for new entity instances.

Note, however, that changing a property from unindexed to indexed does not affect any existing entities that may have been created before the change. Queries filtering on the property will not return such existing entities, because the entities weren't written to the query's index when they were created. To make the entities accessible by future queries, you must rewrite them to the Datastore so that they will be entered in the appropriate indexes. That is, you must do the following for each such existing entity:

1. Look up (get) the entity from the Datastore.
2. Write the entity back to the Datastore.

Similarly, changing a property from indexed to unindexed only affects entities subsequently written to the Datastore. The index entries for any existing entities with that property will continue to exist until the entities are updated or deleted. To avoid unwanted results, you must purge your code of all queries that filter or sort by the (now unindexed) property.

Index limits

The Datastore imposes limits on the number and overall size of index entries that can be associated with a single entity. These limits are large, and most applications are not affected. However, there are circumstances in which you might encounter the limits.

As described above , the Datastore creates an entry in a predefined index for every property of every entity except those you have explicitly declared as unindexed . The property may also be included in additional, custom indexes declared in your index configuration file ( datastore-indexes.xml ). Provided that an entity has no list properties, it will have at most one entry in each such custom index (for non-ancestor indexes) or one for each of the entity's ancestors (for ancestor indexes). Each of these index entries must be updated every time the value of the property changes.

For a property that has a single value for each entity, each possible value needs to be stored just once per entity in the property's predefined index. Even so, it is possible for an entity with a large number of such single-valued properties to exceed the index entry or size limit. Similarly, an entity that can have multiple values for the same property requires a separate index entry for each value; again, if the number of possible values is large, such an entity can exceed the entry limit.

The situation becomes worse in the case of entities with multiple properties, each of which can take on multiple values. To accommodate such an entity, the index must include an entry for every possible combination of property values. Custom indexes that refer to multiple properties, each with multiple values, can "explode" combinatorially, requiring large numbers of entries for an entity with only a relatively small number of possible property values. Such exploding indexes can dramatically increase the cost of writing an entity to the Datastore, because of the large number of index entries that must be updated, and also can easily cause the entity to exceed the index entry or size limit.

Consider the query

datastore.runQuery({
  query: {
    kinds: [{ name: 'Widget' }],
    filter: {
      compositeFilter: {
        operator: 'AND',
        filters: [{
          propertyFilter: {
            property: { name: 'x' },
            operator: 'EQUAL',
            value: { integerValue: 1 }
          }
        }, {
          propertyFilter: {
            property: { name: 'y' },
            operator: 'EQUAL',
            value: { stringValue: "red" }
          }
        }]
      }
    },
    order: [{ property: { name: 'date' }, direction: 'ASCENDING' }]
  }
}).execute(callback);

query = datastore.Query()
query.kind.add().name = 'Widget'
query.filter.composite_filter.operator = datastore.CompositeFilter.AND

x_filter = query.filter.composite_filter.filter.add().property_filter
x_filter.property.name = 'x'
x_filter.operator = datastore.PropertyFilter.EQUAL
x_filter.value.integer_value = 1

y_filter = query.filter.composite_filter.filter.add().property_filter
y_filter.property.name = 'y'
y_filter.operator = datastore.PropertyFilter.EQUAL
y_filter.value.integer_value = 2

order = query.order.add()
order.property.name = 'date'
order.direction = datastore.PropertyOrder.ASCENDING

Query.Builder query = Query.newBuilder();
query.addKindBuilder().setName("Widget");
query.setFilter(makeFilter(
    makeFilter("x", PropertyFilter.Operator.EQUAL, makeValue(1)).build(),
    makeFilter("y", PropertyFilter.Operator.EQUAL, makeValue(2)).build()));
query.addOrder(makeOrder("date", PropertyOrder.Direction.ASCENDING));

which causes the SDK to suggest the following index:

indexes:
- kind: Widget
  properties:
  - name: x
  - name: y
  - name: date

datastore.commit({
  mutation: {
    insertAutoId: [{
      key: { path: [{ kind: 'Widget' }] },
      properties: {
        x: { listValue: [{ integerValue: 1 }, { integerValue: 2 },
                         { integerValue: 3 }, { integerValue: 4 }] },
        y: { listValue: [{ stringValue: 'red' }, { stringValue: 'green' },
                         { stringValue: 'blue' }] },
        date: { dateTimeValue: new Date() }
      }
    }]
  },
  mode: 'NON_TRANSACTIONAL'
}).execute(callback);

entity = datastore.Entity()

entity.key.path_element.add().kind = 'Widget'

x_property = entity.property.add()
x_property.name = 'x'
for i in range(1, 5):
  x_property.value.list_value.add().integer_value = i

y_property = entity.property.add()
y_property.name = 'y'
for color in ['red', 'green', 'blue']:
  y_property.value.list_value.add().string_value = color

date_property = entity.property.add()
date_property.name = 'date'
date_property.value.timestamp_microseconds_value = long(
    time.time() * 1e6)

Entity.Builder widget = Entity.newBuilder()
    .setKey(makeKey("Model"))
    .addProperty(makeProperty("x",
        makeValue(makeValue(1), makeValue(2), makeValue(3), makeValue(4))))
    .addProperty(makeProperty("y",
        makeValue(makeValue("red"), makeValue("green"), makeValue("blue"))))
    .addProperty(makeProperty("date", makeValue(new Date())));
CommitRequest commitRequest = CommitRequest.newBuilder()
    .setMode(CommitRequest.Mode.NON_TRANSACTIONAL)
    .setMutation(Mutation.newBuilder().addInsertAutoId(widget))
    .build();
datastore.commit(commitRequest);

creates an entity with four values for property x , three values for property y , and date set to the current date. This will require 12 index entries, one for each possible combination of property values:

( 1 , "red" , <now> ) ( 1 , "green" , <now> ) ( 1 , "blue" , <now> )

( 2 , "red" , <now> ) ( 2 , "green" , <now> ) ( 2 , "blue" , <now> )

( 3 , "red" , <now> ) ( 3 , "green" , <now> ) ( 3 , "blue" , <now> )

( 4 , "red" , <now> ) ( 4 , "green" , <now> ) ( 4 , "blue" , <now> )

When the same property is repeated multiple times, the Datastore can detect exploding indexes and suggest an alternative index. However, in all other circumstances (such as the query defined in this example), the Datastore will generate an exploding index. In this case, you can circumvent the exploding index by manually configuring an index in your index configuration file:

indexes:
- kind: Widget
  properties:
  - name: x
  - name: date
- kind: Widget
  properties:
  - name: y
  - name: date

( 1 , <now> ) ( 2 , <now> ) ( 3 , <now> ) ( 4 , <now> )

( "red" , <now> ) ( "green" , <now> ) ( "blue" , <now> )

Any commit operation that would cause an index to exceed the index entry or size limit will fail . The text of the error describes which limit was exceeded ( "Too many indexed properties" or "Index entries too large" ) and which custom index was the cause. If you create a new index that would exceed the limits for any entity when built, queries against the index will fail and the index will appear in the Error state in the Cloud Console. To handle such Error indexes,

1. Remove the index from your index configuration file ( datastore-indexes.xml ).
2. Vacuum the index using the gcd command line tool with the vacuum_indexes option as described under Index Configuration .
3. Either
   • reformulate the index definition and corresponding queries, or
   • remove the entities that are causing the index to explode.
4. Add the index back to datastore-indexes.xml .
5. Update the index using the gcd command line tool with the update_indexes option as described under Index Configuration .

You can avoid exploding indexes by avoiding queries that would require a custom index using a list property. As described above, this includes queries with multiple sort orders or queries with a mix of equality and inequality filters.