EXPLAIN FORMAT=JSON: support SJ-Materialization

- Switch Explain data structure from "flat" representation of
  SJ-Materialization into nested one.
- Update functions that print tabular output to operate on the
  nested structure.
- Add function to generate JSON output.

6 files changed, 251 insertions, 81 deletions

diff --git a/mysql-test/r/analyze_format_json.result b/mysql-test/r/analyze_format_json.result
index 91bdfca039b..27b36bbba59 100644
--- a/mysql-test/r/analyze_format_json.result
+++ b/mysql-test/r/analyze_format_json.result
@@ -167,11 +167,5 @@ EXPLAIN
     }
   }
 }
-select count(*) from t1 A, t1 B where A.b<20 and B.b<60;
-count(*)
-1200
-select count(*) from t1 A, t1 B where A.b<20 and B.b<60 and A.c > B.c;
-count(*)
-190
 drop table t1;
 drop table t0;
diff --git a/mysql-test/r/explain_json.result b/mysql-test/r/explain_json.result
index 8353a6b5f42..4a45e8d7594 100644
--- a/mysql-test/r/explain_json.result
+++ b/mysql-test/r/explain_json.result
@@ -540,5 +540,57 @@ EXPLAIN
     }
   }
 }
-drop table t1;
+#
+# Semi-join Materialization
+#
+create table t2 like t1;
+insert into t2 select * from t1;
+explain format=json
+select * from t1,t2 where t1.a in ( select a from t0);
+EXPLAIN
+{
+  "query_block": {
+    "select_id": 1,
+    "table": {
+      "table_name": "t1",
+      "access_type": "ALL",
+      "rows": 10,
+      "filtered": 100
+    },
+    "table": {
+      "table_name": "<subquery2>",
+      "access_type": "eq_ref",
+      "possible_keys": ["distinct_key"],
+      "key": "distinct_key",
+      "key_length": "4",
+      "used_key_parts": ["a"],
+      "ref": ["func"],
+      "rows": 1,
+      "filtered": 100,
+      "materialized": {
+        "unique": 1,
+        "query_block": {
+          "select_id": 2,
+          "table": {
+            "table_name": "t0",
+            "access_type": "ALL",
+            "rows": 10,
+            "filtered": 100
+          }
+        }
+      }
+    },
+    "block-nl-join": {
+      "table": {
+        "table_name": "t2",
+        "access_type": "ALL",
+        "rows": 10,
+        "filtered": 100
+      },
+      "buffer_type": "flat",
+      "join_type": "BNL"
+    }
+  }
+}
+drop table t1,t2;
 drop table t0;
diff --git a/mysql-test/t/explain_json.test b/mysql-test/t/explain_json.test
index ed0cfdaf1eb..2f5c24ab5a5 100644
--- a/mysql-test/t/explain_json.test
+++ b/mysql-test/t/explain_json.test
@@ -105,6 +105,15 @@ tbl2 where cnt=tbl2.a;
 --echo #
 explain format=json 
 select * from t1 where a in (select max(a) from t1 group by b);
-drop table t1;
+
+--echo #
+--echo # Semi-join Materialization
+--echo #
+create table t2 like t1;
+insert into t2 select * from t1;
+explain format=json
+select * from t1,t2 where t1.a in ( select a from t0);
+
+drop table t1,t2;
 drop table t0;
 
diff --git a/sql/sql_explain.cc b/sql/sql_explain.cc
index 77ce692a2be..c4f8002494f 100644
--- a/sql/sql_explain.cc
+++ b/sql/sql_explain.cc
@@ -602,7 +602,7 @@ void Explain_select::replace_table(uint idx, Explain_table_access *new_tab)
 }
 
 
-Explain_select::~Explain_select()
+Explain_basic_join::~Explain_basic_join()
 {
   if (join_tabs)
   {
@@ -663,34 +663,77 @@ int Explain_select::print_explain(Explain_query *query,
         using_fs= false;
       }
     }
+    for (uint i=0; i< n_join_tabs; i++)
+    {
+      Explain_basic_join* nest;
+      if ((nest= join_tabs[i]->sjm_nest))
+        nest->print_explain(query, output, explain_flags, is_analyze);
+    }
   }
 
   return print_explain_for_children(query, output, explain_flags, is_analyze);
 }
 
 
