sql_select.h 50.5 KB
Newer Older
Michael Widenius's avatar
Michael Widenius committed
1
/* Copyright (c) 2000, 2010, Oracle and/or its affiliates.
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4
   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
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
6

unknown's avatar
unknown committed
7 8 9 10
   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.
unknown's avatar
unknown committed
11

unknown's avatar
unknown committed
12 13 14 15 16
   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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


unknown's avatar
unknown committed
17 18
#ifndef SQL_SELECT_INCLUDED
#define SQL_SELECT_INCLUDED
unknown's avatar
unknown committed
19 20 21 22 23 24
/**
  @file

  @brief
  classes to use when handling where clause
*/
unknown's avatar
unknown committed
25

26
#ifdef USE_PRAGMA_INTERFACE
unknown's avatar
unknown committed
27 28 29 30 31 32
#pragma interface			/* gcc class implementation */
#endif

#include "procedure.h"
#include <myisam.h>

Sergey Petrunya's avatar
Sergey Petrunya committed
33
#if defined(WITH_ARIA_STORAGE_ENGINE) && defined(USE_MARIA_FOR_TMP_TABLES)
34 35 36 37 38
#include "../storage/maria/ha_maria.h"
#define TMP_ENGINE_HTON maria_hton
#else
#define TMP_ENGINE_HTON myisam_hton
#endif
39 40 41
/* Values in optimize */
#define KEY_OPTIMIZE_EXISTS		1
#define KEY_OPTIMIZE_REF_OR_NULL	2
42 43 44 45 46
#define KEY_OPTIMIZE_EQ	                4

inline uint get_hash_join_key_no() { return MAX_KEY; }

inline bool is_hash_join_key_no(uint key) { return key == MAX_KEY; }
47

unknown's avatar
unknown committed
48 49
typedef struct keyuse_t {
  TABLE *table;
unknown's avatar
unknown committed
50
  Item	*val;				/**< or value if no field */
unknown's avatar
unknown committed
51
  table_map used_tables;
52
  uint	key, keypart, optimize;
53 54
  key_part_map keypart_map;
  ha_rows      ref_table_rows;
unknown's avatar
unknown committed
55
  /**
56 57 58 59
    If true, the comparison this value was created from will not be
    satisfied if val has NULL 'value'.
  */
  bool null_rejecting;
60 61 62 63 64 65 66 67 68 69 70
  /*
    !NULL - This KEYUSE was created from an equality that was wrapped into
            an Item_func_trig_cond. This means the equality (and validity of 
            this KEYUSE element) can be turned on and off. The on/off state 
            is indicted by the pointed value:
              *cond_guard == TRUE <=> equality condition is on
              *cond_guard == FALSE <=> equality condition is off

    NULL  - Otherwise (the source equality can't be turned off)
  */
  bool *cond_guard;
71 72 73 74 75
  /*
     0..64    <=> This was created from semi-join IN-equality # sj_pred_no.
     MAX_UINT  Otherwise
  */
  uint         sj_pred_no;
76 77

  bool is_for_hash_join() { return is_hash_join_key_no(key); }
unknown's avatar
unknown committed
78 79 80 81
} KEYUSE;

class store_key;

82 83
const int NO_REF_PART= uint(-1);

unknown's avatar
unknown committed
84 85 86
typedef struct st_table_ref
{
  bool		key_err;
87 88
  /** True if something was read into buffer in join_read_key.  */
  bool          has_record;
unknown's avatar
unknown committed
89 90 91 92 93
  uint          key_parts;                ///< num of ...
  uint          key_length;               ///< length of key_buff
  int           key;                      ///< key no
  uchar         *key_buff;                ///< value to look for with key
  uchar         *key_buff2;               ///< key_buff+key_length
unknown's avatar
unknown committed
94
  store_key     **key_copy;               //
unknown's avatar
unknown committed
95
  Item          **items;                  ///< val()'s for each keypart
96 97 98 99 100 101 102 103 104 105 106 107
  /*  
    Array of pointers to trigger variables. Some/all of the pointers may be
    NULL.  The ref access can be used iff
    
      for each used key part i, (!cond_guards[i] || *cond_guards[i]) 

    This array is used by subquery code. The subquery code may inject
    triggered conditions, i.e. conditions that can be 'switched off'. A ref 
    access created from such condition is not valid when at least one of the 
    underlying conditions is switched off (see subquery code for more details)
  */
  bool          **cond_guards;
unknown's avatar
unknown committed
108
  /**
109 110 111 112
    (null_rejecting & (1<<i)) means the condition is '=' and no matching
    rows will be produced if items[i] IS NULL (see add_not_null_conds())
  */
  key_part_map  null_rejecting;
unknown's avatar
unknown committed
113
  table_map	depend_map;		  ///< Table depends on these tables.
114

115
  /* null byte position in the key_buf. Used for REF_OR_NULL optimization */
116
  uchar          *null_ref_key;
117
  /* 
118 119 120
    ref_or_null optimization: number of key part that alternates between
    the lookup value or NULL (there's only one such part). 
    If we're not using ref_or_null, the value is NO_REF_PART
121 122 123
  */
  uint           null_ref_part;

124 125 126 127 128
  /*
    The number of times the record associated with this key was used
    in the join.
  */
  ha_rows       use_count;
129 130 131 132

  /*
    TRUE <=> disable the "cache" as doing lookup with the same key value may
    produce different results (because of Index Condition Pushdown)
unknown's avatar
unknown committed
133

134 135
  */
  bool          disable_cache;
unknown's avatar
unknown committed
136 137

  bool tmp_table_index_lookup_init(THD *thd, KEY *tmp_key, Item_iterator &it,
unknown's avatar
unknown committed
138
                                   bool value, uint skip= 0);
unknown's avatar
unknown committed
139 140
} TABLE_REF;

141

unknown's avatar
unknown committed
142
/*
143
  The structs which holds the join connections and join states
unknown's avatar
unknown committed
144 145
*/
enum join_type { JT_UNKNOWN,JT_SYSTEM,JT_CONST,JT_EQ_REF,JT_REF,JT_MAYBE_REF,
146
		 JT_ALL, JT_RANGE, JT_NEXT, JT_FT, JT_REF_OR_NULL,
147
		 JT_UNIQUE_SUBQUERY, JT_INDEX_SUBQUERY, JT_INDEX_MERGE,
148
                 JT_HASH, JT_HASH_RANGE, JT_HASH_NEXT, JT_HASH_INDEX_MERGE};
unknown's avatar
unknown committed
149 150 151

class JOIN;

152 153 154 155 156 157 158
enum enum_nested_loop_state
{
  NESTED_LOOP_KILLED= -2, NESTED_LOOP_ERROR= -1,
  NESTED_LOOP_OK= 0, NESTED_LOOP_NO_MORE_ROWS= 1,
  NESTED_LOOP_QUERY_LIMIT= 3, NESTED_LOOP_CURSOR_LIMIT= 4
};

159 160 161 162 163 164 165

/* Values for JOIN_TAB::packed_info */
#define TAB_INFO_HAVE_VALUE 1
#define TAB_INFO_USING_INDEX 2
#define TAB_INFO_USING_WHERE 4
#define TAB_INFO_FULL_SCAN_ON_NULL 8

166 167
typedef enum_nested_loop_state
(*Next_select_func)(JOIN *, struct st_join_table *, bool);
168 169 170 171 172 173 174

/*
  Function prototype for reading first record for a join tab

  RETURN
     0     - OK
    -1     - Record not found
175
    Other  - A fatal error
176
*/
177
typedef int (*Read_record_func)(struct st_join_table *tab);
178

179
Next_select_func setup_end_select_func(JOIN *join);
180
int rr_sequential(READ_RECORD *info);
181
int rr_sequential_and_unpack(READ_RECORD *info);
182

183

184
class JOIN_CACHE;
185
class SJ_TMP_TABLE;
186
class JOIN_TAB_RANGE;
187

