Druid query processing with filtering and indexes ---------------------------------------- Many filters are split into

DimFilter

and

Filter

, the former of which can build the later, which is for processing individual segments to do the filtering. this split isn’t necessary, rather it is left overs from earlier decisions on isolating the json request types from the mechanical segment processing types, and we’ve started combining some implementations.

Filter

is the interesting one though from the query engines perspective.

Filtering in Druid can currently happen in two ways, using indexes, and value matchers. 
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/filter/Filter.java#L50>

Every filter must implement a value matcher (and vector value matcher if supporting the vectorized engines), which is typically done as a predicate that just accepts row values as inputs and decides if the row matches or not.
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/filter/ValueMatcher.java>
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/filter/vector/VectorValueMatcher.java>

Filters may also use indexes, if the underlying column supports them. Currently filters only support indexes which can produce a bitmap corresponding to the row numbers of the column which match a given filter, the computation of which is captured in this interface
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/column/BitmapColumnIndex.java#L30>
and produces our bitmap wrapper type to support various implementations:
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/collections/bitmap/ImmutableBitmap.java>
the `BitmapResultFactory` is a wrapper for `ImmutableBitmap` operations to instrument them with metrics, `BitmapColumnIndex`. Roaring is the default bitmap implementation.

Both indexes and value matchers are used when constructing the cursor for processing the segment columns, which currently unfortunately knows a bit more than it should about how filters work,
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/QueryableIndexStorageAdapter.java#L338>
and partitions them into 'pre' filters (indexes) and 'post' filters (value matchers).

The indexes are computed into a
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/BitmapOffset.java> or <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/vector/BitmapVectorOffset.java> as appropriate, and similarly the remaining filters are put into <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/FilteredOffset.java> or <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/vector/FilteredVectorOffset.java>

This is something I am working towards changing, since we actually have the underlying machinery so that cursor construction doesn't have to know how to partition filters, and instead could just allow filters to produce Offsets/VectorOffsets directly. This would allow for filters to use any type of index even if it doesn't produce a `ImmutableBitmap`, since it would have complete control over the Offsets/VectorOffsets that the cursor is built around.

Anyway, back to filters. So filters which use indexes are given a 
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/filter/ColumnIndexSelector.java#L30> which is a thing that can provide a <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/column/ColumnIndexSupplier.java#L44> for a given column, which is the thing that produces indexes for that column.

Filters use this 'as' method to ask the index supplier if it has the type of indexes it is looking for, for the column it is looking at. All columns which exist, have a `ColumnIndexSupplier`, so if the supplier itself is null, it means the filter can build an 'all true' or 'all false' bitmap if the filter matches or doesn't match nulls (for most filters it should probably not match nulls to be SQL compatible, which is sort of a problem area right now with druid filtering/indexes and another area i'd like to work on fixing in the near term)

Using the `LikeFilter` as an example
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/filter/LikeFilter.java#L74>
it first checks to see if the supplier exists, if not, makes a null matching index, but if the supplier does exist, then it checks for a few different specialized indexes (such as one for equality and one that can exploit that the value dictionary and bitmap index are lexicographically sorted in string columns), and finally falls back to a predicate index if the comparator does not match the column type, which can use the same predicate as the value matcher

`ColumnIndexSupplier` are what actually provides the index gizmos from the columns (or virtual columns, but we'll ignore that for now) to the filters. For strings, the supplier is <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/serde/DictionaryEncodedStringIndexSupplier.java#L78>

which is attached to the column when reading it from the segment
<https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/serde/DictionaryEncodedColumnPartSerde.java#L364>

segments themselves load from here <https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/IndexIO.java#L539>