search

stoneatom / stonedb

StoneDB is an Open-Source MySQL HTAP and MySQL-Native DataBase for OLTP, Real-Time Analytics, a counterpart of MySQLHeatWave. (https://stonedb.io)
https://stonedb.io/
GNU General Public License v2.0
865 stars 140 forks source link

bug: 执行外连接的查询过于耗时, tianmu需要执行十四分钟, innodb执行外连接仅需要执行一分钟 #1777

Open haitaoguan opened 1 year ago

haitaoguan commented 1 year ago 
###sql_text
select a.*
  FROM c_acct a
  LEFT JOIN (SELECT b.account_id, b.fiscal_date, b.balance
               FROM (SELECT account_id, max(fiscal_date) fiscal_date
                       FROM c_day
                      WHERE deleted_flag = '0'
                      GROUP BY account_id) a
               JOIN c_day b
                 ON a.account_id = b.account_id
                AND a.fiscal_date = b.fiscal_date
              WHERE b.deleted_flag = '0') c
    ON a.row_id = c.account_id

mysql> select count(*) from c1md_bank_acct;
+----------+
| count(*) |
+----------+
|     1016 |
+----------+
1 row in set (0.00 sec)

mysql> select count(*) from c1am_acct_day;
+----------+
| count(*) |
+----------+
|  3251200 |
+----------+
1 row in set (0.00 sec)

###InnoDB explain plan
+----+-------------+---------------+------------+-------+-------------------------------------------------+-----------------+---------+----------------------------+---------+----------+-------------+
| id | select_type | table         | partitions | type  | possible_keys                                   | key             | key_len | ref                        | rows    | filtered | Extra       |
+----+-------------+---------------+------------+-------+-------------------------------------------------+-----------------+---------+----------------------------+---------+----------+-------------+
|  1 | PRIMARY     | a             | NULL       | ALL   | NULL                                            | NULL            | NULL    | NULL                       |    1022 |   100.00 | NULL        |
|  1 | PRIMARY     | <derived3>    | NULL       | ref   | <auto_key1>                                     | <auto_key1>     | 8       | mbs.a.ROW_ID               |     409 |   100.00 | NULL        |
|  1 | PRIMARY     | b             | NULL       | ref   | IDX_AMACCTDAY02,IDX_AMACCTDAY03,IDX_AMACCTDAY04 | IDX_AMACCTDAY02 | 12      | mbs.a.ROW_ID,a.fiscal_date |       1 |   100.00 | Using where |
|  3 | DERIVED     | c_day         | NULL       | index | IDX_AMACCTDAY02,IDX_AMACCTDAY03                 | IDX_AMACCTDAY03 | 8       | NULL                       | 3136482 |    10.00 | Using where |
+----+-------------+---------------+------------+-------+-------------------------------------------------+-----------------+---------+----------------------------+---------+----------+-------------+
4 rows in set, 1 warning (0.00 sec)

The optimizer of InnoDB prioritizes selecting small tables for association, with an execution time of 6 seconds.

###Tianmu explain plan
+----+-------------+---------------+------------+------+-------------------------------------------------+-------------+---------+------------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id | select_type | table         | partitions | type | possible_keys                                   | key         | key_len | ref                                | rows    | filtered | Extra                                                                                                                                                                     |
+----+-------------+---------------+------------+------+-------------------------------------------------+-------------+---------+------------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|  1 | PRIMARY     | a             | NULL       | ALL  | NULL                                            | NULL        | NULL    | NULL                               |    1016 |   100.00 | NULL                                                                                                                                                                      |
|  1 | PRIMARY     | b             | NULL       | ALL  | IDX_AMACCTDAY02,IDX_AMACCTDAY03,IDX_AMACCTDAY04 | NULL        | NULL    | NULL                               | 3251200 |     0.14 | Using where                                                                                                                                                               |
|  1 | PRIMARY     | <derived3>    | NULL       | ref  | <auto_key0>                                     | <auto_key0> | 12      | mbs.b.ACCOUNT_ID,mbs.b.FISCAL_DATE |     320 |   100.00 | Using where; Using index                                                                                                                                                  |
|  3 | DERIVED     | c_day         | NULL       | ALL  | NULL                                            | NULL        | NULL    | NULL                               | 3251200 |    10.00 | Using where with pushed condition (`mbs`.`c_day`.`DELETED_FLAG` = '0')(t0) Pckrows: 50, susp. 50 (0 empty 0 full). Conditions: 1; Using temporary; Using filesort |
+----+-------------+---------------+------------+------+-------------------------------------------------+-------------+---------+------------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
4 rows in set, 1 warning (0.03 sec)

The optimizer of Tianmu correlates according to the order of table connections, with an execution time of 10 minutes.
adofsauron commented 1 year ago

不过也好理解，内连接是分开两次执行，分别遍历1016 和 3251200 行。 而外连接却做了1016 * 3251200 = 3303219200 的遍历

adofsauron commented 1 year ago

不过有意思的问题就在乎，除了这么简单粗暴的连接的做法，性能更为狂野的数据库是如何处理这个问题的

adofsauron commented 1 year ago

680aeb5586f8afe33bc0653e8b79628f

adofsauron commented 1 year ago

watchmatched: false outer_nullsonly: false other_condexist: true

adofsauron commented 1 year ago

hashtable = 0x7f0574395ec0, keybuffer = 0x7f0896435ec0, matchedrows = 1, currentrow = 151, to_bereturned = 0, current_iteratestep = 11

adofsauron commented 1 year ago

desc_t = Tianmu::core::DescriptorJoinType::DT_NON_JOIN,

adofsauron commented 1 year ago

这倒是绝妙的处理

(gdb) p cond[0].right_dims $14 = {v = std::vector of length 3, capacity 64 = {0, 1, 1}} (gdb) p cond[0].left_dims $15 = {v = std::vector of length 3, capacity 64 = {1, 0, 0}}

adofsauron commented 1 year ago

当个草稿先记下


#0  Tianmu::core::MultiIndex::AddDimension_cross (this=0x7f1998e5c470, size=1016) at /root/work/stonedb-dev-202305026/storage/tianmu/index/multi_index.cpp:202
#1  0x0000000002d559c1 in Tianmu::core::TempTable::TempTable (this=0x7f19343c4580, t=0x7f199803e560, alias=-1, q=0x7f1ca108e7d0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/temp_table_com.cpp:48
#2  0x0000000002d3f2cf in Tianmu::core::TempTable::Create (t=0x7f199803e560, alias=-1, q=0x7f1ca108e7d0, for_subq=false)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/temp_table.cpp:1895
#3  0x0000000002cfdc1e in Tianmu::core::Query::Preexecute (this=0x7f1ca108e7d0, qu=..., sender=0x7f1998e5bb00, display_now=true)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/query.cpp:629
#4  0x0000000002ceba5e in Tianmu::core::Engine::Execute (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result_output=0x7f1998e4c628, unit_for_union=0x0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:513
#5  0x0000000002cea74b in Tianmu::core::Engine::HandleSelect (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:243
#6  0x0000000003084438 in Tianmu::DBHandler::ha_my_tianmu_query (thd=0x7f1998000e10, lex=0x7f1998003138, result_output=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/sql/ha_my_tianmu.cpp:95
#7  0x0000000002427a28 in execute_sqlcom_select (thd=0x7f1998000e10, all_tables=0x7f1998011328) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5204
#8  0x0000000002420d9e in mysql_execute_command (thd=0x7f1998000e10, first_level=true) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:2847
#9  0x0000000002428a8d in mysql_parse (thd=0x7f1998000e10, parser_state=0x7f1ca108ff90) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5642
#10 0x000000000241da84 in dispatch_command (thd=0x7f1998000e10, com_data=0x7f1ca1090730, command=COM_QUERY) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1495
#11 0x000000000241c8c5 in do_command (thd=0x7f1998000e10) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1034
#12 0x000000000254ee35 in handle_connection (arg=0x8ed32e0) at /root/work/stonedb-dev-202305026/sql/conn_handler/connection_handler_per_thread.cc:313
#13 0x0000000002c1e674 in pfs_spawn_thread (arg=0x8d06460) at /root/work/stonedb-dev-202305026/storage/perfschema/pfs.cc:2197
#14 0x00007f1cab3b21ca in start_thread () from /lib64/libpthread.so.0
#15 0x00007f1ca8228e73 in clone () from /lib64/libc.so.6
adofsauron commented 1 year ago 

#0  Tianmu::core::MultiIndex::AddDimension_cross (this=0x7f1998e59a80, size=3251200) at /root/work/stonedb-dev-202305026/storage/tianmu/index/multi_index.cpp:202
#1  0x0000000002d559c1 in Tianmu::core::TempTable::TempTable (this=0x7f191c396840, t=0x7f19989ed370, alias=-3, q=0x7f1ca108e7d0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/temp_table_com.cpp:48
#2  0x0000000002d3f2cf in Tianmu::core::TempTable::Create (t=0x7f19989ed370, alias=-3, q=0x7f1ca108e7d0, for_subq=false)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/temp_table.cpp:1895
#3  0x0000000002cfdc1e in Tianmu::core::Query::Preexecute (this=0x7f1ca108e7d0, qu=..., sender=0x7f1998e5bb00, display_now=true)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/query.cpp:629
#4  0x0000000002ceba5e in Tianmu::core::Engine::Execute (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result_output=0x7f1998e4c628, unit_for_union=0x0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:513
#5  0x0000000002cea74b in Tianmu::core::Engine::HandleSelect (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:243
#6  0x0000000003084438 in Tianmu::DBHandler::ha_my_tianmu_query (thd=0x7f1998000e10, lex=0x7f1998003138, result_output=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/sql/ha_my_tianmu.cpp:95
#7  0x0000000002427a28 in execute_sqlcom_select (thd=0x7f1998000e10, all_tables=0x7f1998011328) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5204
#8  0x0000000002420d9e in mysql_execute_command (thd=0x7f1998000e10, first_level=true) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:2847
#9  0x0000000002428a8d in mysql_parse (thd=0x7f1998000e10, parser_state=0x7f1ca108ff90) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5642
#10 0x000000000241da84 in dispatch_command (thd=0x7f1998000e10, com_data=0x7f1ca1090730, command=COM_QUERY) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1495
#11 0x000000000241c8c5 in do_command (thd=0x7f1998000e10) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1034
#12 0x000000000254ee35 in handle_connection (arg=0x8ed32e0) at /root/work/stonedb-dev-202305026/sql/conn_handler/connection_handler_per_thread.cc:313
#13 0x0000000002c1e674 in pfs_spawn_thread (arg=0x8d06460) at /root/work/stonedb-dev-202305026/storage/perfschema/pfs.cc:2197
#14 0x00007f1cab3b21ca in start_thread () from /lib64/libpthread.so.0
#15 0x00007f1ca8228e73 in clone () from /lib64/libc.so.6
adofsauron commented 1 year ago

以下先记录，回头在日记里做详细分析


#0  Tianmu::core::MultiIndex::MultiplyNoTuples (this=0x7f1998e5c470, factor=3251200) at /root/work/stonedb-dev-202305026/storage/tianmu/index/multi_index.cpp:227
#1  0x0000000002eb32b0 in Tianmu::core::MultiIndex::AddDimension_cross (this=0x7f1998e5c470, size=3251200) at /root/work/stonedb-dev-202305026/storage/tianmu/index/multi_index.cpp:206
#2  0x0000000002d55cd0 in Tianmu::core::TempTable::JoinT (this=0x7f19343c4580, t=0x7f19989ed370, alias=-5, jt=Tianmu::core::JoinType::JO_INNER)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/temp_table_com.cpp:76
#3  0x0000000002cfef96 in Tianmu::core::Query::Preexecute (this=0x7f1ca108e7d0, qu=..., sender=0x7f1998e5bb00, display_now=true)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/query.cpp:743
#4  0x0000000002ceba5e in Tianmu::core::Engine::Execute (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result_output=0x7f1998e4c628, unit_for_union=0x0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:513
#5  0x0000000002cea74b in Tianmu::core::Engine::HandleSelect (this=0x4dcaeb0, thd=0x7f1998000e10, lex=0x7f1998003138, result=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/core/engine_execute.cpp:243
#6  0x0000000003084438 in Tianmu::DBHandler::ha_my_tianmu_query (thd=0x7f1998000e10, lex=0x7f1998003138, result_output=@0x7f1ca108edc8: 0x7f1998e4c628, setup_tables_done_option=0, 
    res=@0x7f1ca108edc4: 0, is_optimize_after_tianmu=@0x7f1ca108edbc: 1, tianmu_free_join=@0x7f1ca108edc0: 1, with_insert=0)
    at /root/work/stonedb-dev-202305026/storage/tianmu/sql/ha_my_tianmu.cpp:95
