MDEV-30699: Updated prev_record_reads() to be more exact

The old code in prev_record_reads() did give wrong estimates when a
join_buffer was used or if the table was depending on more than one
other tables. When join_cache is used, it will cause a re-order of row
combinations, which causes more calls to the engine for tables that
are depending on tables before the join_cached one.

The new prev_records_read() code provides more exact estimates and
should never give a 'too low estimate', assuming that the data to the
function is correct

The definition of prev_record_read() is also updated.
The new definition is:
  "Estimate the number of engine ha_index_read_calls for EQ_REF tables
  when taking into account the one-row-cache in join_read_always_key()"

The cost of using prev_record_reads() value is changed. The value is
now used similar as before to calculate the cost of the storage engine
calls. However the cost of the WHERE cost is changed to take into
account the total number of row combinations as the WHERE has to be
checked even if the one-row-cache is used. This makes the cost
slightly higher than before (for the same prev_record_reads() value).

Other things:
- Cached return value of prev_record_read() in best_access_path() to
  avoid some function calls.
- Fixed bug where position[].use_join_buffer was set in
  best_acess_path() when join buffer was not used. This confused the
  semi join optimizer to try to reoptimize plans that did not need to be
  reoptimized.
  The effect of the bug fix is that we avoid doing some re-optimziations
  with semi-joins when join_buffer is not used. In these cases the value
  shown for the 'Filtering' column in EXPLAIN EXTENDED may change.
- Added 'prev_record.cc' that was used to verify the logic in
  prev_record_reads().

Changes in test suite:
- EQ_REF tables are moved up to be earlier. This is because either the
  higher WHERE cost when EQ_REF is used with more row combination or
  change of cost when using join_cache.
- Filtered has changed (to the better) for some cases using semi-joins
  subselect_sj.test subselect_sj_jcl6.test

1 files changed, 466 insertions, 0 deletions

