Star-tree index

In this page you will learn what a star-tree index is and gain a conceptual understanding of how one works.

Unlike other index techniques which work on a single column, the star-tree index is built on multiple columns and utilizes pre-aggregated results to significantly reduce the number of values to be processed, resulting in improved query performance.

One of the biggest challenges in real-time OLAP systems is achieving and maintaining tight SLAs on latency and throughput on large data sets. Existing techniques such as sorted index or inverted index help improve query latencies, but speed-ups are still limited by the number of documents that need to be processed to compute results. On the other hand, pre-aggregating the results ensures a constant upper bound on query latencies, but can lead to storage space explosion.

Use the star-tree index to utilize pre-aggregated documents to achieve both low query latencies and efficient use of storage space for aggregation and group-by queries.

Existing solutions

Consider the following data set, which is used here as an example to discuss these indexes:

Sorted index

In this approach, data is sorted on a primary key, which is likely to appear as filter in most queries in the query set.

This reduces the time to search the documents for a given primary key value from linear scan O(n) to binary search O(logn), and also keeps good locality for the documents selected.

While this is a significant improvement over linear scan, there are still a few issues with this approach:

• While sorting on one column does not require additional space, sorting on additional columns requires additional storage space to re-index the records for the various sort orders.

• While search time is reduced from O(n) to O(logn), overall latency is still a function of the total number of documents that need to be processed to answer a query.

Inverted index

In this approach, for each value of a given column, we maintain a list of document id’s where this value appears.

Below are the inverted indexes for columns ‘Browser’ and ‘Locale’ for our example data set:

For example, if we want to get all the documents where ‘Browser’ is ‘Firefox’, we can look up the inverted index for ‘Browser’ and identify that it appears in documents [1, 5, 6].

Using an inverted index, we can reduce the search time to constant time O(1). The query latency, however, is still a function of the selectivity of the query: it increases with the number of documents that need to be processed to answer the query.

Pre-aggregation

In this technique, we pre-compute the answer for a given query set upfront.

In the example below, we have pre-aggregated the total impressions for each country:

With this approach, answering queries about total impressions for a country is a value lookup, because we have eliminated the need to process a large number of documents. However, to be able to answer queries that have multiple predicates means we would need to pre-aggregate for various combinations of different dimensions, which leads to an exponential increase in storage space.

Star-tree solution

On one end of the spectrum we have indexing techniques that improve search times with a limited increase in space, but don't guarantee a hard upper bound on query latencies. On the other end of the spectrum, we have pre-aggregation techniques that offer a hard upper bound on query latencies, but suffer from exponential explosion of storage space

The star-tree data structure offers a configurable trade-off between space and time and lets us achieve a hard upper bound for query latencies for a given use case. The following sections cover the star-tree data structure, and explain how Pinot uses this structure to achieve low latencies with high throughput.

Definitions

Tree structure

The star-tree index stores data in a structure that consists of the following properties:

• Root node (Orange): Single root node, from which the rest of the tree can be traversed.

• Leaf node (Blue): A leaf node can containing at most T records, where T is configurable.

• Non-leaf node (Green): Nodes with more than T records are further split into children nodes.

• Star node (Yellow): Non-leaf nodes can also have a special child node called the star node. This node contains the pre-aggregated records after removing the dimension on which the data was split for this level.

• Dimensions split order ([D1, D2]): Nodes at a given level in the tree are split into children nodes on all values of a particular dimension. The dimensions split order is an ordered list of dimensions that is used to determine the dimension to split on for a given level in the tree.

Node properties

The properties stored in each node are as follows:

• Dimension: The dimension that the node is split on

• Start/End Document Id: The range of documents this node points to

• Aggregated Document Id: One single document that is the aggregation result of all documents pointed by this node

Index generation

The star-tree index is generated in the following steps:

• The data is first projected as per the dimensionsSplitOrder. Only the dimensions from the split order are reserved, others are dropped. For each unique combination of reserved dimensions, metrics are aggregated per configuration. The aggregated documents are written to a file and served as the initial star-tree documents (separate from the original documents).

• Sort the star-tree documents based on the dimensionsSplitOrder. It is primary-sorted on the first dimension in this list, and then secondary sorted on the rest of the dimensions based on their order in the list. Each node in the tree points to a range in the sorted documents.

• The tree structure can be created recursively (starting at root node) as follows:

  • If a node has more than T records, it is split into multiple children nodes, one for each value of the dimension in the split order corresponding to current level in the tree.

  • A star node can be created (per configuration) for the current node, by dropping the dimension being split on, and aggregating the metrics for rows containing dimensions with identical values. These aggregated documents are appended to the end of the star-tree documents.

    If there is only one value for the current dimension, a star node won’t be created because the documents under the star node are identical to the single node.

• The above step is repeated recursively until there are no more nodes to split.

• Multiple star-trees can be generated based on different configurations (dimensionsSplitOrder, aggregations, T)

Aggregation

Aggregation is configured as a pair of aggregation functions and the column to apply the aggregation.