#7  0x0000000002427a28 in execute_sqlcom_select (thd=0x7f1998000e10, all_tables=0x7f1998011328) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5204
#8  0x0000000002420d9e in mysql_execute_command (thd=0x7f1998000e10, first_level=true) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:2847
#9  0x0000000002428a8d in mysql_parse (thd=0x7f1998000e10, parser_state=0x7f1ca108ff90) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:5642
#10 0x000000000241da84 in dispatch_command (thd=0x7f1998000e10, com_data=0x7f1ca1090730, command=COM_QUERY) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1495
#11 0x000000000241c8c5 in do_command (thd=0x7f1998000e10) at /root/work/stonedb-dev-202305026/sql/sql_parse.cc:1034
#12 0x000000000254ee35 in handle_connection (arg=0x8ed32e0) at /root/work/stonedb-dev-202305026/sql/conn_handler/connection_handler_per_thread.cc:313
#13 0x0000000002c1e674 in pfs_spawn_thread (arg=0x8d06460) at /root/work/stonedb-dev-202305026/storage/perfschema/pfs.cc:2197
#14 0x00007f1cab3b21ca in start_thread () from /lib64/libpthread.so.0
#15 0x00007f1ca8228e73 in clone () from /lib64/libc.so.6
adofsauron commented 1 year ago 

void TempTable::JoinT(JustATable *t, int alias, JoinType jt) {
  if (jt != JoinType::JO_INNER)
    throw common::NotImplementedException("left/right/outer join is not implemented.");
  tables.push_back(t);
  aliases.push_back(alias);

  if (t->TableType() == TType::TEMP_TABLE) {
    has_temp_table = true;
    ((TempTable *)t)->Materialize();
    filter.mind_->AddDimension_cross(t->NumOfObj());
  } else
    filter.mind_->AddDimension_cross(t->NumOfObj());

  join_types.push_back(jt);

  if (filter.mind_->TooManyTuples())
    no_obj = common::NULL_VALUE_64;  // a big, improper number, which we hope to
                                     // be changed after conditions are applied
  else
    no_obj = filter.mind_->NumOfTuples();
}
adofsauron commented 1 year ago 

(gdb) p t->TableType()
$31 = Tianmu::core::TType::TABLE
adofsauron commented 1 year ago 

void MultiIndex::AddDimension_cross(uint64_t size) {
  AddDimension();
  int new_dim = no_dimensions - 1;
  used_in_output.push_back(true);
  if (no_dimensions > 1)
    MultiplyNoTuples(size);
  else
    no_tuples = size;
  DimensionGroupFilter *nf = nullptr;
  if (size > 0) {
    dim_size[new_dim] = size;
    nf = new DimensionGroupFilter(new_dim, size, p_power);  // redo
  } else {  // size == 0   => prepare a dummy dimension with empty filter
    dim_size[new_dim] = 1;
    nf = new DimensionGroupFilter(new_dim, dim_size[new_dim], p_power);  // redo
    nf->Empty();
  }
  dim_groups.push_back(nf);
  group_for_dim[new_dim] = nf;
  group_num_for_dim[new_dim] = int(dim_groups.size() - 1);
  can_be_distinct.push_back(true);  // may be modified below
  CheckIfVirtualCanBeDistinct();
}
adofsauron commented 1 year ago

有点意思，成为了叉乘

adofsauron commented 1 year ago

3356070707200

adofsauron commented 1 year ago 

