Querying the indexed tree

Owned by ise (Unlicensed)
Last updated: Sept 07, 2012
4 min read

Prerequisite: In order to understand content of this document please carefully read Indexing structure document first.

Requirements

Indexing structure has to provide fast and efficient way for querying the tree and retrieving the wanted objects.

Approach

To be able to search for the objects fast, it is necessary to only look up for the objects in the parts of the tree where they may reside. For example, if a query is to retrieve all Invocation data objects created in last minute, the search for these object should not be performed in the parts of the tree where SQL statements are, or where old data is. This means that given a query, tree must know where to look for the objects.

Except basic queries like one mentioned above, often there is a need to specify the exact properties of objects that are searched. For example, minimum duration of timer data, or that some field is not null, etc. Thus, a mechanism is needed that will be able to retrieve only object with specific properties.

Realization

Realization of the index query system is shown in the class diagram below.

Searching the right tree part

Values that can directly be set in IndexQuery object define what type of objects are wanted. These are more or less properties that all inspectIT DefaultData objects have. But actually these properties are also defining the tree structure because they correspond to the values that branch indexers are using to create different tree parts. So, when the branch is asked to return the correct objects, that branch will use its branch indexer to get the correct keys of the child tree components where objects are (via IBranchIndexer.getKeys(IIndexQuery query) method). Thus the search will continue only in the branch(s) or leaf(s) where correct object might be.

Checking the object properties

When the query has come the the right leafs (because this is where the objects are referred from), each object has to be check to assure it has wanted properties. This check is done via isQueryComoplied(IIndexQuery) method that is defined in DefaultData class and can be overridden in subclasses. The check has two parts:

  1. First the object is checked against the properties set directly in the index query objects (the same ones that were use to find the correct tree part).
  2. Only if first check is passed, the object is check against all index query restrictions that are defined.
Index query restrictions

Index query restrictions are realized using reflection, meaning that each restriction is bounded to the one field of a class. This gives enough flexibility, so that every class and every field in that class can be tested. Different implementations of restrictions check if the passed object/value (which should be the value of the field defined in restriction) in method isFulfilled(Object o) has the correct value in relation the restriction value set in a restriction. Currently implemented restrictions, that are provided by IndexQueryRestrictionFactory, are:

  • is Null
  • is not Null
  • equals
  • not equals
  • greater than
  • greater or equals than
  • less than
  • less or equals than
  • is in collection
  • are all in collection

Since reflection is relatively slow, it was concluded that major performance improvement would be to cache all methods that are invoked. Because of this, IIndexQueryRestirctionProcessor interface is defined, and IndexQuery is simply delegating the checking of all restrictions to the processor.

Updates in version 1.4

There was a need for a extended indexing query class that will provide the needed functionality for the storage tree queering. Because of that the IStorageIndexQuery was defined with three additional properties that can be specified:

  1. Exclude IDs - set of the object IDs that will be excluded in the result
  2. Include IDs - set of objects that will be included in the result
  3. Only invocations without children -  If searching for invocations this flag can be set to specify if the complete objects should be retrieved or their cloned copies without children.

Query providers

The IIndexQueryProvider<E extends IIndexQuery> was introduced, with two implementing classes IndexQueryProvider and StorageIndexQueryProvider. Two problems are solved with providers:

  1. Ability to get correctly initialized query objects as the Spring prototype bean
  2. Ability to create the query factories that will define the queries need, with no distinction if the query is of the simple or the storage type.

Query factories

As mentioned above the query factories are able to create the proper indexing query without depending if the returning object is IIndexQuery or IStorageIndexQuery. Since the storage services on the UI have to execute the same queries as the ones on the CMR, just with the IStorageIndexQuery objects, the factories were introduces as the on-place where queries will be defined. Later on Spring will bound a StorageIndexQueryProvider to a factory that is producing queries for the storage services. On the other hand Spring will bound a IndexQueryProvider for factories used in the CMR DAO classes.

Aggregators

Classes that can aggregate one type of data are called Aggregators and all implement the IAggregator<E extends DefaultData> interface. Currently following are available:

  1. ExceptionDataAggregator
  2. HttpTimerDataAggregator
  3. SqlStatementDataAggregator
  4. TimerDataAggregator

AbstractStorageService class on the UI and AbstractBufferDataDao class provide methods can query the indexed tree with supplied query and optionally the IAggregator, Comparator and element count limit. If all are supplied, the elements retrieved by the query will bi first aggregated, then sorted and at the end result list will be decreased if needed to the limit.