[jira] [Created] (ARROW-2176) [C++] Extend DictionaryBuilder to support delta dictionaries

["Dimitri Vorona (JIRA)" <ji...@apache.org>]

Dimitri Vorona created ARROW-2176:
-------------------------------------

             Summary: [C++] Extend DictionaryBuilder to support delta dictionaries
                 Key: ARROW-2176
                 URL: https://issues.apache.org/jira/browse/ARROW-2176
             Project: Apache Arrow
          Issue Type: New Feature
          Components: C++
            Reporter: Dimitri Vorona
             Fix For: 0.9.0


[The IPC format|https://arrow.apache.org/docs/ipc.html] specifies a possibility of sending additional dictionary batches with a previously seen id and a isDelta flag to extend the existing dictionaries with new entries. Right now, the DictioniaryBuilder (as well as IPC writer and reader) do not support generation of delta dictionaries.

This pull request contains a basic implementation of the DictionaryBuilder with delta dictionaries support. The use API can be seen in the dictionary tests (i.e. [here|https://github.com/alendit/arrow/blob/delta_dictionary_builder/cpp/src/arrow/array-test.cc#L1773]). The basic idea is that the user just reuses the builder object after calling Finish(Array*) for the first time. Subsequent calls to Append will create new entries only for the unseen element and reuse id from previous dictionaries for the seen ones.

Some considerations:
 # The API is pretty implicit, and additional flag for Finish, which explicitly indicates a desire to use the builder for delta dictionary generation might be expedient from the error avoidance point of view.
 # Right now the implementation uses an additional "overflow dictionary" to store the seen items. This adds a copy on each Finish call and an additional lookup at each GetItem or Append call. I assume, we might get away with returning Array slices at Finish, which would remove the need for an additional overflow dictionary. If the gist of the PR is approved, I can look into further optimizations.

The Writer and Reader extensions would be pretty simple, since the DictionaryBuilder API remains basically the same. 



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)