void MIIterator::Init(bool lock) {
  mii_type = MIIteratorType::MII_NORMAL;
  bool *dim_group_used = new bool[mind->dim_groups.size()];
  for (uint i = 0; i < mind->dim_groups.size(); i++) dim_group_used[i] = false;
  for (int i = 0; i < no_dims; i++)
    if (dimensions[i]) {
      dim_group_used[mind->group_num_for_dim[i]] = true;
      mind->LockForGetIndex(i);
    }

  no_obj = 1;  // special case of 0 will be tested soon
  omitted_factor = 1;
  bool zero_tuples = true;
  for (uint i = 0; i < mind->dim_groups.size(); i++) {
    if (dim_group_used[i]) {
      no_obj = SafeMultiplication(no_obj, mind->dim_groups[i]->NumOfTuples());
      zero_tuples = false;
    } else {
      omitted_factor = SafeMultiplication(omitted_factor, mind->dim_groups[i]->NumOfTuples());
    }
  }
  if (zero_tuples)
    no_obj = 0;

  if (no_dims > 0) {
    it_for_dim = new int[no_dims];

    // Create group iterators: ordered filter-based first, if any
    if (po.size() > 0) {
      for (int i = 0; i < no_dims; i++)
        if (dim_group_used[mind->group_num_for_dim[i]] && mind->GetFilter(i) && po[i].Initialized()) {
          assert(mind->IsOrderable(i));
          it.push_back(mind->group_for_dim[i]->NewOrderedIterator(dimensions, &po[i], p_power));
          dg.push_back(mind->group_for_dim[i]);
          dim_group_used[mind->group_num_for_dim[i]] = false;
        }
    }

    // Create group iterators: other filter-based
    std::vector<std::pair<int, int>> ordering_filters;
    for (uint i = 0; i < mind->dim_groups.size(); i++)
      if (dim_group_used[i] && (mind->dim_groups[i]->Type() == DimensionGroup::DGType::DG_FILTER ||
                                mind->dim_groups[i]->Type() == DimensionGroup::DGType::DG_VIRTUAL))  // filters first
        ordering_filters.push_back(std::pair<int, int>(65537 - mind->dim_groups[i]->GetFilter(-1)->DensityWeight(),
                                                       i));  // -1: the default filter for this group
    sort(ordering_filters.begin(),
         ordering_filters.end());  // order filters starting from the
                                   // densest one (for pack
                                   // decompression efficiency)

    for (uint i = 0; i < ordering_filters.size(); i++) {  // create iterators for DimensionGroup numbers from sorter
      it.push_back(mind->dim_groups[ordering_filters[i].second]->NewIterator(dimensions, p_power));
      dg.push_back(mind->dim_groups[ordering_filters[i].second]);
      dim_group_used[ordering_filters[i].second] = false;
    }

    // Create group iterators: materialized
    for (uint i = 0; i < mind->dim_groups.size(); i++)
      if (dim_group_used[i]) {
        it.push_back(mind->dim_groups[i]->NewIterator(dimensions, p_power));
        dg.push_back(mind->dim_groups[i]);
      }

    for (int i = 0; i < no_dims; i++)
      if (dimensions[i]) {
        for (uint j = 0; j < dg.size(); j++) {
          if (mind->group_for_dim[i] == dg[j]) {
            it_for_dim[i] = j;
            break;
          }
        }
      }

    if (lock) {
      mind->IteratorLock();
    }
    cur_pos = new int64_t[no_dims];
    cur_pack = new int[no_dims];
    std::fill(cur_pos, cur_pos + no_dims, common::NULL_VALUE_64);
    std::fill(cur_pack, cur_pack + no_dims, -1);

    // Check the optimized case
    if (dg.size() == 1 && dg[0]->Type() == DimensionGroup::DGType::DG_FILTER) {
      for (int i = 0; i < no_dims; i++)
        if (dimensions[i]) {
          one_filter_dim = i;
          break;
        }
      if (po.size() == 0)
        one_filter_it = (DimensionGroupFilter::DGFilterIterator *)(it[0]);
      else
        one_filter_it = (DimensionGroupFilter::DGFilterOrderedIterator *)(it[0]);
    }
  }

  delete[] dim_group_used;

  Rewind();
  if (!IsValid())
    no_obj = 0;
}
adofsauron commented 1 year ago

表之间的关系

adofsauron commented 1 year ago

表之间的关系

adofsauron commented 1 year ago

有点意思，为了延迟物化所做的处理，得记录下

adofsauron commented 1 year ago

[2023-05-28 01:15:39.509713] [306195] [INFO] [parallel_hash_join.cpp:420] MSG: ExecuteJoin before traversed_dims_size: 1016 matched_dims_size: 1016 [2023-05-28 01:15:39.511074] [306195] [INFO] [parallel_hash_join.cpp:1055] MSG: AsyncMatchDim traversed spend: 0.000526 matching_row: 1016 [2023-05-28 01:15:39.511115] [306195] [INFO] [parallel_hash_join.cpp:1070] MSG: AsyncMatchDim spend: 0.000574 watchmatched: false watchtraversed: false outer_nullsonly: false other_condexist: false [2023-05-28 01:15:39.511294] [306195] [INFO] [parallel_hash_join.cpp:491] MSG: ExecuteJoin over traversed_dims_size: 1016 matched_dims_size: 1016 joined_tuples: 1016 outertuples: 0 [2023-05-28 01:15:39.511460] [306195] [INFO] [parallel_hash_join.cpp:420] MSG: ExecuteJoin before traversed_dims_size: 1016 matched_dims_size: 3251200 [2023-05-28 01:15:39.539505] [306195] [INFO] [parallel_hash_join.cpp:1055] MSG: AsyncMatchDim traversed spend: 0.018271 matching_row: 3251200 [2023-05-28 01:15:39.539555] [306195] [INFO] [parallel_hash_join.cpp:1070] MSG: AsyncMatchDim spend: 0.018329 watchmatched: false watchtraversed: false outer_nullsonly: false other_condexist: false [2023-05-28 01:15:39.539616] [306195] [INFO] [parallel_hash_join.cpp:491] MSG: ExecuteJoin over traversed_dims_size: 1016 matched_dims_size: 3251200 joined_tuples: 1016 outertuples: 0

adofsauron commented 1 year ago

由此可见，三个表，虽然第一个表作为外表，但是在内连接时，将第一个表和第二个表的连接结果作为外表，然后与第三个表做连接

adofsauron commented 1 year ago

joined_tuples: 3 outertuples: 2

adofsauron commented 1 year ago

关于被驱动表的集合交对外成为了叉乘

adofsauron commented 1 year ago

这个连接搞出的查询的物理执行计划吧，真是直白又粗暴，一点不考虑性能，详细分析充值299块钱给我然后去看看，但是要是没钱也不想充钱，那就只记住结论就行了，由本修罗帝尊来处理全部的细节 https://blog.csdn.net/adofsauron/article/details/130913315?spm=1001.2014.3001.5501

adofsauron commented 1 year ago

不过更为重要的是在包理论模型下，重构外连接与联合内连接的处理规则，有点意思，我倒是读过一些这方面的分析，不过还需要更多的细节

adofsauron commented 1 year ago

有点意思，关于如何处理多表的join，mysql简化成了两两之间进行，但是现在倒是出乎寻常的直接

adofsauron commented 1 year ago

作为另一款吊炸天的列存数据库，看看monetdb是怎么处理的：


