Fix for bug #31207: Test "join_nested" shows different strategy on IA64

CPUs / Intel's ICC compile

The bug is a combination of two problems:

1. IA64/ICC MySQL binaries use glibc's qsort(), not the one in mysys.

2. The order relation implemented by join_tab_cmp() is not transitive,
i.e. it is possible to choose such a, b and c that (a < b) && (b < c)
but (c < a). This implies that result of a sort using the relation
implemented by join_tab_cmp() depends on the order in which
elements are compared, i.e. the result is implementation-specific. Since
choose_plan() uses qsort() to pre-sort the
join tables using join_tab_cmp() as a compare function, the results of
the sorting may vary depending on qsort() implementation.

It is neither possible nor important to implement a better ordering
algorithm in join_tab_cmp(). Therefore the only way to fix it is to
force our own qsort() to be used by renaming it to my_qsort(), so we don't depend
on linker to decide that.

This patch also "fixes" bug #20530: qsort redefinition violates the
standard.


include/my_sys.h:
  Renamed qsort() and qsort2() to my_qsort() and my_qsort2(). Since
  previously we relied on stdlib.h to provide a declaration for qsort(), a
  separate declaration for my_qsort() is now required.
libmysql/Makefile.shared:
  Added mf_qsort.c to libmysql, since my_lib.c now uses my_qsort() instead of qsort().
myisam/ft_boolean_search.c:
  Replaced qsort2() with my_qsort2().
myisam/ft_nlq_search.c:
  Replaced qsort2() with my_qsort2().
myisam/myisampack.c:
  Replaced qsort() with my_qsort().
myisam/sort.c:
  Replaced qsort2() with my_qsort2().
mysys/mf_keycache.c:
  Replaced qsort() with my_qsort().
mysys/mf_qsort.c:
  Renamed qsort() to my_qsort() and qsort2() to my_qsort2().
mysys/mf_sort.c:
  Replaced qsort2() with my_qsort2().
mysys/my_lib.c:
  Replaced qsort() with my_qsort().
mysys/queues.c:
  Replaced qsort2() with my_qsort2().
sql/item_cmpfunc.cc:
  Replaced qsort2() with my_qsort2().
sql/item_cmpfunc.h:
  Replaced qsort2() with my_qsort2().
sql/opt_range.cc:
  Replaced qsort() with my_qsort().
sql/records.cc:
  Replaced qsort() with my_qsort().
sql/sql_acl.cc:
  Replaced qsort() with my_qsort().
sql/sql_array.h:
  Replaced qsort() with my_qsort().
sql/sql_help.cc:
  Replaced qsort() with my_qsort().
sql/sql_select.cc:
  Replaced qsort() with my_qsort().
sql/examples/ha_tina.cc:
  Replaced qsort() with my_qsort().
sql/sql_table.cc:
  Replaced qsort() with my_qsort().

10 files changed, 37 insertions, 24 deletions

diff --git a/sql/examples/ha_tina.cc b/sql/examples/ha_tina.cc
index 2c5226222e2..0d1d821cf17 100644
--- a/sql/examples/ha_tina.cc
+++ b/sql/examples/ha_tina.cc
@@ -852,7 +852,7 @@ int ha_tina::rnd_end()
       It also sorts so that we move the final blocks to the
       beginning so that we move the smallest amount of data possible.
     */
-    qsort(chain, (size_t)(chain_ptr - chain), sizeof(tina_set), (qsort_cmp)sort_set);
+    my_qsort(chain, (size_t)(chain_ptr - chain), sizeof(tina_set), (qsort_cmp)sort_set);
     for (ptr= chain; ptr < chain_ptr; ptr++)
     {
       memmove(share->mapped_file + ptr->begin, share->mapped_file + ptr->end,
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc
index 86eb10d50b0..45ed61a2ab7 100644
--- a/sql/item_cmpfunc.cc
+++ b/sql/item_cmpfunc.cc
@@ -2775,7 +2775,7 @@ static inline int cmp_ulongs (ulonglong a_val, ulonglong b_val)
 
   SYNOPSIS
     cmp_longlong()
-      cmp_arg   an argument passed to the calling function (qsort2)
+      cmp_arg   an argument passed to the calling function (my_qsort2)
       a         left argument
       b         right argument
 
diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index 8410c66b034..2ea155b3fac 100644
--- a/sql/item_cmpfunc.h
+++ b/sql/item_cmpfunc.h
@@ -781,7 +781,7 @@ public:
   virtual byte *get_value(Item *item)=0;
   void sort()
   {
-    qsort2(base,used_count,size,compare,collation);
+    my_qsort2(base,used_count,size,compare,collation);
   }
   int find(Item *item);
   
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 04e2816d553..c3e9b6638bd 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -3159,8 +3159,8 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
     ROR_SCAN_INFO's.
     Step 2: Get best ROR-intersection using an approximate algorithm.
   */
-  qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
-        (qsort_cmp)cmp_ror_scan_info);
+  my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
+           (qsort_cmp)cmp_ror_scan_info);
   DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "ordered",
                                           tree->ror_scans,
                                           tree->ror_scans_end););
