docs/index_techniques.rst

..
.. Licensed to the Apache Software Foundation (ASF) under one
.. or more contributor license agreements.  See the NOTICE file
.. distributed with this work for additional information
.. regarding copyright ownership.  The ASF licenses this file
.. to you under the Apache License, Version 2.0 (the
.. "License"); you may not use this file except in compliance
.. with the License.  You may obtain a copy of the License at
..
..   http://www.apache.org/licenses/LICENSE-2.0
..
.. Unless required by applicable law or agreed to in writing,
.. software distributed under the License is distributed on an
.. "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
.. KIND, either express or implied.  See the License for the
.. specific language governing permissions and limitations
.. under the License.
..

.. warning::  The documentation is not up-to-date and has moved to `Apache Pinot Docs <https://docs.pinot.apache.org/>`_.

.. TODO: add more details


Index Techniques
================

.. contents:: Table of Contents

Pinot currently supports the following index techniques, where each of them have their own advantages in different query
scenarios. By default, Pinot will use ``dictionary-encoded forward index`` for each column.

Forward Index
-------------

Dictionary-Encoded Forward Index with Bit Compression (Default)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

For each unique value from a column, we assign an id to it, and build a dictionary from the id to the value. Then in the
forward index, we only store the bit-compressed ids instead of the values.

With few number of unique values, dictionary-encoding can significantly improve the space efficiency of the storage.

The below diagram shows the dictionary encoding for two columns with ``integer`` and ``string`` types. As seen in the
``colA``, dictionary encoding will save significant amount of space for duplicated values. On the other hand, ``colB`` 
has no duplicated data. Dictionary encoding will not compress much data in this case where there are a lot of unique
values in the column. For ``string`` type, we pick the length of the longest value and use it as the length for 
dictionary's fixed length value array. In this case, padding overhead can be high if there are a large number of unique 
values for a column.

.. image:: img/dictionary.png


Raw Value Forward Index
~~~~~~~~~~~~~~~~~~~~~~~

In contrast to the dictionary-encoded forward index, raw value forward index directly stores values instead of ids.

Without the dictionary, the dictionary lookup step can be skipped for each value fetch. Also, the index can take
advantage of the good locality of the values, thus improve the performance of scanning large number of values.

A typical use case to apply raw value forward index is when the column has a large number of unique values and the
dictionary does not provide much compression. As seen the above diagram for dictionary encoding, scanning values
with a dictionary involves a lot of random access because we need to perform dictionary look up. On the other hand, 
we can scan values sequentially with raw value forward index and this can improve performance a lot when applied 
appropriately.

.. image:: img/no-dictionary.png

Raw value forward index can be configured for a table by setting it in the table config as

.. code-block:: none

    {
        "tableIndexConfig": {
            "noDictionaryColumns": [
                "column_name",
                ...
            ],
            ...
        }
    }


Sorted Forward Index with Run-Length Encoding
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

When a column is physically sorted, Pinot uses a sorted forward index with run-length encoding on top of the 
dictionary-encoding. Instead of saving dictionary ids for each document id, we store a pair of start and end 
document id for each value. (The below diagram does not include dictionary encoding layer for simplicity.)

.. image:: img/sorted-forward.png


Sorted forward index has the advantages of both good compression and data locality. Sorted forward index can 
also be used as inverted index.

Sorted index can be configured for a table by setting it in the table config as

.. code-block:: none

    {
        "tableIndexConfig": {
            "sortedColumn": [
                "column_name"
            ],
            ...
        }
    }

Realtime server will sort data on ``sortedColumn`` when generating segment internally. For offline push, input data
needs to be sorted before running Pinot segment conversion and push job.

When applied correctly, one can find the following information on the segment metadata.

.. code-block:: none

    $ grep memberId <segment_name>/v3/metadata.properties | grep isSorted
    column.memberId.isSorted = true


Inverted Index (only available with dictionary-encoded indexes)
---------------------------------------------------------------

Bitmap Inverted Index
~~~~~~~~~~~~~~~~~~~~~

When inverted index is enabled for a column, Pinot maintains a map from each value to a bitmap, which makes value 
lookup to be constant time. When you have a column that is used for filtering frequently, adding an inverted index
will improve the performance greatly.

Inverted index can be configured for a table by setting it in the table config as

.. code-block:: none

    {
        "tableIndexConfig": {
            "invertedIndexColumns": [
                "column_name",
                ...
            ],
            ...
        }
    }


Sorted Inverted Index
~~~~~~~~~~~~~~~~~~~~~
Sorted forward index can directly be used as inverted index, with ``log(n)`` time lookup and it can benefit from data locality. 

For the below example, if the query has a filter on ``memberId``, Pinot will perform binary search on ``memberId`` values 
to find the range pair of docIds for corresponding filtering value. If the query requires to scan values for other columns
after filtering, values within the range docId pair will be located together; therefore, we can benefit a lot from data locality.

.. image:: img/sorted-inverted.png

Sorted index performs much better than inverted index; however, it can only be applied to one column. When the query performance
with inverted index is not good enough and most of queries have a filter on a specific column (e.g. memberId), sorted index can
improve the query performance.


Advanced Index
--------------

Star-Tree Index
~~~~~~~~~~~~~~~

Unlike other index techniques which work on single column, Star-Tree index is built on multiple columns, and utilize the
pre-aggregated results to significantly reduce the number of values to be processed, thus improve the query performance.


Notes on Index Tuning
---------------------

If your use case is not site facing with a strict low latency requirement, inverted index will perform good enough for 
the most of use cases. We recommend to start with adding inverted index and if the query does not perform good enough,
a user can consider to use more advanced indices such as sorted column and star-tree index.