diff --git a/tests/prev_record.cc b/tests/prev_record.cc
new file mode 100644
index 00000000000..66fe8e6a464
--- /dev/null
+++ b/tests/prev_record.cc
@@ -0,0 +1,466 @@
+/* Copyright (c) 2023 MariaDB Corporation
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/*
+  This program simulates the MariaDB query process execution using
+  the SCAN, EQ_REF,  REF and join_cache (CACHE) row lookup methods.
+
+  The purpose is to verify that 'prev_record_reads()' function correctly
+  estimates the number of lookups we have to do for EQ_REF access
+  assuming we have 'one-row-cache' before the lookup.
+
+  The logic for the prev_record_reads() function in this file should
+  match the logic in sql_select.cc::prev_record_reads() in MariaDB 11.0
+  and above.
+
+  The program generates first a randomized plan with the above
+  methods, then executes a full 'query' processing and then lastly
+  checks that the number of EQ_REF engine lookups matches the
+  estimated number of lookups.
+
+  If the number of estimated lookups are not exact, the plan and
+  lookup numbers are printed. That a plan is printed is not to be
+  regarded as a failure. It's a failure only of the number of engine
+  calls are far greater than the number of estimated lookups.
+
+  Note that the estimated number of lookups are exact only if CACHE
+  refills == 1 and if the EQ_REF table only depends on one earlier
+  table.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <time.h>
+
+#define TABLES 21
+#define DEFAULT_TABLES 10
+#define CACHED_ROWS 10000
+#define unlikely(A) A
+
+enum JOIN_TYPE { SCAN, EQ_REF,  REF, CACHE };
+const char *type[]= { "SCAN", "EQ_REF", "REF", "CACHE"};
+
+typedef unsigned long long DEPEND;
+typedef unsigned int uint;
+typedef unsigned long long ulonglong;
+
+struct TABLE
+{
+  ulonglong data;
+  JOIN_TYPE type;
+  DEPEND map;
+  DEPEND ref_depend_map;
+  uint records_in_table;
+  uint matching_records;
+  uint last_key;
+  ulonglong lookups;
+  ulonglong *cache;                             // join cache
+  ulong cached_records;
+  ulong flushed_caches;
+};
+
+struct POSITION
+{
+  TABLE *table;
+  JOIN_TYPE type;
+  double records;
+  double record_count;
+  double records_out;
+  double prev_record_read;
+  double same_keys;
+  ulong refills;
+};
+
+uint opt_tables= DEFAULT_TABLES;
+bool verbose=0;
+uint rand_init;
+struct TABLE table[TABLES];
+struct POSITION positions[TABLES];
+
+void do_select(uint table_index);
+
+
+static void
+prev_record_reads(POSITION *position, uint idx, DEPEND found_ref,
+                  double record_count)
+{
+  double found= 1.0;
+  POSITION *pos_end= position - 1;
+  POSITION *cur_pos= position + idx;
+
+  /* Safety against const tables */
+  if (!found_ref)
+    goto end;
+
+  for (POSITION *pos= cur_pos-1; pos != pos_end; pos--)
+  {
+    if (found_ref & pos->table->map)
+    {
+      found_ref&= ~pos->table->map;
+
+      /* Found depent table */
+      if (pos->type == EQ_REF)
+      {
+        if (!found_ref)
+          found*= pos->same_keys;
+      }
+      else if (pos->type == CACHE)
+      {
+        if (!found_ref)
+          found*= pos->record_count / pos->refills;
+      }
+      break;
+    }
+    if (pos->type != CACHE)
+    {
+      /*
+        We are not depending on the curren table
+        There are 'records_out' rows with idenitical rows
+        value for our depending tables.
+        We are ignoring join_cache as in this case the
+        preceding tables row combination can change for
+        each call.
+      */
+      found*= pos->records_out;
+    }
+    else
+      found/= pos->refills;
+  }
+
+end:
+  cur_pos->record_count= record_count;
+  cur_pos->same_keys= found;
+  assert(record_count >= found);
+
+  if (unlikely(found <= 1.0))
+    cur_pos->prev_record_read= record_count;
+  else if (unlikely(found > record_count))
+    cur_pos->prev_record_read=1;
+  else
+    cur_pos->prev_record_read= record_count / found;
+  return;
+}
+
+
+void cleanup()
+{
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    free(table[i].cache);
+    table[i].cache= 0;
+  }
+}
+
+
+void intialize_tables()
+{
+  int eq_ref_tables;
+
+restart:
+  eq_ref_tables= 0;
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    if (i == 0)
+      table[i].type= SCAN;
+    else
+      table[i].type= (JOIN_TYPE) (rand() % 4);
+    table[i].records_in_table= rand() % 5+3;
+    table[i].matching_records= 2 + rand() % 3;
+    table[i].map= (DEPEND) 1 << i;
+    table[i].ref_depend_map= 0;
+
+/* The following is for testing */
+#ifdef FORCE_COMB
+    if (i == 5 || i == 6)
+    {
+      table[i].type= REF;
+      table[i].matching_records= 5;
+    }
+#endif
+    if (table[i].type != SCAN)
+    {
+      /* This just to make do_select a bit easier */
+      table[i].ref_depend_map=  ((DEPEND) 1) << (rand() % i);
+      if (rand() & 1)
+      {
+        uint second_depend= rand() % i;
+        if (!(table[i].ref_depend_map & second_depend))
+          table[i].ref_depend_map|= ((DEPEND) 1) << second_depend;
+      }
+    }
+
+    if (table[i].type == EQ_REF)
+    {
+      table[i].matching_records= 1;
+      eq_ref_tables++;
+    }
+    else if (table[i].type != REF)
+      table[i].matching_records= table[i].records_in_table;
+
+    table[i].last_key= 0;
+    table[i].lookups= 0;
+    table[i].cached_records= 0;
+    table[i].flushed_caches= 0;
+    table[i].cache= 0;
+    if (table[i].type == CACHE)
+      table[i].cache= (ulonglong*) malloc(CACHED_ROWS *
+                                          sizeof(table[i].data) * i);
+  }
+
+  /* We must have at least one EQ_REF table */
+  if (!eq_ref_tables)
+  {
+    cleanup();
+    goto restart;
+  }
+}
+
+
+void optimize_tables()
+{
+  double record_count= 1.0, records;
+
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    TABLE *tab= table+i;
+    positions[i].refills= 0;
+
+    switch (tab->type) {
+    case SCAN:
+      records= tab->records_in_table;
+      break;
+    case EQ_REF:
+      records= 1.0;
+      prev_record_reads(positions, i, tab->ref_depend_map, record_count);
+      break;
+    case REF:
+      records= tab->matching_records;
+      break;
+    case CACHE:
+      records= tab->records_in_table;
+      positions[i].refills= (record_count + CACHED_ROWS-1)/ CACHED_ROWS;
+      break;
+    default:
+      assert(0);
+    }
+    positions[i].table= table + i;
+    positions[i].type= table[i].type;
+    positions[i].records= records;
+    positions[i].record_count= record_count;
+    positions[i].records_out= records;
+
+    record_count*= records;
+  }
+}
+
+
+
+void process_join_cache(TABLE *tab, uint table_index)
+{
+  if (!tab->cached_records)
+    return;
+
+#ifdef PRINT_CACHE
+  putc('>', stdout);
+  for (uint k= 0 ; k < table_index ; k++)
+  {
+    printf("%8lld ", tab->cache[k]);
+  }
+  putc('\n',stdout);
+  putc('<', stdout);
+  for (uint k= 0 ; k < table_index ; k++)
+  {
+    printf("%8lld ", tab->cache[k+(tab->cached_records-1)*table_index]);
+  }
+  putc('\n',stdout);
+#endif
+
+  for (uint k= 0 ; k < tab->records_in_table; k++)
+  {
+    table[table_index].data= k+1;
+    ulonglong *cache= tab->cache;
+    for (uint i= 0 ; i < tab->cached_records ; i++)
+    {
+      for (uint j= 0 ; j < table_index ; j++)
+        table[j].data= *cache++;
+      do_select(table_index+1);
+    }
+  }
+  tab->flushed_caches++;
+  tab->cached_records= 0;
+}
+
+/*
+  Calculate a key depending on multiple tables
+*/
+
+ulonglong calc_ref_key(DEPEND depend_map)
+{
+  ulonglong value= 1;
+  TABLE *t= table;
+
+  do
+  {
+    if (t->map & depend_map)
+    {
+      depend_map&= ~t->map;
+      value*= t->data;
+    }
+    t++;
+  } while (depend_map);
+  return value;
+}
+
+
+void do_select(uint table_index)
+{
+  if (table_index == opt_tables)
+    return;
+
+  TABLE *tab= table + table_index;
+  switch (tab->type) {
+  case SCAN:
+    for (uint i= 1 ; i <= tab->records_in_table ; i++)
+    {
+      tab->data= i;
+      do_select(table_index+1);
+    }
+    break;
+  case REF:
+  {
+    ulonglong ref_key= calc_ref_key(tab->ref_depend_map);
+    for (uint i=1 ; i <= tab->matching_records ; i++)
+    {
+      tab->data= ref_key * tab->matching_records + i;
+      do_select(table_index+1);
+    }
+    break;
+  }
+  case EQ_REF:
+  {
+    ulonglong ref_key= calc_ref_key(tab->ref_depend_map);
+    if (ref_key != tab->last_key)
+    {
+      tab->lookups++;
+#ifdef PRINT_EQ_KEY
+      if (table_index == 9)
+        printf("ref_key: %lld\n", ref_key);
+#endif
+      tab->last_key= ref_key;
+      tab->data= ref_key * tab->matching_records;
+    }
+    else
+    {
+      assert(tab->lookups != 0);
+    }
+    do_select(table_index+1);
+    break;
+  }
+  case CACHE:
+  {
+    ulonglong *cache= tab->cache + tab->cached_records * table_index;
+    for (uint i= 0 ; i <= table_index ; i++)
+      *cache++ = table[i].data;
+    if (++tab->cached_records == CACHED_ROWS)
+      process_join_cache(tab, table_index);
+    break;
+  }
+  default:
+    break;
+  }
+  return;
+}
+
+
+void do_select_end(uint table_index)
+{
+  if (table_index == opt_tables)
+    return;
+
+  TABLE *tab= table + table_index;
+  switch (tab->type) {
+  case CACHE:
+    process_join_cache(tab, table_index);
+    break;
+  default:
+    break;
+  }
+  do_select_end(table_index+1);
+}
+
+
+void execute()
+{
+  do_select(0);
+  do_select_end(0);
+}
+
+int check_prev_records()
+{
+  int errors= 0;
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    TABLE *tab= table + i;
+    if (tab->type == EQ_REF)
+    {
+      if (positions[i].prev_record_read != (double) tab->lookups)
+      {
+        fprintf(stdout, "table: %d  lookups: %lld  prev_record_read: %g\n",
+                i, tab->lookups, positions[i].prev_record_read);
+        errors++;
+      }
+    }
+  }
+  if (errors || verbose)
+  {
+    fprintf(stdout, "tables:     %u\n", opt_tables);
+    fprintf(stdout, "rand_init:  %u\n", rand_init);
+    fprintf(stdout, "cache_size: %u\n", (uint) CACHED_ROWS);
+    for (uint i= 0; i < opt_tables ; i++)
+    {
+      TABLE *tab= table + i;
+      fprintf(stdout, "table: %2d (%3lx)  type: %-6s  comb: %3lg  out: %2lg  lookups: %lld  prev: %lg  depend: %llx\n",
+              i, (uint) 1 << i, type[tab->type], positions[i].record_count,
+              positions[i].records_out, tab->lookups,
+              positions[i].prev_record_read, tab->ref_depend_map);
+    }
+  }
+  return errors;
+}
+
+
+int main(int argc, char **argv)
+{
+  if (argc > 1)
+  {
+    opt_tables=atoi(argv[1]);
+    if (opt_tables <= 3)
+      opt_tables= 3;
+    if (opt_tables > TABLES)
+      opt_tables= TABLES;
+  }
+  if (argc > 2)
+    rand_init= atoi(argv[2]);
+  else
+    rand_init= (uint) time(0);
+  srand(rand_init);
+
+  intialize_tables();
+  optimize_tables();
+  execute();
+  cleanup();
+  exit(check_prev_records() > 0);
+}