The concept of practical implementation of the array

[izveigor]

Foreword

The article is about arrays in DataFusion. I decided to write it due to this topic become more popular among users and developers.
Active development is currently underway, dedicated to the formatio formation of an array as a full-fledged tool for working with information. I can not call the development itself successful, I think the main reason is the absence of an unified development concept. So, the main goal of this article is to draw up a general concept and give meaning to the technology for the user.

Backstory

Let's start from the beginning and how exactly the idea of implementing arrays was born. Prior to my introduction to DataFusion there were one array function (make_array) and one internal function (unnest_columns). After that, there was a lull in this topic until a user with a nickname @bubbajoe brought this topic up again. During the discussions, we came to the conclusion that it is necessary to implement some array functions, and the relational database PostgreSQL was chosen as a reference. Most of the features have been implemented in PR: #6384. After the merge, we begin to realize that nested data types are not simple, since many DataFusion mechanisms are not adapted to work with them.

The naive implementation of array functions brought a lot of problems and ambiguities. It is related to the fact that the most developers (including me) do not understand how arrays work, which is why they cannot solve the problem correctly. I see the solution to the problem in the use of some concepts of development ethics, because the development of such a voluminous topic should be introduced reasonably.

About development ethics

Let's start with the first mistake that has been made in naive implementation - not having a plan. The development was introduced incrementally, any feature was made taking into the account by individual need. This led to an increase in the cost of development, the lack of communication between individual features. Therefore, in my opinion, further development should go according to the plan. It will also helps to avoid the parallelism work that constantly arises during the wrong order of implementation of specific features.

New development plan

This part will be devoted to developing a plan for solving array problems.

This part is not complete, so more information will be added here over time.

The main postulates DataFusion

In order to form the principles by which arrays will work, it is necessary to understand the areas of application of this technology. Let's start with the purpose of the existence of DataFusion technology. @alamb repeatedly cited similar reasoning in his discussions. Key ideas include:

• DataFusion is Deconstructed Database;
• Vectorization;
• Multithreading;
• Support from Parquet, CSV, JSON and AVRO;
• low latency
• mostly analytical queries
• Based on Apache Arrow, whose principles are:
  • language-independent columnar memory format
  • zero-copy
  • Vectorization
  • SIMD
  • for analytics
• OLTP/OLAP

About array

Basic postulates:

• Array is the object ListArray (Apache Arrow);
• Array is FixedSizeListArray, LargeList and ListArray transform to ListArray;
• Array contains objects of the same data types;
• Array can be heterogeneous (he should contain objects and NULLS) or homogeneous (without NULLS);
• Array from List objects are nested;
• Column with arrays can no consider the length of array, hovewer it should consider their dimensions;
• Array can contain all posible data types if it makes sense.
• Array can contain unique or non unique items;

Thus we can conclude that the main characteristics of the array are:

• Empty array
• Data type
• Length
• Dimension
• Homogeneity
• Uniqueness

About array functions:

Basic postulates:

• Element can be anything from which an array can be built (NULL, array, number...);
• Function can return either an element, or a boolean value, or an array, or NULL;

Why are arrays needed?

Now let's see what is the main point of using an array from the user's point of view. The main points of use are:

• An array allows you to see an object as atomic. For Example, LMS matrix can be presented as an array and assigned image;
• Arrays can be represented as a set or multiset or ordered set;
• Arrays can take on the behavior of tensors and matrices in the mathematics;
• Arrays are a means of storing similar objects if storing them in a different form is impractical;

So, an array can be represented as:

• Set;
• Ordered Set;
• MultiSet;
• Vector;
• Stack;
• Deque;
• Queue;

About the features of the user query language

DataFusion adheres to the principles of SQL databases. Every command in SQL is atomic. The set of SQL command results forms a query language.
A language can be composed of many other languages.

Now let's figure out which languages ​​will arrange work with an array:

• DML (Data Manipulation Language) is needed to manage the data inside the array.
• A set language is needed to implement an array as a concrete set

Language DML

Let's start with the data manipulation language. For effective. Its principles:

• any element of the array can be read.
• in the array, you can insert the corresponding element at any place.
• any element of the array can be updated.
• any element of the array can be removed.

Set the characteristics of the array:

In quantity:

• uniqueness
• plurality
• integrity (will not be used, since there are classic functions of the SQL language (SELECT, SET ...) for this).

By quality:

• By index (means we can read, insert, update and delete a specific index)
• By value (here the concepts change to search, fill, replace and delete)
• By borders (here we highlight the feature of the first and last element of the array).
• By predicates

