[MDEV-30603] Wrong result with non-default JOIN_CACHE_LEVEL=[4|5] and USE_STAT_TABLES=[NEVER|COMPLEMENTARY] Created: 2023-02-07  Updated: 2023-12-05

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: N/A
Fix Version/s: 11.0

Type: Bug Priority: Critical
Reporter: Elena Stepanova Assignee: Igor Babaev
Resolution: Unresolved Votes: 0
Labels: None

Attachments: File opt2.test    
Issue Links:
Blocks
is blocked by MDEV-30938 Wrong result with small join_buffer_s... Stalled
Problem/Incident
is caused by MDEV-26974 Improve selectivity and related costs... Closed
Relates

 Description   

I could only reproduce it on bb-11.0, but it is of course not a guarantee that it's feature-specific.

The dataset in the test case is dbt3 0.0001, i.e. ~1/10 of the dbt3 dataset which comes with MTR (lineitem ~600 rows).
The test case is attached, as it doesn't fit into JIRA description.

bb-11.0 527cc3e2c51e5bfb6899dd6bc65c25f92f0fe0bc

 
MariaDB [test]> SELECT SUM( l_partkey ) 
FROM region JOIN nation ON ( r_regionkey = n_regionkey ) 
LEFT JOIN supplier ON ( s_nationkey = n_nationkey ) JOIN partsupp ON ( s_suppkey = ps_suppkey ) 
RIGHT JOIN lineitem ON ( ps_partkey = l_partkey AND ps_suppkey = l_suppkey ) 
JOIN orders ON ( l_orderkey = o_orderkey ) 
WHERE o_comment IS NOT NULL OR n_comment IS NOT NULL AND ps_availqty = l_quantity;
 
+------------------+
 
| SUM( l_partkey ) |
 
+------------------+
 
|         15457500 |
 
+------------------+
 
1 row in set (0.657 sec)
 
 
 
MariaDB [test]> set USE_STAT_TABLES=DEFAULT, JOIN_BUFFER_SPACE_LIMIT=DEFAULT, JOIN_CACHE_LEVEL=DEFAULT;
 
Query OK, 0 rows affected (0.000 sec)
 
 
 
MariaDB [test]> SELECT SUM( l_partkey ) 
FROM region JOIN nation ON ( r_regionkey = n_regionkey ) 
LEFT JOIN supplier ON ( s_nationkey = n_nationkey ) JOIN partsupp ON ( s_suppkey = ps_suppkey ) 
RIGHT JOIN lineitem ON ( ps_partkey = l_partkey AND ps_suppkey = l_suppkey ) 
JOIN orders ON ( l_orderkey = o_orderkey ) 
WHERE o_comment IS NOT NULL OR n_comment IS NOT NULL AND ps_availqty = l_quantity;
 
+------------------+
 
| SUM( l_partkey ) |
 
+------------------+
 
|             6183 |
 
+------------------+
 
1 row in set (0.002 sec)

6183 is apparently the expected result.
Plan with the bigger result:

MariaDB [test]> explain extended SELECT SUM( l_partkey ) FROM region JOIN nation ON ( r_regionkey = n_regionkey ) LEFT JOIN supplier ON ( s_nationkey = n_nationkey ) JOIN partsupp ON ( s_suppkey = ps_suppkey ) RIGHT JOIN lineitem ON ( ps_partkey = l_partkey AND ps_suppkey = l_suppkey ) JOIN orders ON ( l_orderkey = o_orderkey ) WHERE o_comment IS NOT NULL OR n_comment IS NOT NULL AND ps_availqty = l_quantity;
 
+------+-------------+----------+------------+--------------------------------------------+-----------------------------+---------+-------------------------------------------------+------+----------+----------------------------------------------------------------------+
 
| id   | select_type | table    | type       | possible_keys                              | key                         | key_len | ref                                             | rows | filtered | Extra                                                                |
 
+------+-------------+----------+------------+--------------------------------------------+-----------------------------+---------+-------------------------------------------------+------+----------+----------------------------------------------------------------------+
 
|    1 | SIMPLE      | orders   | ALL        | PRIMARY                                    | NULL                        | NULL    | NULL                                            | 150  |   100.00 |                                                                      |
 
|    1 | SIMPLE      | lineitem | hash_ALL   | PRIMARY,i_l_orderkey,i_l_orderkey_quantity | #hash#PRIMARY               | 4       | test.orders.o_orderkey                          | 586  |     0.51 | Using join buffer (flat, BNLH join)                                  |
 
|    1 | SIMPLE      | supplier | hash_index | PRIMARY,i_s_nationkey                      | #hash#PRIMARY:i_s_nationkey | 4:5     | test.lineitem.l_suppkey                         | 1    |   100.00 | Using where; Using index; Using join buffer (incremental, BNLH join) |
 
|    1 | SIMPLE      | nation   | hash_ALL   | PRIMARY,i_n_regionkey                      | #hash#PRIMARY               | 4       | test.supplier.s_nationkey                       | 25   |     4.00 | Using where; Using join buffer (incremental, BNLH join)              |
 
