Skiplists Index in 3.0.8

[fceller]

This is what we’re seeing when evaluating a skiplist index on 3.0.8:

Query string:

FOR hs in Host_Session
FILTER hs.end_time > "2016-10-05T00:51:16.780137Z"
RETURN hs

Execution plan:

Id NodeType Est. Comment
1 SingletonNode 1 * ROOT
6 IndexNode 23035 - FOR hs IN Host_Session /* skiplist index scan */
5 ReturnNode 23035 - RETURN hs

Indexes used:

By Type Collection Unique Sparse Selectivity Fields Ranges

6 skiplist Host_Session false true n/a end_time

Optimization rules applied:

Id RuleName
1 use-indexes
2 remove-filter-covered-by-index

But when I invert the ‘greater-than’ operator to ‘less-than’, the index is no longer used:

Query string:

FOR hs in Host_Session
FILTER hs.end_time < "2016-10-05T00:51:16.780137Z"
RETURN hs

Execution plan:

Id NodeType Est. Comment
1 SingletonNode 1 * ROOT
2 EnumerateCollectionNode 46071 - FOR hs IN Host_Session /* full collection scan /
3 CalculationNode 46071 - LET #1 = (hs.end_time < "2016-10-05T00:51:16.780137Z") / simple expression / / collections used: hs : Host_Session */
4 FilterNode 46071 - FILTER #1
5 ReturnNode 46071 - RETURN hs

Indexes used:

none

Optimization rules applied:

None

[jsteemann]

From the above output it looks like the skiplist index is sparse, meaning that null values are excluded.
The predicate end_time < "2016-10-05T00:51:16.780137Z" however would include null values so the index cannot be used for it. The opposite predicate excludes null, so the index is used.
To use the index for any predicate on end_time, the index can be made non-sparse.

[Simran-B]

Could this be related to #2081?

[DeShadow]

@Simran-B No. The issues are not the same. This issue is about sparse index. And the property sparse of the index affects to use or not the index with some conditions. @jsteemann explained that behaviour of the database is right in this situation because of null values.

My issue #2081 is only about optimizer and reverse skiplist index.

[jsteemann]

@Simran-B : I briefly looked into this, and it seems the root cause for this issue is different.

[fceller]

@jsteemann so we would need an optimizer rule that recognizes the filter condition is hs.end_time != null and end_time < "2016-10-05T00:51:16.780137Z"?

[jsteemann]

The sub-condition end_time < ... is not considered for index usage because it could include the value null, which is not provided by a sparse index. This is correct if the condition is only attribute < value.
However, for ranges such as attribute > value1 && attribute < value2 the optimizer could be smart enough to find that value null is not included. Currently it won't and will discard the sub-condition attribute < value2 for the index usage but post-filter on the index results using this sub-condition.

[jsteemann]

3.1 can now use a sparse index for conditions such as attribute < value1 && attribute > value2 and attribute < value1 && attribute >= value2 (if value2 is not null). This is limited to value2 being a constant value at the moment.
Still no sparse index will be used for conditions such as attribute != null because the != operator is not handled by the optimizer very well.

[hkernbach]

ArangoDB 3.1 has been released. Please note that the download urls and repositories have changed slightly.

Download or see Release Notes for details.