unknown's avatar
unknown committed
188
typedef struct st_join_table {
189
  st_join_table() {}                          /* Remove gcc warning */
unknown's avatar
unknown committed
190
  TABLE		*table;
unknown's avatar
unknown committed
191
  KEYUSE	*keyuse;			/**< pointer to first used key */
192 193
  KEY           *hj_key;       /**< descriptor of the used best hash join key
				    not supported by any index                 */
unknown's avatar
unknown committed
194 195
  SQL_SELECT	*select;
  COND		*select_cond;
196 197
  COND          *on_precond;    /**< part of on condition to check before
				     accessing the first inner table           */  
unknown's avatar
unknown committed
198
  QUICK_SELECT_I *quick;
199 200 201 202 203 204 205 206
  /* 
    The value of select_cond before we've attempted to do Index Condition
    Pushdown. We may need to restore everything back if we first choose one
    index but then reconsider (see test_if_skip_sort_order() for such
    scenarios).
    NULL means no index condition pushdown was performed.
  */
  Item          *pre_idx_push_select_cond;
207 208 209 210 211 212 213
  /*
    Pointer to the associated ON expression. on_expr_ref=!NULL except for
    degenerate joins. 
    *on_expr_ref!=NULL for tables that are first inner tables within an outer
    join.
  */
  Item	       **on_expr_ref;
unknown's avatar
unknown committed
214 215 216 217 218 219 220
  COND_EQUAL    *cond_equal;    /**< multiple equalities for the on expression */
  st_join_table *first_inner;   /**< first inner table for including outerjoin */
  bool           found;         /**< true after all matches or null complement */
  bool           not_null_compl;/**< true before null complement is added      */
  st_join_table *last_inner;    /**< last table table for embedding outer join */
  st_join_table *first_upper;  /**< first inner table for embedding outer join */
  st_join_table *first_unmatched; /**< used for optimization purposes only     */
221 222

  /*
Sergey Petrunya's avatar
Sergey Petrunya committed
223
    For join tabs that are inside an SJM bush: root of the bush
224 225 226
  */
  st_join_table *bush_root_tab;

Sergey Petrunya's avatar
Sergey Petrunya committed
227
  /* TRUE <=> This join_tab is inside an SJM bush and is the last leaf tab here */
228 229 230 231 232 233 234
  bool          last_leaf_in_bush;
  
  /*
    ptr  - this is a bush, and ptr points to description of child join_tab
           range
    NULL - this join tab has no bush children
  */
235
  JOIN_TAB_RANGE *bush_children;
236 237
  
  /* Special content for EXPLAIN 'Extra' column or NULL if none */
unknown's avatar
unknown committed
238
  const char	*info;
239 240 241 242 243 244
  /* 
    Bitmap of TAB_INFO_* bits that encodes special line for EXPLAIN 'Extra'
    column, or 0 if there is no info.
  */
  uint          packed_info;

245 246
  Read_record_func read_first_record;
  Next_select_func next_select;
unknown's avatar
unknown committed
247
  READ_RECORD	read_record;
248 249 250 251 252 253 254
  /* 
    Currently the following two fields are used only for a [NOT] IN subquery
    if it is executed by an alternative full table scan when the left operand of
    the subquery predicate is evaluated to NULL.
  */  
  Read_record_func save_read_first_record;/* to save read_first_record */ 
  int (*save_read_record) (READ_RECORD *);/* to save read_record.read_record */
unknown's avatar
unknown committed
255
  double	worst_seeks;
unknown's avatar
unknown committed
256 257
  key_map	const_keys;			/**< Keys with constant part */
  key_map	checked_keys;			/**< Keys checked in find_best */
unknown's avatar
unknown committed
258
  key_map	needed_reg;
unknown's avatar
unknown committed
259
  key_map       keys;                           /**< all keys with can be used */
260 261 262 263 264 265 266 267 268 269 270 271 272

  /* Either #rows in the table or 1 for const table.  */
  ha_rows	records;
  /*
    Number of records that will be scanned (yes scanned, not returned) by the
    best 'independent' access method, i.e. table scan or QUICK_*_SELECT)
  */
  ha_rows       found_records;
  /*
    Cost of accessing the table using "ALL" or range/index_merge access
    method (but not 'index' for some reason), i.e. this matches method which
    E(#records) is in found_records.
  */
273
  double        read_time;
274 275
  
  /* psergey-todo: make the below have type double, like POSITION::records_read? */
276
  ha_rows       records_read;
277
  
278 279
  /* Startup cost for execution */
  double        startup_cost;
280 281 282
    
  double        partial_join_cardinality;

unknown's avatar
unknown committed
283 284
  table_map	dependent,key_dependent;
  uint		use_quick,index;
unknown's avatar
unknown committed
285
  uint		status;				///< Save status for cache
286 287 288 289
  uint		used_fields;
  ulong         used_fieldlength;
  ulong         max_used_fieldlength;
  uint          used_blobs;
290 291
  uint          used_null_fields;
  uint          used_uneven_bit_fields;
unknown's avatar
unknown committed
292 293
  enum join_type type;
  bool		cached_eq_ref_table,eq_ref_table,not_used_in_distinct;
294
  bool		sorted;
unknown's avatar
unknown committed
295 296 297 298 299 300
  /* 
    If it's not 0 the number stored this field indicates that the index
    scan has been chosen to access the table data and we expect to scan 
    this number of rows for the table.
  */ 
  ha_rows       limit; 
unknown's avatar
unknown committed
301
  TABLE_REF	ref;
302 303 304 305 306 307 308
  /* TRUE <=> condition pushdown supports other tables presence */
  bool          icp_other_tables_ok;
  /* 
    TRUE <=> condition pushed to the index has to be factored out of
    the condition pushed to the table
  */
  bool          idx_cond_fact_out;
309
  bool          use_join_cache;
310
  uint          used_join_cache_level;
311
  ulong         join_buffer_size_limit;
312 313 314 315 316 317
  JOIN_CACHE	*cache;
  /*
    Index condition for BKA access join
  */
  Item          *cache_idx_cond;
  SQL_SELECT    *cache_select;
318
  JOIN		*join;
319 320 321 322 323
  /*
    Embedding SJ-nest (may be not the direct parent), or NULL if none.
    This variable holds the result of table pullout.
  */
  TABLE_LIST    *emb_sj_nest;
Sergey Petrunya's avatar
Sergey Petrunya committed
324

325 326 327 328
  /* FirstMatch variables (final QEP) */
  struct st_join_table *first_sj_inner_tab;
  struct st_join_table *last_sj_inner_tab;

329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
  /* Variables for semi-join duplicate elimination */
  SJ_TMP_TABLE  *flush_weedout_table;
  SJ_TMP_TABLE  *check_weed_out_table;
  
  /*
    If set, means we should stop join enumeration after we've got the first
    match and return to the specified join tab. May point to
    join->join_tab[-1] which means stop join execution after the first
    match.
  */
  struct st_join_table  *do_firstmatch;
 
  /* 
     ptr  - We're doing a LooseScan, this join tab is the first (i.e. 
            "driving") join tab), and ptr points to the last join tab
            handled by the strategy. loosescan_match_tab->found_match
            should be checked to see if the current value group had a match.
     NULL - Not doing a loose scan on this join tab.
  */
  struct st_join_table *loosescan_match_tab;
349 350 351
  
  /* TRUE <=> we are inside LooseScan range */
  bool inside_loosescan_range;
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370

  /* Buffer to save index tuple to be able to skip duplicates */
  uchar *loosescan_buf;
  
  /* Length of key tuple (depends on #keyparts used) to store in the above */
  uint loosescan_key_len;

  /* Used by LooseScan. TRUE<=> there has been a matching record combination */
  bool found_match;
  
  /*
    Used by DuplicateElimination. tab->table->ref must have the rowid
    whenever we have a current record.
  */
  int  keep_current_rowid;

  /* NestedOuterJoins: Bitmap of nested joins this table is part of */
  nested_join_map embedding_map;

371 372 373
  /*
    Semi-join strategy to be used for this join table. This is a copy of
    POSITION::sj_strategy field. This field is set up by the
374
    fix_semijoin_strategies_for_picked_join_order.
375 376 377
  */
  uint sj_strategy;

Sergey Petrunya's avatar
Sergey Petrunya committed
378
  uint n_sj_tables;
379

380 381
  bool preread_init_done;

382
  void cleanup();
383 384 385 386 387 388
  inline bool is_using_loose_index_scan()
  {
    return (select && select->quick &&
            (select->quick->get_type() ==
             QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX));
  }
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
  bool is_inner_table_of_semi_join_with_first_match()
  {
    return first_sj_inner_tab != NULL;
  }
  bool is_inner_table_of_outer_join()
  {
    return first_inner != NULL;
  }
  bool is_single_inner_of_semi_join_with_first_match()
  {
    return first_sj_inner_tab == this && last_sj_inner_tab == this;            
  }
  bool is_single_inner_of_outer_join()
  {
    return first_inner == this && first_inner->last_inner == this;
  }
  bool is_first_inner_for_outer_join()
  {
    return first_inner && first_inner == this;
  }
  bool use_match_flag()
  {
    return is_first_inner_for_outer_join() || first_sj_inner_tab == this ; 
  }
  bool check_only_first_match()
  {
415 416
    return is_inner_table_of_semi_join_with_first_match() ||
           (is_inner_table_of_outer_join() &&
417 418 419 420 421 422 423
            table->reginfo.not_exists_optimize);
  }
  bool is_last_inner_table()
  {
    return (first_inner && first_inner->last_inner == this) ||
           last_sj_inner_tab == this;
  }
Igor Babaev's avatar
Igor Babaev committed
424 425 426 427 428 429 430 431 432 433 434 435 436
  /*
    Check whether the table belongs to a nest of inner tables of an
    outer join or to a nest of inner tables of a semi-join
  */
  bool is_nested_inner()
  {
    if (first_inner && 
        (first_inner != first_inner->last_inner || first_inner->first_upper))
      return TRUE;
    if (first_sj_inner_tab && first_sj_inner_tab != last_sj_inner_tab)
      return TRUE;
    return FALSE;
  }
437 438 439 440 441 442
  struct st_join_table *get_first_inner_table()
  {
    if (first_inner)
      return first_inner;
    return first_sj_inner_tab; 
  }
443 444 445 446 447 448 449 450 451 452 453 454 455 456
  void set_select_cond(COND *to, uint line)
  {
    DBUG_PRINT("info", ("select_cond changes %p -> %p at line %u tab %p",
                        select_cond, to, line, this));
    select_cond= to;
  }
  COND *set_cond(COND *new_cond)
  {
    COND *tmp_select_cond= select_cond;
    set_select_cond(new_cond, __LINE__);
    if (select)
      select->cond= new_cond;
    return tmp_select_cond;
  }
457 458
  void calc_used_field_length(bool max_fl);
  ulong get_used_fieldlength()
459
  {
460 461 462
    if (!used_fieldlength)
      calc_used_field_length(FALSE);
    return used_fieldlength;
463
  }
464
  ulong get_max_used_fieldlength()
465
  {
466 467 468
    if (!max_used_fieldlength)
      calc_used_field_length(TRUE);
    return max_used_fieldlength;
469
  }
470
  double get_partial_join_cardinality() { return partial_join_cardinality; }
Igor Babaev's avatar
Igor Babaev committed
471
  bool hash_join_is_possible();
472
  int make_scan_filter();
473 474 475 476 477
  bool is_ref_for_hash_join() { return is_hash_join_key_no(ref.key); }
  KEY *get_keyinfo_by_key_no(uint key) 
  {
    return (is_hash_join_key_no(key) ? hj_key : table->key_info+key);
  }
478
  double scan_time();
479
  bool preread_init();
480 481

  bool is_sjm_nest() { return test(bush_children); }
unknown's avatar
unknown committed
482
} JOIN_TAB;
483 484