+int Explain_basic_join::print_explain(Explain_query *query, 
+                                      select_result_sink *output,
+                                      uint8 explain_flags, bool is_analyze)
+{
+  for (uint i=0; i< n_join_tabs; i++)
+  {
+    if (join_tabs[i]->print_explain(output, explain_flags, is_analyze, 
+                                    select_id,
+                                    "MATERIALIZED" /*select_type*/, 
+                                    FALSE /*using temporary*/, 
+                                    FALSE /*using filesort*/))
+      return 1;
+  }
+  return 0;
+}
+
+
 void Explain_select::print_explain_json(Explain_query *query, 
                                         Json_writer *writer, bool is_analyze)
 {
   Json_writer_nesting_guard guard(writer);
 
-  writer->add_member("query_block").start_object();
-  writer->add_member("select_id").add_ll(select_id);
   if (message)
   {
+    writer->add_member("query_block").start_object();
+    writer->add_member("select_id").add_ll(select_id);
+
     writer->add_member("table").start_object();
     writer->add_member("message").add_str(message);
     writer->end_object();
+
+    print_explain_json_for_children(query, writer, is_analyze);
+    writer->end_object();
   }
   else
   {
-    for (uint i=0; i< n_join_tabs; i++)
-    {
-      // psergey-todo: Need to honor SJM nests...
-      join_tabs[i]->print_explain_json(query, writer, is_analyze);
-    }
+    /*
+       TODO: how does this approach allow to print ORDER BY members?
+         Explain_basic_join does not have ORDER/GROUP.
+         A: factor out join tab printing loop into a common func.
+    */
+    Explain_basic_join::print_explain_json(query, writer, is_analyze);
   }
 
+}
+
+
+void Explain_basic_join::print_explain_json(Explain_query *query, 
+                                            Json_writer *writer, 
+                                            bool is_analyze)
+{
+  Json_writer_nesting_guard guard(writer);
+
+  writer->add_member("query_block").start_object();
+  writer->add_member("select_id").add_ll(select_id);
+  for (uint i=0; i< n_join_tabs; i++)
+  {
+    join_tabs[i]->print_explain_json(query, writer, is_analyze);
+  }
   print_explain_json_for_children(query, writer, is_analyze);
   writer->end_object();
 }
@@ -837,17 +880,11 @@ int Explain_table_access::print_explain(select_result_sink *output, uint8 explai
   List<Item> item_list;
   Item *item_null= new Item_null();
   
-  if (sjm_nest_select_id)
-    select_id= sjm_nest_select_id;
-
   /* `id` column */
   item_list.push_back(new Item_int((int32) select_id));
 
   /* `select_type` column */
-  if (sjm_nest_select_id)
-    push_str(&item_list, "MATERIALIZED");
-  else
-    push_str(&item_list, select_type);
+  push_str(&item_list, select_type);
 
   /* `table` column */
   push_string(&item_list, &table_name);
@@ -1242,6 +1279,14 @@ void Explain_table_access::print_explain_json(Explain_query *query,
     node->print_explain_json(query, writer, is_analyze);
     writer->end_object();
   }
+  if (sjm_nest)
+  {
+    /* This is a non-merged semi-join table. Print its contents here */
+    writer->add_member("materialized").start_object();
+    writer->add_member("unique").add_ll(1);
+    sjm_nest->print_explain_json(query, writer, is_analyze);
+    writer->end_object();
+  }
 
   writer->end_object();
 }