| function user.main():void;                                                                                                                                                                 |
|     X_1:void := querylog.define("explain \nselect b.b1,x.c1 from b \nleft join \n(\n select c1 from c inner join a on a.a1 = c.c1\n) x\non b.b1 = x.c1;":str, "default_pipe":str, 47:int); |
| barrier X_126:bit := language.dataflow();                                                                                                                                                  |
|     X_4:int := sql.mvc();                                                                                                                                                                  |
|     C_5:bat[:oid] := sql.tid(X_4:int, "sys":str, "b":str);                                                                                                                                 |
|     X_8:bat[:int] := sql.bind(X_4:int, "sys":str, "b":str, "b1":str, 0:int);                                                                                                               |
|     C_15:bat[:oid] := sql.tid(X_4:int, "sys":str, "a":str);                                                                                                                                |
|     X_17:bat[:int] := sql.bind(X_4:int, "sys":str, "a":str, "a1":str, 0:int);                                                                                                              |
|     C_22:bat[:oid] := sql.tid(X_4:int, "sys":str, "c":str);                                                                                                                                |
|     X_24:bat[:int] := sql.bind(X_4:int, "sys":str, "c":str, "c1":str, 0:int);                                                                                                              |
|     X_29:bat[:int] := algebra.projection(C_15:bat[:oid], X_17:bat[:int]);                                                                                                                  |
|     X_30:bat[:int] := algebra.projection(C_22:bat[:oid], X_24:bat[:int]);                                                                                                                  |
|     X_32:bat[:oid] := algebra.join(X_30:bat[:int], X_29:bat[:int], nil:BAT, nil:BAT, false:bit, nil:lng);                                                                                  |
|     X_38:bat[:int] := algebra.projection(X_32:bat[:oid], X_30:bat[:int]);                                                                                                                  |
|     X_39:bat[:int] := algebra.projection(C_5:bat[:oid], X_8:bat[:int]);                                                                                                                    |
|     (X_40:bat[:oid], X_41:bat[:oid]) := algebra.join(X_39:bat[:int], X_38:bat[:int], nil:BAT, nil:BAT, false:bit, nil:lng);                                                                |
|     C_42:bat[:oid] := bat.mirror(X_39:bat[:int]);                                                                                                                                          |
|     C_43:bat[:oid] := algebra.difference(C_42:bat[:oid], X_40:bat[:oid], nil:BAT, nil:BAT, false:bit, false:bit, nil:lng);                                                                 |
|     X_44:bat[:int] := algebra.projection(X_40:bat[:oid], X_39:bat[:int]);                                                                                                                  |
|     X_45:bat[:int] := bat.new(nil:int);                                                                                                                                                    |
|     X_47:bat[:int] := bat.append(X_45:bat[:int], X_44:bat[:int], true:bit);                                                                                                                |
|     X_49:bat[:int] := algebra.projection(C_43:bat[:oid], X_39:bat[:int]);                                                                                                                  |
|     X_50:bat[:int] := bat.append(X_47:bat[:int], X_49:bat[:int], true:bit);                                                                                                                |
|     X_57:bat[:int] := algebra.projection(X_41:bat[:oid], X_38:bat[:int]);                                                                                                                  |
|     X_58:bat[:int] := bat.new(nil:int);                                                                                                                                                    |
|     X_59:bat[:int] := bat.append(X_58:bat[:int], X_57:bat[:int], true:bit);                                                                                                                |
|     X_61:bat[:int] := algebra.project(C_43:bat[:oid], nil:int);                                                                                                                            |
|     X_62:bat[:int] := bat.append(X_59:bat[:int], X_61:bat[:int], true:bit);                                                                                                                |
|     X_64:bat[:str] := bat.pack(".b":str, ".x":str);                                                                                                                                        |
|     X_65:bat[:str] := bat.pack("b1":str, "c1":str);                                                                                                                                        |
|     X_66:bat[:str] := bat.pack("int":str, "int":str);                                                                                                                                      |
|     X_67:bat[:int] := bat.pack(32:int, 32:int);                                                                                                                                            |
|     X_68:bat[:int] := bat.pack(0:int, 0:int);                                                                                                                                              |
|     X_128:void := language.pass(X_30:bat[:int]);                                                                                                                                           |
|     X_129:void := language.pass(X_40:bat[:oid]);                                                                                                                                           |
|     X_130:void := language.pass(X_39:bat[:int]);                                                                                                                                           |
|     X_131:void := language.pass(X_38:bat[:int]);                                                                                                                                           |
|     X_132:void := language.pass(C_43:bat[:oid]);                                                                                                                                           |
| exit X_126:bit;                                                                                                                                                                            |
|     X_63:int := sql.resultSet(X_64:bat[:str], X_65:bat[:str], X_66:bat[:str], X_67:bat[:int], X_68:bat[:int], X_50:bat[:int], X_62:bat[:int]);                                             |
| end user.main;                                                                                                                                                                             |
| #inline               actions= 0 time=1 usec                                                                                                                                               |
| #remap                actions= 0 time=1 usec                                                                                                                                               |
| #costmodel            actions= 1 time=2 usec                                                                                                                                               |
| #coercion             actions= 0 time=2 usec                                                                                                                                               |
| #aliases              actions= 2 time=7 usec                                                                                                                                               |
| #evaluate             actions= 0 time=7 usec                                                                                                                                               |
| #emptybind            actions= 3 time=8 usec                                                                                                                                               |
| #deadcode             actions= 9 time=10 usec                                                                                                                                              |
| #pushselect           actions= 0 time=3 usec                                                                                                                                               |
| #aliases              actions= 3 time=5 usec                                                                                                                                               |
| #mitosis              actions=0 time=7 usec                                                                                                                                                |
| #mergetable           actions= 0 time=1 usec                                                                                                                                               |
| #aliases              actions= 0 time=0 usec                                                                                                                                               |
| #constants            actions= 1 time=8 usec                                                                                                                                               |
| #commonTerms          actions= 0 time=6 usec                                                                                                                                               |
| #projectionpath       actions= 0 time=4 usec                                                                                                                                               |
| #deadcode             actions= 0 time=4 usec                                                                                                                                               |
| #reorder              actions= 1 time=1 usec                                                                                                                                               |
| #matpack              actions= 0 time=1 usec                                                                                                                                               |
| #dataflow             actions= 1 time=19 usec                                                                                                                                              |
| #multiplex            actions= 0 time=1 usec                                                                                                                                               |
| #candidates           actions= 1 time=2 usec                                                                                                                                               |
| #deadcode             actions= 0 time=3 usec                                                                                                                                               |
| #postfix              actions= 1 time=7 usec                                                                                                                                               |
| #wlc                  actions= 0 time=1 usec                                                                                                                                               |
| #garbagecollector     actions= 1 time=18 usec                                                                                                                                              |
| #profiler             actions= 1 time=1 usec                                                                                                                                               |
| #total                actions=30 time=215 usec
adofsauron commented 1 year ago 

+---------------------------------------------+
| rel                                         |
+=============================================+
| project (                                   |
| | left outer join (                         |
| | | table("sys"."b") [ "b"."b1" ] COUNT ,   |
| | | join (                                  |
| | | | table("sys"."a") [ "a"."a1" ] COUNT , |
| | | | table("sys"."c") [ "c"."c1" ] COUNT   |
| | | ) [ "a"."a1" = "c"."c1" ]               |
| | ) [ "b"."b1" = "c"."c1" ]                 |
| ) [ "b"."b1", "c"."c1" as "x"."c1" ]        |
+---------------------------------------------+
adofsauron commented 1 year ago

可以很明显的看出，虽然和stonedb一样都采用了列的BAT语言重建了查询计划，但是monteb是先执行内连接，然后将结果与外表进行外连接

adofsauron commented 1 year ago

但是使用了merge join来处理内连接，然后用选择排序来处理外连接

