The agnostic query
Nov 6, 2015
Ruby Query Cloudsearch Elasticsearch

In our CRM system, users are able to create cases and manage them through resolving their tasks. In order to keep track of all these tasks we provide a search interface.

At the beginning this was simple: The number of concrete tasks and their associations was not very big and the filters needed were kept down to a reasonable amount. We hooked some after-save callbacks into tasks and related models, and therefore all the data needed were aggregated and placed into a table in our database. In this way we skipped joining multiple tables in order to apply the queries.

However as time went by, more tasks were added and the querying requirements expanded. Having millions of records in this table made migrations unbearable due to increased associated downtimes. Thus, we decided to expand on this rationale by introducing associations to this table, so that we could more easily gather the information needed.

This was not an easy venture to handle. There were two major considerations that kept pushing for a change:

  • Flexibility: Adding new fields, especially when needed to be part of our query, was nearly impossible.
  • Performance: Some queries were so expensive that hung our database.

We decided to give a try with indexing stores. The basic candidates were elasticsearch, cloudsearch and solr.

Basic idea

We needed a generic querying mechanism which could potentially create queries for any store. The main challenge was to make this mechanism plugable and easy to adapt in different stores.

We ended up with a library that:

  • allows clients to create abstract queries in a uniform way.
  • provides a powerful traversing mechanism which is used in query evaluation and validation.
  • controls execution of queries in order to achieve better performance.
  • transforms results in a uniform way independent of indexing store.

Let’s take it a piece at a time:

Queries just like trees

The first step towards creating an agnostic query is to define an abstract structure able to represent it. The fundamental block to achieve this structure is a tree node class, which is inherited by all components of our query and creates a common interface. It’s not necessary to create subclasses for composite and leaf nodes, because we can easily determine the type (if needed) from the node’s children. This is how simple and elegant a tree node looks:

1 class TreeNode
2   attr_reader :children
3   attr_reader :context
4 
5   def initialize(children = [], context = nil)
6     @children, @context = children, context
7   end
8 end

Figure 1 Figure 1: The tree node.

Before moving on to how we actually created this tree-like query, let’s analyze the structure of a query a little further. There are four families of nodes composing a query:

  • Expressions (select, where, order, etc), which are first class citizens in a query.
  • Criteria (equal, greater, like, etc), which define the conditions for selecting records. We also included logical operations (and, or, not, etc) in this family, since they can be used in creating complex criteria.
  • Attribute nodes, which describe a record’s attributes.
  • Value nodes, which describe all kinds of values that can be part of a query.

Abstracting query creation

Creating and composing node objects isn’t especially expressive for a query interface. We needed to put a layer of abstraction on top of object creation, so that directly working with constructors is no longer necessary. In this way the complexity of constructor calls is hidden, allowing a more expressive and flexible interface.

As stated above, we have divided the nodes composing a query into four families. Two builders, one for expressions and one for criteria, serve as the abstraction layer for creating node objects. Attributes and Values are completely hidden from the client, as their processing happens behind the scenes. The main difference between them is that the criteria builder creates and returns a new criterion-node at method invocation and the query builder internally composes a query and returns itself at method invocation.

Initially one builder was responsible for creating all kind of nodes. This implementation provided a more expressive interface but resulted in reduced flexibility in query creation. In particular a core requirement was to create queries in parts, which wasn’t feasible with this approach.

This is the resulting interface for building queries:

 1 q_b = QueryBuilder.new(context)
 2 c_b = q_b.criteria_builder
 3 
 4 equal = c_b.eq('foo', 'a_value')
 5 greater = c_b.gt('bar', 5)
 6 criteria = c_b.or(equal, greater)
 7 
 8 q_b.where(criteria)
 9 q_b.order('bar', :asc)
10 q_b.limit(20)
11 
12 query = q_b.build

Figure 2 Figure 2: The tree

Before we move on

Our indexing store needs a schema. So does our query mechanism for reasons that will become apparent later. Schema generation is pure Ruby magic and we will discuss this in another post, but for the time let’s assume that somehow we have access to it. Our schema looks something like this (where associations are represented as nested hashes):

 1 {
 2   "a_string" => :string,
 3   "an_int" => :integer,
 4   "a_nested_model" =>
 5   {
 6     "a_boolean" => :boolean,
 7     "another_nested_model" =>
 8     {
 9       "a_date" => :date,
10       "a_double" => :double,
11       "a_string_array" => :string_array,
12     }
13   }
14 }

Evaluating a query and more

