Estimate selectivity of Index Queries

After gaining some insights to the GraphCentricQueryBuilder and the SubqueryIterator internals thanks to @li-boxuan's PRs (#2040, #2055), I think we can improve the selection of indexes to answer a query even more. The current implementation tries to cover as many conditions as possible by consulting one or more indexes (see #2048). Concerning the selection of indexes, our only measure of how useful an index is, is the number of conditions it covers.

In the long term, we should focus on selecting indexes by (an estimation of) their selectivity. Consider the following example. Assume we are querying a database of cars and have two indexes:

• carByModelName covers the property name
• carBySeatsAndGears covers the properties seats and gears

For the query

g.V().hasLabel(car).has('name', 'Edison Model S').has('seats', 5).has('gears', 1)

the current Implementation would prefer the index carBySeatsAndGears, because it covers two conditions in contrast to carByModelName which only covers one. Obviously, it would be more efficient to consult carByModelName, which reduces the intermediate result size immensely.

To achieve this, it is necessary to somehow track the selectivity of index queries. This could be done by keeping track of inserted elements by maintaining histograms. An easier (and probably less effective) solution would be to keep track of how selective the last N queries to an index were and thereby estimate the selectivity of the N+1st query.

In theory, if we can improve the index selection to always find the most selective index, we can achieve another gain in performance by streaming the results of the first index query and matching all remaining conditions on the fly instead of waiting for the (larger) result sets of other indexes and intersect them.

No file or test is named. Start by reading GraphCentricQueryBuilder and SubqueryIterator, then review the referenced PRs #2040, #2055, and #2048 to understand current index selection. Done requires a decided selectivity-estimation approach and an agreed implementation path for choosing indexes and handling remaining conditions.