+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| usec | statement                                                                                                                                                                              |
+======+========================================================================================================================================================================================+
|    3 | X_0=0@0:void := querylog.define("trace \nselect b.b1,x.c1 from b \nleft join \n(\n select c1 from c inner join a on a.a1 = c.c1\n) x\non b.b1 = x.c1;":str, "default_pipe":str, 47:int |
:      : );                                                                                                                                                                                     :
|    4 | X_1=0:int := sql.mvc();                                                                                                                                                                |
|   37 | X_2=[2]:bat[:str] := bat.pack("b1":str, "c1":str);                                                                                                                                     |
|   15 | X_3=[2]:bat[:str] := bat.pack("int":str, "int":str);                                                                                                                                   |
|   18 | X_4=[2]:bat[:int] := bat.pack(32:int, 32:int);                                                                                                                                         |
|    4 | X_7=[0]:bat[:int] := bat.new(nil:int);                                                                                                                                                 |
|   27 | X_5=[2]:bat[:int] := bat.pack(0:int, 0:int);                                                                                                                                           |
|   13 | X_8=[0]:bat[:int] := bat.new(nil:int);                                                                                                                                                 |
|   17 | X_6=[2]:bat[:str] := bat.pack(".b":str, ".x":str);                                                                                                                                     |
|   26 | C_9=[3]:bat[:oid] := sql.tid(X_1=0:int, "sys":str, "b":str);                                                                                                                           |
|   30 | X_10=[2]:bat[:int] := sql.bind(X_1=0:int, "sys":str, "a":str, "a1":str, 0:int);                                                                                                        |
|    6 | C_12=[2]:bat[:oid] := sql.tid(X_1=0:int, "sys":str, "a":str);                                                                                                                          |
|   16 | C_11=[4]:bat[:oid] := sql.tid(X_1=0:int, "sys":str, "c":str);                                                                                                                          |
|    4 | X_13=[3]:bat[:int] := sql.bind(X_1=0:int, "sys":str, "b":str, "b1":str, 0:int);                                                                                                        |
|   14 | X_14=[3]:bat[:int] := algebra.projection(C_9=[3]:bat[:oid], X_13=[3]:bat[:int]);                                                                                                       |
|   11 | X_15=[4]:bat[:int] := sql.bind(X_1=0:int, "sys":str, "c":str, "c1":str, 0:int);                                                                                                        |
|   11 | X_16=[2]:bat[:int] := algebra.projection(C_12=[2]:bat[:oid], X_10=[2]:bat[:int]);                                                                                                      |
|    7 | C_17=[3]:bat[:oid] := bat.mirror(X_14=[3]:bat[:int]);                                                                                                                                  |
|    6 | X_18=[4]:bat[:int] := algebra.projection(C_11=[4]:bat[:oid], X_15=[4]:bat[:int]);                                                                                                      |
|   30 | X_19=[1]:bat[:oid] := algebra.join(X_18=[4]:bat[:int], X_16=[2]:bat[:int], nil:BAT, nil:BAT, false:bit, nil:lng); # mergejoin                                                          |
|   16 | X_20=[1]:bat[:int] := algebra.projection(X_19=[1]:bat[:oid], X_18=[4]:bat[:int]);                                                                                                      |
|    2 | X_21=0@0:void := language.pass(X_18=[4]:bat[:int]);                                                                                                                                    |
|   39 | (X_22=[1]:bat[:oid], X_23=[1]:bat[:oid]) := algebra.join(X_14=[3]:bat[:int], X_20=[1]:bat[:int], nil:BAT, nil:BAT, false:bit, nil:lng); # selectjoin; select: sorted                   |
|   10 | C_24=[2]:bat[:oid] := algebra.difference(C_17=[3]:bat[:oid], X_22=[1]:bat[:oid], nil:BAT, nil:BAT, false:bit, false:bit, nil:lng); # leftjoin; mergejoin_void; select: dense           |
|   10 | X_25=[1]:bat[:int] := algebra.projection(X_22=[1]:bat[:oid], X_14=[3]:bat[:int]);                                                                                                      |
|    4 | X_26=[1]:bat[:int] := bat.append(X_7=[1]:bat[:int], X_25=[1]:bat[:int], true:bit);                                                                                                     |
|    3 | X_27=[1]:bat[:int] := algebra.projection(X_23=[1]:bat[:oid], X_20=[1]:bat[:int]);                                                                                                      |
|    0 | X_28=0@0:void := language.pass(X_20=[1]:bat[:int]);                                                                                                                                    |
|    9 | X_29=0@0:void := language.pass(X_22=[1]:bat[:oid]);                                                                                                                                    |
|    8 | X_30=[2]:bat[:int] := algebra.projection(C_24=[2]:bat[:oid], X_14=[3]:bat[:int]);                                                                                                      |
|   12 | X_31=[2]:bat[:int] := algebra.project(C_24=[2]:bat[:oid], nil:int);                                                                                                                    |
|    7 | X_32=[1]:bat[:int] := bat.append(X_8=[1]:bat[:int], X_27=[1]:bat[:int], true:bit);                                                                                                     |
|    2 | X_33=0@0:void := language.pass(X_14=[3]:bat[:int]);                                                                                                                                    |
|    2 | X_34=0@0:void := language.pass(C_24=[2]:bat[:oid]);                                                                                                                                    |
|    6 | X_35=[3]:bat[:int] := bat.append(X_32=[3]:bat[:int], X_31=[2]:bat[:int], true:bit);                                                                                                    |
|    4 | X_36=[3]:bat[:int] := bat.append(X_26=[3]:bat[:int], X_30=[2]:bat[:int], true:bit);                                                                                                    |
| 1882 | barrier X_37=false:bit := language.dataflow();                                                                                                                                         |
|  104 | X_38=7:int := sql.resultSet(X_6=[2]:bat[:str], X_2=[2]:bat[:str], X_3=[2]:bat[:str], X_4=[2]:bat[:int], X_5=[2]:bat[:int], X_36=[3]:bat[:int], X_35=[3]:bat[:int]);                    |
+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
adofsauron commented 1 year ago