|    1 | SIMPLE      | partsupp | hash_ALL   | PRIMARY,i_ps_partkey,i_ps_suppkey          | #hash#PRIMARY               | 8       | test.lineitem.l_partkey,test.lineitem.l_suppkey | 20   |     5.00 | Using where; Using join buffer (incremental, BNLH join)              |
 
|    1 | SIMPLE      | region   | hash_ALL   | PRIMARY                                    | #hash#PRIMARY               | 4       | test.nation.n_regionkey                         | 5    |    20.00 | Using join buffer (incremental, BNLH join)                           |
 
+------+-------------+----------+------------+--------------------------------------------+-----------------------------+---------+-------------------------------------------------+------+----------+----------------------------------------------------------------------+
 
6 rows in set, 1 warning (0.000 sec)
 
 
 
MariaDB [test]> show warnings;
 
+-------+------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Level | Code | Message                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
 
+-------+------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Note  | 1003 | select sum(`test`.`lineitem`.`l_partkey`) AS `SUM( l_partkey )` from `test`.`lineitem` left join (`test`.`region` join `test`.`nation` join `test`.`supplier` join `test`.`partsupp`) on(`test`.`partsupp`.`ps_partkey` = `test`.`lineitem`.`l_partkey` and `test`.`supplier`.`s_suppkey` = `test`.`lineitem`.`l_suppkey` and `test`.`partsupp`.`ps_suppkey` = `test`.`lineitem`.`l_suppkey` and `test`.`nation`.`n_nationkey` = `test`.`supplier`.`s_nationkey` and `test`.`region`.`r_regionkey` = `test`.`nation`.`n_regionkey` and `test`.`lineitem`.`l_suppkey` is not null and `test`.`supplier`.`s_nationkey` is not null and `test`.`lineitem`.`l_partkey` is not null and `test`.`lineitem`.`l_suppkey` is not null and `test`.`nation`.`n_regionkey` is not null) join `test`.`orders` where `test`.`lineitem`.`l_orderkey` = `test`.`orders`.`o_orderkey` and (`test`.`orders`.`o_comment` is not null or `test`.`nation`.`n_comment` is not null and `test`.`partsupp`.`ps_availqty` = `test`.`lineitem`.`l_quantity`) |
 
+-------+------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
1 row in set (0.000 sec)



 Comments   
Comment by Sergei Petrunia [ 2023-02-08 ]

One can get almost the same query plan on 11.0 vanilla. (there is difference in the access to the last table but I think it's not relevant).

Diff'ing EXPLAIN outputs:

--- /tmp/explain-json-11-orig.txt       2023-02-08 11:07:36.080736467 +0300
 
+++ /tmp/explain-json-bb11.txt  2023-02-08 11:12:20.409761413 +0300
 
@@ -29,7 +29,7 @@
 
             "used_key_parts": ["l_orderkey"],
 
             "ref": ["test.orders.o_orderkey"],
 
             "rows": 586,
 
-            "filtered": 0.170648471
 
+            "filtered": 0.511945367
 
           },
 
           "buffer_type": "flat",
 
           "buffer_size": "16Kb",
 
@@ -52,7 +52,7 @@
 
             "using_index": true
 
           },
 
           "buffer_type": "incremental",
 
-          "buffer_size": "8Kb",
 
+          "buffer_size": "24Kb",
 
           "join_type": "BNLH",
 
           "attached_condition": "trigcond(supplier.s_nationkey is not null and trigcond(lineitem.l_suppkey is not null and lineitem.l_partkey is not null and lineitem.l_suppkey is not null))"
 
         }
 
@@ -72,7 +72,7 @@
 
             "attached_condition": "nation.n_regionkey is not null"
 
           },
 
           "buffer_type": "incremental",
 
-          "buffer_size": "6Kb",
 
+          "buffer_size": "17Kb",
 
           "join_type": "BNLH",
 
           "attached_condition": "trigcond(orders.o_comment is not null or nation.n_comment is not null) and trigcond(nation.n_regionkey is not null)"
 
         }


 
 
@@ -91,7 +91,7 @@
 
             "filtered": 5
 
           },
 
           "buffer_type": "incremental",
 
-          "buffer_size": "29Kb",
 
+          "buffer_size": "84Kb",
 
           "join_type": "BNLH",
 
           "attached_condition": "trigcond(orders.o_comment is not null or nation.n_comment is not null and partsupp.ps_availqty = lineitem.l_quantity)"
 
         }