485
#include "sql_join_cache.h"
486

487 488 489 490
enum_nested_loop_state sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool
                                        end_of_records);
enum_nested_loop_state sub_select(JOIN *join,JOIN_TAB *join_tab, bool
                                  end_of_records);
491 492 493 494 495 496 497 498
enum_nested_loop_state
end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
	       bool end_of_records);
enum_nested_loop_state
end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
		bool end_of_records);


unknown's avatar
unknown committed
499
/**
500 501 502 503
  Information about a position of table within a join order. Used in join
  optimization.
*/
typedef struct st_position
504
{
505 506 507 508 509
  /*
    The "fanout": number of output rows that will be produced (after
    pushed down selection condition is applied) per each row combination of
    previous tables.
  */
unknown's avatar
unknown committed
510
  double records_read;
511

512 513 514 515 516
  /* 
    Cost accessing the table in course of the entire complete join execution,
    i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) times 
    number the access method will be invoked.
  */
517
  double read_time;
unknown's avatar
unknown committed
518
  JOIN_TAB *table;
519 520 521 522 523

  /*
    NULL  -  'index' or 'range' or 'index_merge' or 'ALL' access is used.
    Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}
  */
unknown's avatar
unknown committed
524
  KEYUSE *key;
525 526 527

  /* If ref-based access is used: bitmap of tables this table depends on  */
  table_map ref_depend_map;
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591

  bool use_join_buffer; 
  
  
  /* These form a stack of partial join order costs and output sizes */
  COST_VECT prefix_cost;
  double    prefix_record_count;

  /*
    Current optimization state: Semi-join strategy to be used for this
    and preceding join tables.
    
    Join optimizer sets this for the *last* join_tab in the
    duplicate-generating range. That is, in order to interpret this field, 
    one needs to traverse join->[best_]positions array from right to left.
    When you see a join table with sj_strategy!= SJ_OPT_NONE, some other
    field (depending on the strategy) tells how many preceding positions 
    this applies to. The values of covered_preceding_positions->sj_strategy
    must be ignored.
  */
  uint sj_strategy;
  /*
    Valid only after fix_semijoin_strategies_for_picked_join_order() call:
    if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that
    are covered by the specified semi-join strategy
  */
  uint n_sj_tables;

/* LooseScan strategy members */

  /* The first (i.e. driving) table we're doing loose scan for */
  uint        first_loosescan_table;
  /* 
     Tables that need to be in the prefix before we can calculate the cost
     of using LooseScan strategy.
  */
  table_map   loosescan_need_tables;

  /*
    keyno  -  Planning to do LooseScan on this key. If keyuse is NULL then 
              this is a full index scan, otherwise this is a ref+loosescan
              scan (and keyno matches the KEUSE's)
    MAX_KEY - Not doing a LooseScan
  */
  uint loosescan_key;  // final (one for strategy instance )
  uint loosescan_parts; /* Number of keyparts to be kept distinct */
  
/* FirstMatch strategy */
  /*
    Index of the first inner table that we intend to handle with this
    strategy
  */
  uint first_firstmatch_table;
  /*
    Tables that were not in the join prefix when we've started considering 
    FirstMatch strategy.
  */
  table_map first_firstmatch_rtbl;
  /* 
    Tables that need to be in the prefix before we can calculate the cost
    of using FirstMatch strategy.
   */
  table_map firstmatch_need_tables;

592 593
  bool in_firstmatch_prefix() { return (first_firstmatch_table != MAX_TABLES); }
  void invalidate_firstmatch_prefix() { first_firstmatch_table= MAX_TABLES; }
594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612

/* Duplicate Weedout strategy */
  /* The first table that the strategy will need to handle */
  uint  first_dupsweedout_table;
  /*
    Tables that we will need to have in the prefix to do the weedout step
    (all inner and all outer that the involved semi-joins are correlated with)
  */
  table_map dupsweedout_tables;

/* SJ-Materialization-Scan strategy */
  /* The last inner table (valid once we're after it) */
  uint      sjm_scan_last_inner;
  /*
    Tables that we need to have in the prefix to calculate the correct cost.
    Basically, we need all inner tables and outer tables mentioned in the
    semi-join's ON expression so we can correctly account for fanout.
  */
  table_map sjm_scan_need_tables;
613 614

  table_map prefix_dups_producing_tables;
unknown's avatar
unknown committed
615 616
} POSITION;

617

618 619 620 621
typedef struct st_rollup
{
  enum State { STATE_NONE, STATE_INITED, STATE_READY };
  State state;
unknown's avatar
unknown committed
622
  Item_null_result **null_items;
623 624 625 626
  Item ***ref_pointer_arrays;
  List<Item> *fields;
} ROLLUP;

627 628 629 630 631 632 633 634 635 636 637 638 639

#define SJ_OPT_NONE 0
#define SJ_OPT_DUPS_WEEDOUT 1
#define SJ_OPT_LOOSE_SCAN   2
#define SJ_OPT_FIRST_MATCH  3
#define SJ_OPT_MATERIALIZE  4
#define SJ_OPT_MATERIALIZE_SCAN  5

inline bool sj_is_materialize_strategy(uint strategy)
{
  return strategy >= SJ_OPT_MATERIALIZE;
}