Based on the characteristics of the array, we obtain the corresponding functions.

Corresponding index table:

Quantity	Read	Insert	Update	Remove
Uniqueness	array_element	array_insert	SET array[i] = value	array_delete
Plurality	array_slice	array_insert	SET array[i:j] = value	array_delete

Corresponding table by values:

Quantity	Search	Fill	Replacement	Remove
Uniqueness	array_position(array, [i])	array_resize(x, 1)	array_replace(array, from, to)	array_remove(array, element)
Plurality	array_positions(array)[:i]	array_resize(x, n)	array_replace(array, from, to, max)	array_remove(array, element, max)
Wholeness	array_positions(array)	array_resize(x, array_length(array))	array_replaces(array, from, to)	array_removes(array, element)

Corresponding table by borders:

Border	Quantity	Read	Insert	Update	Remove
Right	Uniqueness	array_first	array_append	SET array[0] = value	array_pop_front
Left	Uniqueness	array_last	array_prepend	SET array[array_length(array) - 1] = value	array_pop_back
Right	Plurality	array_slice(0, n)	array_insert(0, n)	SET array[0:n] = value	array_delete(0, n)
Left	Plurality	array_slice(n, array_length(array))	array_insert(n, array_length(array))	SET array[n:array_length(array) - 1] = value	array_delete(n, array_length(array))

Corresponding table by predicates:

Quantity	Read	Insert	Update	Remove
Uniqueness and Plurality	array_filter	-	array_transform	negation array_filter

Set Language

An array can be viewed not only as a vector, but also as a set.

Basic set operations

• Union (array_concat or array_union)
• Intersection (array_intersect or &&)
• Set difference (array_except)

All subsequent operations can be derived from these concepts.

Cartesian product:

• array_zip

Example (ClickHouse):

SELECT arrayZip([1, 2, 3], ['a', 'b', 'c'])

Query id: 12f6cb4c-50db-4d31-9ff0-8fb15bf849cf

┌─arrayZip([1, 2, 3], ['a', 'b', 'c'])─┐
│ [(1,'a'),(2,'b'),(3,'c')]            │
└──────────────────────────────────────┘

###
1 row in set. Elapsed: 0.075 sec.

Checking if a subset belongs to a set

• array_has_all

SELECT hasAll([1, 2, 3, 4], [1, 4])

Query id: 91f73cf4-9527-4ee5-95d8-20211ca42652

┌─hasAll([1, 2, 3, 4], [1, 4])─┐
│                            1 │
└──────────────────────────────┘

1 row in set. Elapsed: 0.001 sec.

Checking if any element of another set belongs to a set

• array_has_any

SELECT hasAny([1, 2, 3], [1, 4, 5])

Query id: 88619172-38cf-4124-a0c3-853fe95d5260

┌─hasAny([1, 2, 3], [1, 4, 5])─┐
│                            1 │
└──────────────────────────────┘

1 row in set. Elapsed: 0.001 sec.

Checking if an element belongs to a set

• array_has or array_contains

SELECT hasAll([1, 2, 3, 4], [1, 4])

Query id: 91f73cf4-9527-4ee5-95d8-20211ca42652

┌─hasAll([1, 2, 3, 4], [1, 4])─┐
│                            1 │
└──────────────────────────────┘

1 row in set. Elapsed: 0.001 sec.

About aliases

My postulate regarding aliases is simple: an alias is admissible under conditions:

• alias allow you to split the characteristics of an array;
• alias is handy for people used to naming while working with other tools;
  So, I propose to introduce the alias list_ for each function as a mutable object and array_ as an immutable object.

Other aliases of functions should be assigned based on other technologies (for instance, the PostgreSQL function array_cat is an alias for array_concat).

Sort

An array can be sorted in two ways: left to right (array_sort) and right to left (array_reverse_sort).

About aggregate functions

Based on the postulate - convinience from the user's point of view, all aggregate functions must be adapted to the array.
Two approaches can be distinguished:

• via expansion (unnest)
• through functions (for example: list_sum)
• through the argument of one function (list_aggregate)

I think all these ways should be used.

Working with Array Characteristics

Characteristics can be divided into categories:

Quality:

• data type
• homogeneity
• uniqueness
• emptiness

Quantity:

• length
• dimension

For qualitative categories, the following behavior corresponds:

• qualities are limited;
• we can know the quality;
• free exchange between qualities;
• we can make an affirmative judgment about qualities;

For quantitative categories, the following behavior corresponds:

• quantities are limited (from 1 to the maximum value);
• we can know the quantity;
• we can convert the quantity to one;
• we can know the quantity from other quantitative attributes;

Data type

• We can find out the data type of an array (array_length);
• We can translate (if it makes sense) the array data type (CAST);

Length

• We can find out the length of an array (array_length);
• We can translate the length to 1 (array_element(array, 0));
• We can find out the length of an array without taking into account the dimension (cardinality);
• We can find out the lengths of arrays given the dimension (array_dims);

Emptiness

• There should be a function that answers the question: "Is the array empty or not?" (empty);

Dimension

• We can find out the dimension of an array (array_ndims);
• We can convert the dimension to unity (flatten);

Homogeneity

• Function that answers the question: "Is the array homogeneous or not?" (NOT (array_filter(array, x -> x IS NULL)));
• The function of transferring an array from homogeneous to non-homogeneous (array_filter(array, x -> x IS NOT NULL));

Uniqueness

• Function that answers the question: "Is an array unique?" (array_distinct(array) == array);
• Function to convert an array from unique to non-unique (array_distinct);

Documentation

After the implementation of each function, the corresponding documentation must be written.
Documentation should have the following features:

• All data types that form an array must be painted
• For each function there must be:
  • Type of accepted arguments (array, column, string, number...);
  • Description;
  • Small example;
  • Some clarifying data, if needed;

Other applications

For other areas (such as optimization, hashing, and so on), should be consistent with the general concept, but it is considered redundant to write about it here.

Criticism of various array implementations among other databases

PostgreSQL

Pros:

• Quite a lot of functions with dimension work (array_ndims, array_dims...);
  Cons:
  It is diffucult to represent an array as a set in PostgreSQL, so its language is limited in the following operations:
  • does not allow you to create an array based on predicates;
  • incomplete set of set operations;
  • there is no Cartesian product;
    Other restrictions include:
• declarative language does not support some array modifications (see example with stones);
• most routine operations require complex code to be written;

DuckDB

Pros:

• Support for predicates;
• Rich functional support;
  Cons:
• Few functions for working with length and dimension;
• declarative language does not support some array modifications (see example with stones);

ClickHouse

Pros:

• Huge support for predicates;
• Rich functional support;
  Cons:
• Few functions for working with length and dimension;
• declarative language does not support some array modifications (see example with stones);

Comparison

Here we will consider three binary relations: an equivalence relation, a parial order relation, and a strict order relation.

With order relationships (partial and strict), the results are based on the first other pair of elements, not on the sizes of the arrays.

With equivalence relations, results are based on exact element-by-element comparison (=, !=).

Operators

• @> = array_contains(first_array, second_array);
• <@ = array_contains(second_array, first_array);
• && = array_intersect(first_array, second_array);
• || = array_concat(first_array, second_array)
• array[i] = array_element(array, i);
• array[i:j] = array_slice(array, i, j);
• array[i] = value = array_update(array, value, i);
• array[i:j] = values = array_update_slice(array, values, i, j);
• <, <=, =, !=, >, >= (See: Comparison);
• [a1,...,an] = make_array(a1,...,an);

Reference: Examples of Difficult Scenarios

Example with stones

Let's say in some country there is a vote for the approval of some reform. Every citizen can vote for and against. The color of the stones will be used as the subject of the vote, namely black (against) and white (for). From the point of view of the array, this reconstruction will look like this, we have an array consisting of 0 (black color) and 1 (white color). However, a situation may arise the elections. For example, 2 white balls and 3 black balls were dishonestly counted in the vote. Having noticed the falsification, the state decides to remove or replace these stones with NULL.

Now let's try to solve these problems using different databases:

Initial list: [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0]

My decision

# Remove
SELECT array_remove(array_remove([1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0], 1, 3), 0, 2);
----
[1, 1, 1, 0, 1, 1, 0]

# Replace
SELECT array_replace(array_replace([1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0], 1, NULL, 3), 0, NULL, 2);
----
[NULL, NULL, NULL, 1, 1, 1, NULL, NULL, 0, 1, 1, 0]

Other databases

There are no solutions using Turing incomplete declarative language (classic SQL) for databases like DuckDB, PostgreSQL.

List of array functions

List of array functions and their aliases