@@ -3349,8 +3349,8 @@ TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
         bitmap_get_first(&(*scan)->covered_fields);
     }
 
-    qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
-          (qsort_cmp)cmp_ror_scan_info_covering);
+    my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
+             (qsort_cmp)cmp_ror_scan_info_covering);
 
     DBUG_EXECUTE("info", print_ror_scans_arr(param->table,
                                              "remaining scans",
diff --git a/sql/records.cc b/sql/records.cc
index 3a833c87b7b..f61efc13034 100644
--- a/sql/records.cc
+++ b/sql/records.cc
@@ -497,7 +497,8 @@ static int rr_from_cache(READ_RECORD *info)
       int3store(ref_position,(long) i);
       ref_position+=3;
     }
-    qsort(info->read_positions,length,info->struct_length,(qsort_cmp) rr_cmp);
+    my_qsort(info->read_positions, length, info->struct_length,
+             (qsort_cmp) rr_cmp);
 
     position=info->read_positions;
     for (i=0 ; i < length ; i++)
diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc
index f9bd2c6ba0d..d5257b1076a 100644
--- a/sql/sql_acl.cc
+++ b/sql/sql_acl.cc
@@ -248,8 +248,8 @@ static my_bool acl_load(THD *thd, TABLE_LIST *tables)
 #endif
     VOID(push_dynamic(&acl_hosts,(gptr) &host));
   }
-  qsort((gptr) dynamic_element(&acl_hosts,0,ACL_HOST*),acl_hosts.elements,
-	sizeof(ACL_HOST),(qsort_cmp) acl_compare);
+  my_qsort((gptr) dynamic_element(&acl_hosts,0,ACL_HOST*),acl_hosts.elements,
+           sizeof(ACL_HOST),(qsort_cmp) acl_compare);
   end_read_record(&read_record_info);
   freeze_size(&acl_hosts);
 
@@ -421,8 +421,8 @@ static my_bool acl_load(THD *thd, TABLE_LIST *tables)
         allow_all_hosts=1;			// Anyone can connect
     }
   }
-  qsort((gptr) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements,
-	sizeof(ACL_USER),(qsort_cmp) acl_compare);
+  my_qsort((gptr) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements,
+           sizeof(ACL_USER),(qsort_cmp) acl_compare);
   end_read_record(&read_record_info);
   freeze_size(&acl_users);
 
@@ -479,8 +479,8 @@ static my_bool acl_load(THD *thd, TABLE_LIST *tables)
 #endif
     VOID(push_dynamic(&acl_dbs,(gptr) &db));
   }
-  qsort((gptr) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
-	sizeof(ACL_DB),(qsort_cmp) acl_compare);
+  my_qsort((gptr) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
+           sizeof(ACL_DB),(qsort_cmp) acl_compare);
   end_read_record(&read_record_info);
   freeze_size(&acl_dbs);
   init_check_host();