640 641 642 643 644 645 646
class JOIN_TAB_RANGE: public Sql_alloc
{
public:
  JOIN_TAB *start;
  JOIN_TAB *end;
};

unknown's avatar
unknown committed
647

648 649
class JOIN :public Sql_alloc
{
650
private:
unknown's avatar
unknown committed
651 652
  JOIN(const JOIN &rhs);                        /**< not implemented */
  JOIN& operator=(const JOIN &rhs);             /**< not implemented */
653 654

protected:
unknown's avatar
unknown committed
655 656

  /**
unknown's avatar
unknown committed
657
    The subset of the state of a JOIN that represents an optimized query
658 659
    execution plan. Allows saving/restoring different JOIN plans for the same
    query.
unknown's avatar
unknown committed
660
  */
661
  class Join_plan_state {
unknown's avatar
unknown committed
662 663 664 665 666 667 668
  public:
    DYNAMIC_ARRAY keyuse; /* Copy of the JOIN::keyuse array. */
    POSITION best_positions[MAX_TABLES+1]; /* Copy of JOIN::best_positions */
    /* Copies of the JOIN_TAB::keyuse pointers for each JOIN_TAB. */
    KEYUSE *join_tab_keyuse[MAX_TABLES];
    /* Copies of JOIN_TAB::checked_keys for each JOIN_TAB. */
    key_map join_tab_checked_keys[MAX_TABLES];
669
    SJ_MATERIALIZATION_INFO *sj_mat_info[MAX_TABLES];
unknown's avatar
unknown committed
670
  public:
671
    Join_plan_state()
unknown's avatar
unknown committed
672 673 674 675
    {   
      keyuse.elements= 0;
      keyuse.buffer= NULL;
    }
676 677
    Join_plan_state(JOIN *join);
    ~Join_plan_state()
unknown's avatar
unknown committed
678 679 680 681 682
    {
      delete_dynamic(&keyuse);
    }
  };

683 684 685 686 687 688 689 690
  /* Results of reoptimizing a JOIN via JOIN::reoptimize(). */
  enum enum_reopt_result {
    REOPT_NEW_PLAN, /* there is a new reoptimized plan */
    REOPT_OLD_PLAN, /* no new improved plan can be found, use the old one */
    REOPT_ERROR,    /* an irrecovarable error occured during reoptimization */
    REOPT_NONE      /* not yet reoptimized */
  };

691
  /* Support for plan reoptimization with rewritten conditions. */
unknown's avatar
unknown committed
692
  enum_reopt_result reoptimize(Item *added_where, table_map join_tables,
693 694
                               Join_plan_state *save_to);
  void save_query_plan(Join_plan_state *save_to);
unknown's avatar
unknown committed
695
  void reset_query_plan();
696
  void restore_query_plan(Join_plan_state *restore_from);
697 698
  /* Choose a subquery plan for a table-less subquery. */
  bool choose_tableless_subquery_plan();
699

unknown's avatar
unknown committed
700
public:
701
  JOIN_TAB *join_tab, **best_ref;
unknown's avatar
unknown committed
702 703
  JOIN_TAB **map2table;    ///< mapping between table indexes and JOIN_TABs
  JOIN_TAB *join_tab_save; ///< saved join_tab for subquery reexecution
704 705 706

  List<JOIN_TAB_RANGE> join_tab_ranges;
  
707 708
  /*
    Base tables participating in the join. After join optimization is done, the
709 710
    tables are stored in the join order (but the only really important part is 
    that const tables are first).
711
  */
712 713 714 715 716 717 718
  TABLE    **table;
  /**
    The table which has an index that allows to produce the requried ordering.
    A special value of 0x1 means that the ordering will be produced by
    passing 1st non-const table to filesort(). NULL means no such table exists.
  */
  TABLE    *sort_by_table;
719 720 721 722 723 724 725
  /* 
    Number of tables in the join. 
    (In MySQL, it is named 'tables' and is also the number of elements in 
     join->join_tab array. In MariaDB, the latter is not true, so we've renamed
     the variable)
  */
  uint	   table_count;
726 727
  uint     outer_tables;  /**< Number of tables that are not inside semijoin */
  uint     const_tables;
728 729 730 731 732 733
  /* 
    Number of tables in the top join_tab array. Normally this matches
    (join_tab_ranges.head()->end - join_tab_ranges.head()->start). 
    
    We keep it here so that it is saved/restored with JOIN::restore_tmp.
  */
734
  uint     top_join_tab_count;
unknown's avatar
unknown committed
735
  uint	   send_group_parts;
736
  bool	   group;          /**< If query contains GROUP BY clause */
737 738 739 740 741 742 743
  /**
    Indicates that grouping will be performed on the result set during
    query execution. This field belongs to query execution.

    @see make_group_fields, alloc_group_fields, JOIN::exec
  */
  bool     sort_and_group; 
744
  bool     first_record,full_join, no_field_update;
745
  bool	   do_send_rows;
unknown's avatar
unknown committed
746
  /**
747 748 749 750
    TRUE when we want to resume nested loop iterations when
    fetching data from a cursor
  */
  bool     resume_nested_loop;
Sergey Petrunya's avatar
Sergey Petrunya committed
751 752 753 754 755 756
  table_map const_table_map;
  /*
    Constant tables for which we have found a row (as opposed to those for
    which we didn't).
  */
  table_map found_const_table_map;
Sergey Petrunia's avatar
Sergey Petrunia committed
757 758
  
  /* Tables removed by table elimination. Set to 0 before the elimination. */
Sergey Petrunia's avatar
Sergey Petrunia committed
759
  table_map eliminated_tables;
760
  /*
761 762
     Bitmap of all inner tables from outer joins (set at start of
     make_join_statistics)
763 764
  */
  table_map outer_join;
Igor Babaev's avatar
Igor Babaev committed
765 766
  /* Bitmap of tables used in the select list items */
  table_map select_list_used_tables;
unknown's avatar
unknown committed
767
  ha_rows  send_records,found_records,examined_rows,row_limit, select_limit;
unknown's avatar
unknown committed
768
  /**
unknown's avatar
unknown committed
769
    Used to fetch no more than given amount of rows per one
770 771 772 773 774 775 776 777
    fetch operation of server side cursor.
    The value is checked in end_send and end_send_group in fashion, similar
    to offset_limit_cnt:
      - fetch_limit= HA_POS_ERROR if there is no cursor.
      - when we open a cursor, we set fetch_limit to 0,
      - on each fetch iteration we add num_rows to fetch to fetch_limit
  */
  ha_rows  fetch_limit;
778 779 780 781 782 783 784 785 786
  /* Finally picked QEP. This is result of join optimization */
  POSITION best_positions[MAX_TABLES+1];

/******* Join optimization state members start *******/
  /*
    pointer - we're doing optimization for a semi-join materialization nest.
    NULL    - otherwise
  */
  TABLE_LIST *emb_sjm_nest;
787
  
788 789 790 791
  /* Current join optimization state */
  POSITION positions[MAX_TABLES+1];
  
  /*
792 793 794 795
    Bitmap of nested joins embedding the position at the end of the current 
    partial join (valid only during join optimizer run).
  */
  nested_join_map cur_embedding_map;
796 797 798 799 800 801 802 803 804 805 806 807 808 809
  
  /*
    Bitmap of inner tables of semi-join nests that have a proper subset of
    their tables in the current join prefix. That is, of those semi-join
    nests that have their tables both in and outside of the join prefix.
  */
  table_map cur_sj_inner_tables;
  
