[Proposal] More flexible dimension types

[jon-wei]

Currently, Druid assumes that all dimensions have string values and are associated with a bitmap index.

There has been interest in loosening these constraints to support use cases that blur the existing separation between dimensions and metrics, e.g., filtering on numeric columns, aggregating dimensions at query time.

A recent discussion on these topics can be found here:
https://groups.google.com/d/msg/druid-user/Mk6omlC6Vbk/jtIFGFrACwAJ

This proposal was initially sent out on the druid-dev list, and initial comments can be found there:
https://groups.google.com/d/topic/druid-development/obtfNJnXPDg/discussion

This proposal calls for two major changes/features:

---

1.) Remove the assumption that dimensions always have string values.

This change is a path towards reducing the distinction between dimensions and metrics.

This would involve changes to:

• IncrementalIndex, IndexMerger, etc. (ingestion)
• StorageAdapters, query engines, etc. (querying)
• Ingestion specs, allow user to specify dimension types (e.g., String, Long, Float)

---

2.) Allow user to choose per-column index strategies

Druid could support a wider range of index types beyond bitmaps. Giving users control over what indexes are used on a per-column basis could make Druid more powerful and efficient.

For example, if a dimension is expected to have high cardinality and range filters applied to it, the user may want to choose a tree-based index instead of bitmaps.

As another example, trie indexes could be used to better support text search on dimension values.

The existing ColumnCapabilities class could be used to describe what indexes are supported for a column.

This would involve changes to:

• query-related components, allow them to handle columns that do not use bitmap indexes
• on-disk storage format, to store new index types with the columns
• ingestion specs

---

EDIT, Mar. 15 2016:

The following patch has been merged, it prepares IncrementalIndex for later typing-related changes:
#2263

The following PRs are currently open, and should be reviewed/merged in order:
druid-io/druid-api#75 - Adds DimensionSchema class for specifying dimension type, properties
#2607 - Updates druid main to use DimensionSchema
#2621 - larger PR that adds support for Long/Float typed dims

[jon-wei]

I have opened a PR with some initial work on Part 1 (corresponding to the ingestion subitem):

#2263

The PR changes the internal structures used by IncrementalIndex such that they can now store numeric types for dimensions.

Interfaces between IncrementalIndex and other modules are left unchanged (i.e., dims will still appear to be Strings to other modules)

[jon-wei]

As a next step, I am currently working on adding basic support for numeric dimensions to the query engines and filters (part 1, subitem 2).

At a high level, the approach I am considering is:

• Reuse the existing Long/Float column formats to represent numeric dimensions on disk, similar to how timestamp is stored now (not adding new index types at this point)
• No dictionary encoding on numeric dims, just use the numeric values directly
• Change the QueryableIndex and Adapter classes to support numeric dims
• Adapt the query-related components to support dim columns without bitmap indexes and dictionary encoding

I plan to have a PR out for this by the end of next week (end of January).

[drcrallen]

Are these two changes required to go in at the same time? as in: is it a lot of extra effort to add string/float/long values backed by bitmaps separately from arbitrary index types?

[drcrallen]

If I use LONG dimension values to store fake ISO dates like 20150119, does that still fit in with the "no dictionary" approach?

[gianm]

@drcrallen That kind of column should compress really well with just block compression on long columns, since there will be a lot of runs of repeated data.

[jon-wei]

@drcrallen

For your first point, I don't think they would be required to go in at the same time.

In terms of effort, I think adding float/long backed by bitmaps/dictionary encoding would probably be the "minimal" path, in that it involves less change to existing logic/interfaces, compared to adding support for arbitrary index types.

I discussed dictionary encoding for numeric dims briefly with @gianm today; from that, we were leaning towards a "no index/dictionary" approach for numeric dims as an initial implementation because of concerns with wasted storage and added cost of dictionary lookups since the numeric types are fixed-width already.

[jon-wei]

@drcrallen For your second point, what is the impact of having dictionary encoding/not having it for the fake ISO date use case?

[drcrallen]

Imagine having a dataset where your event stream includes "signup-date" and you want to filter events based on who signed up between 30 days and 6 months ago. One potential implementation using the dictionary approach would filter dimension values on if they are in the range and use an OR function on the bitmaps.

If we're sticking with the cursor based approach and NO dictionary/index, would you want to read every row value and evaluate some predicate to determine the inclusion?

[drcrallen]

Intuitively it seems like it would make a difference for low vs high cardinality numeric dimensions, where I can see the dictionary/index approach being useful for low cardinality ones, but potentially counter-productive (due to disk space and bitmap-merge time) for high cardinality ones.

[drcrallen]

But some numbers to back up such things would be required

[KurtYoung]

I think we should add another option to dimension too, which is whether is dimension is multi value and what the delimiter is. Currently, we configured a global "listDelimeter" for overall dimension and it will cause some dimension which i think should be single-value but turns out that dimension contains some "listDelimeter" and druid treat it as multi-value dimension. And in second case, it sometimes hard to let users to set one listDelimeter for all multi-value dimensions because these dimensions may come from different source and owned by different people.

[jon-wei]

@drcrallen I see, makes sense.

I think it would be a sensible end-goal to be able to support bitmaps+dictionaries, no index, and alternate indexes (e.g.,the sorted array+binary search structure for range queries that Conrad Lee suggested in the original "numeric dimensions" thread.) as a user-configurable option.

In terms of plan/development steps, I am leaning towards getting one indexing strategy working for numeric vals for initial "it works" functionality, and then adding support for configurable indexes as a later PR.

[drcrallen]

I'm wondering now if 2 from your list makes more sense to hammer out first so that 1 will be retain backwards compat during iterations of "what dimension indices are supported"