2023-05-28 22:59:21 M_DEBUG ALGO client4 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling querylog.define [1, 0] 2023-05-28 22:59:21 M_DEBUG ALGO client4 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.dataflow [1, 0] 2023-05-28 22:59:21 M_DEBUG PAR client4 gdk/gdk_utils.c:1610 THRnew 1f 18446744073709551615 sp = 140052245909564 2023-05-28 22:59:21 M_DEBUG PAR client4 gdk/gdk_utils.c:1612 THRnew Number of threads: 36 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker19 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.pack [29, 30] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker11 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.mvc [3, 4] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker0 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.pack [32, 33] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker10 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.pack [31, 32] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.bind [5, 6] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker10 gdk/gdk_bat.c:296 COLnew_intern -> tmp_557#0@0[int]TSRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker28 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.tid [6, 7] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker28 gdk/gdk_bat.c:296 COLnew_intern -> tmp_522#0@0[void]TSRK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker28 gdk/gdk_bat.c:328 BATdense 0,0,2-> tmp_522#2@0[void]TDSKN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.bind [7, 8] 2023-05-28 22:59:21 MDEBUG IO DFLOWworker25 gdk/gdk_bbp.c:2911 getBBPdescriptor load tmp_266 2023-05-28 22:59:21 MDEBUG IO DFLOWworker25 gdk/gdk_storage.c:631 DESCload DESCload: 02/266 2023-05-28 22:59:21 MDEBUG IO DFLOWworker25 gdk/gdk_storage.c:530 GDKload GDKload: name=02/266.tail, ext=, mode 1 2023-05-28 22:59:21 MDEBUG IO DFLOWworker25 gdk/gdk_storage.c:552 GDKload read(dst 0x7f6018001390, n_expected 8, fd 10) = 8 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 gdk/gdk_align.c:154 VIEWcreate tmp_266#2@0[int]PS!rK -> tmp_614#2@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 gdk/gdk_batop.c:1903 BATslice b=tmp_266#2@0[int]PS!rK,lo=0,hi=2 -> tmp_614#2@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [10, 11] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 gdk/gdk_align.c:154 VIEWcreate tmp_614#2@0[int]VS!rK -> tmp_532#2@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 gdk/gdk_batop.c:1903 BATslice b=tmp_614#2@0[int]VS!rK,lo=0,hi=2 -> tmp_532#2@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker25 gdk/gdk_project.c:818 BATproject2 l=tmp_522#2@0[void]TDSKN r1=tmp_614#2@0[int]VS!rK r2=00 -> tmp_532#2@0[int]VS!rK (slice) 13us 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker19 gdk/gdk_bat.c:296 COLnew_intern -> tmp_517#0@0[str]TESRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker11 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.tid [4, 5] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker11 gdk/gdk_bat.c:296 COLnew_intern -> tmp_614#0@0[void]TSRK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker11 gdk/gdk_bat.c:328 BATdense 0,0,3-> tmp_614#3@0[void]TDSKN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker20 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.new [24, 25] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker20 gdk/gdk_bat.c:296 COLnew_intern -> tmp_522#0@0[int]TSRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker27 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.pack [30, 31] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker27 gdk/gdk_bat.c:296 COLnew_intern -> tmp_572#0@0[str]TESRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker30 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.pack [28, 29] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker0 gdk/gdk_bat.c:296 COLnew_intern -> tmp_566#0@0[int]TSRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker30 gdk/gdk_bat.c:296 COLnew_intern -> tmp_534#0@0[str]TESRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker21 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.tid [8, 9] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker21 gdk/gdk_bat.c:296 COLnew_intern -> tmp_610#0@0[void]TSRK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker21 gdk/gdk_bat.c:328 BATdense 0,0,4-> tmp_610#4@0[void]TDSKN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker17 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling bat.new [19, 20] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker17 gdk/gdk_bat.c:296 COLnew_intern -> tmp_524#0@0[int]TSRN 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_bbp.c:2911 getBBPdescriptor load tmp_263 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:631 DESCload DESCload: 02/263 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:530 GDKload GDKload: name=02/263.tail, ext=, mode 1 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:552 GDKload read(dst 0x7f6044000d80, n_expected 12, fd 10) = 12 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_align.c:154 VIEWcreate tmp_263#3@0[int]PS!rK -> tmp_574#3@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_batop.c:1903 BATslice b=tmp_263#3@0[int]PS!rK,lo=0,hi=3 -> tmp_574#3@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.bind [9, 10] 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_bbp.c:2911 getBBPdescriptor load tmp_271 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:631 DESCload DESCload: 02/271 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:530 GDKload GDKload: name=02/271.tail, ext=, mode 1 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:552 GDKload read(dst 0x7f60440016b0, n_expected 16, fd 10) = 16 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [14, 15] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 gdk/gdk_align.c:154 VIEWcreate tmp_574#3@0[int]VS!rK -> tmp_617#3@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 gdk/gdk_batop.c:1903 BATslice b=tmp_574#3@0[int]VS!rK,lo=0,hi=3 -> tmp_617#3@0[int]VS!rK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_align.c:154 VIEWcreate tmp_271#4@0[int]P!s!r!kH -> tmp_577#4@0[int]V!s!r!k 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_batop.c:1903 BATslice b=tmp_271#4@0[int]P!s!r!kH,lo=0,hi=4 -> tmp_577#4@0[int]V!r 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 gdk/gdk_project.c:818 BATproject2 l=tmp_614#3@0[void]TDSKN r1=tmp_574#3@0[int]VS!rK r2=00 -> tmp_617#3@0[int]VS!rK (slice) 17us 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [11, 12] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_align.c:154 VIEWcreate tmp_577#4@0[int]V!r -> tmp_574#4@0[int]V!r 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling bat.mirror [16, 17] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_batop.c:1903 BATslice b=tmp_577#4@0[int]V!r,lo=0,hi=4 -> tmp_574#4@0[int]V!r 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 gdk/gdk_bat.c:296 COLnew_intern -> tmp_614#0@0[void]TSRK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_project.c:818 BATproject2 l=tmp_610#4@0[void]TDSKN r1=tmp_577#4@0[int]V!r r2=00 -> tmp_574#4@0[int]V!r (slice) 14us 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker12 gdk/gdk_bat.c:328 BATdense 0,0,3-> tmp_614#3@0[void]TDSKN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.join [12, 13] 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:530 GDKload GDKload: name=02/271, ext=thashl, mode 1 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:552 GDKload read(dst 0x7f60440012d0, n_expected 8, fd 11) = 8 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:530 GDKload GDKload: name=02/271, ext=thashb, mode 1 2023-05-28 22:59:21 MDEBUG IO DFLOWworker18 gdk/gdk_storage.c:552 GDKload read(dst 0x7f6044001ae0, n_expected 568, fd 11) = 568 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_bat.c:296 COLnew_intern -> tmp_577#0@0[oid]TSRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_bat.c:296 COLnew_intern -> tmp_610#0@0[oid]TSRN 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_join.c:2673 hashjoin tmp_271#4@0[int]P!s!r!kH: using existing hash (swapped) 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_join.c:2695 hashjoin hash for tmp_271#4@0[int]P!s!r!kH: nbucket 256, nunique 3, nheads 3 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_join.c:2940 hashjoin l=tmp_266#2@0[int]PS!rK,r=tmp_271#4@0[int]P!s!r!kH,sl=00,sr=00,nil_matches=false,nil_on_miss=false,semi=false,only_misses=false,not_in=false,max_one=false,min_one=false; swapped BATjoin -> tmp_577#1@0[oid]TDSRKN,tmp_610#1@0[oid]TDSRKN (79usec) 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [13, 14] 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_align.c:154 VIEWcreate tmp_574#4@0[int]V!r -> tmp_532#4@0[int]V!r 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_batop.c:1903 BATslice b=tmp_574#4@0[int]V!r,lo=0,hi=1 -> tmp_532#1@0[int]VSRK 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 gdk/gdk_project.c:818 BATproject2 l=tmp_610#1@0[oid]TDSRKN r1=tmp_574#4@0[int]V!r r2=00 -> tmp_532#1@0[int]VSRK (slice) 8us 2023-05-28 22:59:21 M_DEBUG ALGO DFLOWworker18 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.pass [33, 34] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.join [15, 16] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:296 COLnew_intern -> tmp_574#0@0[void]TSRK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:328 BATdense 0,0,1-> tmp_574#1@0[void]TDSRKN 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_select.c:1807 BATselect b=tmp_263#3@0[int]PS!rK,anti=false -> tmp_574#1@0[void]TDSRKN select: sorted (28 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:296 COLnew_intern -> tmp_610#0@0[oid]TSRN 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:296 COLnew_intern -> tmp_577#0@0[oid]TSRN 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_join.c:410 selectjoin l=tmp_532#1@0[int]VSRK,r=tmp_263#3@0[int]PS!rK,sl=00,sr=00,nil_matches=false; swapped BATjoin -> tmp_610#1@0[oid]TDSRKN,tmp_577#1@0[oid]TDSRKN (82usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.difference [17, 18] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:296 COLnew_intern -> tmp_574#0@0[void]TSRK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_bat.c:328 BATdense 0,1,2-> tmp_574#2@0[void]TDSKN 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_select.c:1807 BATselect b=tmp_614#3@0[void]TDSKN,anti=false -> tmp_574#2@0[void]TDSKN select: dense (15 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_join.c:759 mergejoin_void l=tmp_614#3@0[void]TDSKN,r=tmp_577#1@0[oid]TDSRKN,sl=00,sr=00,nil_on_miss=false,only_misses=true; BATdiff -> tmp_574#2@0[void]TDSKN,00 (21usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker4 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [23, 24] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [18, 19] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker4 gdk/gdk_align.c:154 VIEWcreate tmp_532#1@0[int]VSRK -> tmp_614#1@0[int]VSRK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker4 gdk/gdk_batop.c:1903 BATslice b=tmp_532#1@0[int]VSRK,lo=0,hi=1 -> tmp_614#1@0[int]VSRK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 gdk/gdk_align.c:154 VIEWcreate tmp_617#3@0[int]VS!rK -> tmp_535#3@0[int]VS!rK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 gdk/gdk_batop.c:1903 BATslice b=tmp_617#3@0[int]VS!rK,lo=0,hi=1 -> tmp_535#1@0[int]VSRK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 gdk/gdk_project.c:818 BATproject2 l=tmp_577#1@0[oid]TDSRKN r1=tmp_617#3@0[int]VS!rK r2=00 -> tmp_535#1@0[int]VSRK (slice) 17us 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker4 gdk/gdk_project.c:818 BATproject2 l=tmp_610#1@0[oid]TDSRKN r1=tmp_532#1@0[int]VSRK r2=00 -> tmp_614#1@0[int]VSRK (slice) 14us 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling bat.append [20, 21] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker23 gdk/gdk_batop.c:929 BATappend2 b=tmp_524#0@0[int]TSRKN,n=tmp_535#1@0[int]VSRK,s=00 -> tmp_524#1@0[int]TSRK (3 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling algebra.projection [21, 22] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker4 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.pass [36, 37] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_align.c:154 VIEWcreate tmp_617#3@0[int]VS!rK -> tmp_610#3@1[int]VS!rK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_batop.c:1903 BATslice b=tmp_617#3@0[int]VS!rK,lo=1,hi=3 -> tmp_610#2@1[int]VSK 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker5 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.pass [34, 35] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker16 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling bat.append [25, 26] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker16 gdk/gdk_batop.c:929 BATappend2 b=tmp_522#0@0[int]TSRKN,n=tmp_614#1@0[int]VSRK,s=00 -> tmp_522#1@0[int]TSRK (2 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 gdk/gdk_project.c:818 BATproject2 l=tmp_574#2@0[void]TDSKN r1=tmp_617#3@0[int]VS!rK r2=00 -> tmp_610#2@0[int]VSK (slice) 73us 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker8 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling algebra.project [26, 27] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker8 gdk/gdk_bat.c:296 COLnew_intern -> tmp_614#0@0[int]TSRN 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker8 gdk/gdk_batop.c:2805 BATconstant -> tmp_614#2@0[int]TSR 58usec 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker9 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.pass [35, 36] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker8 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling bat.append [27, 28] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker24 monetdb5/mal/mal_interpreter.c:674 runMALsequence calling bat.append [22, 23] 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker8 gdk/gdk_batop.c:929 BATappend2 b=tmp_522#1@0[int]TSRK,n=tmp_614#2@0[int]TSR!k,s=00 -> tmp_522#3@0[int]TR (3 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker24 gdk/gdk_batop.c:929 BATappend2 b=tmp_524#1@0[int]TSRK,n=tmp_610#2@0[int]VS!rK,s=00 -> tmp_524#3@0[int]TSK (2 usec) 2023-05-28 22:59:22 M_DEBUG ALGO DFLOWworker6 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling language.pass [37, 38] 2023-05-28 22:59:22 M_DEBUG ALGO client4 monetdb5/mal/mal_interpreter.c:645 runMALsequence calling sql.resultSet [1, 0] 2023-05-28 22:59:22 M_DEBUG PAR DFLOWworker26 gdk/gdk_utils.c:1692 THRdel pid = 39, disconnected, 36 left

