sql: add support for ARRAY type

[petermattis]

• arrays in expressions sql: add support for ARRAY indexing #10518 sql: add support for ARRAY operators and functions #10519
• arrays on pgwire sql/pgwire: text decoding and binary en/decoding for arrays is not supported #13358 sql/pgwire: Support decoding ARRAY OIDs in string format #10713 sql: pgwire behavior for vector types is partially incorrect #13434
• arrays in pg_catalog virtual tables sql: list the typelem for arrays in pg_type #13524 sql: list the conversion functions in pg_type #12526 sql: incompatible array type names in pg_type (Npgsql support) #13470
• arrays in table/view descriptors (storing arrays)
• KV array encoding (storing arrays)
• DistSQL support (encoding over the wire)
• optimize table lookups for = ANY(array) like for IN expressions sql: optimize = ANY like IN #13593

[vivekmenezes]

I've been thinking about how youtube could store all their user comments on cockroachdb. On youtube you can post a comment against a video. You can also reply to an existing comment about a video. So the comment space can be modeled in a table where every row represents a video, with a column containing an array of all the comments related to a video. In addition comments can reference other comments, so the comment type needs to be a tuple like <id, other-comment-id, comment>

The array type should support fast append and update operations, to allow quick commenting and editing of comments.

[kevincox]

@vivekmenezes Your method would work for small comment sets but you would quickly run into an issue with contention on that array for videos with people commenting quickly and size problems with large amounts of comments. However I think that your suggestion of update operations is a great one. Having array operations built in would avoid having to read the value and then process it locally in a transaction before sending back the new array to the server. Using update commands could create much shorter transactions witch would obviously be good for performance.

[JackKrupansky]

1. I'd recommend arrays within a row to be limited to "modest" size (dozens, maybe hundreds of entries at most.) In any case, a row should be a manageable size.
2. User-defined types are great to define the tuple to be stored in an array. Synchronizing a bunch of parallel arrays (user ID, timestamp, comment text) is a pain. Need to look at how they would be queried, such as all comments by a particular user or all comments within a timestamp range.
3. Non-modest arrays are best handled as rows in a table, accessed either vis JOIN, nested SELECT, or a separate manual query.
4. Non-modest arrays frequently need to be queryable, so rows in a table make sense.
5. The eternal question: Should we just do what Postgres does? (Or at least use it as a starting point for discussion.)
6. Most comments these days are threaded (hierarchical), which further argues that user comments should be distinct rows.

[vivekmenezes]

One of the reasons for me putting in a real world example, is to allow the
choice of an architecture where each element of the array maps to a
different kv pair on the underlying KV store be part of the consideration
here. It will still mean a lot of contention reading the entire array, but
perhaps we anyway need to support a read with a timestamp a few
milliseconds into the past, or perhaps a read up to a certain array index
to reduce contention.

Alternatively, propose a different schema for the domain. A table with each
individual comment stored in an individual row and the comment id acting as
the primary key, with a column for the video id and secondary index on it.
The comments are read using a secondary index on the video.

A key design consideration is the ability to read all the comments off a
single node (few nodes)

On Tue, Jan 26, 2016 at 11:33 AM Kevin Cox notifications@github.com wrote:

@vivekmenezes https://github.com/vivekmenezes Your method would work
for small comment sets but you would quickly run into an issue with
contention on that array for videos with people commenting quickly and size
problems with large amounts of comments. However I think that your
suggestion of update operations is a great one. Having array operations
built in would avoid having to read the value and then process it locally
in a transaction before sending back the new array to the server. Using
update commands could create much shorter transactions witch would
obviously be good for performance.

—
Reply to this email directly or view it on GitHub
#2115 (comment)
.

[kevincox]

WWPGD (What would postgres do) seems like a pretty good starting point for db related questions (it has served sqlite well although very different from cockroach).

I suspect that inline arrays should probably not go over a "modest" size. I'm not saying it should be forbidden but probably discouraged and not optimized for.

At the very least there comes a point where returning the whole array becomes not very useful and that probably means that you need to filter, and once you filter you should probably be using a separate table.

That's my 2 cents at least.

[JackKrupansky]

We might also consider the Cassandra model of collections - list, set, and map. Sure, sometimes people actually do want mathematical arrays, matrices, and multi-dimensional arrays (ala Postgres), but sometimes they just want simple lists or are trying to simulate a set using an array, or similarly storing keyword/value pairs in two-dimensional arrays or parallel linear arrays.

The map collection type is nice since it lets you store and query arbitrary semi-structured data, typically keyword/value pairs much more naturally.

Cassandra has convenient operations to operate on lists, sets, and maps, such as append and prepend for list, removing list elements, removing all occurrences of a value from a list or set, removing from a map by keyword, etc. Doing all this with raw arrays would be... not so fun.

And I would encourage the same philosophy that Cassandra adopted for lists, sets, and maps: "Collections are meant for storing/denormalizing relatively small amount of data. They work well for things like “the phone numbers of a given user”, “labels applied to an email”, etc. But when items are expected to grow unbounded (“all the messages sent by a given user”, “events registered by a sensor”, ...), then collections are not appropriate anymore and a specific table (with clustering columns) should be used."

It all depends on the use case.

See:
https://cassandra.apache.org/doc/cql3/CQL.html#collections

[kevincox]

The Cassandra collection model looks really nice. It also appears similar to what I was recommending. I have quoted some of what I deem as the important parts below:

• "Collections are meant for storing/denormalizing relatively small amount of data."
• "Collections are always read in their entirety"
• "Collections cannot have more than 65535 elements."

That limit seems pretty high but I wouldn't be surprised if it is considered bad practice to get anywhere near that. Personally I would be thinking that embedded collections would be suited for "tens of elements" at most.

Again, there are multiple right answers, just sharing what I'm thinking :)

[MehSha]

+1 for Cassandra collection model.
arrays are very cool, reduce number of queries and checks to get data, both in one2many and many2many cases.
in many cases we emulate set by two queries (even if we have array).
and maps, eliminate two column tables and unnecessary relations.
all this inches us closed to embedding model (like in Mongodb) and increase both convenience (number of queries) and performance.

please implement