@@ -100,18 +100,18 @@
 
         "block-nl-join": {
 
           "table": {
 
             "table_name": "region",
 
-            "access_type": "hash_index",
 
+            "access_type": "hash_ALL",
 
             "possible_keys": ["PRIMARY"],
 
-            "key": "#hash#PRIMARY:PRIMARY",
 
-            "key_length": "4:4",
 
+            "key": "#hash#PRIMARY",
 
+            "key_length": "4",
 
             "used_key_parts": ["r_regionkey"],
 
             "ref": ["test.nation.n_regionkey"],
 
             "rows": 5,
 
-            "filtered": 20,
 
-            "using_index": true
 
+            "cost": 0.4033172,
 
+            "filtered": 20
 
           },
 
           "buffer_type": "incremental",
 
-          "buffer_size": "6Kb",
 
+          "buffer_size": "-37128",
 
           "join_type": "BNLH"
 
         }
 
       }

Comment by Sergei Petrunia [ 2023-02-08 ]

The 

+          "buffer_size": "-37128",

part is the first thing one needs to check.

Comment by Sergei Petrunia [ 2023-02-08 ]

Ok the negative join buffer size comes from this logic:

Consider a join order:

orders,
 
lineitem,
 
supplier, Using join buffer
 
nation, Using join buffer
 
partsupp, Using join buffer
 
region, Using join buffer

execution reaches JOIN_CACHE::alloc_buffer() for table region:

  int JOIN_CACHE::alloc_buffer()
 
  {
 
    ...
 
    for (tab= start_tab; tab!= join_tab;
 
         tab= next_linear_tab(join, tab, WITHOUT_BUSH_ROOTS))
 
    {
 
      cache= tab->cache;
 
      if (cache)
 
      {
 
        curr_min_buff_space_sz+= cache->get_min_join_buffer_size();
 
        curr_buff_space_sz+= cache->get_join_buffer_size();
 
      } 
    }
 
    curr_min_buff_space_sz+= min_buff_size;
 
    curr_buff_space_sz+= buff_size;

It computes the total buffer size by adding up join buffer sizes
in [this->start_tab... this->join_tab] case.

In our case
start_tab= partsupp
join_tab= region.

Buffer sizes are 

  partsupp: 89718
 
  region: 20719

The sum is 110437 which is 1 over the join_buff_space_limit=108544.

So, this if is taken:

    if (curr_min_buff_space_sz > join_buff_space_limit ||
 
        (curr_buff_space_sz > join_buff_space_limit &&
 
         (!optimize_buff_size ||
 
          join->shrink_join_buffers(join_tab, curr_buff_space_sz,
 
                                    join_buff_space_limit))))

and it calls shrink_join_buffers() to shrink buffers by 2%.
shrink_join_buffers() tries to shrink buffers for ALL tables:

    for (tab= first_linear_tab(this, WITHOUT_BUSH_ROOTS, WITHOUT_CONST_TABLES);
 
         tab != jt;
 
         tab= next_linear_tab(this, tab, WITHOUT_BUSH_ROOTS))
 
    {

We have:
Consider a join order:

orders,
 
lineitem,
 
supplier, Using join buffer  16886
 
nation, Using join buffer    18465 
partsupp, Using join buffer  89718 
region, Using join buffer  20719

so it goes there shrinking the buffer by 1% and subtracting it from
"curr_space" and "needed_space".

    cache= tab->cache;
 
    if (cache)
 
    { 
      size_t buff_size;
 
      if (needed_space < cache->get_min_join_buffer_size())
 
        return TRUE;
 
      if (cache->shrink_join_buffer_in_ratio(curr_space, needed_space))
 
      { 
        revise_cache_usage(tab);
 
        return TRUE;
 
      }
 
      buff_size= cache->get_join_buffer_size();
 
      curr_space-= buff_size;
 
      needed_space-= buff_size;

shrinking buffers by 1% doesn't let them fit into the needed_space.
cur_space and needed_space are "ulonglong" so soon we get an underflow and start to
operate on very large numbers.

Comment by Sergei Petrunia [ 2023-02-08 ]

Adding a trivial "cop-out" logic to avoid negative buffer sizes:

@@ -4437,8 +4447,13 @@ bool JOIN::shrink_join_buffers(JOIN_TAB *jt,
 
         revise_cache_usage(tab);
 
         return TRUE;
 
       }
 
       buff_size= cache->get_join_buffer_size();
 
       curr_space-= buff_size;
 
+      if (needed_space < buff_size)
 
+      {
 
+        return TRUE;
 
+      }
 
       needed_space-= buff_size;
 
     }
 
   }

Changes EXPLAIN not to use linked join buffers but the query output is still wrong.

Comment by Sergei Petrunia [ 2023-02-08 ]

But the above patch makes the query produce a nonsensical EXPLAIN: https://gist.github.com/spetrunia/bef22d46dd95b0da4f0885fa86706b60
what is "#hash#PRIMARY" when there is no "Using join buffer" ?

Comment by Sergei Petrunia [ 2023-02-08 ]

Fixing JOIN_CACHE::alloc_buffer() instead fixes the issue.

Comment by Sergei Petrunia [ 2023-02-10 ]

Fixed in bb-11.0 tree. I think , the fix should be backported to earlier versions

Comment by Julien Fritsch [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Comment by JiraAutomate [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Generated at Thu Feb 08 10:17:29 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.