Input type for min/max/min_by/max_by should be restricted to "orderable" types

[mbasmanova]

Bug description

In Presto, input to min/max is restricted to orderable types. For example, MAP type is not orderable. Velox currently allows MAP inputs.

com.facebook.presto.sql.analyzer.SemanticException: line 1:28: 
Unexpected parameters (map(real,varchar)) for function max. Expected: max(E) E:orderable, max(E, bigint) E:orderable

This issue is similar to #6712 and applies to all scalar and aggregate functions that sort inputs.

This issue was discovered by running AggregationFuzzer with Presto as source of truth.

CC: @laithsakka @duanmeng

System information

n/a

Relevant logs

No response

[duanmeng]

Would be better to do this check and restriction in the analyzer layer?
Or remove the unorderable type from registration (through code review or add an orderable flag in the type?

[mbasmanova]

Fixing this issue requires multiple changes.

• Extend Velox Type class to add isOrderable() and isComparable() methods.
• Extend Function Signature APIs to allow restricting argument types to orderable or comparable.
• Fix array_sort implementation to reject non-orderable input types.
• Modify AggregationFuzzer and ExpressionFuzzer to take 'orderable' and 'comparable' restrictions on argument types into account when generating expressions.

For example, this is how signature for min/max functions may look like:

  signatures.push_back(exec::AggregateFunctionSignatureBuilder()
                           .orderableTypeVariable("T")
                           .returnType("T")
                           .intermediateType("T")
                           .argumentType("T")
                           .build());

For example, this is how signature for array_sort may look like:

      exec::FunctionSignatureBuilder()
          .orderableTypeVariable("T")
          .returnType("array(T)")
          .argumentType("array(T)")
          .build(),

[duanmeng]

Extend Velox Type class to add isOrderable() and isComparable() methods.

@mbasmanova Can you help explain the difference between "orderable" and "comparable", I used to think "comparable" implies "orderable".

[mbasmanova]

@duanmeng For example, MAP type values are comparable as long as both key and value types are comparable, but MAP type values are not orderable. Comparison allows for a == b to return true, false, or NULL, but sorting requires that a < b comparison never returns NULL.

presto> select map(array[1, 2], array[10, null]) = map(array[1, 2], array[10, null]);
 _col0
-------
 NULL
(1 row)

presto> select map(array[1, 2], array[10, 20]) = map(array[1, 2], array[10, 20]);
 _col0
-------
 true
(1 row)

[duanmeng]

@duanmeng For example, MAP type values are comparable as long as both key and value types are comparable, but MAP type values are not orderable. Comparison allows for a == b to return true, false, or NULL, but sorting requires that a < b comparison never returns NULL.

@mbasmanova Got it, thanks. Could you assign this to me, I will break it into multiple tasks to track.

[mbasmanova]

@duanmeng Thank you for helping with this.

[duanmeng]

• Extend Velox Type class to add isOrderable() and isComparable() methods. Add isOrderable and isComparable for Type #6770
• Allow marking arguments as orderable or comparable in the function signature Allow restricting arguments as orderable or comparable in the function signature #6906
• Fix array_sort implementation to reject non-orderable input types.
• Fix min/max implementation to reject non-orderable input types.
• Modify AggregationFuzzer and ExpressionFuzzer to take 'orderable' and 'comparable' restrictions on argument types into account when generating expressions.

cc @mbasmanova

[duanmeng]

@mbasmanova I used to add the constantArgumentType in this PR Allow marking arguments as constant in the function signature, and modify the fuzzer in the following PR Add support for constant function arguments to Expression Fuzzer.

• Extend Function Signature APIs to allow restricting argument types to orderable or comparable.
• Modify AggregationFuzzer and ExpressionFuzzer to take 'orderable' and 'comparable' restrictions on argument types

Could these two requirements use the same solution?

Update: It should be similar to SignatureVariable.knownTypesOnly_

[mbasmanova]

@duanmeng I'm not sure I understand the question, but, yes this work would be similar to prior work on adding constantArgumentType and knownType.

[mbasmanova]

@duanmeng Meng, are you still interested in working on this? Anything blocking?

[duanmeng]

@mbasmanova Yes, left the one task "min/max implementation to reject non-orderable input types", I will file a PR to resolve it.