  /*
    Bitmap of semi-join inner tables that are in the join prefix and for
    which there's no provision for how to eliminate semi-join duplicates
    they produce.
  */
  table_map cur_dups_producing_tables;
810

811 812 813 814 815 816 817
  /* We also maintain a stack of join optimization states in * join->positions[] */
/******* Join optimization state members end *******/
  /*
    The cost of best complete join plan found so far during optimization,
    after optimization phase - cost of picked join order (not taking into
    account the changes made by test_if_skip_sort_order()).
  */
unknown's avatar
unknown committed
818
  double   best_read;
unknown's avatar
unknown committed
819
  /*
820
    Estimated result rows (fanout) of the join operation. If this is a subquery
unknown's avatar
unknown committed
821 822 823 824 825
    that is reexecuted multiple times, this value includes the estiamted # of
    reexecutions. This value is equal to the multiplication of all
    join->positions[i].records_read of a JOIN.
  */
  double   record_count;
unknown's avatar
unknown committed
826
  List<Item> *fields;
unknown's avatar
unknown committed
827
  List<Cached_item> group_fields, group_fields_cache;
unknown's avatar
unknown committed
828
  TABLE    *tmp_table;
unknown's avatar
unknown committed
829
  /// used to store 2 possible tmp table of SELECT
830
  TABLE    *exec_tmp_table1, *exec_tmp_table2;
unknown's avatar
unknown committed
831
  THD	   *thd;
832
  Item_sum  **sum_funcs, ***sum_funcs_end;
unknown's avatar
unknown committed
833
  /** second copy of sumfuncs (for queries with 2 temporary tables */
834
  Item_sum  **sum_funcs2, ***sum_funcs_end2;
unknown's avatar
unknown committed
835 836
  Procedure *procedure;
  Item	    *having;
unknown's avatar
unknown committed
837 838
  Item      *tmp_having; ///< To store having when processed temporary table
  Item      *having_history; ///< Store having for explain
839
  ulonglong  select_options;
840 841 842 843 844 845 846 847 848
  /* 
    Bitmap of allowed types of the join caches that
    can be used for join operations
  */
  uint allowed_join_cache_types;
  bool allowed_semijoin_with_cache;
  bool allowed_outer_join_with_cache;
  /* Maximum level of the join caches that can be used for join operations */ 
  uint max_allowed_join_cache_level;
unknown's avatar
unknown committed
849 850 851
  select_result *result;
  TMP_TABLE_PARAM tmp_table_param;
  MYSQL_LOCK *lock;
unknown's avatar
unknown committed
852
  /// unit structure (with global parameters) for this select
853
  SELECT_LEX_UNIT *unit;
unknown's avatar
unknown committed
854
  /// select that processed
855
  SELECT_LEX *select_lex;
unknown's avatar
unknown committed
856
  /** 
857 858 859 860 861 862 863
    TRUE <=> optimizer must not mark any table as a constant table.
    This is needed for subqueries in form "a IN (SELECT .. UNION SELECT ..):
    when we optimize the select that reads the results of the union from a
    temporary table, we must not mark the temp. table as constant because
    the number of rows in it may vary from one subquery execution to another.
  */
  bool no_const_tables; 
864 865 866 867 868
  /*
    This flag is set if we call no_rows_in_result() as par of end_group().
    This is used as a simple speed optimization to avoiding calling
    restore_no_rows_in_result() in ::reinit()
  */
869
  bool no_rows_in_result_called;
870
  
871 872 873
  /**
    Copy of this JOIN to be used with temporary tables.

874 875 876 877 878 879 880 881 882 883 884 885
    tmp_join is used when the JOIN needs to be "reusable" (e.g. in a
    subquery that gets re-executed several times) and we know will use
    temporary tables for materialization. The materialization to a
    temporary table overwrites the JOIN structure to point to the
    temporary table after the materialization is done. This is where
    tmp_join is used : it's a copy of the JOIN before the
    materialization and is used in restoring before re-execution by
    overwriting the current JOIN structure with the saved copy.
    Because of this we should pay extra care of not freeing up helper
    structures that are referenced by the original contents of the
    JOIN. We can check for this by making sure the "current" join is
    not the temporary copy, e.g.  !tmp_join || tmp_join != join
886
 
887 888
    We should free these sub-structures at JOIN::destroy() if the
    "current" join has a copy is not that copy.
889 890
  */
  JOIN *tmp_join;
unknown's avatar
unknown committed
891
  ROLLUP rollup;				///< Used with rollup
892

unknown's avatar
unknown committed
893 894
  bool select_distinct;				///< Set if SELECT DISTINCT
  /**
895 896 897 898 899 900 901
    If we have the GROUP BY statement in the query,
    but the group_list was emptied by optimizer, this
    flag is TRUE.
    It happens when fields in the GROUP BY are from
    constant table
  */
  bool group_optimized_away;
unknown's avatar
unknown committed
902 903 904 905 906

  /*
    simple_xxxxx is set if ORDER/GROUP BY doesn't include any references
    to other tables than the first non-constant table in the JOIN.
    It's also set if ORDER/GROUP BY is empty.
907 908
    Used for deciding for or against using a temporary table to compute 
    GROUP/ORDER BY.
unknown's avatar
unknown committed
909 910
  */
  bool simple_order, simple_group;
unknown's avatar
unknown committed
911
  /**
unknown's avatar
unknown committed
912 913 914 915
    Is set only in case if we have a GROUP BY clause
    and no ORDER BY after constant elimination of 'order'.
  */
  bool no_order;
unknown's avatar
unknown committed
916
  /** Is set if we have a GROUP BY and we have ORDER BY on a constant. */
unknown's avatar
unknown committed
917 918
  bool          skip_sort_order;

919
  bool need_tmp, hidden_group_fields;
920
  DYNAMIC_ARRAY keyuse;
921
  Item::cond_result cond_value, having_value;
unknown's avatar
unknown committed
922 923
  List<Item> all_fields; ///< to store all fields that used in query
  ///Above list changed to use temporary table
924
  List<Item> tmp_all_fields1, tmp_all_fields2, tmp_all_fields3;
unknown's avatar
unknown committed
925
  ///Part, shared with list above, emulate following list
926
  List<Item> tmp_fields_list1, tmp_fields_list2, tmp_fields_list3;
unknown's avatar
unknown committed
927
  List<Item> &fields_list; ///< hold field list passed to mysql_select
928
  List<Item> procedure_fields_list;
929 930 931 932
  int error;

