Pg Optimizer Wrapper

42 files changed, 915 insertions, 5 deletions

diff --git a/ydb/library/yql/core/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/core/CMakeLists.darwin-x86_64.txt
index 08c0d7bbdb..0ed421225f 100644
--- a/ydb/library/yql/core/CMakeLists.darwin-x86_64.txt
+++ b/ydb/library/yql/core/CMakeLists.darwin-x86_64.txt
@@ -7,6 +7,7 @@
 
 
 add_subdirectory(arrow_kernels)
+add_subdirectory(cbo)
 add_subdirectory(common_opt)
 add_subdirectory(credentials)
 add_subdirectory(expr_nodes)
diff --git a/ydb/library/yql/core/CMakeLists.linux-aarch64.txt b/ydb/library/yql/core/CMakeLists.linux-aarch64.txt
index f0ee199095..393631c18f 100644
--- a/ydb/library/yql/core/CMakeLists.linux-aarch64.txt
+++ b/ydb/library/yql/core/CMakeLists.linux-aarch64.txt
@@ -7,6 +7,7 @@
 
 
 add_subdirectory(arrow_kernels)
+add_subdirectory(cbo)
 add_subdirectory(common_opt)
 add_subdirectory(credentials)
 add_subdirectory(expr_nodes)
diff --git a/ydb/library/yql/core/CMakeLists.linux-x86_64.txt b/ydb/library/yql/core/CMakeLists.linux-x86_64.txt
index f0ee199095..393631c18f 100644
--- a/ydb/library/yql/core/CMakeLists.linux-x86_64.txt
+++ b/ydb/library/yql/core/CMakeLists.linux-x86_64.txt
@@ -7,6 +7,7 @@
 
 
 add_subdirectory(arrow_kernels)
+add_subdirectory(cbo)
 add_subdirectory(common_opt)
 add_subdirectory(credentials)
 add_subdirectory(expr_nodes)
diff --git a/ydb/library/yql/core/CMakeLists.windows-x86_64.txt b/ydb/library/yql/core/CMakeLists.windows-x86_64.txt
index 08c0d7bbdb..0ed421225f 100644
--- a/ydb/library/yql/core/CMakeLists.windows-x86_64.txt
+++ b/ydb/library/yql/core/CMakeLists.windows-x86_64.txt
@@ -7,6 +7,7 @@
 
 
 add_subdirectory(arrow_kernels)
+add_subdirectory(cbo)
 add_subdirectory(common_opt)
 add_subdirectory(credentials)
 add_subdirectory(expr_nodes)