All types of aggregation function that have a bounded-sized intermediate result are supported.

Supported functions

• COUNT

• MIN

• MAX

• SUM

• AVG

• MIN_MAX_RANGE

• DISTINCT_COUNT_HLL

• PERCENTILE_EST

• PERCENTILE_TDIGEST

• DISTINCT_COUNT_BITMAP

  • NOTE: The intermediate result RoaringBitmap is not bounded-sized, use carefully on high cardinality columns.

• DISTINCT_COUNT_HLL

• DISTINCT_COUNT_RAW_HLL

• DISTINCT_COUNT_THETA_SKETCH

• DISTINCT_COUNT_RAW_THETA_SKETCH

• DISTINCT_COUNT_TUPLE_SKETCH

• DISTINCT_COUNT_RAW_INTEGER_SUM_TUPLE_SKETCH

• SUM_VALUES_INTEGER_SUM_TUPLE_SKETCH

• AVG_VALUE_INTEGER_SUM_TUPLE_SKETCH

• DISTINCT_COUNT_CPC_SKETCH

• DISTINCT_COUNT_RAW_CPC_SKETCH

• DISTINCT_COUNT_ULL

• DISTINCT_COUNT_RAW_ULL

Unsupported functions

• DISTINCT_COUNT

  • Intermediate result Set is unbounded.

• SEGMENT_PARTITIONED_DISTINCT_COUNT:

  • Intermediate result Set is unbounded.

• PERCENTILE

  • Intermediate result List is unbounded.

Functions to be supported

• ST_UNION

Index generation configuration

Multiple index generation configurations can be provided to generate multiple star-trees. Each configuration should contain the following properties:

AggregationConfigs

Default index generation configuration

A default star-tree index can be added to a segment by using the boolean config enableDefaultStarTree under the tableIndexConfig.

A default star-tree will have the following configuration:

• All dictionary-encoded single-value dimensions with cardinality smaller or equal to a threshold (10000) will be included in the dimensionsSplitOrder, sorted by their cardinality in descending order.

• All dictionary-encoded Time/DateTime columns will be appended to the _dimensionsSplitOrder _following the dimensions, sorted by their cardinality in descending order. Here we assume that time columns will be included in most queries as the range filter column and/or the group by column, so for better performance, we always include them as the last elements in the dimensionsSplitOrder.

• Include COUNT(*) and SUM for all numeric metrics in the functionColumnPairs.

• Use default maxLeafRecords (10000).

Example

For our example data set, in order to solve the following query efficiently:

SELECT SUM(Impressions) 
FROM myTable 
WHERE Country = 'USA' 
AND Browser = 'Chrome' 
GROUP BY Locale

We may config the star-tree index as follows:

"tableIndexConfig": {
  "starTreeIndexConfigs": [{
    "dimensionsSplitOrder": [
      "Country",
      "Browser",
      "Locale"
    ],
    "skipStarNodeCreationForDimensions": [
    ],
    "functionColumnPairs": [
      "SUM__Impressions"
    ],
    "maxLeafRecords": 1
  }],
  ...
}

Note: In above config maxLeafRecords is set to 1 so that all of the dimension combinations are pre-aggregated for clarity in the visualization below.

Alternatively using aggregationConfigs instead of functionColumnPairs and enabling compression on the aggregation:

"tableIndexConfig": {
  "starTreeIndexConfigs": [{
    "dimensionsSplitOrder": [
      "Country",
      "Browser",
      "Locale"
    ],
    "skipStarNodeCreationForDimensions": [
    ],
    "aggregationConfigs": [
      {
        "columnName": "Impressions",
        "aggregationFunction": "SUM",
        "compressionCodec": "LZ4"
      }
    ],
    "maxLeafRecords": 1
  }],
  ...
}

The star-tree and documents should be something like below:

Tree structure

The values in the parentheses are the aggregated sum of Impressions for all the documents under the node.

Star-tree documents

Query execution

For query execution, the idea is to first check metadata to determine whether the query can be solved with the star-tree documents, then traverse the Star-Tree to identify documents that satisfy all the predicates. After applying any remaining predicates that were missed while traversing the star-tree to the identified documents, apply aggregation/group-by on the qualified documents.

The algorithm to traverse the tree can be described as follows:

• Start from root node.

• For each level, what child node(s) to select depends on whether there are any predicates/group-by on the split dimension for the level in the query.

  • If there is no predicate or group-by on the split dimension, select the Star-Node if exists, or all child nodes to traverse further.

  • If there are predicate(s) on the split dimension, select the child node(s) that satisfy the predicate(s).

  • If there is no predicate, but there is a group-by on the split dimension, select all child nodes except Star-Node.

• Recursively repeat the previous step until all leaf nodes are reached, or all predicates are satisfied.

• Collect all the documents pointed by the selected nodes.

  • If all predicates and group-by's are satisfied, pick the single aggregated document from each selected node.

  • Otherwise, collect all the documents in the document range from each selected node.note