[C++] `DictionaryBuilder::InsertMemoValues` should not deduplicate values

[kdkavanagh]

Describe the bug, including details regarding any error messages, version, and platform.

Per #47134, duplicate values are tolerable in dictionaries, however the C++ API currently deduplicates memo values even when they are explicitly inserted by the user.

I believe this is the offending line: https://github.com/apache/arrow/blob/main/cpp/src/arrow/array/builder_dict.cc#L85

This becomes an issue when the user thinks they insert N values, but the dictionary ends up containing << N dictionary values. Since the user explicitly called InsertMemoValues, they might proceed by directly calling AppendIndices in the future - unaware that the dictionary contents do not directly map to the indices the user is appending

Component(s)

C++

[egolearner]

I will take this issue, thx.

[egolearner]

take

[egolearner]

From my perspective, there are two options:

Option 1: InsertMemoValues disallows duplicate input.
Since InsertMemoValues is designed for scenarios with known dictionary values, it makes sense to only allow unique input values. For duplicate inputs, users should use Append or AppendArray instead.

arrow/cpp/src/arrow/array/builder_dict.h

Lines 403 to 410 in 80addfa

	/// \brief Insert values into the dictionary's memo, but do not append any
	/// indices. Can be used to initialize a new builder with known dictionary
	/// values
	/// \param[in] values dictionary values to add to memo. Type must match
	/// builder type
	Status InsertMemoValues(const Array& values) {
	return memo_table_->InsertValues(values);
	}

Option 2: InsertMemoValues performs deduplication, and AppendIndices maps user input indices to the actual indices.
The DictionaryBuilder already handles deduplication for both Append and AppendArray. IMHO, it should also deduplicate inputs for InsertMemoValues, as storing duplicate values is inefficient from both memory and storage perspectives.
For each InsertMemoValues call, the deduplicated indices would be stored in memory, and later, AppendIndices would map the user-provided indices to the actual indices.

Personal preference: I lean toward Option 1.

@kdkavanagh @raulcd

[kdkavanagh]

Agree that option 1 is far better than 2 for performance reasons (the whole reason to prepopulate / appendIndices).

If the memo_table_ wasnt populated but the underlying dictionary array was (manually) populated, what would happen if the user invoked the regular append() instead of appendIndices() on the outer DictionaryBuilder?

Perhaps a happy medium is that InsertMemoValues tolerates duplicates and adds them all to the underlying dictionary array, but then only inserts unique values into the memo_table datastructure? Subsequent calls to append() would effectively use the "first" value->index mapping (the one that was stored in the memo_table), but direct calls to appendIndices() would still map directly to what the user provided to InsertMemoValues