diff --git a/sql/sql_explain.h b/sql/sql_explain.h
index 9cdaacd61ed..20e2f856840 100644
--- a/sql/sql_explain.h
+++ b/sql/sql_explain.h
@@ -94,7 +94,8 @@ public:
   enum explain_node_type 
   {
     EXPLAIN_UNION, 
-    EXPLAIN_SELECT, 
+    EXPLAIN_SELECT,
+    EXPLAIN_BASIC_JOIN,
     EXPLAIN_UPDATE,
     EXPLAIN_DELETE, 
     EXPLAIN_INSERT
@@ -144,6 +145,49 @@ public:
 class Explain_table_access;
 
 
+/* 
+  A basic join. This is only used for SJ-Materialization nests.
+
+  Basic join doesn't have ORDER/GROUP/DISTINCT operations. It also cannot be
+  degenerate.
+
+  It has its own select_id.
+*/
+class Explain_basic_join : public Explain_node
+{
+public:
+  enum explain_node_type get_type() { return EXPLAIN_BASIC_JOIN; }
+  
+  Explain_basic_join() : join_tabs(NULL) {}
+  ~Explain_basic_join();
+
+  bool add_table(Explain_table_access *tab)
+  {
+    if (!join_tabs)
+    {
+      join_tabs= (Explain_table_access**) my_malloc(sizeof(Explain_table_access*) *
+                                                MAX_TABLES, MYF(0));
+      n_join_tabs= 0;
+    }
+    join_tabs[n_join_tabs++]= tab;
+    return false;
+  }
+
+  int get_select_id() { return select_id; }
+
+  int select_id;
+
+  int print_explain(Explain_query *query, select_result_sink *output,
+                    uint8 explain_flags, bool is_analyze);
+  void print_explain_json(Explain_query *query, Json_writer *writer, 
+                          bool is_analyze);
+
+  /* A flat array of Explain structs for tables. */
+  Explain_table_access** join_tabs;
+  uint n_join_tabs;
+};
+
+
 /*
   EXPLAIN structure for a SELECT.
   
@@ -159,30 +203,16 @@ class Explain_table_access;
   a way get node's children.
 */
 
-class Explain_select : public Explain_node
+class Explain_select : public Explain_basic_join
 {
 public:
   enum explain_node_type get_type() { return EXPLAIN_SELECT; }
 
   Explain_select() : 
-    message(NULL), join_tabs(NULL),
+    message(NULL),
     using_temporary(false), using_filesort(false)
   {}
-  
-  ~Explain_select();
 
-  bool add_table(Explain_table_access *tab)
-  {
-    if (!join_tabs)
-    {
-      join_tabs= (Explain_table_access**) my_malloc(sizeof(Explain_table_access*) *
-                                                MAX_TABLES, MYF(0));
-      n_join_tabs= 0;
-    }
-    join_tabs[n_join_tabs++]= tab;
-    return false;
-  }
-  
   /*
     This is used to save the results of "late" test_if_skip_sort_order() calls
     that are made from JOIN::exec
@@ -190,24 +220,14 @@ public:
   void replace_table(uint idx, Explain_table_access *new_tab);
 
 public:
-  int select_id;
   const char *select_type;
 
-  int get_select_id() { return select_id; }
-
   /*
     If message != NULL, this is a degenerate join plan, and all subsequent
     members have no info 
   */
   const char *message;
   
-  /*
-    A flat array of Explain structs for tables. The order is "just like EXPLAIN
-    would print them".
-  */
-  Explain_table_access** join_tabs;
-  uint n_join_tabs;
-
   /* Global join attributes. In tabular form, they are printed on the first row */
   bool using_temporary;
   bool using_filesort;
@@ -521,19 +541,15 @@ public:
     non_merged_sjm_number(0),
     where_cond(NULL),
     cache_cond(NULL),
-    pushed_index_cond(NULL)
+    pushed_index_cond(NULL),
+    sjm_nest(NULL)
   {}
+  ~Explain_table_access() { delete sjm_nest; }
 
   void push_extra(enum explain_extra_tag extra_tag);
 
   /* Internals */
 public:
-  /* 
-    0 means this tab is not inside SJM nest and should use Explain_select's id
-    other value means the tab is inside an SJM nest.
-  */
-  int sjm_nest_select_id;
-
   /* id and 'select_type' are cared-of by the parent Explain_select */
   StringBuffer<32> table_name;
 
@@ -610,6 +626,8 @@ public:
 
   Item *pushed_index_cond;
 
+  Explain_basic_join *sjm_nest;
+
   int print_explain(select_result_sink *output, uint8 explain_flags, 
                     bool is_analyze,
                     uint select_id, const char *select_type,
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index f9cdd08cf68..354978b5362 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -8186,6 +8186,41 @@ JOIN_TAB *next_breadth_first_tab(JOIN *join, enum enum_exec_or_opt tabs_kind,
 }
 
 
+/* 
+  Enumerate JOIN_TABs in "EXPLAIN order". This order
+   - const tabs are included
+   - we enumerate "optimization tabs".
+   - 
+*/
+
+JOIN_TAB *first_explain_order_tab(JOIN* join)
+{
+  JOIN_TAB* tab;
+  tab= join->table_access_tabs;
+  return (tab->bush_children) ? tab->bush_children->start : tab;
+}
+
+
+JOIN_TAB *next_explain_order_tab(JOIN* join, JOIN_TAB* tab)
+{
+  /* If we're inside SJM nest and have reached its end, get out */
+  if (tab->last_leaf_in_bush)
+    return tab->bush_root_tab;
+  
+  /* Move to next tab in the array we're traversing */
+  tab++;
+  
+  if (tab == join->table_access_tabs + join->top_join_tab_count)
+    return NULL; /* Outside SJM nest and reached EOF */
+
+  if (tab->bush_children)
+    return tab->bush_children->start;
+
+  return tab;
+}
+
+
+
 JOIN_TAB *first_top_level_tab(JOIN *join, enum enum_with_const_tables const_tbls)
 {
   JOIN_TAB *tab= join->join_tab;
@@ -23277,16 +23312,7 @@ void JOIN_TAB::save_explain_data(Explain_table_access *eta, table_map prefix_tab
   tab->tracker= &eta->tracker;
   tab->jbuf_tracker= &eta->jbuf_tracker;
   
-  /* id */
-  if (tab->bush_root_tab)
-  {
-    JOIN_TAB *first_sibling= tab->bush_root_tab->bush_children->start;
-    eta->sjm_nest_select_id= first_sibling->emb_sj_nest->sj_subq_pred->get_identifier();
-  }
-  else
-    eta->sjm_nest_select_id= 0;
-
-  /* select_type is kept in Explain_select */
+  /* id and select_type are kept in Explain_select */
 
   /* table */
   if (table->derived_select_number)
@@ -23719,12 +23745,22 @@ int JOIN::save_explain_data_intern(Explain_query *output, bool need_tmp_table,
     if (select_lex->master_unit()->derived)
       xpl_sel->connection_type= Explain_node::EXPLAIN_NODE_DERIVED;
 
+    if (need_tmp_table)
+      xpl_sel->using_temporary= true;
+
+    if (need_order)
+      xpl_sel->using_filesort= true;
+
     JOIN_TAB* const first_top_tab= first_breadth_first_tab(join, WALK_OPTIMIZATION_TABS);
+    JOIN_TAB* prev_bush_root_tab= NULL;
 
-    for (JOIN_TAB *tab= first_breadth_first_tab(join, WALK_OPTIMIZATION_TABS); tab;
-         tab= next_breadth_first_tab(join, WALK_OPTIMIZATION_TABS, tab))
+    Explain_basic_join *cur_parent= xpl_sel;
+    
+    for (JOIN_TAB *tab= first_explain_order_tab(join); tab;
+         tab= next_explain_order_tab(join, tab))
+    //for (JOIN_TAB *tab= first_breadth_first_tab(join, WALK_OPTIMIZATION_TABS); tab;
+    //     tab= next_breadth_first_tab(join, WALK_OPTIMIZATION_TABS, tab))
     {
-      
       JOIN_TAB *saved_join_tab= NULL;
       TABLE *table=tab->table;
 
@@ -23735,6 +23771,7 @@ int JOIN::save_explain_data_intern(Explain_query *output, bool need_tmp_table,
         continue;
       }
 
+
       if (join->table_access_tabs == join->join_tab &&
           tab == (first_top_tab + join->const_tables) && pre_sort_join_tab)
       {
@@ -23743,20 +23780,35 @@ int JOIN::save_explain_data_intern(Explain_query *output, bool need_tmp_table,
       }
 
       Explain_table_access *eta= new (output->mem_root) Explain_table_access;
-      xpl_sel->add_table(eta);
 
-      tab->save_explain_data(eta, used_tables, distinct, first_top_tab);
-
-      if (need_tmp_table)
-      {
-        need_tmp_table=0;
-        xpl_sel->using_temporary= true;
-      }
-      if (need_order)
+      if (tab->bush_root_tab != prev_bush_root_tab)
       {
-        need_order=0;
-        xpl_sel->using_filesort= true;
+        if (tab->bush_root_tab)
+        {
+          /* 
+            We've entered an SJ-Materialization nest. Create an object for it.
+          */
+          cur_parent= new Explain_basic_join;
+
+          JOIN_TAB *first_child= tab->bush_root_tab->bush_children->start;
+          cur_parent->select_id=
+            first_child->emb_sj_nest->sj_subq_pred->get_identifier();
+        }
+        else
+        {
+          /* 
+            We've just left an SJ-Materialization nest. We are at the join tab
+            that 'embeds the nest'
+          */
+          DBUG_ASSERT(tab->bush_children);
+          eta->sjm_nest= cur_parent;
+          cur_parent= xpl_sel;
+        }
       }
+      prev_bush_root_tab= tab->bush_root_tab;
+
+      cur_parent->add_table(eta);
+      tab->save_explain_data(eta, used_tables, distinct, first_top_tab);
 
       if (saved_join_tab)
         tab= saved_join_tab;