docs/RFCS/20170518_array_encoding.md
Provide a kv encoding for arrays sufficient to permit array column types in user tables in non-indexed positions.
Specifically, once this RFC is implemented, users will be able to create and store tables like the following:
CREATE TABLE t (INT a PRIMARY KEY,
INT[] intArr,
STRING[] stringArr,
DATE[] dateArr);
but not like the following index or table:
CREATE INDEX idx ON t(intArr);
CREATE TABLE u (INT[] arr PRIMARY KEY);
Adding ordinary or Postgres GIN-style indexing support for arrays is out of scope for this RFC and will be addressed elsewhere.
Users will be able to perform all existing array operations on their array columns, such as inclusion tests, concatenation and element retrieval.
Arrays are a popular feature of Postgres and are a frequently requested feature for CockroachDB.
While the proper relational way to handle the problem arrays solve is to create a separate table and do a join, in many cases it can be easier, cleaner, and faster to simply have an array as a column type.
Some use cases users have shared include:
Our arrays, like Postgres' arrays, are 1-indexed, homogenous, and rectangular. Arrays can have at most 16 dimensions (this limit is arbitrary—Postgres restricts to 6 dimensions). Unlike Postgres, we include the dimensionality (number of dimensions) of an array in the column type, so a given column can only contain arrays with the same number of dimensions. We also do not support the Postgres feature of lower bounds on dimensions other than 1.
Like Postgres, we do not support nested array types. This is somewhat obscured by Postgres' use of syntax, which appear to describe nested arrays, but actually describe multidimensional arrays:
SELECT ARRAY[ARRAY[1,2,3], ARRAY[4,5,6]];
It's of note that this is not describing an array of arrays. Rather, it's describing a two dimensional array. This is an important distinction because it means that Postgres can't support subarrays of different lengths:
SELECT ARRAY[ARRAY[1,2,3], ARRAY[4,5]];
is invalid. For multidimensionality, we will only support this alternate syntax, which Postgres treats as equivalent:
SELECT ARRAY[[1,2,3],[4,5,6]];
Arrays are limited to at most 2^31-1 elements, although it's likely that the 64MB row size limit will be the proximal limiting factor to large arrays.
A column can be declared to contain an array by appending [] to the name
of any non-array datatype. So int[] denotes a 1-dimensional array of ints,
int[][] denotes a 2-dimensional array of ints, and so on.
This is the same as Postgres, with the distinction that Postgres does not
enforce the specified dimensionality of the arrays.
The column type protobuf will be modified to include an ARRAY value for
the SemanticType, and a nullable field indicating the element type if the type is
an array. The existing array_dimensions field will be replaced with an int
field denoting the number of dimensions in the array.
We also introduce a version field to the column type.
This will allow us to make a change to support multi-kv arrays in the future.
Existing columns will not be changed to the new version, so that during
deployment of a version supporting multi-kv arrays, existing columns will not
be rewritten in a way incompatible with old nodes (however we will have to
instruct users not to add new ARRAY columns during such an upgrade).
If a node sees a version number it doesn’t understand, it gives an appropriate
error message (“please finish upgrading the cluster”).
Arrays will be encoded into a single kv entry. This places a restriction on the maximum size of an array, but significantly reduces the complexity of implementation.
Array values will be encoded using a format very similar to the one used in Postgres. The format is:
NULL.As the data is homogenous, and the NULL bitmap tells us the location of any
NULLs in the array, each datum does not need to include its column value
tag. Variable-sized datums do need to be prefixed with their lengths according
to their usual encodings.
In the future, additional flags could be used to indicate things like whether this array spans multiple kv entries (and thus whether we have an associated number of kv entries), or be used as a version number.
Encoding arrays as KV-layer keys is out of scope of this RFC.
The existing in-memory array values will need to be augmented to support multidimensionality and elements besides ints and strings.
A number of Postgres array
functions
such as array_append (and its corresponding operator form ||),
array_cat, and others will also need to be implemented for users to be
able to operate on their arrays.
Currently, all data types must have a comparison implementation in order
to support IN expressions. If we remove that requirement it will allow
us to avoid the complicated discussion of how to compare arrays
(which has subtle interactions with how we will have to key-encode
arrays, if we go that route eventually).
unnest on the array and treating it as a table.NULL in the
array, we could tag every value within the array.
This was deemed wasteful as arrays are restricted to 64MB to begin
with, and it is expected that the common case is that arrays do not contain
any NULLs (and thus the bitmap can be omitted).SemanticType denote the element type, with no special cases required, as
a 0-dimensional array can be interpreted as a scalar. This option is
attractive but it was rejected on the grounds that it overly-centralizes the
concept of column types around arrays and makes scalar datum types the special
case rather than the common case. That said, when it comes time to implement
it may turn out that this alternative is significantly easier.