adofsauron commented 1 year ago

成本估算还没有使用任何关于实际数据分布的统计数据。它依赖于前端或其他优化器提供的行属性。它只是应用了一些启发式成本估算器

adofsauron commented 1 year ago

内连接使用hash join倒是十分合理，除了实现上的不同

| 133 | X_19=[1]:bat[:oid] := algebra.join(X_16=[4]:bat[:int], X_14=[2]:bat[:int], nil:BAT, nil:BAT, false:bit, nil:lng); # hashjoin using existing hash (swapped) |

adofsauron commented 1 year ago

对应到stonedb里，在对内连接做处理的时候，就开始走向了分歧

adofsauron commented 1 year ago

所以可以分析出，问题并不是出在具体操作符的物理计划的实现上，而是对多表之间连接的语义实现上

adofsauron commented 1 year ago

具体到代码上，以下两个函数脱不了干系


void CompiledQuery::LeftJoinOn(const TabID &temp_table, std::vector<TabID> &left_tables,
                               std::vector<TabID> &right_tables, const CondID &cond_id) {
  CompiledQuery::CQStep s;
  s.type = StepType::LEFT_JOIN_ON;
  s.t1 = temp_table;
  s.c1 = cond_id;
  s.tables1 = left_tables;
  s.tables2 = right_tables;
  steps.push_back(s);
}

void CompiledQuery::InnerJoinOn(const TabID &temp_table, std::vector<TabID> &left_tables,
                                std::vector<TabID> &right_tables, const CondID &cond_id) {
  CompiledQuery::CQStep s;
  s.type = StepType::INNER_JOIN_ON;
  s.t1 = temp_table;
  s.c1 = cond_id;
  s.tables1 = left_tables;
  s.tables1.insert(s.tables1.end(), right_tables.begin(), right_tables.end());
  steps.push_back(s);
}
adofsauron commented 1 year ago

相比monetdb的MAL， stonedb的BAT已经并非是列属性的关系代数的映射，而是成为了一种包含更为复杂操作的执行过程，考虑这一点的话，stonedb的执行序列就简直是个大杂烩

adofsauron commented 1 year ago

相比外连接这种不对称的连接关系，内连接是对称的，分别拆出与外连接的语义

adofsauron commented 1 year ago

作为一个伪代码的实现，可以这么理解当前的执行过程


FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t2 in T2 such that P1(t1,t2) {
    FOR each row t3 in T3 such that P2(t1,t3) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f1:=TRUE
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}
adofsauron commented 1 year ago

对于具有外部连接的查询，优化器只能选择外部表循环先于内部表循环的顺序。因此，对于我们的外连接查询，只有一种嵌套顺序是可能的。对于以下查询，优化器评估两个不同的嵌套。在两个嵌套中， T1必须在外循环中处理，因为它用于外连接。T2和 T3用于内部连接，因此连接必须在内循环中处理。但是，由于连接是内部连接，T2因此 T3可以按任意顺序处理

adofsauron commented 1 year ago

所以目标并不在于重写特定操作符的物理计划，而在于重新构建包含内连接的外连接的嵌套连接的执行关系。 由此开始进入设计阶段，设计目标围绕此进行。

adofsauron commented 1 year ago

这一步的条件上提简直是十足的愚蠢，a和c的叉乘再和b做连接，这个时候再考虑限制, 对于myql/sql的查询执行来说没问题，但是对于stonedb这么做简直就是强行增大了连接的元组数量


          {
            "transformations_to_nested_joins": {
              "transformations": [
                "JOIN_condition_to_WHERE",
                "parenthesis_removal"
              ],
              "expanded_query": "/* select#1 */ select `b`.`b1` AS `b1`,`c`.`c1` AS `c1` from `b` left join (`c` join `a`) on(((`b`.`b1` = `c`.`c1`) and (`a`.`a1` = `c`.`c1`)))"
            }
          }
adofsauron commented 1 year ago

去除这个条件上拉到where优化，stonedb的执行时间从14分钟减少的不到一秒钟，所以对于这个优化，对于stonedb来说是反作用，去掉

adofsauron commented 1 year ago

left_dims = { v = std::vector of length 3, capacity 64 = {1, 0, 0} }, right_dims = { v = std::vector of length 3, capacity 64 = {0, 1, 1} --Type for more, q to quit, c to continue without paging-- },

adofsauron commented 1 year ago

