YQL-13710 partial support for presort

ref:882b0e78c6b5fe9ca71d2d1cfd5ca40f10ff377a

3 files changed, 122 insertions, 1 deletions

diff --git a/ydb/library/yql/minikql/mkql_node.cpp b/ydb/library/yql/minikql/mkql_node.cpp
index 37063811034..23f0397bb9c 100644
--- a/ydb/library/yql/minikql/mkql_node.cpp
+++ b/ydb/library/yql/minikql/mkql_node.cpp
@@ -348,6 +348,10 @@ void TTypeType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TTypeType::CalculatePresortSupport() {
+    return false;
+}
+
 TDataType::TDataType(NUdf::TDataTypeId schemeType, const TTypeEnvironment& env)
     : TType(EKind::Data, env.GetTypeOfType())
     , SchemeType(schemeType)
@@ -387,6 +391,10 @@ void TDataType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TDataType::CalculatePresortSupport() {
+    return true;
+}
+
 TDataDecimalType::TDataDecimalType(ui8 precision, ui8 scale, const TTypeEnvironment& env)
     : TDataType(NUdf::TDataType<NUdf::TDecimal>::Id, env), Precision(precision), Scale(scale)
 {
@@ -496,6 +504,23 @@ void TPgType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+static THashSet<TStringBuf> PG_SUPPORTED_PRESORT = {
+    "bool",
+    "int2",
+    "int4",
+    "int8",
+    "float4",
+    "float8",
+    "bytea",
+    "varchar",
+    "text",
+    "cstring"
+};
+
+bool TPgType::CalculatePresortSupport() {
+    return PG_SUPPORTED_PRESORT.contains(GetName());
+}
+
 const TString& TPgType::GetName() const {
     return NYql::NPg::LookupType(TypeId).Name;
 }
@@ -624,6 +649,16 @@ void TStructType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TStructType::CalculatePresortSupport() {
+    for (ui32 i = 0; i < MembersCount; ++i) {
+        if (!Members[i].second->IsPresortSupported()) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
 ui32 TStructType::GetMemberIndex(const TStringBuf& name) const {
     auto index = FindMemberIndex(name);
     if (index) {
@@ -798,6 +833,10 @@ void TListType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TListType::CalculatePresortSupport() {
+    return GetItemType()->IsPresortSupported();
+}
+
 TListLiteral::TListLiteral(TRuntimeNode* items, ui32 count, TListType* type, const TTypeEnvironment& env, bool validate)
     : TNode(type)
     , Items(items)
@@ -969,6 +1008,10 @@ void TStreamType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TStreamType::CalculatePresortSupport() {
+    return false;
+}
+
 TFlowType::TFlowType(TType* itemType, const TTypeEnvironment& env, bool validate)
     : TType(EKind::Flow, env.GetTypeOfType())
     , Data(itemType)
@@ -1009,6 +1052,10 @@ void TFlowType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TFlowType::CalculatePresortSupport() {
+    return false;
+}
+
 TOptionalType::TOptionalType(TType* itemType, const TTypeEnvironment& env, bool validate)
     : TType(EKind::Optional, env.GetTypeOfType())
     , Data(itemType)
@@ -1050,6 +1097,10 @@ void TOptionalType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TOptionalType::CalculatePresortSupport() {
+    return GetItemType()->IsPresortSupported();
+}
+
 TTaggedType::TTaggedType(TType* baseType, TInternName tag, const TTypeEnvironment& env)
     : TType(EKind::Tagged, env.GetTypeOfType())
     , BaseType(baseType)
@@ -1090,6 +1141,10 @@ void TTaggedType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TTaggedType::CalculatePresortSupport() {
+    return GetBaseType()->IsPresortSupported();
+}
+
 TOptionalLiteral::TOptionalLiteral(TOptionalType* type, bool validate)
     : TNode(type)
 {
@@ -1215,6 +1270,10 @@ void TDictType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TDictType::CalculatePresortSupport() {
+    return KeyType->IsPresortSupported() && PayloadType->IsPresortSupported();
+}
+
 TDictType::TDictType(TType* keyType, TType* payloadType, const TTypeEnvironment& env, bool validate)
     : TType(EKind::Dict, env.GetTypeOfType())
     , KeyType(keyType)
@@ -1536,6 +1595,10 @@ void TCallableType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TCallableType::CalculatePresortSupport() {
+    return false;
+}
+
 TCallable::TCallable(ui32 inputsCount, TRuntimeNode* inputs, TCallableType* type, bool validate)
     : TNode(type)
     , InputsCount(inputsCount)
@@ -1776,6 +1839,10 @@ void TAnyType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TAnyType::CalculatePresortSupport() {
+    return false;
+}
+
 TAnyType* TAnyType::Create(TTypeType* type, const TTypeEnvironment& env) {
     return ::new(env.Allocate<TAnyType>()) TAnyType(type);
 }
@@ -1927,6 +1994,16 @@ void TTupleType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TTupleType::CalculatePresortSupport() {
+    for (ui32 i = 0; i < ElementsCount; ++i) {
+        if (!Elements[i]->IsPresortSupported()) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
 TTupleLiteral::TTupleLiteral(TRuntimeNode* values, TTupleType* type, bool validate)
     : TNode(type)
     , Values(values)
@@ -2057,6 +2134,10 @@ void TResourceType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TResourceType::CalculatePresortSupport() {
+    return false;
+}
+
 TResourceType* TResourceType::Create(const TStringBuf& tag, const TTypeEnvironment& env) {
     return ::new(env.Allocate<TResourceType>()) TResourceType(env.GetTypeOfType(), env.InternName(tag));
 }
@@ -2111,6 +2192,10 @@ void TVariantType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TVariantType::CalculatePresortSupport() {
+    return GetUnderlyingType()->IsPresortSupported();
+}
+
 TVariantLiteral* TVariantLiteral::Create(TRuntimeNode item, ui32 index, TVariantType* type, const TTypeEnvironment& env) {
     return ::new(env.Allocate<TVariantLiteral>()) TVariantLiteral(item, index, type);
 }
@@ -2219,6 +2304,10 @@ void TBlockType::DoFreeze(const TTypeEnvironment& env) {
     Y_UNUSED(env);
 }
 
+bool TBlockType::CalculatePresortSupport() {
+    return false;
+}
+
 bool IsNumericType(NUdf::TDataTypeId typeId) {
     auto slot = NUdf::FindDataSlot(typeId);
     return slot && NUdf::GetDataTypeInfo(*slot).Features & NUdf::NumericType;
diff --git a/ydb/library/yql/minikql/mkql_node.h b/ydb/library/yql/minikql/mkql_node.h
index e44307f9429..20a25acb599 100644
--- a/ydb/library/yql/minikql/mkql_node.h
+++ b/ydb/library/yql/minikql/mkql_node.h
@@ -177,6 +177,13 @@ public:
     void UpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* CloneOnCallableWrite(const TTypeEnvironment& env) const;
     void Freeze(const TTypeEnvironment& env);
+    bool IsPresortSupported() {
+        if (!SupportsPresort) {
+            SupportsPresort = CalculatePresortSupport();
+        }
+
+        return *SupportsPresort;
+    }
 
 protected:
     TType(EKind kind, TTypeType* type);
@@ -186,8 +193,11 @@ protected:
     {
     }
 
+    virtual bool CalculatePresortSupport() = 0;
+
 private:
     const EKind Kind;
+    TMaybe<bool> SupportsPresort; // transient
 };
 
 class TTypeType : public TType {
@@ -209,6 +219,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
     static TTypeType* Create(const TTypeEnvironment& env);
 };
@@ -232,6 +243,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
     static TSingularType<SingularKind>* Create(TTypeType* type, const TTypeEnvironment& env);
 };
@@ -540,6 +552,7 @@ protected:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     const NUdf::TDataTypeId SchemeType;
@@ -609,6 +622,7 @@ protected:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     const ui32 TypeId;
@@ -677,6 +691,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     ui32 MembersCount;
@@ -738,6 +753,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* Data;
@@ -796,6 +812,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* Data;
@@ -822,6 +839,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* Data;
@@ -848,6 +866,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* Data;
@@ -913,6 +932,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* KeyType;
@@ -1008,6 +1028,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     bool IsMergeDisabled0;
@@ -1111,6 +1132,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 };
 
 class TAny : public TNode {
@@ -1172,6 +1194,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     ui32 ElementsCount;
@@ -1237,6 +1260,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TInternName const Tag;
@@ -1271,6 +1295,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* BaseType;
@@ -1315,6 +1340,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* Data;
@@ -1383,6 +1409,7 @@ private:
     void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
     TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
     void DoFreeze(const TTypeEnvironment& env);
+    bool CalculatePresortSupport() override;
 
 private:
     TType* ItemType;
@@ -1447,6 +1474,11 @@ void TSingularType<SingularKind>::DoFreeze(const TTypeEnvironment& env) {
 }
 
 template <TType::EKind SingularKind>
+bool TSingularType<SingularKind>::CalculatePresortSupport() {
+    return true;
+}
+
+template <TType::EKind SingularKind>
 TSingular<SingularKind>* TSingular<SingularKind>::Create(const TTypeEnvironment& env) {
     return ::new(env.Allocate<TSingular<SingularKind>>()) TSingular<SingularKind>(env);
 }
diff --git a/ydb/library/yql/providers/dq/actors/proto_builder.cpp b/ydb/library/yql/providers/dq/actors/proto_builder.cpp
index e4b16403c3b..e1ae7d369c5 100644
--- a/ydb/library/yql/providers/dq/actors/proto_builder.cpp
+++ b/ydb/library/yql/providers/dq/actors/proto_builder.cpp
@@ -59,7 +59,7 @@ NDqProto::EDataTransportVersion GetTransportVersion(const NYql::NDqProto::TData&
 TProtoBuilder::TProtoBuilder(const TString& type, const TVector<TString>& columns)
     : Alloc()
     , TypeEnv(Alloc)
-    , ResultType(reinterpret_cast<TType*>(DeserializeNode(type, TypeEnv)))
+    , ResultType(static_cast<TType*>(DeserializeNode(type, TypeEnv)))
     , ColumnOrder(BuildColumnOrder(columns, ResultType))
 {
     Alloc.Release();