  ORDER *order, *group_list, *proc_param; //hold parameters of mysql_select
  COND *conds;                            // ---"---
unknown's avatar
unknown committed
933
  Item *conds_history;                    // store WHERE for explain
Igor Babaev's avatar
Igor Babaev committed
934
  COND *outer_ref_cond;       ///<part of conds containing only outer references
unknown's avatar
unknown committed
935 936
  TABLE_LIST *tables_list;           ///<hold 'tables' parameter of mysql_select
  List<TABLE_LIST> *join_list;       ///< list of joined tables in reverse order
937
  COND_EQUAL *cond_equal;
938
  COND_EQUAL *having_equal;
939 940 941 942 943 944
  /*
    Constant codition computed during optimization, but evaluated during
    join execution. Typically expensive conditions that should not be
    evaluated at optimization time.
  */
  Item *exec_const_cond;
unknown's avatar
unknown committed
945 946 947 948 949 950 951
  /*
    Constant ORDER and/or GROUP expressions that contain subqueries. Such
    expressions need to evaluated to verify that the subquery indeed
    returns a single row. The evaluation of such expressions is delayed
    until query execution.
  */
  List<Item> exec_const_order_group_cond;
unknown's avatar
unknown committed
952 953 954
  SQL_SELECT *select;                ///<created in optimisation phase
  JOIN_TAB *return_tab;              ///<used only for outer joins
  Item **ref_pointer_array; ///<used pointer reference for this select
955
  // Copy of above to be used with different lists
956
  Item **items0, **items1, **items2, **items3, **current_ref_pointer_array;
unknown's avatar
unknown committed
957 958
  uint ref_pointer_array_size; ///< size of above in bytes
  const char *zero_result_cause; ///< not 0 if exec must return zero result
959
  
unknown's avatar
unknown committed
960 961
  bool union_part; ///< this subselect is part of union 
  bool optimized; ///< flag to avoid double optimization in EXPLAIN
962
  bool initialized; ///< flag to avoid double init_execution calls
963

964 965 966 967 968 969
  /*
    Additional WHERE and HAVING predicates to be considered for IN=>EXISTS
    subquery transformation of a JOIN object.
  */
  Item *in_to_exists_where;
  Item *in_to_exists_having;
970
  
971 972
  /* Temporary tables used to weed-out semi-join duplicates */
  List<TABLE> sj_tmp_tables;
Sergey Petrunya's avatar
Sergey Petrunya committed
973
  /* SJM nests that are executed with SJ-Materialization strategy */
974 975
  List<SJ_MATERIALIZATION_INFO> sjm_info_list;

976 977 978 979 980 981
  /* 
    storage for caching buffers allocated during query execution. 
    These buffers allocations need to be cached as the thread memory pool is
    cleared only at the end of the execution of the whole query and not caching
    allocations that occur in repetition at execution time will result in 
    excessive memory usage.
982 983 984
    Note: make_simple_join always creates an execution plan that accesses
    a single table, thus it is sufficient to have a one-element array for
    table_reexec.
985 986
  */  
  SORT_FIELD *sortorder;                        // make_unireg_sortorder()
987
  TABLE *table_reexec[1];                       // make_simple_join()
988
  JOIN_TAB *join_tab_reexec;                    // make_simple_join()
989 990
  /* end of allocation caching storage */

991
  JOIN(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
992
       select_result *result_arg)
Igor Babaev's avatar
Igor Babaev committed
993
    :fields_list(fields_arg)
994
  {
995
    init(thd_arg, fields_arg, select_options_arg, result_arg);
996
  }
997

998
  void init(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
999 1000
       select_result *result_arg)
  {
1001
    join_tab= join_tab_save= 0;
1002
    table= 0;
1003
    table_count= 0;
1004
    top_join_tab_count= 0;
1005
    const_tables= 0;
Sergey Petrunia's avatar
Sergey Petrunia committed
1006
    eliminated_tables= 0;
1007
    join_list= 0;
1008
    implicit_grouping= FALSE;
1009 1010 1011
    sort_and_group= 0;
    first_record= 0;
    do_send_rows= 1;
1012
    resume_nested_loop= FALSE;
1013 1014
    send_records= 0;
    found_records= 0;
1015
    fetch_limit= HA_POS_ERROR;
1016 1017 1018
    examined_rows= 0;
    exec_tmp_table1= 0;
    exec_tmp_table2= 0;
1019
    sortorder= 0;
1020
    table_reexec[0]= 0;
1021
    join_tab_reexec= 0;
1022
    thd= thd_arg;
unknown's avatar
merge  
unknown committed
1023
    sum_funcs= sum_funcs2= 0;
1024
    procedure= 0;
unknown's avatar
unknown committed
1025
    having= tmp_having= having_history= 0;
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
    select_options= select_options_arg;
    result= result_arg;
    lock= thd_arg->lock;
    select_lex= 0; //for safety
    tmp_join= 0;
    select_distinct= test(select_options & SELECT_DISTINCT);
    no_order= 0;
    simple_order= 0;
    simple_group= 0;
    skip_sort_order= 0;
    need_tmp= 0;
    hidden_group_fields= 0; /*safety*/
    error= 0;
    select= 0;
1040
    return_tab= 0;
1041 1042 1043 1044
    ref_pointer_array= items0= items1= items2= items3= 0;
    ref_pointer_array_size= 0;
    zero_result_cause= 0;
    optimized= 0;
1045
    initialized= 0;
1046
    cond_equal= 0;
1047
    having_equal= 0;
1048
    exec_const_cond= 0;
1049
    group_optimized_away= 0;
1050
    no_rows_in_result_called= 0;
1051

unknown's avatar
unknown committed
1052
    all_fields= fields_arg;
1053 1054
    if (&fields_list != &fields_arg)      /* Avoid valgrind-warning */
      fields_list= fields_arg;
1055
    bzero((char*) &keyuse,sizeof(keyuse));
1056
    tmp_table_param.init();
1057
    tmp_table_param.end_write_records= HA_POS_ERROR;
1058
    rollup.state= ROLLUP::STATE_NONE;
1059 1060

    no_const_tables= FALSE;
Igor Babaev's avatar
Igor Babaev committed
1061
    outer_ref_cond= 0;
1062 1063
    in_to_exists_where= NULL;
    in_to_exists_having= NULL;
1064
  }
1065

1066 1067 1068
  int prepare(Item ***rref_pointer_array, TABLE_LIST *tables, uint wind_num,
	      COND *conds, uint og_num, ORDER *order, ORDER *group,
	      Item *having, ORDER *proc_param, SELECT_LEX *select,
1069
	      SELECT_LEX_UNIT *unit);
1070
  bool prepare_stage2();
1071
  int optimize();
1072
  int reinit();
1073
  int init_execution();
1074
  void exec();
1075
  int destroy();
1076
  void restore_tmp();
1077
  bool alloc_func_list();
1078
  bool flatten_subqueries();
1079
  bool optimize_unflattened_subqueries();
1080
  bool make_sum_func_list(List<Item> &all_fields, List<Item> &send_fields,
1081
			  bool before_group_by, bool recompute= FALSE);
1082

1083 1084 1085 1086 1087
  inline void set_items_ref_array(Item **ptr)
  {
    memcpy((char*) ref_pointer_array, (char*) ptr, ref_pointer_array_size);
    current_ref_pointer_array= ptr;
  }
1088 1089 1090 1091
  inline void init_items_ref_array()
  {
    items0= ref_pointer_array + all_fields.elements;
    memcpy(items0, ref_pointer_array, ref_pointer_array_size);
1092
    current_ref_pointer_array= items0;
1093
  }
1094 1095

  bool rollup_init();
1096
  bool rollup_process_const_fields();
1097 1098
  bool rollup_make_fields(List<Item> &all_fields, List<Item> &fields,
			  Item_sum ***func);
1099
  int rollup_send_data(uint idx);
unknown's avatar
unknown committed
1100
  int rollup_write_data(uint idx, TABLE *table);
unknown's avatar
unknown committed
1101
  /**
1102 1103 1104 1105 1106
    Release memory and, if possible, the open tables held by this execution
    plan (and nested plans). It's used to release some tables before
    the end of execution in order to increase concurrency and reduce
    memory consumption.
  */
1107
  void join_free();
unknown's avatar
unknown committed
1108
  /** Cleanup this JOIN, possibly for reuse */
1109
  void cleanup(bool full);
1110
  void clear();
1111
  bool save_join_tab();
unknown's avatar
unknown committed
1112
  bool init_save_join_tab();
1113 1114
  bool send_row_on_empty_set()
  {
unknown's avatar
unknown committed
1115
    return (do_send_rows && implicit_grouping && !group_optimized_away &&
unknown's avatar
unknown committed
1116
            having_value != Item::COND_FALSE);
1117
  }
unknown's avatar
unknown committed
1118
  bool change_result(select_result *result);
1119 1120 1121 1122 1123
  bool is_top_level_join() const
  {
    return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 ||
                                        select_lex == unit->fake_select_lex));
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
1124 1125
  inline table_map all_tables_map()
  {
1126
    return (table_map(1) << table_count) - 1;
Sergey Petrunya's avatar
Sergey Petrunya committed
1127
  }
1128
  void drop_unused_derived_keys();
Igor Babaev's avatar
Igor Babaev committed
1129
  inline void eval_select_list_used_tables();
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139
  /* 
    Return the table for which an index scan can be used to satisfy 
    the sort order needed by the ORDER BY/(implicit) GROUP BY clause 
  */
  JOIN_TAB *get_sort_by_join_tab()
  {
    return (need_tmp || !sort_by_table || skip_sort_order ||
            ((group || tmp_table_param.sum_func_count) && !group_list)) ?
              NULL : join_tab+const_tables;
  }
unknown's avatar
unknown committed
1140
  bool setup_subquery_caches();
1141 1142 1143
  bool shrink_join_buffers(JOIN_TAB *jt, 
                           ulonglong curr_space,
                           ulonglong needed_space);
1144 1145 1146 1147 1148 1149
  void set_allowed_join_cache_types();
  bool is_allowed_hash_join_access()
  { 
    return test(allowed_join_cache_types & JOIN_CACHE_HASHED_BIT) &&
           max_allowed_join_cache_level > JOIN_CACHE_HASHED_BIT;
  }
1150
  bool choose_subquery_plan(table_map join_tables);
1151
  void get_partial_cost_and_fanout(int end_tab_idx,
Sergey Petrunya's avatar
Sergey Petrunya committed
1152 1153 1154
                                   table_map filter_map,
                                   double *read_time_arg, 
                                   double *record_count_arg);
Sergey Petrunya's avatar
Sergey Petrunya committed
1155 1156 1157
  void get_prefix_cost_and_fanout(uint n_tables, 
                                  double *read_time_arg,
                                  double *record_count_arg);
1158 1159
  /* defined in opt_subselect.cc */
  bool transform_max_min_subquery();
1160 1161 1162 1163 1164
  /* True if this JOIN is a subquery under an IN predicate. */
  bool is_in_subquery()
  {
    return (unit->item && unit->item->is_in_predicate());
  }