diff --git a/ydb/library/yql/core/cbo/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/core/cbo/CMakeLists.darwin-x86_64.txt
new file mode 100644
index 0000000000..32062084c6
--- /dev/null
+++ b/ydb/library/yql/core/cbo/CMakeLists.darwin-x86_64.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(yql-core-cbo)
+target_link_libraries(yql-core-cbo PUBLIC
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(yql-core-cbo PRIVATE
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/core/cbo/cbo_optimizer.cpp
+)
diff --git a/ydb/library/yql/core/cbo/CMakeLists.linux-aarch64.txt b/ydb/library/yql/core/cbo/CMakeLists.linux-aarch64.txt
new file mode 100644
index 0000000000..e1eef0c49f
--- /dev/null
+++ b/ydb/library/yql/core/cbo/CMakeLists.linux-aarch64.txt
@@ -0,0 +1,18 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(yql-core-cbo)
+target_link_libraries(yql-core-cbo PUBLIC
+  contrib-libs-linux-headers
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(yql-core-cbo PRIVATE
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/core/cbo/cbo_optimizer.cpp
+)
diff --git a/ydb/library/yql/core/cbo/CMakeLists.linux-x86_64.txt b/ydb/library/yql/core/cbo/CMakeLists.linux-x86_64.txt
new file mode 100644
index 0000000000..e1eef0c49f
--- /dev/null
+++ b/ydb/library/yql/core/cbo/CMakeLists.linux-x86_64.txt
@@ -0,0 +1,18 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(yql-core-cbo)
+target_link_libraries(yql-core-cbo PUBLIC
+  contrib-libs-linux-headers
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(yql-core-cbo PRIVATE
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/core/cbo/cbo_optimizer.cpp
+)
diff --git a/ydb/library/yql/core/cbo/CMakeLists.txt b/ydb/library/yql/core/cbo/CMakeLists.txt
new file mode 100644
index 0000000000..f8b31df0c1
--- /dev/null
+++ b/ydb/library/yql/core/cbo/CMakeLists.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+if (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "aarch64" AND NOT HAVE_CUDA)
+  include(CMakeLists.linux-aarch64.txt)
+elseif (CMAKE_SYSTEM_NAME STREQUAL "Darwin" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64")
+  include(CMakeLists.darwin-x86_64.txt)
+elseif (WIN32 AND CMAKE_SYSTEM_PROCESSOR STREQUAL "AMD64" AND NOT HAVE_CUDA)
+  include(CMakeLists.windows-x86_64.txt)
+elseif (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64" AND NOT HAVE_CUDA)
+  include(CMakeLists.linux-x86_64.txt)
+endif()
diff --git a/ydb/library/yql/core/cbo/CMakeLists.windows-x86_64.txt b/ydb/library/yql/core/cbo/CMakeLists.windows-x86_64.txt
new file mode 100644
index 0000000000..32062084c6
--- /dev/null
+++ b/ydb/library/yql/core/cbo/CMakeLists.windows-x86_64.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(yql-core-cbo)
+target_link_libraries(yql-core-cbo PUBLIC
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(yql-core-cbo PRIVATE
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/core/cbo/cbo_optimizer.cpp
+)
diff --git a/ydb/library/yql/core/cbo/cbo_optimizer.cpp b/ydb/library/yql/core/cbo/cbo_optimizer.cpp
new file mode 100644
index 0000000000..7ed787fe4d
--- /dev/null
+++ b/ydb/library/yql/core/cbo/cbo_optimizer.cpp
@@ -0,0 +1,98 @@
+#include "cbo_optimizer.h"
+
+#include <array>
+
+#include <util/string/builder.h>
+
+namespace NYql {
+
+namespace {
+
+std::array<TStringBuf,6> Prefixes = {
+    "",
+    " ",
+    "  ",
+    "   ",
+    "    ",
+    "     "
+};
+
+TStringBuf Prefix(int level) {
+    return level < (int)Prefixes.size()
+        ? Prefixes[level]
+        : Prefixes.back();
+}
+
+void PrettyPrintVar(TStringBuilder& b, const IOptimizer::TOutput& output, IOptimizer::TVarId varId) {
+    const auto& [relno, varno] = varId;
+    auto varName = output.Input
+        ? output.Input->Rels[relno-1].TargetVars[varno-1].name
+        : '\0';
+    if (!varName) {
+        b << "(" << relno << "," << varno << ")";
+    } else {
+        b << varName;
+    }
+}
+
+void PrettyPrintNode(int level, TStringBuilder& b, const IOptimizer::TOutput& output, int id) {
+    TStringBuf prefix = Prefix(level);
+    const auto& node = output.Nodes[id];
+    switch (node.Mode) {
+        case IOptimizer::EJoinType::UNKNOWN: b << prefix <<  " Node\n"; break;
+        case IOptimizer::EJoinType::INNER: b << prefix <<  " Inner Join\n"; break;
+        default: b << prefix <<  " Unknown\n"; break;
+    }
+    switch (node.Strategy) {
+        case IOptimizer::EJoinStrategy::HASH: b << prefix <<  " Hash Strategy\n"; break;
+        case IOptimizer::EJoinStrategy::LOOP: b << prefix <<  " Loop Strategy\n"; break;
+        default: break;
+    }
+    if (!node.Rels.empty())
+    {
+        b << prefix << " Rels: [";
+        for (int i = 0; i < (int)node.Rels.size()-1; i++) {
+            b << node.Rels[i] << ",";
+        }
+        b << node.Rels.back();
+        b << "]\n";
+    }
+
+    {
+        auto isEmpty = [](IOptimizer::TVarId id) -> bool {
+            auto& [a, b] = id;
+            return a<=0 || b<=0;
+        };
+
+        if (!isEmpty(node.LeftVar) && !isEmpty(node.RightVar)) {
+            b << prefix << " Op: ";
+            PrettyPrintVar(b, output, node.LeftVar);
+            b << " = ";
+            PrettyPrintVar(b, output, node.RightVar);
+            b << "\n";
+        }
+    }
+
+    if (node.Outer != -1) {
+        b << prefix << " {\n";
+        PrettyPrintNode(level+1, b, output, node.Outer);
+        b << prefix << " }\n";
+    }
+    if (node.Inner != -1) {
+        b << prefix << " {\n";
+        PrettyPrintNode(level+1, b, output, node.Inner);
+        b << prefix << " }\n";
+    }
+}
+
+} // namespace
+
+TString IOptimizer::TOutput::ToString() const {
+    TStringBuilder b;
+    b << "{\n";
+    PrettyPrintNode(0, b, *this, 0);
+    b << "}\n";
+    return b;
+}
+
+} // namespace NYql
diff --git a/ydb/library/yql/core/cbo/cbo_optimizer.h b/ydb/library/yql/core/cbo/cbo_optimizer.h
new file mode 100644
index 0000000000..fb1657c1d7
--- /dev/null
+++ b/ydb/library/yql/core/cbo/cbo_optimizer.h
@@ -0,0 +1,66 @@
+#pragma once
+
+#include <util/generic/vector.h>
+
+#include <unordered_map>
+#include <map>
+
+namespace NYql {
+
+struct IOptimizer {
+    using TVarId = std::tuple<int, int>;
+
+    struct TVar {
+        char name = 0; // debug name: 'a', 'b', 'c', ...
+    };
+
+    struct TRel {
+        double rows = 0;
+        double total_cost = 0;
+
+        std::vector<TVar> TargetVars;
+    };
+
+    struct TEq {
+        std::vector<TVarId> Vars;
+    };
+
+    struct TInput {
+        std::vector<TRel> Rels;
+        std::vector<TEq> EqClasses;
+    };
+
+    enum class EJoinType {
+        UNKNOWN,
+        INNER
+    };
+
+    enum class EJoinStrategy {
+        UNKNOWN,
+        HASH,
+        LOOP
+    };
+
+    struct TJoinNode {
+        EJoinType Mode = EJoinType::UNKNOWN;
+        EJoinStrategy Strategy = EJoinStrategy::UNKNOWN;
+        // only a = b supported yet
+        TVarId LeftVar = {};
+        TVarId RightVar = {};
+        std::vector<int> Rels = {};
+        int Outer = -1; // index in Nodes
+        int Inner = -1; // index in Nodes
+    };
+
+    struct TOutput {
+        std::vector<TJoinNode> Nodes;
+        TInput* Input = nullptr;
+
+        TString ToString() const;
+    };
+
+    virtual ~IOptimizer() = default;
+    virtual TOutput JoinSearch() = 0;
+};
+
+} // namespace NYql
diff --git a/ydb/library/yql/core/cbo/ya.make b/ydb/library/yql/core/cbo/ya.make
new file mode 100644
index 0000000000..3a8fd2a503
--- /dev/null
+++ b/ydb/library/yql/core/cbo/ya.make
@@ -0,0 +1,6 @@
+LIBRARY()
+
+SRCS(cbo_optimizer.cpp)
+
+END()
+
diff --git a/ydb/library/yql/parser/pg_wrapper/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/CMakeLists.darwin-x86_64.txt
index e1466619ac..791e1ba67f 100644
--- a/ydb/library/yql/parser/pg_wrapper/CMakeLists.darwin-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/CMakeLists.darwin-x86_64.txt
@@ -142,6 +142,7 @@ target_sources(yql-parser-pg_wrapper PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.2.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.3.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/config.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42_choose.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin.c
diff --git a/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-aarch64.txt b/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-aarch64.txt
index 6cf6acebb0..ecc1f941e8 100644
--- a/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-aarch64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-aarch64.txt
@@ -141,6 +141,7 @@ target_sources(yql-parser-pg_wrapper PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.2.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.3.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/config.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin_bloom.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin_inclusion.c
diff --git a/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-x86_64.txt
index 1ed6036faa..522eef8bbd 100644
--- a/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/CMakeLists.linux-x86_64.txt
@@ -143,6 +143,7 @@ target_sources(yql-parser-pg_wrapper PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.2.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.3.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/config.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42_choose.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin.c
diff --git a/ydb/library/yql/parser/pg_wrapper/CMakeLists.windows-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/CMakeLists.windows-x86_64.txt
index 3c71a2bab7..041aac3f40 100644
--- a/ydb/library/yql/parser/pg_wrapper/CMakeLists.windows-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/CMakeLists.windows-x86_64.txt
@@ -159,6 +159,7 @@ target_sources(yql-parser-pg_wrapper PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.2.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/pg_kernels.3.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/config.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/port/pg_crc32c_sse42_choose.c
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/access/brin/brin.c
diff --git a/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp b/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
new file mode 100644
index 0000000000..57b75427da
--- /dev/null
+++ b/ydb/library/yql/parser/pg_wrapper/cost_mocks.cpp
@@ -0,0 +1,57 @@
+#include <util/system/compiler.h>
+
+#define TypeName PG_TypeName
+#define SortBy PG_SortBy
+#undef SIZEOF_SIZE_T
+
+extern "C" {
+#include "postgres.h"
+#include "optimizer/paths.h"
+#include "nodes/print.h"
+#include "utils/selfuncs.h"
+#include "utils/palloc.h"
+}
+
+#undef Min
+#undef Max
+#undef TypeName
+#undef SortBy
+
+
+extern "C" void
+add_function_cost(PlannerInfo *root, Oid funcid, Node *node,
+				  QualCost *cost)
+{
+    Y_UNUSED(root);
+    Y_UNUSED(funcid);
+    Y_UNUSED(node);
+	cost->per_tuple += 100000;
+}
+
+extern "C" bool
+op_mergejoinable(Oid opno, Oid inputtype) {
+    Y_UNUSED(opno);
+    Y_UNUSED(inputtype);
+    return false;
+}
+
+extern "C" bool
+op_hashjoinable(Oid opno, Oid inputtype) {
+    Y_UNUSED(opno);
+    Y_UNUSED(inputtype);
+    return true;
+}
+
+extern "C" RegProcedure
+get_oprjoin(Oid opno)
+{
+    Y_UNUSED(opno);
+	return 105;
+}
+
+extern "C" char
+func_volatile(Oid funcid)
+{
+    Y_UNUSED(funcid);
+    return 'i';
+}
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.darwin-x86_64.txt
index a1a2fa37d7..3346319134 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.darwin-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.darwin-x86_64.txt
@@ -17,6 +17,7 @@ target_link_libraries(parser-pg_wrapper-interface PUBLIC
   library-yql-ast
   yql-public-udf
   public-udf-arrow
+  yql-core-cbo
 )
 target_sources(parser-pg_wrapper-interface PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/interface/interface.cpp
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-aarch64.txt b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-aarch64.txt
index 6bc55e03a4..c3d59ce35c 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-aarch64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-aarch64.txt
@@ -18,6 +18,7 @@ target_link_libraries(parser-pg_wrapper-interface PUBLIC
   library-yql-ast
   yql-public-udf
   public-udf-arrow
+  yql-core-cbo
 )
 target_sources(parser-pg_wrapper-interface PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/interface/interface.cpp
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-x86_64.txt
index 6bc55e03a4..c3d59ce35c 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.linux-x86_64.txt
@@ -18,6 +18,7 @@ target_link_libraries(parser-pg_wrapper-interface PUBLIC
   library-yql-ast
   yql-public-udf
   public-udf-arrow
+  yql-core-cbo
 )
 target_sources(parser-pg_wrapper-interface PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/interface/interface.cpp
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.windows-x86_64.txt b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.windows-x86_64.txt
index a1a2fa37d7..3346319134 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.windows-x86_64.txt
+++ b/ydb/library/yql/parser/pg_wrapper/interface/CMakeLists.windows-x86_64.txt
@@ -17,6 +17,7 @@ target_link_libraries(parser-pg_wrapper-interface PUBLIC
   library-yql-ast
   yql-public-udf
   public-udf-arrow
+  yql-core-cbo
 )
 target_sources(parser-pg_wrapper-interface PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/interface/interface.cpp
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/interface.h b/ydb/library/yql/parser/pg_wrapper/interface/interface.h
index 0f5ff7bcc6..269d7ea279 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/interface.h
+++ b/ydb/library/yql/parser/pg_wrapper/interface/interface.h
@@ -10,3 +10,4 @@
 #include "parser.h"
 #include "type_desc.h"
 #include "utils.h"
+#include "optimizer.h"
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/optimizer.h b/ydb/library/yql/parser/pg_wrapper/interface/optimizer.h
new file mode 100644
index 0000000000..f73376652e
--- /dev/null
+++ b/ydb/library/yql/parser/pg_wrapper/interface/optimizer.h
@@ -0,0 +1,9 @@
+#pragma once
+
+#include <ydb/library/yql/core/cbo/cbo_optimizer.h>
+
+namespace NYql {
+
+IOptimizer* MakePgOptimizer(const IOptimizer::TInput& input, const std::function<void(const TString&)>& log = {});
+
+} // namespace NYql
diff --git a/ydb/library/yql/parser/pg_wrapper/interface/ya.make b/ydb/library/yql/parser/pg_wrapper/interface/ya.make
index 0bd4744477..a2d4b6633e 100644
--- a/ydb/library/yql/parser/pg_wrapper/interface/ya.make
+++ b/ydb/library/yql/parser/pg_wrapper/interface/ya.make
@@ -18,6 +18,7 @@ PEERDIR(
     ydb/library/yql/ast
     ydb/library/yql/public/udf
     ydb/library/yql/public/udf/arrow
+    ydb/library/yql/core/cbo
 )
 
 YQL_LAST_ABI_VERSION()
diff --git a/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/optimizer/util/plancat.c b/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/optimizer/util/plancat.c
index a2b756f7ec..54f4af2a8c 100644
--- a/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/optimizer/util/plancat.c
+++ b/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/optimizer/util/plancat.c
@@ -1964,7 +1964,7 @@ function_selectivity(PlannerInfo *root,
  * In some usages root might be NULL, too.
  */
 void
-add_function_cost(PlannerInfo *root, Oid funcid, Node *node,
+add_function_cost_original(PlannerInfo *root, Oid funcid, Node *node,
 				  QualCost *cost)
 {
 	HeapTuple	proctup;
diff --git a/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/utils/cache/lsyscache.c b/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/utils/cache/lsyscache.c
index 9c1c51e287..4f4f37337f 100644
--- a/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/utils/cache/lsyscache.c
+++ b/ydb/library/yql/parser/pg_wrapper/postgresql/src/backend/utils/cache/lsyscache.c
@@ -1354,7 +1354,7 @@ op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
  * is needed to check this --- by convention, pass the left input's data type.
  */
 bool
-op_mergejoinable(Oid opno, Oid inputtype)
+op_mergejoinable_original(Oid opno, Oid inputtype)
 {
 	bool		result = false;
 	HeapTuple	tp;
@@ -1405,7 +1405,7 @@ op_mergejoinable(Oid opno, Oid inputtype)
  * to check this --- by convention, pass the left input's data type.
  */
 bool
-op_hashjoinable(Oid opno, Oid inputtype)
+op_hashjoinable_original(Oid opno, Oid inputtype)
 {
 	bool		result = false;
 	HeapTuple	tp;
@@ -1549,7 +1549,7 @@ get_oprrest(Oid opno)
  *		Returns procedure id for computing selectivity of a join.
  */
 RegProcedure
-get_oprjoin(Oid opno)
+get_oprjoin_original(Oid opno)
 {
 	HeapTuple	tp;
 
@@ -1748,7 +1748,7 @@ func_strict(Oid funcid)
  *		Given procedure id, return the function's provolatile flag.
  */
 char
-func_volatile(Oid funcid)
+func_volatile_original(Oid funcid)
 {
 	HeapTuple	tp;
 	char		result;
diff --git a/ydb/library/yql/parser/pg_wrapper/ya.make b/ydb/library/yql/parser/pg_wrapper/ya.make
index a26caf2142..a9699205c2 100644
--- a/ydb/library/yql/parser/pg_wrapper/ya.make
+++ b/ydb/library/yql/parser/pg_wrapper/ya.make
@@ -35,6 +35,7 @@ SRCS(
     pg_kernels.2.cpp
     pg_kernels.3.cpp
     config.cpp
+    cost_mocks.cpp
 )
 
 IF (ARCH_X86_64)
diff --git a/ydb/library/yql/sql/pg/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/sql/pg/CMakeLists.darwin-x86_64.txt
index 2337fcbd45..81be7f0f17 100644
--- a/ydb/library/yql/sql/pg/CMakeLists.darwin-x86_64.txt
+++ b/ydb/library/yql/sql/pg/CMakeLists.darwin-x86_64.txt
@@ -10,6 +10,8 @@ add_subdirectory(ut)
 
 add_library(yql-sql-pg)
 target_compile_options(yql-sql-pg PRIVATE
+  -Dpalloc0=yql_palloc0
+  -Dpfree=yql_pfree
   -DUSE_CURRENT_UDF_ABI_VERSION
   $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
 )
@@ -27,5 +29,6 @@ target_link_libraries(yql-sql-pg PUBLIC
 )
 target_sources(yql-sql-pg PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/utils.cpp
 )
diff --git a/ydb/library/yql/sql/pg/CMakeLists.linux-aarch64.txt b/ydb/library/yql/sql/pg/CMakeLists.linux-aarch64.txt
index 477c06a316..b902823cf8 100644
--- a/ydb/library/yql/sql/pg/CMakeLists.linux-aarch64.txt
+++ b/ydb/library/yql/sql/pg/CMakeLists.linux-aarch64.txt
@@ -10,6 +10,8 @@ add_subdirectory(ut)
 
 add_library(yql-sql-pg)
 target_compile_options(yql-sql-pg PRIVATE
+  -Dpalloc0=yql_palloc0
+  -Dpfree=yql_pfree
   -DUSE_CURRENT_UDF_ABI_VERSION
   $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
 )
@@ -28,5 +30,6 @@ target_link_libraries(yql-sql-pg PUBLIC
 )
 target_sources(yql-sql-pg PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/utils.cpp
 )
diff --git a/ydb/library/yql/sql/pg/CMakeLists.linux-x86_64.txt b/ydb/library/yql/sql/pg/CMakeLists.linux-x86_64.txt
index 477c06a316..b902823cf8 100644
--- a/ydb/library/yql/sql/pg/CMakeLists.linux-x86_64.txt
+++ b/ydb/library/yql/sql/pg/CMakeLists.linux-x86_64.txt
@@ -10,6 +10,8 @@ add_subdirectory(ut)
 
 add_library(yql-sql-pg)
 target_compile_options(yql-sql-pg PRIVATE
+  -Dpalloc0=yql_palloc0
+  -Dpfree=yql_pfree
   -DUSE_CURRENT_UDF_ABI_VERSION
   $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
 )
@@ -28,5 +30,6 @@ target_link_libraries(yql-sql-pg PUBLIC
 )
 target_sources(yql-sql-pg PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/utils.cpp
 )
diff --git a/ydb/library/yql/sql/pg/CMakeLists.windows-x86_64.txt b/ydb/library/yql/sql/pg/CMakeLists.windows-x86_64.txt
index c5889549cb..169f9dfca7 100644
--- a/ydb/library/yql/sql/pg/CMakeLists.windows-x86_64.txt
+++ b/ydb/library/yql/sql/pg/CMakeLists.windows-x86_64.txt
@@ -10,6 +10,8 @@ add_subdirectory(ut)
 
 add_library(yql-sql-pg)
 target_compile_options(yql-sql-pg PRIVATE
+  -Dpalloc0=yql_palloc0
+  -Dpfree=yql_pfree
   -D__thread=__declspec(thread)
   -Dfstat=microsoft_native_fstat
   -Dstat=microsoft_native_stat
@@ -30,5 +32,6 @@ target_link_libraries(yql-sql-pg PUBLIC
 )
 target_sources(yql-sql-pg PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer.cpp
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/utils.cpp
 )
diff --git a/ydb/library/yql/sql/pg/optimizer.cpp b/ydb/library/yql/sql/pg/optimizer.cpp
new file mode 100644
index 0000000000..6694e8a9e9
--- /dev/null
+++ b/ydb/library/yql/sql/pg/optimizer.cpp
@@ -0,0 +1,281 @@
+#include "utils.h"
+#include "optimizer.h"
+
+#include <iostream>
+#include <ydb/library/yql/parser/pg_wrapper/arena_ctx.h>
+
+#include <util/string/builder.h>
+#include <util/generic/yexception.h>
+
+#ifdef _WIN32
+#define __restrict
+#endif
+
+#define TypeName PG_TypeName
+#define SortBy PG_SortBy
+#undef SIZEOF_SIZE_T
+
+extern "C" {
+#include "postgres.h"
+#include "optimizer/paths.h"
+#include "nodes/print.h"
+#include "utils/selfuncs.h"
+#include "utils/palloc.h"
+}
+
+#undef Min
+#undef Max
+#undef TypeName
+#undef SortBy
+
+namespace NYql {
+
+namespace {
+
+bool RelationStatsHook(
+    PlannerInfo *root,
+    RangeTblEntry *rte,
+    AttrNumber attnum,
+    VariableStatData *vardata)
+{
+    vardata->statsTuple = nullptr;
+    return true;
+}
+
+} // namespace
+
+Var* MakeVar(int varno, int relno) {
+    Var* v = makeNode(Var);
+    v->varno = relno; // table number
+    v->varattno = varno; // column number in table
+
+    // ?
+    v->vartype = 25; // ?
+    v->vartypmod = -1; // ?
+    v->varcollid = 0;
+    v->varnosyn = v->varno;
+    v->varattnosyn = v->varattno;
+    v->location = -1;
+    return v;
+}
+
+RelOptInfo* MakeRelOptInfo(const IOptimizer::TRel& r, int relno) {
+    RelOptInfo* rel = makeNode(RelOptInfo);
+    rel->rows = r.rows;
+    rel->tuples = r.rows;
+    rel->pages = r.rows;
+    rel->allvisfrac = 1.0;
+    rel->relid = relno;
+    rel->amflags = 1.0;
+    rel->rel_parallel_workers = -1;
+
+    PathTarget* t = makeNode(PathTarget);
+    int maxattno = 0;
+    for (int i = 0; i < (int)r.TargetVars.size(); i++) {
+        t->exprs = lappend(t->exprs, MakeVar(i+1, relno));
+        maxattno = i+1;
+    }
+    t->width = 8;
+
+    rel->reltarget = t;
+    rel->max_attr = maxattno;
+
+    Path* p = makeNode(Path);
+    p->pathtype = T_SeqScan;
+    p->rows = r.rows;
+    p->startup_cost = 0;
+    p->total_cost = r.total_cost;
+    p->pathtarget = t;
+    p->parent = rel;
+
+    rel->pathlist = list_make1(p);
+    rel->cheapest_total_path = p;
+    rel->relids = bms_add_member(nullptr, rel->relid);
+    rel->attr_needed = (Relids*)palloc0((1+maxattno)*sizeof(Relids));
+
+    return rel;
+}
+
+List* MakeRelOptInfoList(const IOptimizer::TInput& input) {
+    List* l = nullptr;
+    int id = 1;
+    for (auto& rel : input.Rels) {
+        l = lappend(l, MakeRelOptInfo(rel, id++));
+    }
+    return l;
+}
+
+TPgOptimizer::TPgOptimizer(
+    const TInput& input,
+    const std::function<void(const TString&)>& log)
+    : Input(input)
+    , Log(log)
+{
+    get_relation_stats_hook = RelationStatsHook;
+}
+
+TPgOptimizer::~TPgOptimizer()
+{ }
+
+TPgOptimizer::TOutput TPgOptimizer::JoinSearch()
+{
+    TArenaMemoryContext ctx;
+    auto* rel = JoinSearchInternal();
+    return MakeOutput(rel->cheapest_total_path);
+}
+
+Var* TPgOptimizer::MakeVar(TVarId varId) {
+    auto*& var = Vars[varId];
+    return var
+        ? var
+        : (var = ::NYql::MakeVar(std::get<0>(varId), std::get<1>(varId)));
+}
+
+EquivalenceClass* TPgOptimizer::MakeEqClass(int i) {
+    EquivalenceClass* eq = makeNode(EquivalenceClass);
+
+    for (auto [relno, varno] : Input.EqClasses[i].Vars) {
+        EquivalenceMember* m = makeNode(EquivalenceMember);
+        m->em_expr = (Expr*)MakeVar(std::make_tuple(varno, relno));
+        m->em_relids = bms_add_member(nullptr, relno);
+        m->em_datatype = 20;
+        eq->ec_opfamilies = list_make1_oid(1976);
+        eq->ec_members = lappend(eq->ec_members, m);
+        eq->ec_relids = bms_union(eq->ec_relids, m->em_relids);
+    }
+    return eq;
+}
+
+List* TPgOptimizer::MakeEqClasses() {
+    List* l = nullptr;
+    for (int i = 0; i < (int)Input.EqClasses.size(); i++) {
+        l = lappend(l, MakeEqClass(i));
+    }
+    return l;
+}
+
+void TPgOptimizer::LogNode(const TString& prefix, void* node)
+{
+    if (Log) {
+        auto* str = nodeToString(node);
+        auto* fmt = pretty_format_node_dump(str);
+        pfree(str);
+        Log(TStringBuilder() << prefix << ": " << fmt);
+        pfree(fmt);
+    }
+}
+
+IOptimizer::TOutput TPgOptimizer::MakeOutput(Path* path) {
+    TOutput output = {{}, &Input};
+    MakeOutputJoin(output, path);
+    return output;
+}
+
+int TPgOptimizer::MakeOutputJoin(TOutput& output, Path* path) {
+    if (path->type == T_MaterialPath) {
+        return MakeOutputJoin(output, ((MaterialPath*)path)->subpath);
+    }
+    int id = output.Nodes.size();
+    TJoinNode node = output.Nodes.emplace_back(TJoinNode{});
+
+    int relid = -1;
+    while ((relid = bms_next_member(path->parent->relids, relid)) >= 0)
+	{
+        node.Rels.emplace_back(relid);
+    }
+
+    if (path->type != T_Path) {
+        node.Mode = EJoinType::INNER;
+        node.Strategy = EJoinStrategy::UNKNOWN;
+        if (path->type == T_HashPath) {
+            node.Strategy = EJoinStrategy::HASH;
+        } else if (path->type == T_NestPath) {
+            node.Strategy = EJoinStrategy::LOOP;
+        } else {
+            ythrow yexception() << "Uknown pathtype " << (int)path->type;
+        }
+
+        JoinPath* jpath = (JoinPath*)path;
+
+        if (list_length(jpath->joinrestrictinfo) != 1) {
+            ythrow yexception() << "Unsupported joinrestrictinfo len";
+        }
+        RestrictInfo* rinfo = (RestrictInfo*)jpath->joinrestrictinfo->elements[0].ptr_value;
+        if (rinfo->left_em->em_expr->type != T_Var) {
+            ythrow yexception() << "Unsupported left em type";
+        }
+        if (rinfo->right_em->em_expr->type != T_Var) {
+            ythrow yexception() << "Unsupported right em type";
+        }
+
+        Var* left = (Var*)rinfo->left_em->em_expr;
+        Var* right = (Var*)rinfo->right_em->em_expr;
+
+        node.LeftVar = std::make_tuple(left->varno, left->varattno);
+        node.RightVar = std::make_tuple(right->varno, right->varattno);
+
+        node.Inner = MakeOutputJoin(output, jpath->innerjoinpath);
+        node.Outer = MakeOutputJoin(output, jpath->outerjoinpath);
+    }
+
+    output.Nodes[id] = node;
+
+    return id;
+}
+
+RelOptInfo* TPgOptimizer::JoinSearchInternal() {
+    List* rels = MakeRelOptInfoList(Input);
+    ListCell* l;
+
+    if (Log) {
+        int i = 1;
+        foreach (l, rels) {
+            LogNode(TStringBuilder() << "Input: " << i++, lfirst(l));
+        }
+    }
+
+    PlannerInfo root;
+    memset(&root, 0, sizeof(root));
+    root.type = T_PlannerInfo;
+    root.query_level = 1;
+    root.simple_rel_array_size = rels->length+1;
+    root.simple_rel_array = (RelOptInfo**)palloc0(
+        root.simple_rel_array_size
+        * sizeof(RelOptInfo*));
+    root.simple_rte_array = (RangeTblEntry**)palloc0(
+        root.simple_rel_array_size * sizeof(RangeTblEntry)
+    );
+    for (int i = 0; i <= rels->length; i++) {
+        root.simple_rte_array[i] = makeNode(RangeTblEntry);
+        root.simple_rte_array[i]->rtekind = RTE_RELATION;
+    }
+    root.all_baserels = bms_add_range(nullptr, 1, rels->length+1);
+    root.eq_classes = MakeEqClasses();
+
+    root.planner_cxt = CurrentMemoryContext;
+
+    for (int i = 0; i < rels->length; i++) {
+        auto* r = (RelOptInfo*)rels->elements[i].ptr_value;
+        root.simple_rel_array[i+1] = r;
+    }
+
+    for (int eqId = 0; eqId < (int)Input.EqClasses.size(); eqId++) {
+        for (auto& [relno, _] : Input.EqClasses[eqId].Vars) {
+            root.simple_rel_array[relno]->eclass_indexes = bms_add_member(
+                root.simple_rel_array[relno]->eclass_indexes,
+                eqId);
+            root.simple_rel_array[relno]->has_eclass_joins = true;
+        }
+    }
+
+    auto* result = standard_join_search(&root, rels->length, rels);
+    LogNode("Result: ", result);
+    return result;
+}
+
+IOptimizer* MakePgOptimizer(const IOptimizer::TInput& input, const std::function<void(const TString&)>& log)
+{
+    return new TPgOptimizer(input, log);
+}
+
+} // namespace NYql {
diff --git a/ydb/library/yql/sql/pg/optimizer.h b/ydb/library/yql/sql/pg/optimizer.h
new file mode 100644
index 0000000000..c2e9748fec
--- /dev/null
+++ b/ydb/library/yql/sql/pg/optimizer.h
@@ -0,0 +1,42 @@
+#pragma once
+
+#include <ydb/library/yql/parser/pg_wrapper/interface/optimizer.h>
+
+struct Var;
+struct RelOptInfo;
+struct List;
+struct EquivalenceClass;
+struct Path;
+
+namespace NYql {
+
+class TPgOptimizer: public IOptimizer {
+public:
+    TPgOptimizer(const TInput& input, const std::function<void(const TString&)>& log = {});
+    ~TPgOptimizer();
+
+    TOutput JoinSearch() override;
+
+private:
+    TInput Input;
+    std::function<void(const TString&)> Log;
+    std::map<TVarId, Var*> Vars;
+
+    void LogNode(const TString& prefix, void* node);
+    RelOptInfo* JoinSearchInternal();
+    List* MakeEqClasses();
+    EquivalenceClass* MakeEqClass(int eqId);
+    Var* MakeVar(TVarId);
+    TOutput MakeOutput(Path*);
+    int MakeOutputJoin(TOutput& output, Path*);
+    void LogOutput(const TString& prefix, const TOutput& output, int id);
+    TString PrettyPrintVar(TVarId varId);
+};
+
+// export for tests
+Var* MakeVar(int varno, int relno);
+RelOptInfo* MakeRelOptInfo(const IOptimizer::TRel& r, int relno);
+List* MakeRelOptInfoList(const IOptimizer::TInput& input);
+
+} // namespace NYql
+
diff --git a/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp b/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
new file mode 100644
index 0000000000..7384dc3397
--- /dev/null
+++ b/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
@@ -0,0 +1,92 @@
+#include <library/cpp/testing/unittest/registar.h>
+#include <library/cpp/testing/hook/hook.h>
+
+#include <ydb/library/yql/parser/pg_wrapper/arena_ctx.h>
+
+#include "optimizer.h"
+
+extern "C" {
+#include <ydb/library/yql/parser/pg_wrapper/thread_inits.h>
+}
+
+#ifdef _WIN32
+#define __restrict
+#endif
+
+#define TypeName PG_TypeName
+#define SortBy PG_SortBy
+#undef SIZEOF_SIZE_T
+
+extern "C" {
+#include "postgres.h"
+#include "optimizer/paths.h"
+}
+
+#undef Min
+#undef Max
+#undef TypeName
+#undef SortBy
+
+using namespace NYql;
+
+Y_UNIT_TEST_SUITE(PgOptimizerImpl) {
+
+Y_TEST_HOOK_BEFORE_RUN(InitTest) {
+    pg_thread_init();
+}
+
+Y_UNIT_TEST(MakeVar) {
+    TArenaMemoryContext ctx;
+
+    auto* v1 = MakeVar(1, 1);
+    UNIT_ASSERT(v1);
+    UNIT_ASSERT_EQUAL(v1->varno, 1);
+    UNIT_ASSERT_EQUAL(v1->varattno, 1);
+
+    auto* v2 = MakeVar(2, 2);
+    UNIT_ASSERT(v2);
+    UNIT_ASSERT_EQUAL(v2->varno, 2);
+    UNIT_ASSERT_EQUAL(v2->varattno, 2);
+}
+
+Y_UNIT_TEST(MakeRelOptInfo) {
+    TArenaMemoryContext ctx;
+    IOptimizer::TRel rel1 = {10, 100, {{}}};
+    auto* r1 = MakeRelOptInfo(rel1, 1);
+    UNIT_ASSERT(r1);
+    UNIT_ASSERT_EQUAL(r1->reltarget->exprs->length, 1);
+    UNIT_ASSERT_EQUAL(
+        ((Var*)r1->reltarget->exprs->elements[0].ptr_value)->varattno, 1
+    );
+
+    UNIT_ASSERT_EQUAL(r1->pathlist->length, 1);
+    UNIT_ASSERT_EQUAL(
+        ((Path*)r1->pathlist->elements[0].ptr_value)->rows, 10
+    );
+    UNIT_ASSERT_EQUAL(
+        ((Path*)r1->pathlist->elements[0].ptr_value)->total_cost, 100
+    );
+
+    IOptimizer::TRel rel2 = {100, 99, {{}, {}}};
+    auto* r2 = MakeRelOptInfo(rel2, 2);
+    UNIT_ASSERT(r2);
+    UNIT_ASSERT_EQUAL(r2->reltarget->exprs->length, 2);
+}
+
+Y_UNIT_TEST(MakeRelOptInfoListNull) {
+    TArenaMemoryContext ctx;
+    auto* l = MakeRelOptInfoList({});
+    UNIT_ASSERT(l == nullptr);
+}
+
+Y_UNIT_TEST(MakeRelOptInfoList) {
+    TArenaMemoryContext ctx;
+    IOptimizer::TRel rel1 = {10, 100, {{}}};
+    IOptimizer::TRel rel2 = {100, 99, {{}}};
+    IOptimizer::TInput input = {{rel1, rel2}};
+    auto* l = MakeRelOptInfoList(input);
+    UNIT_ASSERT(l);
+    UNIT_ASSERT_EQUAL(l->length, 2);
+}
+
+} // PgOptimizerImpl
diff --git a/ydb/library/yql/sql/pg/optimizer_ut.cpp b/ydb/library/yql/sql/pg/optimizer_ut.cpp
new file mode 100644
index 0000000000..0b814718c2
--- /dev/null
+++ b/ydb/library/yql/sql/pg/optimizer_ut.cpp
@@ -0,0 +1,100 @@
+#include <library/cpp/testing/unittest/registar.h>
+#include <library/cpp/testing/hook/hook.h>
+
+#include <ydb/library/yql/parser/pg_wrapper/interface/optimizer.h>
+
+extern "C" {
+#include <ydb/library/yql/parser/pg_wrapper/thread_inits.h>
+}
+
+using namespace NYql;
+
+Y_UNIT_TEST_SUITE(PgOptimizer) {
+
+Y_TEST_HOOK_BEFORE_RUN(InitTest) {
+    pg_thread_init();
+}
+
+Y_UNIT_TEST(PgJoinSearch2Rels) {
+    IOptimizer::TRel rel1 = {100000, 1000000, {{'a'}}};
+    IOptimizer::TRel rel2 = {1000000, 9000009, {{'b'}}};
+    IOptimizer::TInput input = {{rel1, rel2}};
+
+    input.EqClasses.emplace_back(IOptimizer::TEq {
+        {{1, 1}, {2, 1}}
+    });
+
+    auto log = [](const TString& str) {
+        Cerr << str << "\n";
+    };
+
+    auto optimizer = std::unique_ptr<IOptimizer>(MakePgOptimizer(input, log));
+
+    auto res = optimizer->JoinSearch();
+    auto resStr = res.ToString();
+    Cerr << resStr;
+    TString expected = R"__({
+ Inner Join
+ Loop Strategy
+ Rels: [1,2]
+ Op: a = b
+ {
+  Node
+  Rels: [2]
+ }
+ {
+  Node
+  Rels: [1]
+ }
+}
+)__";
+    UNIT_ASSERT_STRINGS_EQUAL(expected, resStr);
+}
+
+Y_UNIT_TEST(PgJoinSearch3Rels) {
+    IOptimizer::TRel rel1 = {100000, 1000000, {{'a'}}};
+    IOptimizer::TRel rel2 = {1000000, 9000009, {{'b'}}};
+    IOptimizer::TRel rel3 = {10000, 9009, {{'c'}}};
+    IOptimizer::TInput input = {{rel1, rel2, rel3}};
+
+    input.EqClasses.emplace_back(IOptimizer::TEq {
+        {{1, 1}, {2, 1}, {3, 1}}
+    });
+
+    auto log = [](const TString& str) {
+        Cerr << str << "\n";
+    };
+
+    auto optimizer = std::unique_ptr<IOptimizer>(MakePgOptimizer(input, log));
+    auto res = optimizer->JoinSearch();
+    auto resStr = res.ToString();
+    Cerr << resStr;
+    TString expected = R"__({
+ Inner Join
+ Hash Strategy
+ Rels: [1,2,3]
+ Op: a = b
+ {
+  Inner Join
+  Loop Strategy
+  Rels: [1,3]
+  Op: a = c
+  {
+   Node
+   Rels: [1]
+  }
+  {
+   Node
+   Rels: [3]
+  }
+ }
+ {
+  Node
+  Rels: [2]
+ }
+}
+)__";
+    UNIT_ASSERT_STRINGS_EQUAL(expected, resStr);
+}
+
+} // Y_UNIT_TEST_SUITE(PgOptimizer)
diff --git a/ydb/library/yql/sql/pg/ut/CMakeLists.darwin-x86_64.txt b/ydb/library/yql/sql/pg/ut/CMakeLists.darwin-x86_64.txt
index a97ae7640d..738414dcb0 100644
--- a/ydb/library/yql/sql/pg/ut/CMakeLists.darwin-x86_64.txt
+++ b/ydb/library/yql/sql/pg/ut/CMakeLists.darwin-x86_64.txt
@@ -8,8 +8,12 @@
 
 
 add_executable(ydb-library-yql-sql-pg-ut)
+target_compile_options(ydb-library-yql-sql-pg-ut PRIVATE
+  $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
+)
 target_include_directories(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/include
 )
 target_link_libraries(ydb-library-yql-sql-pg-ut PUBLIC
   contrib-libs-cxxsupp
@@ -30,6 +34,8 @@ target_link_options(ydb-library-yql-sql-pg-ut PRIVATE
 )
 target_sources(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
 )
 set_property(
   TARGET
diff --git a/ydb/library/yql/sql/pg/ut/CMakeLists.linux-aarch64.txt b/ydb/library/yql/sql/pg/ut/CMakeLists.linux-aarch64.txt
index 25ac8f596b..221548471d 100644
--- a/ydb/library/yql/sql/pg/ut/CMakeLists.linux-aarch64.txt
+++ b/ydb/library/yql/sql/pg/ut/CMakeLists.linux-aarch64.txt
@@ -8,8 +8,12 @@
 
 
 add_executable(ydb-library-yql-sql-pg-ut)
+target_compile_options(ydb-library-yql-sql-pg-ut PRIVATE
+  $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
+)
 target_include_directories(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/include
 )
 target_link_libraries(ydb-library-yql-sql-pg-ut PUBLIC
   contrib-libs-linux-headers
@@ -33,6 +37,8 @@ target_link_options(ydb-library-yql-sql-pg-ut PRIVATE
 )
 target_sources(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
 )
 set_property(
   TARGET
diff --git a/ydb/library/yql/sql/pg/ut/CMakeLists.linux-x86_64.txt b/ydb/library/yql/sql/pg/ut/CMakeLists.linux-x86_64.txt
index 2a9f4f65f6..f448b135ca 100644
--- a/ydb/library/yql/sql/pg/ut/CMakeLists.linux-x86_64.txt
+++ b/ydb/library/yql/sql/pg/ut/CMakeLists.linux-x86_64.txt
@@ -8,8 +8,12 @@
 
 
 add_executable(ydb-library-yql-sql-pg-ut)
+target_compile_options(ydb-library-yql-sql-pg-ut PRIVATE
+  $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
+)
 target_include_directories(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/include
 )
 target_link_libraries(ydb-library-yql-sql-pg-ut PUBLIC
   contrib-libs-linux-headers
@@ -34,6 +38,8 @@ target_link_options(ydb-library-yql-sql-pg-ut PRIVATE
 )
 target_sources(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
 )
 set_property(
   TARGET
diff --git a/ydb/library/yql/sql/pg/ut/CMakeLists.windows-x86_64.txt b/ydb/library/yql/sql/pg/ut/CMakeLists.windows-x86_64.txt
index 883f4b5502..c86c2af5ca 100644
--- a/ydb/library/yql/sql/pg/ut/CMakeLists.windows-x86_64.txt
+++ b/ydb/library/yql/sql/pg/ut/CMakeLists.windows-x86_64.txt
@@ -8,8 +8,12 @@
 
 
 add_executable(ydb-library-yql-sql-pg-ut)
+target_compile_options(ydb-library-yql-sql-pg-ut PRIVATE
+  $<IF:$<CXX_COMPILER_ID:MSVC>,,-Wno-everything>
+)
 target_include_directories(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/parser/pg_wrapper/postgresql/src/include
 )
 target_link_libraries(ydb-library-yql-sql-pg-ut PUBLIC
   contrib-libs-cxxsupp
@@ -23,6 +27,8 @@ target_link_libraries(ydb-library-yql-sql-pg-ut PUBLIC
 )
 target_sources(ydb-library-yql-sql-pg-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/pg_sql_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/library/yql/sql/pg/optimizer_impl_ut.cpp
 )
 set_property(
   TARGET
diff --git a/ydb/library/yql/sql/pg/ut/ya.make b/ydb/library/yql/sql/pg/ut/ya.make
index 985e682fe7..d00c6f1c41 100644
--- a/ydb/library/yql/sql/pg/ut/ya.make
+++ b/ydb/library/yql/sql/pg/ut/ya.make
@@ -2,6 +2,12 @@ UNITTEST_FOR(ydb/library/yql/sql/pg)
 
 SRCS(
     pg_sql_ut.cpp
+    optimizer_ut.cpp
+    optimizer_impl_ut.cpp
+)
+
+ADDINCL(
+    ydb/library/yql/parser/pg_wrapper/postgresql/src/include
 )
 
 PEERDIR(
@@ -14,4 +20,6 @@ PEERDIR(
 
 SIZE(MEDIUM)
 
+NO_COMPILER_WARNINGS()
+
 END()
diff --git a/ydb/library/yql/sql/pg/ya.make b/ydb/library/yql/sql/pg/ya.make
index 531e41df31..0e95b2da09 100644
--- a/ydb/library/yql/sql/pg/ya.make
+++ b/ydb/library/yql/sql/pg/ya.make
@@ -18,9 +18,15 @@ ADDINCL(
 
 SRCS(
     pg_sql.cpp
+    optimizer.cpp
     utils.cpp
 )
 
+CFLAGS(
+    -Dpalloc0=yql_palloc0
+    -Dpfree=yql_pfree
+)
+
 IF (OS_WINDOWS)
 CFLAGS(
    "-D__thread=__declspec(thread)"
diff --git a/ydb/library/yql/sql/pg_dummy/pg_sql_dummy.cpp b/ydb/library/yql/sql/pg_dummy/pg_sql_dummy.cpp
index 70391634c1..5560845714 100644
--- a/ydb/library/yql/sql/pg_dummy/pg_sql_dummy.cpp
+++ b/ydb/library/yql/sql/pg_dummy/pg_sql_dummy.cpp
@@ -352,6 +352,13 @@ std::function<NKikimr::NMiniKQL::IComputationNode* (NKikimr::NMiniKQL::TCallable
     };
 }
 
+IOptimizer* MakePgOptimizer(const IOptimizer::TInput& input, const std::function<void(const TString&)>& log)
+{
+    Y_UNUSED(input);
+    Y_UNUSED(log);
+    ythrow yexception() << "PgJoinSearch does nothing";
+}
+
 } // NYql
 
 namespace NKikimr::NPg {