Array function	Aliases
make_array	make_list
array_element	list_element, array[i]
array_insert	array_insert, list_insert
array_delete	list_delete
array_slice	array[i:j], list_slice
array_position	list_position
array_repeat	list_repeat
array_replace	list_replace
array_remove	list_remove
array_positions	list_positions
array_replaces	list_replaces
array_removes	list_removes
array_first	list_first
array_append	list_append
array_pop_front	list_pop_front
array_last	list_last
array_prepend	list_prepend
array_pop_back	list_pop_back
array_filter	list_filter
array_transform	list_transform
array_concat	list_concat, array_cat, list_cat, array_union, list_union
array_intersect	&&, list_intersect
array_except	list_except
array_zip	list_zip
array_has	array_contains, list_contains, list_has
array_has_any	list_has_any
array_has_all	list_has_all
array_sort	list_sort
array_reverse_sort	list_reverse_sort
unnest	-
array_aggregate	list_aggr, list_aggregate, array_aggr
array_length	list_length
cardinality	-
array_dims	list_dims
empty	-
array_ndims	list_ndims
flatten	-
array_distinct	list_distinct

List of array functions and their counterparts from other databases

Array function	PostgreSQL	Azure	DuckDB	ClickHouse
make_array	array[]	array	list_value	array
array_element	array[i]	array[i]	list_element(array, i)	arrayElement
array_insert	-	array_insert	-	-
array_slice	-	list_slice	-	-
array_position	array_position	array_position	array_position	indexOf
array_repeat	array_fill	array_repeat	-	arrayResize
array_replace	-	-	-	-
array_remove	-	-	-	-
array_positions	array_positions	-	-	-
array_replaces	array_replace	array_replace	array_transform	array_transform
array_removes	array_remove	array_remove	array_filter	array_filter
array_first	array[0]	array[0]	array[0]	arrayFirst
array_append	array_append	array_append	array_append	arrayPushBack
array_pop_front	-	-	array_pop_front	arrayPopFront
array_last	array[array_length(array) - 1]	array[array_length(array) - 1]	array[array_length(array) - 1]	array[length(array) - 1]
array_prepend	array_prepend	array_prepend	arrayPushFront
array_pop_back	-	-	array_pop_back	arrayPopBack
array_filter	-	-	array_filter	arrayFilter
array_transform	-	-	array_transform	arrayTransform
array_concat	array_concat	array_union	array_concat	arrayConcat
array_intersect	-	array_intersect	array_intersect	arrayIntersect
array_except	-	array_except	array_except	-
array_zip	-	arrays_zip	-	array_zip
array_has	-	array_contains	array_has	has
array_has_any	&&	arrays_overlap	array_has_any	hasAny
array_has_all	@> or <@	-	array_has_all	hasAll
array_sort	-	array_sort	array_sort	arraySort
array_reverse_sort	-	array_sort	array_reverse_sort	arrayReverseSort
unnest	unnest	-	unnest	arrayJoin
array_aggregate	-	-	list_aggregate	-
array_length	array_length	array_length	array_length	length
cardinality	cardinality	-	-	-
array_dims	array_dims	-	-	-
empty	-	-	-	Empty
array_ndims	array_ndims	-	-	-
flatten	-	-	flatten	arrayFlatten
array_distinct	-	array_distinct	array_distinct	arrayDistinct

Sources:

Articles:
https://www.usenix.org/system/files/login/articles/login_winter18_08_khurana.pdf

Videos:
https://www.youtube.com/watch?v=kHpy64smpYQ - From flat files to deconstructed database The evolution and future of the big data ecosyst

Documentations:

• DuckDB:
  • https://duckdb.org/docs/sql/data_types/list.html
  • https://duckdb.org/docs/sql/functions/nested
• Azure:
  • https://learn.microsoft.com/en-us/azure/databricks/sql/language-manual/data-types/array-type
  • https://learn.microsoft.com/en-us/azure/databricks/sql/language-manual/functions/array
• ClickHouse:
  • https://clickhouse.com/docs/en/sql-reference/functions/array-functions
• PostgreSQL:
  • https://www.postgresql.org/docs/current/functions-array.html

Pull Requests:
#6384

Issues:
#6119

Discussions:
#6441

[izveigor]

@alamb I would like to ask a few questions.
Don't you think that copying behavior PostgreSQL is not a right approach to the formation of array functions?
In my opinion, DataFusion should form its purpose and the behavior of array functions based on its goals, as well as the experience of other databases.
Some of my thoughts:

• DML (each element of the array must be read, modified, updated or deleted (you can use both the index and values as a basis));
• Array can be a set, and obey their laws;
• Array elements can be processed by aggregate functions;
  I have nothing against PostgreSQL, but I consider their feature set incomplete for analytical queries.