1165
private:
1166 1167 1168 1169 1170
  /**
    TRUE if the query contains an aggregate function but has no GROUP
    BY clause. 
  */
  bool implicit_grouping; 
1171
  bool make_simple_join(JOIN *join, TABLE *tmp_table);
1172
  void cleanup_item_list(List<Item> &items) const;
unknown's avatar
unknown committed
1173 1174
};

1175 1176
enum enum_with_bush_roots { WITH_BUSH_ROOTS, WITHOUT_BUSH_ROOTS};
enum enum_with_const_tables { WITH_CONST_TABLES, WITHOUT_CONST_TABLES};
unknown's avatar
unknown committed
1177

1178 1179 1180
JOIN_TAB *first_linear_tab(JOIN *join, enum enum_with_const_tables const_tbls);
JOIN_TAB *next_linear_tab(JOIN* join, JOIN_TAB* tab, 
                          enum enum_with_bush_roots include_bush_roots);
unknown's avatar
unknown committed
1181

1182 1183
JOIN_TAB *first_top_level_tab(JOIN *join, enum enum_with_const_tables with_const);
JOIN_TAB *next_top_level_tab(JOIN *join, JOIN_TAB *tab);
unknown's avatar
unknown committed
1184 1185 1186 1187 1188 1189 1190 1191 1192

typedef struct st_select_check {
  uint const_ref,reg_ref;
} SELECT_CHECK;

extern const char *join_type_str[];
void TEST_join(JOIN *join);

/* Extern functions in sql_select.cc */
unknown's avatar
unknown committed
1193
bool store_val_in_field(Field *field, Item *val, enum_check_fields check_flag);
1194 1195
void count_field_types(SELECT_LEX *select_lex, TMP_TABLE_PARAM *param, 
                       List<Item> &fields, bool reset_with_sum_func);
1196 1197 1198 1199
bool setup_copy_fields(THD *thd, TMP_TABLE_PARAM *param,
		       Item **ref_pointer_array,
		       List<Item> &new_list1, List<Item> &new_list2,
		       uint elements, List<Item> &fields);
unknown's avatar
unknown committed
1200
void copy_fields(TMP_TABLE_PARAM *param);
1201
bool copy_funcs(Item **func_ptr, const THD *thd);
1202
bool create_internal_tmp_table_from_heap(THD *thd, TABLE *table, TMP_TABLE_PARAM *param,
unknown's avatar
unknown committed
1203
			     int error, bool ignore_last_dupp_error);
unknown's avatar
unknown committed
1204
uint find_shortest_key(TABLE *table, const key_map *usable_keys);
1205
Field* create_tmp_field_from_field(THD *thd, Field* org_field,
unknown's avatar
unknown committed
1206 1207 1208
                                   const char *name, TABLE *table,
                                   Item_field *item, uint convert_blob_length);
                                                                      
unknown's avatar
unknown committed
1209
/* functions from opt_sum.cc */
1210
bool simple_pred(Item_func *func_item, Item **args, bool *inv_order);
1211
int opt_sum_query(THD* thd,
Igor Babaev's avatar
Merge  
Igor Babaev committed
1212
                  List<TABLE_LIST> &tables, List<Item> &all_fields, COND *conds);
unknown's avatar
unknown committed
1213

1214
/* from sql_delete.cc, used by opt_range.cc */
1215
extern "C" int refpos_order_cmp(void* arg, const void *a,const void *b);
1216

unknown's avatar
unknown committed
1217
/** class to copying an field/item to a key struct */
unknown's avatar
unknown committed
1218 1219 1220

class store_key :public Sql_alloc
{
1221 1222
public:
  bool null_key; /* TRUE <=> the value of the key has a null part */
unknown's avatar
unknown committed
1223
  enum store_key_result { STORE_KEY_OK, STORE_KEY_FATAL, STORE_KEY_CONV };
Igor Babaev's avatar
Igor Babaev committed
1224
  enum Type { FIELD_STORE_KEY, ITEM_STORE_KEY, CONST_ITEM_STORE_KEY };
1225
  store_key(THD *thd, Field *field_arg, uchar *ptr, uchar *null, uint length)
1226
    :null_key(0), null_ptr(null), err(0)
unknown's avatar
unknown committed
1227
  {
1228 1229
    if (field_arg->type() == MYSQL_TYPE_BLOB
        || field_arg->type() == MYSQL_TYPE_GEOMETRY)
1230
    {
1231 1232 1233 1234
      /* 
        Key segments are always packed with a 2 byte length prefix.
        See mi_rkey for details.
      */
1235
      to_field= new Field_varstring(ptr, length, 2, null, 1, 
unknown's avatar
unknown committed
1236 1237 1238
                                    Field::NONE, field_arg->field_name,
                                    field_arg->table->s, field_arg->charset());
      to_field->init(field_arg->table);
1239
    }
unknown's avatar
unknown committed
1240
    else
unknown's avatar
unknown committed
1241
      to_field=field_arg->new_key_field(thd->mem_root, field_arg->table,
1242
                                        ptr, null, 1);
unknown's avatar
unknown committed
1243
  }
unknown's avatar
unknown committed
1244
  virtual ~store_key() {}			/** Not actually needed */
Igor Babaev's avatar
Igor Babaev committed
1245
  virtual enum Type type() const=0;
unknown's avatar
unknown committed
1246
  virtual const char *name() const=0;
1247 1248 1249 1250 1251 1252 1253 1254 1255 1256

  /**
    @brief sets ignore truncation warnings mode and calls the real copy method

    @details this function makes sure truncation warnings when preparing the
    key buffers don't end up as errors (because of an enclosing INSERT/UPDATE).
  */
  enum store_key_result copy()
  {
    enum store_key_result result;
1257 1258 1259 1260
    THD *thd= to_field->table->in_use;
    enum_check_fields saved_count_cuted_fields= thd->count_cuted_fields;
    ulong sql_mode= thd->variables.sql_mode;
    thd->variables.sql_mode&= ~(MODE_NO_ZERO_IN_DATE | MODE_NO_ZERO_DATE);
1261

1262
    thd->count_cuted_fields= CHECK_FIELD_IGNORE;
1263 1264 1265

    result= copy_inner();

1266 1267
    thd->count_cuted_fields= saved_count_cuted_fields;
    thd->variables.sql_mode= sql_mode;
1268 1269 1270 1271 1272 1273

    return result;
  }

 protected:
  Field *to_field;				// Store data here
1274 1275
  uchar *null_ptr;
  uchar err;
1276 1277

  virtual enum store_key_result copy_inner()=0;
unknown's avatar
unknown committed
1278 1279 1280 1281 1282 1283 1284 1285
};


class store_key_field: public store_key
{
  Copy_field copy_field;
  const char *field_name;
 public:
1286 1287
  store_key_field(THD *thd, Field *to_field_arg, uchar *ptr,
                  uchar *null_ptr_arg,
unknown's avatar
unknown committed
1288
		  uint length, Field *from_field, const char *name_arg)
unknown's avatar
unknown committed
1289
    :store_key(thd, to_field_arg,ptr,
unknown's avatar
unknown committed
1290
	       null_ptr_arg ? null_ptr_arg : from_field->maybe_null() ? &err
1291
	       : (uchar*) 0, length), field_name(name_arg)
unknown's avatar
unknown committed
1292 1293 1294 1295 1296
  {
    if (to_field)
    {
      copy_field.set(to_field,from_field,0);
    }
Igor Babaev's avatar
Igor Babaev committed
1297 1298 1299
  }  

  enum Type type() const { return FIELD_STORE_KEY; }
1300 1301
  const char *name() const { return field_name; }

Igor Babaev's avatar
Igor Babaev committed
1302 1303 1304 1305 1306 1307
  void change_source_field(Item_field *fld_item)
  {
    copy_field.set(to_field, fld_item->field, 0);
    field_name= fld_item->full_name();
  }

1308 1309
 protected: 
  enum store_key_result copy_inner()
1310
  {
1311 1312 1313
    TABLE *table= copy_field.to_field->table;
    my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
                                                     table->write_set);
Igor Babaev's avatar
Igor Babaev committed
1314 1315 1316 1317 1318 1319 1320 1321 1322

