[C++] Consider adding a scalar type object model

[asfimport]

Just did this on the Python side. In later analytics routines, passing in scalar values (example: Array + Scalar) requires some kind of container. Some systems, like the R language, solve this problem with length-1 arrays, but we should do some analysis of use cases and figure out what will work best for Arrow.

Reporter: Wes McKinney / @wesm
Assignee: Wes McKinney / @wesm

Related issues:

• [C++] Add kernels for comparison operations to scalars (blocks)

PRs and other links:

• GitHub Pull Request #3604

_{Note: This issue was originally created as ARROW-47. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
I think there are several dimensions in the design space that should be explored.

• Should scalars be backed by an ArrayData, or be standalone (or possibly one or the other)? Backing by an ArrayData allows cheap passing of binary values for example (like a std::string_view), while standalone values would be more expensive (some types will come with their owned piece of memory like a std::string). But standalone values are also more flexible in usage (you don't need a separate ArrayData that you must remember to keep alive...).

• Can scalars have disjoint types, or is a common base class desired? Or perhaps even a single union type, possible a variant? Those different solutions have different costs, and also different usage models.

[asfimport]

Wes McKinney / @wesm:
I had been thinking about having standalone in-struct storage for primitive types and using Array/ArrayData for list scalars at least. For binary I'm not sure. I just sketched the following

class Scalar {
  std::shared_ptr<DataType> type() const { return type_; }

  bool is_valid() const { return is_valid_; }

 protected:
  std::shared_ptr<DataType> type_;
  bool is_valid_;
};

template <typename Type>
class PrimitiveScalar : public Scalar {
 public:
  using T = typename Type::c_type;

  T value() const { return value_; }

 private:
  T value_;
};

class BinaryScalar : public Scalar {
 protected:
  std::shared_ptr<Buffer> value_;
};

class ListScalar : public Scalar {
 protected:
  std::shared_ptr<Array> value_;
};

I think using Buffer for binary scalars is probably the lightest weight thing that also ensures memory lifetime. In practice (e.g. in analytics code paths), we will do dynamic dispatch on the type, so as long as we have a reasonable base class that exposes that, we should try to make the object as lightweight / simple as possible.

I don't anticipate we'll be dealing with large collections of these scalar objects. But we want to be able to have a suitable way to algebraically represent the data when executing a computation graph (and writing kernel implementations that may accept either array or scalar – with "broadcasting" – arguments)

[asfimport]

Wes McKinney / @wesm:
I'm not sure about what StructScalar should look like. as we are perhaps not overly concerned about efficiency with these objects, a struct could have an internal vector of shared_ptr<Scalar>

cc @fsaintjacques @bkietz @xhochy for any thoughts

[asfimport]

Francois Saint-Jacques / @fsaintjacques:
At first sight, I'd say that StructScalar (and Scalar) memory layout will be critical to the implementation of ARROW-3978 (and joins of multiple columns/expressions), hashing/probing on the columnar representation SoA is a performance killer (due k pointer indirections and cacheline reads where k is the number of field).

The second thing, is that when we'll work with intermediary results of Scalars, the types will almost always be homogeneous. For example, when computing the hash table of a join/group-by, you'll have something like hash<Scalar, Result> where the type for each scalar instances is the same (minus Null, but we can and should specialize for nullability). Thus adding the type shared_ptr and an is_valid boolean is somewhat costly (16 + 1 + sizeof(primitive_type).

This optimization can be hidden in the implementation, but I wonder if we'll have to expose the collections at the API boundaries.

[asfimport]

Wes McKinney / @wesm:
I do not think these objects should be used on computation hot paths at all (like joins or hash aggregations); since such code is vector-oriented in general it will require more specialization

[asfimport]

Ben Kietzman / @bkietz:
One alternative to using vector<shared_ptr<Scalar>> would be a flatbuffer, which would make hashing pretty straightforward and keep small allocations low:

struct StructScalar {
  template <typename T>
  T GetFieldAs(int field_index);

  flatbuffers::Table *root_;
  std::vector<flatbuffers::reflection::Field*> fields_;
  std::shared_ptr<Buffer> storage_;
};

In any case, the main challenge I see is the amount of fragile unboxing boilerplate that StructScalar would require to be user friendly. That can be mitigated with good metaprogramming, but it's still a bit verbose:

StructScalar* obj = get();
Status s = Unbox1<int, string, ignore, bool>(obj, [](bitset<4> is_valid, int id, string_view name, ignore, bool admin) {
  // ...
});

bitset<4> is_valid;
tuple<int, string_view, ignore, bool> employee;
RETURN_NOT_OK(Unbox2(obj, &employee, &is_valid));

pair<bool, int> id;
pair<bool, string_view> name;
pair<bool, bool> admin;
RETURN_NOT_OK(Unbox3(obj, 0, &id));
RETURN_NOT_OK(Unbox3(obj, 1, &name));
RETURN_NOT_OK(Unbox3(obj, 3, &admin));

// more options available beyond c++11

[asfimport]

Wes McKinney / @wesm:
That's an interesting approach.

In any case, I don't think there's a need to do anything very complicated right now. The basic requirements are:

• A base type Scalar that exposes its type information, and nullness

• A public API for accessing values in concrete subclasses, including nested types

  So, a scalar analogue to the Array classes. Let's start with making sure we can do things like Add(Array, Scalar). The implementation details of the data structure would best be encapsulated behind a public API for the time being.

[asfimport]

Micah Kornfield / @emkornfield:
Is this covered by Datum and the implementation at https://github.com/apache/arrow/pull/3407/files ?

[asfimport]

Uwe Korn / @xhochy:
The implementation in https://github.com/apache/arrow/pull/3407/files looks like a good start. I think we can resolve this issue when the PR is merged. We probably need to add more scalar types in future, e.g. for strings but the implementation in the PR looks sufficient at the moment.

[asfimport]

Wes McKinney / @wesm:
Issue resolved by pull request 3604
#3604