One more time: Relation Index Entities with Python for Google Datastore

Hey, why not? Relation Index Entities implemented in Python should nicely complement my RIE with Java/Objectify post. Because I follow the same example and concepts I will not go over them twice but rather concentrate on specifics of Python example (again, please see RIE with Java/Objectify post for general concepts).

I start with defining datastore entities in Python:

class Document(db.Model):
    title = db.StringProperty()
    abstract = db.StringProperty()
    authors = db.StringListProperty()
    publisher = db.StringProperty()
    tags = db.StringListProperty()
    

class DocumentKeywords(db.Model):
    keywords = db.StringListProperty()

As before list property keywords of DocumentKeywords is a critical element of RIE design. The brevity of Python implementation is striking when comparing entity definitions with Java/Objectify version. For example, there is nothing that indicates these 2 entities comprise an entity group. The entity classes as defined may or may not belong to the same entity group: during construction of concrete instances we can establish optional parent-child relationship.

Let’s see how we could add new Document with Python:

def add_document(title, authors, publisher, tags):
    
    doc = Document()
    doc.title = title
    doc.authors = authors
    doc.publisher = publisher
    doc.tags = tags
    
    doc.put()
    
    keywords = []
    keywords.append(doc.title)
    keywords.extend(doc.authors)
    keywords.append(doc.publisher)
    keywords.extend(doc.tags)
    
    doc_keywords = DocumentKeywords(parent=doc, keywords=keywords)
    doc_keywords.put() 
    
    return doc

By constructing DocumentKeyword with parent argument it becomes part of the document entity group so we can call add_document within a transaction:

doc = db.run_in_transaction(add_document, title, authors, publisher, tags)
  

Of course I oversimplified this example as real keywords would have been treated more carefully with consistent case, stop word filtering, robust parsing, etc. But this is not the goal of this exercise so I am leaving it all out.

Finally, the keyword search method:

def find_by_keywords(keywords):
        
        query = reduce(lambda x, y : x.filter('keywords =', y), 
                       keywords.insert(0, db.Query(DocumentKeywords, keys_only=True)))
        
        keywords_keys = query.fetch(100, 0)
        
        doc_keys = map(lambda x:x.parent(), keywords_keys)
        docs = db.get(doc_keys)
        
        return docs

Again as in Java/Objectify version it is a 3-step process. First step (line 3-4) builds a query reducing the list of keywords on a query object (AND condition only). The query built is for keys only as we are never interested in anything else from DocumentKeywords. Second step (line 6) uses the query to retrieve keys only (keys of DocumentKeywords that is). And lastly (lines 8-9) we map retrieved keys to parent Document keys and retrieve desired documents with batch get.

I find this Python solution more elegant and concise than Java/Objectify code. And it is clear that Java code is saved by Objectify especially the query part where all datastore API features are clearly defined and easily available.

Some questions arise when discussing Relation Index Entity pattern (RIE) that are about its feasibility in real applications. Performance issues associated with creating and maintaining such index are common ones as well as its applicability in modeling data (for example see this post by Jeff Schnitzer of Objectify fame).

In my view the effectiveness of RIE depends on how this index is used (just like any index in general). If its usage is in order of 100s or more reads than updates then it could be feasible. The higher the ratio the better. Thus for mostly static data such as document library or other references near free text search implemented with RIE is definitely option to consider. Of course the ultimate test should be a GAE bill that reflects resources spent on both queries and updates and where alternatives stand against this bill.

The other point is that RIE should not play any part in the data model. Effectively it is an extension of indexes generated by datastore and should be treated as such.

And lastly there is clearly high initial cost of creating RIE index for datastore artifacts (like documents). I can recommend using task queues, mapreduce and/or blobstore and do as much pre-processing locally as possible before loading data into GAE. For example, document keywords can be extracted and processed on your own server before uploading them to datastore. That way you can end up with simple CSV file to process on GAE.

Efficient Keyword Search with Relation Index Entities and Objectify for Google Datastore

Free text search with keywords on Google App Engine datastore made simple - in fact simple enough to fit into single blog entry.

I will use GAE/Java with Objectify for datastore API (also see my newer post with Python implementation). Assume we maintain a document library where each document has several textual attributes: name, title, subtitle, authors, publisher, reference number (similar to ISBN), tags, abstract, etc. While each attribute is semantically different, for a searcher they all present some value (or relevance). Thus, user may search for any of them with one or more keywords. For simplification, I consider only AND searches.

First, let’s model our entities (remember, we use Objectify that in turn uses standard JPA annotations wherever possible):

@Entity(name = "Document")
public class Document {

  @Id
  private Long id;