For example, most of ideas from DuckDB, ClickHouse, Vertica or Azure can make an array a more complete data type.

[alamb]

Thank you for bringing this up @izveigor -- I think in general, the ability to handle structured data (Lists/Arrays and Structs) is a very important feature for DataFusion as such structured types are more and more used in analytic processing scenarios.

I would also agree that we do not have a coherent design / plan for what behavior is desired. Instead we have what has emerged as people try to use it. The emergent list is #2326

Don't you think that copying behavior PostgreSQL is not a right approach to the formation of array functions?

I think there is significant value in copying the behavior of some existing system, rather than inventing new behavior, even if that new behavior is better in some ways. Following an existing system is valuable so that new users do not have to learn a substantially new dialect and lowers the barrier to entry and the cost to DataFusion to define the new features

As you have pointed out, DataFusion tries to follow postgres by default, though in some it has adopted Spark's semantics (e.g. the handling of Decimal)

Array contains the objects different data types;

I don't think this is compatible with Arrow's List type -- all the elements need to be the same type (though those types can be nested)

Thus, what I would recommend is:

1. Agree that in DataFusion ARRAY will be represented by ListArray
2. Pick a system that has reasonable ARRAY semantics and propose implementing that set of features in DataFusion

I honestly don't have the background / experience in ARRAYs in SQL to know what is the best set of features.

[izveigor]

Okay, I'll try to write a complete concept based on best practices over the weekend. I still consider such databases as the main standards, such as ClickHouse and DuckDB.

[alamb]

I still consider such databases as the main standards, such as ClickHouse and DuckDB.

I think either of those databases are good candidates for what "modern support for structured types" looks like : 👍

[izveigor]

@alamb Updated a new version. I wonder if you have time to evaluate it.

[alamb]

I will review it carefully over the next few days -- thank you @izveigor

[alamb]

Hi @izveigor -- I read through the description again -- while I would not say I followed everything what I did made sense to me. Thank you for writing it.

I think the biggest thing that is unclear to me is what are you proposing.

Is it the current (postgres based) set of functions / operators for working with ARRAYs? Is it a combination of the current set of functions as well as some addition functions (based on what is offered by DuckDb/Clickhouse?

Or perhaps you mean this document to serve as the intellectual foundation for a coherent design for List support in DataFusion and not really a change at all.

BTW I have a blog post in the works about the various types of structured arrays supported by Arrow (ListArray, StructArray, MapArray) that can hopefully help provide some more background for this discussion too.

[izveigor]

Hello @alamb!
Thank you for reading my article.

I'll answer your questions:

1. My main idea is not to pick a specific implementation.
   I think every implementation of an array in any database matters to us, and from experience we can conclude that each of them has its own unique ecosystem.
   Therefore, if answering your first question, I can say that the implementation that I want to propose is a combination of databases such as PostgreSQL, DuckDB, ClickHouse and some own functions.

About own functions. As I said above, any of the above bases has its own characteristics.
For instance, here are some advantages that I have chosen from the databases I reviewed.

1. PostgreSQL - good work with dimensions;
2. Azure DataBricks - the usual library for working with arrays;
3. DuckDB - large number of functions with work with arrays;
4. ClickHouse - great support for lambda expressions;

What in my opinion are the advantages system:

1. User can read, modify, insert or delete any data in array that he needs. (make the elements of the array maximally adapted to any user request);
2. Support all aggregate functions for array (Important to save vectorization and SIMD for speed);
3. Allow user to use set language;

P.S. My concept does not mean the destruction of all the work done by DataFusion developers.
(all functions and other implementation according to my concept remain the same, except of the function trim_array (it would be replaced by array_slice)).

2. According to my concept, most of functions should be implemented.
   However, it is important to observe the law of the impermanence of matter, so some aspects can be changed.

In the end, I would like to add that these are just mu thoughts. If developers or users do not like some aspects, then I can edit or remove them.

[alamb]

It seems very plausible to me @izveigor -- thank you for putting the time in to it.

Also I would definitely encourage you to report usability issues or potential functionality to add back upstream as you work with ListArray. Whenever we have done a feature in DataFusion and pushed learnings up to arrow I think both projects have benefitted.

[ozankabak]

Thanks for this @izveigor. I found your syntax summary and the comparison matrix very useful. I think we should have an array subpage in Datafusion docs that presents our syntax along with your comparison matrix -- I'm sure others will find it useful too.

[izveigor]

Hello, @ozankabak!
Thank you for appreciating my work, it means a lot to me!
The idea is really good. I think I will soon adapt the article for documentation.