Undoubtedly the tree-like query is a programming masterpiece, but it has no value unless it’s translated to a specific query language. Notice that so far our implementation didn’t involve any specific backend store details.

Evaluation of the query expression can take place inside the components of our query. This is perfectly fine, but it will unfortunately throw away the previous implementation. All the nodes should now have store-specific logic, and in order to keep this nice building interface untouched we should add another layer of abstraction. Going through the well known book by Gang of Four, we found that the Visitor Pattern was an excellent candidate for separating the evaluation of query from the node classes. The basic consequence using this pattern, is that behavior isn’t spread over the classes; it’s localized in a visitor. This solution was far more powerful than we initially expected.

Visitor Pattern relies on double dispatch (which means dispatching depends on the class of the object and the class of the input object). Ruby inherently doesn’t support this kind of functionality, so this is how we got around it:

1 class TreeNode
2   #...# 
3   def accept(visitor)
4     visitor.visit(self)
5   end
6 end
1 class Visitor
2   def visit(subject)
3     method_name = "visit_#{subject.class.name.lowercase}"
4     send(method_name, subject)
5   end
6 end

Having the visitor class we can easily define how each node is evaluated. Let’s look at an example to make this more clear:

1 def visit_equal(subject)          
2  "#{ subject.attribute.accept(self)} = #{subject.value.accept(self) }"
3 end
4 
5 def visit_and(subject)
6  "#{ subject.children.map { |child| child.accept(self) }.join('and') }"
7 end

Here is where the schema comes in play. In order to evaluate a value we need to know its type. What really happens is that we try to link a value to its associated attribute and then we look at the schema to determine its type.

 1 def visit_value(subject)
 2   attribute_type = subject.associated_attribute.type
 3   case attribute_type
 4     when :integer
 5       "#{ subject.value }"
 6     when :string
 7       "'#{ subject.value }'"
 8     #...#
 9   end
10 end

As mentioned before, the visitor pattern is really powerful. Specifically:

  • we can accumulate state as it visits each element in the tree structure. This notion is used in our validation mechanism (another visitor), that applies validation rules to the nodes and accumulates the result back.
  • we can transform the tree structure. This can be applied in order to make the resulting query more performant.
  • It gives unlimited flexibility traversing the tree in any manner needed.

Execute and return the results

The internals of query execution are handled by the Executor class. Initially its purpose was to evaluate the query (for the specific store) and execute it. This may look enough for a first approach, but considering the next scenario some weaknesses became apparent. Let’s assume that a user creates a query with criteria matching thousands of results. With the approach described, this will result in a single call on the backend store, which will return all these documents at once. For obvious reasons this is potentially harmful.

We introduced a sequence of interactions which allows internal controlling of query execution. When the client executes a query, we return a special object called Result Set. At this point the indexing stored hasn’t received any query request. When the client iterates through this object, narrowed subqueries are executed (keeping an internal cursor), and the results are yielded back.

1 result_set = query.execute
2 result_set.each do |result|
3   #...#
4 end

The advantages of this approach are that:

  • Query execution only returns results that are actually used by the user.
  • A safeguard, preventing massive number of results, is placed under the hood keeping the interface simple and clean.

Figure 3 Figure 3: Sequence diagram

Lastly but equally importantly, we should mention that before a result is yielded back to the user, it’s transformed to a schema-like document. We achieve this by using some generic utilities created for this purpose. In this way we manage to keep the client agnostic of the store used both in the query’s creation and the query’s results.

 1 {
 2   "a_string" => 'foo',
 3   "an_int" => 10,
 4   "a_nested_model" =>
 5   {
 6     "a_boolean" => 'true',
 7     "another_nested_model" =>
 8     {
 9       "a_date" => '2015-10-15T00:00:00Z',
10       "a_double" => 1.33,
11       "a_string_array" => ['a', 'b', 'c'],
12     }
13   }
14 }

Final thoughts & future work

Lets see at some facts:

  • Cloudsearch is currently used as our backend store (since we are hosted in the Amazon cloud and our query language works like a charm).
  • Other models that live in our application are indexed in a solr instance.
  • Recently Amazon announced Elasticsearch Service.

This is an excellent setup for our agnostic query. The query interface fits very naturally in our application and can be applied to any indexing store without clients to be aware. Also migrating our data to another store, is relatively easy as it requires changes to few classes.

And a promise:

We intend to make this mechanism (plus the document generation mechanism) an open source gem, so others can enjoy the fruits of our labor. Keep track of this effort and other neat e-Travel perks here.

Share on