@@ -1110,8 +1110,8 @@ static void acl_insert_user(const char *user, const char *host,
   if (!acl_user.host.hostname ||
       (acl_user.host.hostname[0] == wild_many && !acl_user.host.hostname[1]))
     allow_all_hosts=1;		// Anyone can connect /* purecov: tested */
-  qsort((gptr) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements,
-	sizeof(ACL_USER),(qsort_cmp) acl_compare);
+  my_qsort((gptr) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements,
+           sizeof(ACL_USER),(qsort_cmp) acl_compare);
 
   /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */
   rebuild_check_host();
@@ -1173,8 +1173,8 @@ static void acl_insert_db(const char *user, const char *host, const char *db,
   acl_db.access=privileges;
   acl_db.sort=get_sort(3,acl_db.host.hostname,acl_db.db,acl_db.user);
   VOID(push_dynamic(&acl_dbs,(gptr) &acl_db));
-  qsort((gptr) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
-	sizeof(ACL_DB),(qsort_cmp) acl_compare);
+  my_qsort((gptr) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
+           sizeof(ACL_DB),(qsort_cmp) acl_compare);
 }
 
 
diff --git a/sql/sql_array.h b/sql/sql_array.h
index e2e12bee241..dcef457dce7 100644
--- a/sql/sql_array.h
+++ b/sql/sql_array.h
@@ -62,7 +62,7 @@ public:
 
   void sort(CMP_FUNC cmp_func)
   {
-    qsort(array.buffer, array.elements, sizeof(Elem), (qsort_cmp)cmp_func);
+    my_qsort(array.buffer, array.elements, sizeof(Elem), (qsort_cmp)cmp_func);
   }
 };
 
diff --git a/sql/sql_help.cc b/sql/sql_help.cc
index ba7f1a534ea..69a257a9d37 100644
--- a/sql/sql_help.cc
+++ b/sql/sql_help.cc
@@ -524,7 +524,7 @@ int send_variant_2_list(MEM_ROOT *mem_root, Protocol *protocol,
   List_iterator<String> it(*names);
   for (pos= pointers; pos!=end; (*pos++= it++));
 
-  qsort(pointers,names->elements,sizeof(String*),string_ptr_cmp);
+  my_qsort(pointers,names->elements,sizeof(String*),string_ptr_cmp);
 
   for (pos= pointers; pos!=end; pos++)
   {
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 1d11f23d854..b519c06420f 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -3658,7 +3658,7 @@ update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
   {
     KEYUSE key_end,*prev,*save_pos,*use;
 
-    qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE),
+    my_qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE),
 	  (qsort_cmp) sort_keyuse);
 
     bzero((char*) &key_end,sizeof(key_end));    /* Add for easy testing */
@@ -4371,8 +4371,9 @@ choose_plan(JOIN *join, table_map join_tables)
       Apply heuristic: pre-sort all access plans with respect to the number of
       records accessed.
   */
-  qsort(join->best_ref + join->const_tables, join->tables - join->const_tables,
-        sizeof(JOIN_TAB*), straight_join?join_tab_cmp_straight:join_tab_cmp);
+  my_qsort(join->best_ref + join->const_tables,
+           join->tables - join->const_tables, sizeof(JOIN_TAB*),
+           straight_join ? join_tab_cmp_straight : join_tab_cmp);
   
   if (straight_join)
   {
@@ -4421,6 +4422,17 @@ choose_plan(JOIN *join, table_map join_tables)
     ptr1 pointer to first JOIN_TAB object
     ptr2 pointer to second JOIN_TAB object
 
+  NOTES
+    The order relation implemented by join_tab_cmp() is not transitive,
+    i.e. it is possible to choose such a, b and c that (a < b) && (b < c)
+    but (c < a). This implies that result of a sort using the relation
+    implemented by join_tab_cmp() depends on the order in which
+    elements are compared, i.e. the result is implementation-specific.
+    Example:
+      a: dependent = 0x0 table->map = 0x1 found_records = 3 ptr = 0x907e6b0
+      b: dependent = 0x0 table->map = 0x2 found_records = 3 ptr = 0x907e838
+      c: dependent = 0x6 table->map = 0x10 found_records = 2 ptr = 0x907ecd0
+     
   RETURN
     1  if first is bigger
     -1 if second is bigger
diff --git a/sql/sql_table.cc b/sql/sql_table.cc
index 6cbe98fe862..b6e41788ef0 100644
--- a/sql/sql_table.cc
+++ b/sql/sql_table.cc
@@ -1476,7 +1476,7 @@ static int mysql_prepare_table(THD *thd, HA_CREATE_INFO *create_info,
     DBUG_RETURN(-1);
   }
   /* Sort keys in optimized order */
-  qsort((gptr) *key_info_buffer, *key_count, sizeof(KEY),
+  my_qsort((gptr) *key_info_buffer, *key_count, sizeof(KEY),
 	(qsort_cmp) sort_keys);
   create_info->null_bits= null_fields;