    /* 
      It looks like the next statement is needed only for a simplified
      hash function over key values used now in BNLH join.
      When the implementation of this function will be replaced for a proper
      full version this statement probably should be removed.
    */  
    bzero(copy_field.to_ptr,copy_field.to_length);

1323
    copy_field.do_copy(&copy_field);
1324
    dbug_tmp_restore_column_map(table->write_set, old_map);
1325
    null_key= to_field->is_null();
unknown's avatar
unknown committed
1326
    return err != 0 ? STORE_KEY_FATAL : STORE_KEY_OK;
1327
  }
unknown's avatar
unknown committed
1328 1329 1330 1331 1332 1333 1334
};


class store_key_item :public store_key
{
 protected:
  Item *item;
unknown's avatar
unknown committed
1335 1336 1337 1338 1339
  /*
    Flag that forces usage of save_val() method which save value of the
    item instead of save_in_field() method which saves result.
  */
  bool use_value;
unknown's avatar
unknown committed
1340
public:
1341
  store_key_item(THD *thd, Field *to_field_arg, uchar *ptr,
unknown's avatar
unknown committed
1342
                 uchar *null_ptr_arg, uint length, Item *item_arg, bool val)
1343
    :store_key(thd, to_field_arg, ptr,
unknown's avatar
unknown committed
1344
	       null_ptr_arg ? null_ptr_arg : item_arg->maybe_null ?
unknown's avatar
unknown committed
1345
	       &err : (uchar*) 0, length), item(item_arg), use_value(val)
unknown's avatar
unknown committed
1346
  {}
Igor Babaev's avatar
Igor Babaev committed
1347 1348

  enum Type type() const { return ITEM_STORE_KEY; }
1349 1350 1351 1352
  const char *name() const { return "func"; }

 protected:  
  enum store_key_result copy_inner()
unknown's avatar
unknown committed
1353
  {
1354 1355 1356
    TABLE *table= to_field->table;
    my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
                                                     table->write_set);
unknown's avatar
unknown committed
1357
    int res= FALSE;
Igor Babaev's avatar
Igor Babaev committed
1358 1359 1360 1361 1362 1363 1364 1365 1366

    /* 
      It looks like the next statement is needed only for a simplified
      hash function over key values used now in BNLH join.
      When the implementation of this function will be replaced for a proper
      full version this statement probably should be removed.
    */  
    to_field->reset();

unknown's avatar
unknown committed
1367 1368 1369 1370
    if (use_value)
      item->save_val(to_field);
    else
      res= item->save_in_field(to_field, 1);
1371 1372 1373 1374 1375
    /*
     Item::save_in_field() may call Item::val_xxx(). And if this is a subquery
     we need to check for errors executing it and react accordingly
    */
    if (!res && table->in_use->is_error())
1376
      res= 1; /* STORE_KEY_FATAL */
1377
    dbug_tmp_restore_column_map(table->write_set, old_map);
1378
    null_key= to_field->is_null() || item->null_value;
1379 1380
    return ((err != 0 || res < 0 || res > 2) ? STORE_KEY_FATAL : 
            (store_key_result) res);
unknown's avatar
unknown committed
1381 1382 1383 1384 1385 1386 1387 1388
  }
};


class store_key_const_item :public store_key_item
{
  bool inited;
public:
1389 1390
  store_key_const_item(THD *thd, Field *to_field_arg, uchar *ptr,
		       uchar *null_ptr_arg, uint length,
unknown's avatar
unknown committed
1391
		       Item *item_arg)
unknown's avatar
unknown committed
1392
    :store_key_item(thd, to_field_arg,ptr,
unknown's avatar
unknown committed
1393
		    null_ptr_arg ? null_ptr_arg : item_arg->maybe_null ?
unknown's avatar
unknown committed
1394
		    &err : (uchar*) 0, length, item_arg, FALSE), inited(0)
unknown's avatar
unknown committed
1395 1396
  {
  }
Igor Babaev's avatar
Igor Babaev committed
1397 1398

  enum Type type() const { return CONST_ITEM_STORE_KEY; }
1399 1400 1401 1402
  const char *name() const { return "const"; }

protected:  
  enum store_key_result copy_inner()
unknown's avatar
unknown committed
1403
  {
unknown's avatar
unknown committed
1404
    int res;
unknown's avatar
unknown committed
1405 1406 1407
    if (!inited)
    {
      inited=1;
1408 1409 1410
      TABLE *table= to_field->table;
      my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
                                                       table->write_set);
unknown's avatar
unknown committed
1411 1412 1413
      if ((res= item->save_in_field(to_field, 1)))
      {       
        if (!err)
1414
          err= res < 0 ? 1 : res; /* 1=STORE_KEY_FATAL */
unknown's avatar
unknown committed
1415
      }
1416 1417 1418 1419 1420
      /*
        Item::save_in_field() may call Item::val_xxx(). And if this is a subquery
        we need to check for errors executing it and react accordingly
        */
      if (!err && to_field->table->in_use->is_error())
1421
        err= 1; /* STORE_KEY_FATAL */
1422
      dbug_tmp_restore_column_map(table->write_set, old_map);
unknown's avatar
unknown committed
1423
    }
1424
    null_key= to_field->is_null() || item->null_value;
1425
    return (err > 2 ? STORE_KEY_FATAL : (store_key_result) err);
unknown's avatar
unknown committed
1426 1427 1428
  }
};

1429
bool cp_buffer_from_ref(THD *thd, TABLE *table, TABLE_REF *ref);
unknown's avatar
unknown committed
1430
bool error_if_full_join(JOIN *join);
1431
int report_error(TABLE *table, int error);
1432
int safe_index_read(JOIN_TAB *tab);
1433
COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value);
1434
int test_if_item_cache_changed(List<Cached_item> &list);
1435
int join_init_read_record(JOIN_TAB *tab);
1436
int join_read_record_no_init(JOIN_TAB *tab);
Sergey Petrunia's avatar
Sergey Petrunia committed
1437
void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key);
1438 1439 1440 1441
inline Item * and_items(Item* cond, Item *item)
{
  return (cond? (new Item_cond_and(cond, item)) : item);
}
unknown's avatar
unknown committed
1442
bool choose_plan(JOIN *join, table_map join_tables);
1443 1444 1445
void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab, 
                                table_map last_remaining_tables, 
                                bool first_alt, uint no_jbuf_before,
1446
                                double *outer_rec_count, double *reopt_cost);
1447 1448 1449 1450
Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field,
                            bool *inherited_fl);
bool test_if_ref(COND *root_cond, 
                 Item_field *left_item,Item *right_item);
1451 1452 1453 1454 1455 1456

inline bool optimizer_flag(THD *thd, uint flag)
{ 
  return (thd->variables.optimizer_switch & flag);
}

1457
/* Table elimination entry point function */
Sergey Petrunya's avatar
Sergey Petrunya committed
1458
void eliminate_tables(JOIN *join);
Sergey Petrunia's avatar
Sergey Petrunia committed
1459

1460
/* Index Condition Pushdown entry point function */
1461
void push_index_cond(JOIN_TAB *tab, uint keyno);
1462

1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474
/****************************************************************************
  Temporary table support for SQL Runtime
 ***************************************************************************/

#define STRING_TOTAL_LENGTH_TO_PACK_ROWS 128
#define AVG_STRING_LENGTH_TO_PACK_ROWS   64
#define RATIO_TO_PACK_ROWS	       2
#define MIN_STRING_LENGTH_TO_PACK_ROWS   10

TABLE *create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
			ORDER *group, bool distinct, bool save_sum_fields,
			ulonglong select_options, ha_rows rows_limit,
1475
                        char* alias, bool do_not_open=FALSE);
1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486
void free_tmp_table(THD *thd, TABLE *entry);
bool create_internal_tmp_table_from_heap(THD *thd, TABLE *table,
                                         ENGINE_COLUMNDEF *start_recinfo,
                                         ENGINE_COLUMNDEF **recinfo, 
                                         int error, bool ignore_last_dupp_key_error);
bool create_internal_tmp_table(TABLE *table, KEY *keyinfo, 
                               ENGINE_COLUMNDEF *start_recinfo,
                               ENGINE_COLUMNDEF **recinfo, 
                               ulonglong options);
bool open_tmp_table(TABLE *table);
void setup_tmp_table_column_bitmaps(TABLE *table, uchar *bitmaps);
unknown's avatar
unknown committed
1487
double prev_record_reads(POSITION *positions, uint idx, table_map found_ref);
1488
void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist);
1489

unknown's avatar
unknown committed
1490
#endif /* SQL_SELECT_INCLUDED */