Removing ak.sort for Records and RecordArray in v2

[ioanaif]

The motivation behind removing the sorting facility for Records and RecordArray lays in the fact that we do not have any order defined for records. Thus, sorting across record boundaries destroys the identities of those records. Consider the following example:

>>> array = ak.Array([{"x": 3, "y": 1.1}, {"x": 1, "y": 3.3}, {"x": 2, "y": 2.2}])
>>> sorted_array = ak.sort(array)
>>> array.tolist()
[{'x': 3, 'y': 1.1}, {'x': 1, 'y': 3.3}, {'x': 2, 'y': 2.2}]
>>> sorted_array.tolist()
{'x': [1, 2, 3], 'y': [1.1, 2.2, 3.3]}

Do we want to keep this in v2? I'll vote no.

@jpivarski

[jpivarski]

Including everyone who was involved on an issue or PR about sorting:

• @ianna
• @agoose77
• @nsmith-
• @yimuchen (Reduction to unique elements #1104 and awkward.argsort is wrong for arrays with dimensions > 2 #506)
• @sterbini (support 'datetime64' and 'timedelta64' types #835)
• @drahnreb (also support 'datetime64' and 'timedelta64' types #835)
• @jrueb (ak.argsort returns floats #763 and Segmentation fault from argsort and sort #686)
• @gordonwatts (argsort fails with RunTimeError when processing awkward array #523)

Anyone who wants to keep the v1 record-sorting rule in v2, please speak up!

It's a bit non-intuitive, as you can see from @ioanaif's example (above). By making ak.sort(record_array) and ak.argsort(record_array) be TypeErrors, we'd have the freedom thereafter to define a more logical sorting rule. (It's always easier to add a behavior to what is an error-state than to change a behavior.)

This affects v2 and not v1—it would make the refusal to sort records be an API-changing change between v1 and v2.

[agoose77]

@jpivarski this is maybe offtopic, but would it be in future scope to add a __key__ behaviour to records, so that they have a defined ordering?

[jpivarski]

In Python, key is a callable; Awkward parameters have to be JSON-serializable. So if the __record_sort_fields__ is an ordered list of field names to use for sorting, then maybe.

It wouldn't be super-necessary, though. You can change a record's field order with a slice, sort it lexicographically by the field order, and then restore the original field order on the sorted output.

>>> original = ak._v2.Array([
...     [{"x": 1, "y": 1.1, "z": "one"}, {"x": 2, "y": 2.2, "z": "two"}],
...     [],
...     [{"x": 3, "y": 3.3, "z": "three"}],
... ])

>>> original.show(type=True)
type: 3 * var * {
    x: int64,
    y: float64,
    z: string
}
[[{x: 1, y: 1.1, z: 'one'}, {x: 2, y: 2.2, z: 'two'}],
 [],
 [{x: 3, y: 3.3, z: 'three'}]]

>>> reordered = original[["z", "x", "y"]]
>>> reordered.show(type=True)
type: 3 * var * {
    z: string,
    x: int64,
    y: float64
}
[[{z: 'one', x: 1, y: 1.1}, {z: 'two', x: 2, y: 2.2}],
 [],
 [{z: 'three', x: 3, y: 3.3}]]

So one would just need a lexicographical sort to be defined to get many others.

If you meant __key__ to provide an arbitrary callable (like Python), a better fit to the way Awkward Array does things would be to use argsort on computed items and then apply the resulting integer array to the record array as a slice.

[agoose77]

Your suggestion to re-order the fields raises an interesting question for me — is the field ordering in a RecordArray a meaningful part of its type? I believe the answer is currently "no": the JSON representation of the form is unordered (by definition), and the type object performs unordered comparison. As such, it feels slightly awkward if we rely on field ordering for a particular feature (sorting), but do not preserve it elsewhere (well, we might preserve it, but any reasonable JSON-JSON transform could destroy the ordering).

As such, my original thought process was to have __key__ be a sequence of strings that denotes the sorting order, mapping each record to a key tuple. Unlike your proposal, this would enable sorting on an opt-in basis. One absolutely could do this already with argsort, e.g.

def sort_records(array, keys, axis=-1):
    ordered = array
    for key in reversed(keys):
        ordered = ordered[ak.argsort(ordered[key], axis=axis, stable=True)]
    return ordered

but it's a bit clunky. I don't know enough about the wider use cases for ordering a record, but I imagine there's a fairly strong case to be made for it.

One thing that I don't like about __key__ being an array parameter is that it adds an extra step for users to construct valid arrays. At the moment, users can construct vector arrays using ak.with_name or the vector constructors. If it made sense to define a sorting order for vectors (it doesn't), then users would need to use the vector constructors to ensure that they don't forget to call ak.with_ordering (terrible name).

Equally, we don't want it to be a behavior class attribute, because we want this ordering to be found even when the record is contained within another record.

So, if not a __key__ parameter, maybe a new ak.behavior overload? But, I'm getting ahead of myself - I don't have a demonstrable need for this myself.

[agoose77]

Thinking about this again, I think we would benefit from implementing an Awkward equivalent to https://numpy.org/doc/stable/reference/generated/numpy.lexsort.html. Perhaps we could even overload it, as we could detect tuple-arrays and use their ordering.

I'm still thinking we probably need to handle non-tuple records with a specified order. The form that we translate to/from JSON does not allow us to order the parameters, so we cannot rely on the ordering as it might not round-trip. I don't know whether we need to "fix" that with a schema evolution, or whether we specify that the order is not guaranteed. I quite like the idea that the order is not given for a record.

I propose we change the sorting behaviour to be lexicographic, rather than make it an error. I think most users would expect the sorting algorithm to preserve the atomicity of records. We've already established that the existing behaviour is wrong (unexpected), so I think the next step is to make it do what we expect. I realise this is a silent breaking change for some. Maybe we add a short-lived allow_records to allow users to opt-in to the correct behaviour? In future, that parameter will be required to be True if passed at all, before finally being removed as redundant. We can specify in the roadmap the version / date at which this flag must be passed as True or ignored.

As an aside @jpivarski have there been any thoughts as to versioning our form schema (probably just a monotonic increasing number) for backwards compatibility?

[jpivarski]

I think specifying a sort order for all of the data types is a good idea, and we can make it exactly the same as Python's sort order for lists and dicts of equal type. (Except—Awkward record fields have a prescribed order that is not necessarily alphabetical for the fields. We want the sort order to depend on Awkward field order because Awkward field order can easily be changed, and that would give someone a lot of flexibility in sorting something they way they want it, even before bringing in argsort.)

However, I think the process of introducing a sort order is a big project, since record fields can have any type and we therefore have to have an ordering on all types, not just records. (Maybe a subproject could be to define a sort order for records of only numeric types, and while that's a major use-case, it feels arbitrary. Some objects representing particles would be sortable, but give them a list of links to associated jets and then they become non-sortable?)

Also, the list sorting is going to mix in strange ways with NumPy-style sorting:

>>> sorted([[4, 2, 6], [1, 5, 3]])
[[1, 5, 3], [4, 2, 6]]
>>> np.sort([[4, 2, 6], [1, 5, 3]], axis=0)
array([[1, 2, 3],
       [4, 5, 6]])

Lexicographic sorting treats objects like lists and records as unbreakable objects and rearranges them according to an order defined by __lt__. NumPy sorting moves numbers between objects. It makes sense if you're thinking of the data as a table.

So if lexicographic sorting of records needs some kind of order defined for lists because the fields may be lists, how do we harmonize that list-ordering with NumPy-style sorting? This is similar to the problem we have with Awkward-style (left-to-right) broadcasting and NumPy-style (right-to-left) broadcasting: agreement with NumPy is in conflict with intuition about objects.

Whatever we do to solve these problems in the long-term, I think we should prevent sorting of records in the short-term. Currently, something like NumPy-style sorting is applied to records, which is wildly at odds with intuition about objects, and it's causing trouble. We do eventually want to change the behavior, but I don't think we can do that on a short enough timescale (the v2 release in December). Excluding the non-intuitive behavior at a major release boundary opens the possibility of adding better behavior at any time, not necessarily a major release boundary, since error state → new behavior is not considered an API breaking change, whereas old behavior → new behavior is.

As an aside @jpivarski have there been any thoughts as to versioning our form schema (probably just a monotonic increasing number) for backwards compatibility?

By "form schema," do you mean the JSON representation of Forms? These aren't versioned; that JSON representation is fixed since 1.1.0 with no updates planned, since it's necessary for reading old data (e.g. in pickle, but in other formats, too). I don't see a reason why it would have to evolve, since it's only concerned with the physical layer (how to turn bytes into ak.Arrays); new behaviors and functionality go into the parameters, which are free-form. How arrays behave (as opposed to what data they contain) are determined by the version of the awkward package and what classes you have loaded into ak.behaviors (and therefore the versions of vector or coffea, or whatever is defining those behaviors).

(Arrow did a similar thing: they fixed the physical layer at 1.0 and won't be changing it. All new features are in metadata, which is like our parameters. Similarly, JSON was specified in 2002 and hasn't been modified since—you can't express new physical types with it, but you can interpret those structures in various ways.)

[jpivarski]

Note: sorting of records is also being discussed in #1361.