left_dims = { v = std::vector of length 3, capacity 64 = {1, 0, 0} }, right_dims = { v = std::vector of length 3, capacity 64 = {0, 0, 0}

adofsauron commented 1 year ago

记录下以下函数，将外连接转为内连接导致数据丢失


void ParameterizedFilter::SyntacticalDescriptorListPreprocessing(bool for_rough_query) {
  MEASURE_FET("ParameterizedFilter::SyntacticalDescriptorListPreprocessing(...)");

  // outer joins preprocessing (delaying conditions etc.)
  bool outer_join_found = false;
  uint no_desc = uint(descriptors_.Size());
  DimensionVector all_outer(mind_->NumOfDimensions());

  for (uint i = 0; i < no_desc; i++) {
    if (descriptors_[i].done || !descriptors_[i].IsOuter())
      continue;

    outer_join_found = true;
    all_outer.Plus(descriptors_[i].right_dims);
  }

  if (outer_join_found) {
    for (uint i = 0; i < no_desc; i++) {
      if (descriptors_[i].done || !descriptors_[i].IsInner())
        continue;

      DimensionVector inner(mind_->NumOfDimensions());
      descriptors_[i].DimensionUsed(inner);
      if (all_outer.Intersects(inner)) {
        if (descriptors_[i].NullMayBeTrue()) {
          descriptors_[i].delayed = true;  // delayed, i.e. must be calculated after nulls occur
        } else {
          // e.g. t1 LEFT JOIN t2 ON a1=a2 WHERE t2.c = 5   - in such cases
          // all nulls are excluded anyway,
          //                                                  so it is an
          //                                                  equivalent of
          //                                                  inner join
          all_outer.Minus(inner);  // set all involved dimensions as no longer outer
        }
      }
    }

    for (uint j = 0; j < no_desc; j++) {
      if (descriptors_[j].done || !descriptors_[j].IsOuter() || all_outer.Intersects(descriptors_[j].right_dims))
        continue; /*[descriptors_[i].outer_dim])*/

      descriptors_[j].right_dims.Clean();
      /*outer_dim = -1;*/  // change outer joins to inner (these identified above)
    }
  }

  bool false_desc = false;

  // descriptor preparation (normalization etc.)
  for (uint i = 0; i < no_desc; i++) {      // Note that desc.size() may enlarge
                                            // when joining with BETWEEN occur
    assert(descriptors_[i].done == false);  // If not false, check it carefully.
    if (descriptors_[i].IsTrue()) {
      if (descriptors_[i].IsInner())
        descriptors_[i].done = true;
      continue;
    } else if (descriptors_[i].IsFalse())
      continue;

    if (descriptors_[i].IsDelayed())
      continue;

    assert(descriptors_[i].lop == common::LogicalOperator::O_AND);
    // if(descriptors_[i].lop != common::LogicalOperator::O_AND && descriptors_[i].IsType_Join() &&
    // (descriptors_[i].op == common::Operator::O_BETWEEN || descriptors_[i].op ==
    // common::Operator::O_NOT_BETWEEN))
    //  throw common::NotImplementedException("This kind of join condition with
    // OR is not
    // implemented.");

    // normalization of descriptor of type 1 between a and b
    if (descriptors_[i].op == common::Operator::O_BETWEEN) {
      if (descriptors_[i].GetJoinType() != DescriptorJoinType::DT_COMPLEX_JOIN && !descriptors_[i].IsType_Join() &&
          descriptors_[i].attr.vc && descriptors_[i].attr.vc->IsConst()) {
        std::swap(descriptors_[i].attr.vc, descriptors_[i].val1.vc);
        descriptors_[i].op = common::Operator::O_LESS_EQ;

        // now, the second part
        Descriptor dd(table_, mind_->NumOfDimensions());
        dd.attr = descriptors_[i].val2;
        descriptors_[i].val2.vc = nullptr;
        dd.op = common::Operator::O_MORE_EQ;
        dd.val1 = descriptors_[i].val1;
        dd.done = false;
        dd.left_dims = descriptors_[i].left_dims;
        dd.right_dims = descriptors_[i].right_dims;
        dd.CalculateJoinType();

        descriptors_[i].CalculateJoinType();
        descriptors_.AddDescriptor(dd);

        no_desc++;
      } else if (descriptors_[i].IsType_JoinSimple()) {
        // normalization of descriptor of type a between 1 and b
        descriptors_[i].op = common::Operator::O_MORE_EQ;
        Descriptor dd(table_, mind_->NumOfDimensions());
        dd.attr = descriptors_[i].attr;
        dd.val1 = descriptors_[i].val2;
        descriptors_[i].val2.vc = nullptr;
        dd.op = common::Operator::O_LESS_EQ;
        dd.done = false;
        dd.left_dims = descriptors_[i].left_dims;
        dd.right_dims = descriptors_[i].right_dims;
        dd.CalculateJoinType();

        descriptors_[i].CalculateJoinType();
        descriptors_.AddDescriptor(dd);

        no_desc++;
      }
    }

    descriptors_[i].CoerceColumnTypes();
    descriptors_[i].Simplify();
    if (descriptors_[i].IsFalse()) {
      false_desc = true;
    }
  }

  // join descriptor merging (before normalization, because we may then add a condition for another column)
  std::vector<Descriptor> added_cond;
  for (uint i = 0; i < no_desc; i++) {  // t1.x == t2.y && t2.y == 5   =>   t1.x == 5
    if (descriptors_[i].done || descriptors_[i].op != common::Operator::O_EQ || !descriptors_[i].IsType_JoinSimple() ||
        !descriptors_[i].IsInner())
      continue;

    // desc[i] is a joining (eq.) condition
    for (uint j = 0; j < descriptors_.Size(); j++) {
      if (i == j || descriptors_[j].done || !descriptors_[j].IsType_AttrValOrAttrValVal() || !descriptors_[j].IsInner())
        continue;

      // desc[j] is a second condition, non-join
      if (descriptors_[j].attr.vc == descriptors_[i].attr.vc) {
        // the same table_ and column
        if (descriptors_[j].op ==
            common::Operator::O_EQ) {  // t2.y == t1.x && t2.y == 5  change to  t1.x == 5 && t2.y == 5
          descriptors_[i].attr = descriptors_[i].val1;
          descriptors_[i].val1 = descriptors_[j].val1;
          descriptors_[i].CalculateJoinType();
          descriptors_[i].CoerceColumnTypes();
          break;
        } else {  // t2.y == t1.x && t2.y > 5  change to  t2.y == t1.x && t2.y > 5 && t1.x > 5
          Descriptor dd(table_, mind_->NumOfDimensions());
          dd.attr = descriptors_[i].val1;
          dd.op = descriptors_[j].op;
          dd.val1 = descriptors_[j].val1;
          dd.val2 = descriptors_[j].val2;
          dd.CalculateJoinType();
          dd.CoerceColumnTypes();
          added_cond.push_back(dd);
        }
      }

      if (descriptors_[j].attr.vc == descriptors_[i].val1.vc) {  // the same as above for val1
        // the same table_ and column
        if (descriptors_[j].op ==
            common::Operator::O_EQ) {  // t1.x == t2.y && t2.y == 5  change to  t1.x == 5 && t2.y == 5
          descriptors_[i].val1 = descriptors_[j].val1;
          descriptors_[i].CalculateJoinType();
          descriptors_[i].CoerceColumnTypes();
          break;
        } else {  // t1.x == t2.y && t2.y > 5  change to  t1.x == t2.y && t2.y > 5 && t1.x > 5
          Descriptor dd(table_, mind_->NumOfDimensions());
          dd.attr = descriptors_[i].attr;
          dd.op = descriptors_[j].op;
          dd.val1 = descriptors_[j].val1;
          dd.val2 = descriptors_[j].val2;
          dd.CalculateJoinType();
          dd.CoerceColumnTypes();
          added_cond.push_back(dd);
        }
      }
    }
  }

  if (!added_cond.empty() && tianmu_control_.isOn())
    tianmu_control_.lock(mind_->m_conn->GetThreadID())
        << "Adding " << int(added_cond.size()) << " conditions..." << system::unlock;

  for (uint i = 0; i < added_cond.size(); i++) {
    descriptors_.AddDescriptor(added_cond[i]);
    no_desc++;
  }

  // attribute-based transformation (normalization) of descriptors_
  // "attr-operator-value" and other, if possible
  if (!false_desc) {
    for (uint i = 0; i < no_desc; i++) {
      DimensionVector all_dims(mind_->NumOfDimensions());
      descriptors_[i].DimensionUsed(all_dims);
      bool additional_nulls_possible = false;

      for (int d = 0; d < mind_->NumOfDimensions(); d++) {
        if (all_dims[d] && mind_->GetFilter(d) == nullptr)
          additional_nulls_possible = true;
      }

      if (descriptors_[i].IsOuter())
        additional_nulls_possible = true;

      ConditionEncoder::EncodeIfPossible(descriptors_[i], for_rough_query, additional_nulls_possible);

      if (descriptors_[i].IsTrue()) {  // again, because something might be simplified
        if (descriptors_[i].IsInner())
          descriptors_[i].done = true;

        continue;
      }
    }

    // descriptor merging
    for (uint i = 0; i < no_desc; i++) {
      if (descriptors_[i].done || descriptors_[i].IsDelayed())
        continue;

      for (uint jj = i + 1; jj < no_desc; jj++) {
        if (descriptors_[jj].right_dims != descriptors_[i].right_dims || descriptors_[jj].done ||
            descriptors_[jj].IsDelayed())
          continue;

        if (TryToMerge(descriptors_[i], descriptors_[jj])) {
          tianmu_control_.lock(mind_->m_conn->GetThreadID()) << "Merging conditions..." << system::unlock;
          descriptors_[jj].done = true;
        }
      }
    }
  }
}
adofsauron commented 1 year ago 
for (uint j = 0; j < no_desc; j++) {
  if (descriptors_[j].done || !descriptors_[j].IsOuter() || all_outer.Intersects(descriptors_[j].right_dims))
    continue; /*[descriptors_[i].outer_dim])*/

  descriptors_[j].right_dims.Clean();
  /*outer_dim = -1;*/  // change outer joins to inner (these identified above)
}
adofsauron commented 1 year ago

当去除了对条件外推，保持原来的条件位置后，在stonedb的处理中，出现了两个问题:

  1. 存在将外连接转换为内连接的优化，但是该优化是直接进行，未考虑更为充分的外连接的语义，导致语义被破坏，现象就是外连接的查询结果错误
  2. 当去除外连接优化为内连接后，在hash join的处理中，嵌套外连接的查询对了，但是在客户POC的的查询中出现了冗余的叉乘
adofsauron commented 1 year ago

条件变换如下：


        descriptors_[i].op = common::Operator::O_MORE_EQ;
        Descriptor dd(table_, mind_->NumOfDimensions());
        dd.attr = descriptors_[i].attr;
        dd.val1 = descriptors_[i].val2;
        descriptors_[i].val2.vc = nullptr;
        dd.op = common::Operator::O_LESS_EQ;
        dd.done = false;
        dd.left_dims = descriptors_[i].left_dims;
        dd.right_dims = descriptors_[i].right_dims;
        dd.CalculateJoinType();

        descriptors_[i].CalculateJoinType();
        descriptors_.AddDescriptor(dd);
adofsauron commented 1 year ago

traversed_dims_size: 3251200 matched_dims_size: 1016 joined_tuples: 1032256 outertuples: 0