  private String title;
  private List<String> authors = = new ArrayList<String>();
  private String publisher;
  private List<String> tags = new ArrayList<String>();
  // more attributes as necessary...

  public Document() {
    super();
  }

  // standard getters/setters follow...
}

One thing to emphasize is the use of list properties such as authors and tags. Datastore treats them as multi-valued attributes so that condition like authors == ‘John Doe’ would return all documents that have John doe as one of authors. This list property feature is critical in the next (and last) entity we define:

@Entity(name = "DocumentKeywords")
public class DocumentKeywords {

  @Id Long id;
  @Parent Key<Document> document;
  List<String> keywords = new ArrayList<String>();

  private DocumentKeywords() {
    super();
  }

  public DocumentKeywords (Key<Document> parent) {
    this(parent, Collections.<string>emptyList());
  }

  public DocumentKeywords (Key<Document> parent, Collection<String> keywords) {
    super();

    this. document = parent;
    this.keywords.addAll(keywords);
  }

  // add single keyword
  public boolean add(String keyword) {
    return keywords.add(keyword);
  }

  // add collection of keywords
  public boolean add(Collection<String> keywords) {
    return this.keywords.addAll(keywords);
  }
}

There are several things worth noting about DocumentKeywords.

First, it’s a child entity to Document (see @Parent annotation in Objectify). Parent Document and child DocumentKeywords make an entity group in datastore. This is important for data integrity – entity group rows can participate in transactions in datastore. Data integrity is critical in this case (you'll see shortly). Indeed, we'll duplicate attribute values between Document and DocumentKeywords. For each Document entity we create corresponding child DocumentKeywords to consolidate all document attributes into property keywords.

Secondly, keywords is a list property. List property is limited to 5000 entries which is often sufficient. And if it’s not we could add more DocumentKeywords child rows for the same Document parent (not implemented here).

Finally, what is DocumentKeywords entity defined for? Why is its keywords attribute not part of Document entity? The answer is in this Google IO presentation (Spoiler: Keywords being list property in Document would produce serialization overhead on Document entity (at least doubling it since it's exact copy of the rest of Document attributes). Moving keywords to separate entity is called Relation Index Entity and it gives us best of both worlds: fully indexed attributes (via list property) and no serialization overhead for documents.)

We add new Document and index document attributes in child DocumentKeywords in one transaction:

// we use DI to initialize factory (application scoped)
private final ObjectifyFactory factory;

private Objectify tran = null;

public Document addDocument(Document document) throws {

  try {
    Objectify ofy = beginTransaction();

    Key<Document> key = ofy.put(document);

    // crate Relation Index Entity
    DocumentKeywords rie = new DocumentKeywords(key);
    rie.add(document.getTitle());
    rie.add(document.getAuthors());
    rie.add(document.getPublisher());
    rie.add(document.getTags());
    ofy.put(rie);

    commit();

    Document savedDocument = beginQuery().find(key);
    return savedDocument;

  }finally {
    rollbackIfActive();
  }
}

I left out as an exercise transactional methods above. Just note important datastore gotcha: rows added inside transaction are not available within this transaction if it’s still active. If you add row and then try to query it before committing then you won’t find it. Commit transaction first and then read its data.

Now we are ready to make actual keyword searches:

public Collection<document> findByKeywords(Collection<String> keywords) {

  Objectify ofy = beginQuery();

  Query<DocumentKeywords> query = ofy.query(DocumentKeywords.class);
  for (String keyword : keywords) {
    query = query.filter("keywords", keyword);
  }

  Set<Key<Document>> keys = query.<Document>fetchParentKeys();

  Collection<Document> documents = ofy.get(keys).values();

  return documents;
}

You can see that keyword search is a 3-step process: during first step we iteratively build search condition (AND only), in second step we query DocumentKeywrods toretrieve keys only – no overhead of serialization bulky keywords here. And lastly we convert retrieved DocumentKeywords keys into parent keys (documents) and use datastore batch get to return them. Objectify made all steps quite transparent and efficient.

This is all to it. Let me make few comments about this example. It is purposely contrived but it should map to real cases with no principal changes. Documents could be friends in a social network, products from online retail catalog, or blog entries in blogging web site. I intentionally left document content out of the list of attributes. Current limit of datastore doesn’t allow me to build elegant and concise solution beyond 5000 thousand keywords per document so it makes inclusion of document content risky. Even though simple enhancement trounces this limitation I didn’t want to overload code above.

Extending to free text search would mean support for such features as word normalization and stemming, case-sensitivity, logical operations, keyword proximity (e.g. same attribute or related attributes), extending beyond datastore 5000 list property limit.

References:
1. Building Scalable, Complex Apps on App Engine
2. Datastore List Property
3. Stemming
4. Objectify
5. RIE with Python