← Back to branch summary

~drizzle-pbxt/drizzle/drizzle-pbxt-2

« back to all changes in this revision

Viewing changes to drizzled/join.h

  • Committer: Paul McCullagh
  • Date: 2009-11-10 14:18:39 UTC
  • mfrom: (1038.1.7 drizzle-pbxt-pre-merge)
  • Revision ID: paul.mccullagh@primebase.org-20091110141839-2j3k43b17ag6f605
Merged Drizzle trunk and PBXT 1.0.09

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/join.h
 
1
/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 
3
 *
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
 
5
 *
 
6
 *  This program is free software; you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation; either version 2 of the License, or
 
9
 *  (at your option) any later version.
 
10
 *
 
11
 *  This program is distributed in the hope that it will be useful,
 
12
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 *  GNU General Public License for more details.
 
15
 *
 
16
 *  You should have received a copy of the GNU General Public License
 
17
 *  along with this program; if not, write to the Free Software
 
18
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
19
 */
 
20
 
 
21
/**
 
22
 * @file
 
23
 *
 
24
 * Defines the JOIN class
 
25
 */
 
26
 
 
27
#ifndef DRIZZLED_JOIN_H
 
28
#define DRIZZLED_JOIN_H
 
29
 
 
30
#include <drizzled/optimizer/position.h>
 
31
#include <bitset>
 
32
 
 
33
class JOIN :public Sql_alloc
 
34
{
 
35
  JOIN(const JOIN &rhs);                        /**< not implemented */
 
36
  JOIN& operator=(const JOIN &rhs);             /**< not implemented */
 
37
 
 
38
  /**
 
39
   * Contains a partial query execution plan which is extended during
 
40
   * cost-based optimization.
 
41
   */
 
42
  drizzled::optimizer::Position positions[MAX_TABLES+1];
 
43
 
 
44
  /**
 
45
   * Contains the optimal query execution plan after cost-based optimization
 
46
   * has taken place. 
 
47
   */
 
48
  drizzled::optimizer::Position best_positions[MAX_TABLES+1];
 
49
 
 
50
public:
 
51
  JoinTable *join_tab;
 
52
  JoinTable **best_ref;
 
53
  JoinTable **map2table;    /**< mapping between table indexes and JoinTables */
 
54
  JoinTable *join_tab_save; /**< saved join_tab for subquery reexecution */
 
55
 
 
56
  Table **table;
 
57
  Table **all_tables;
 
58
  /**
 
59
    The table which has an index that allows to produce the requried ordering.
 
60
    A special value of 0x1 means that the ordering will be produced by
 
61
    passing 1st non-const table to filesort(). NULL means no such table exists.
 
62
  */
 
63
  Table *sort_by_table;
 
64
 
 
65
  uint32_t tables;        /**< Number of tables in the join */
 
66
  uint32_t outer_tables;  /**< Number of tables that are not inside semijoin */
 
67
  uint32_t const_tables;
 
68
  uint32_t send_group_parts;
 
69
 
 
70
  bool sort_and_group;
 
71
  bool first_record;
 
72
  bool full_join;
 
73
  bool group;
 
74
  bool no_field_update;
 
75
  bool do_send_rows;
 
76
  /**
 
77
    true when we want to resume nested loop iterations when
 
78
    fetching data from a cursor
 
79
  */
 
80
  bool resume_nested_loop;
 
81
  /**
 
82
    true <=> optimizer must not mark any table as a constant table.
 
83
    This is needed for subqueries in form "a IN (SELECT .. UNION SELECT ..):
 
84
    when we optimize the select that reads the results of the union from a
 
85
    temporary table, we must not mark the temp. table as constant because
 
86
    the number of rows in it may vary from one subquery execution to another.
 
87
  */
 
88
  bool no_const_tables;
 
89
  bool select_distinct;                         /**< Set if SELECT DISTINCT */
 
90
  /**
 
91
    If we have the GROUP BY statement in the query,
 
92
    but the group_list was emptied by optimizer, this
 
93
    flag is true.
 
94
    It happens when fields in the GROUP BY are from
 
95
    constant table
 
96
  */
 
97
  bool group_optimized_away;
 
98
 
 
99
  /*
 
100
    simple_xxxxx is set if order_st/GROUP BY doesn't include any references
 
101
    to other tables than the first non-constant table in the JOIN.
 
102
    It's also set if order_st/GROUP BY is empty.
 
103
  */
 
104
  bool simple_order;
 
105
  bool simple_group;
 
106
  /**
 
107
    Is set only in case if we have a GROUP BY clause
 
108
    and no order_st BY after constant elimination of 'order'.
 
109
  */
 
110
  bool no_order;
 
111
  /** Is set if we have a GROUP BY and we have order_st BY on a constant. */
 
112
  bool skip_sort_order;
 
113
  bool union_part; /**< this subselect is part of union */
 
114
  bool optimized; /**< flag to avoid double optimization in EXPLAIN */
 
115
  bool need_tmp;
 
116
  bool hidden_group_fields;
 
117
 
 
118
  table_map const_table_map;
 
119
  table_map found_const_table_map;
 
120
  table_map outer_join;
 
121
 
 
122
  ha_rows send_records;
 
123
  ha_rows found_records;
 
124
  ha_rows examined_rows;
 
125
  ha_rows row_limit;
 
126
  ha_rows select_limit;
 
127
  /**
 
128
    Used to fetch no more than given amount of rows per one
 
129
    fetch operation of server side cursor.
 
130
    The value is checked in end_send and end_send_group in fashion, similar
 
131
    to offset_limit_cnt:
 
132
      - fetch_limit= HA_POS_ERROR if there is no cursor.
 
133
      - when we open a cursor, we set fetch_limit to 0,
 
134
      - on each fetch iteration we add num_rows to fetch to fetch_limit
 
135
  */
 
136
  ha_rows fetch_limit;
 
137
 
 
138
  Session       *session;
 
139
  List<Item> *fields;
 
140
  List<Item> &fields_list; /**< hold field list passed to mysql_select */
 
141
  List<TableList> *join_list; /**< list of joined tables in reverse order */
 
142
  /** unit structure (with global parameters) for this select */
 
143
  Select_Lex_Unit *unit;
 
144
  /** select that processed */
 
145
  Select_Lex *select_lex;
 
146
  SQL_SELECT *select; /**< created in optimisation phase */
 
147
  Array<Item_in_subselect> sj_subselects;
 
148
 
 
149
  /**
 
150
    Bitmap of nested joins embedding the position at the end of the current
 
151
    partial join (valid only during join optimizer run).
 
152
  */
 
153
  std::bitset<64> cur_embedding_map;
 
154
 
 
155
  /**
 
156
   * The cost for the final query execution plan chosen after optimization
 
157
   * has completed. The QEP is stored in the best_positions variable.
 
158
   */
 
159
  double best_read;
 
160
  List<Cached_item> group_fields;
 
161
  List<Cached_item> group_fields_cache;
 
162
  Table *tmp_table;
 
163
  /** used to store 2 possible tmp table of SELECT */
 
164
  Table *exec_tmp_table1;
 
165
  Table *exec_tmp_table2;
 
166
  Item_sum **sum_funcs;
 
167
  Item_sum ***sum_funcs_end;
 
168
  /** second copy of sumfuncs (for queries with 2 temporary tables */
 
169
  Item_sum **sum_funcs2;
 
170
  Item_sum ***sum_funcs_end2;
 
171
  Item *having;
 
172
  Item *tmp_having; /**< To store having when processed temporary table */
 
173
  Item *having_history; /**< Store having for explain */
 
174
  uint64_t select_options;
 
175
  select_result *result;
 
176
  Tmp_Table_Param tmp_table_param;
 
177
  DRIZZLE_LOCK *lock;
 
178
 
 
179
  JOIN *tmp_join; /**< copy of this JOIN to be used with temporary tables */
 
180
  ROLLUP rollup;                                /**< Used with rollup */
 
181
  DYNAMIC_ARRAY keyuse;
 
182
  Item::cond_result cond_value;
 
183
  Item::cond_result having_value;
 
184
  List<Item> all_fields; /**< to store all fields that used in query */
 
185
  /** Above list changed to use temporary table */
 
186
  List<Item> tmp_all_fields1;
 
187
  List<Item> tmp_all_fields2;
 
188
  List<Item> tmp_all_fields3;
 
189
  /** Part, shared with list above, emulate following list */
 
190
  List<Item> tmp_fields_list1;
 
191
  List<Item> tmp_fields_list2;
 
192
  List<Item> tmp_fields_list3;
 
193
  int error;
 
194
 
 
195
  order_st *order;
 
196
  order_st *group_list; /**< hold parameters of mysql_select */
 
197
  COND *conds;                            // ---"---
 
198
  Item *conds_history; /**< store WHERE for explain */
 
199
  TableList *tables_list; /**< hold 'tables' parameter of mysql_select */
 
200
  COND_EQUAL *cond_equal;
 
201
  JoinTable *return_tab; /**< used only for outer joins */
 
202
  Item **ref_pointer_array; /**< used pointer reference for this select */
 
203
  /** Copy of above to be used with different lists */
 
204
  Item **items0;
 
205
  Item **items1;
 
206
  Item **items2;
 
207
  Item **items3;
 
208
  Item **current_ref_pointer_array;
 
209
  uint32_t ref_pointer_array_size; ///< size of above in bytes
 
210
  const char *zero_result_cause; ///< not 0 if exec must return zero result
 
211
 
 
212
  /*
 
213
    storage for caching buffers allocated during query execution.
 
214
    These buffers allocations need to be cached as the thread memory pool is
 
215
    cleared only at the end of the execution of the whole query and not caching
 
216
    allocations that occur in repetition at execution time will result in
 
217
    excessive memory usage.
 
218
  */
 
219
  SORT_FIELD *sortorder;                        // make_unireg_sortorder()
 
220
  Table **table_reexec;                         // make_simple_join()
 
221
  JoinTable *join_tab_reexec;                    // make_simple_join()
 
222
  /* end of allocation caching storage */
 
223
 
 
224
  /** Constructors */
 
225
  JOIN(Session *session_arg, 
 
226
       List<Item> &fields_arg, 
 
227
       uint64_t select_options_arg,
 
228
       select_result *result_arg)
 
229
    :
 
230
      join_tab(NULL),
 
231
      best_ref(NULL),
 
232
      map2table(NULL),
 
233
      join_tab_save(NULL),
 
234
      table(NULL),
 
235
      all_tables(NULL),
 
236
      sort_by_table(NULL),
 
237
      tables(0),
 
238
      outer_tables(0),
 
239
      const_tables(0),
 
240
      send_group_parts(0),
 
241
      sort_and_group(false),
 
242
      first_record(false),
 
243
      full_join(false),
 
244
      group(false),
 
245
      no_field_update(false),
 
246
      do_send_rows(true),
 
247
      resume_nested_loop(false),
 
248
      no_const_tables(false),
 
249
      select_distinct(false),
 
250
      group_optimized_away(false),
 
251
      simple_order(false),
 
252
      simple_group(false),
 
253
      no_order(false),
 
254
      skip_sort_order(false),
 
255
      union_part(false),
 
256
      optimized(false),
 
257
      need_tmp(false),
 
258
      hidden_group_fields(false),
 
259
      const_table_map(0),
 
260
      found_const_table_map(0),
 
261
      outer_join(0),
 
262
      send_records(0),
 
263
      found_records(0),
 
264
      examined_rows(0),
 
265
      row_limit(0),
 
266
      select_limit(0),
 
267
      fetch_limit(HA_POS_ERROR),
 
268
      session(session_arg),
 
269
      fields_list(fields_arg), 
 
270
      join_list(NULL),
 
271
      unit(NULL),
 
272
      select_lex(NULL),
 
273
      select(NULL),
 
274
      sj_subselects(session_arg->mem_root, 4),
 
275
      exec_tmp_table1(NULL),
 
276
      exec_tmp_table2(NULL),
 
277
      sum_funcs(NULL),
 
278
      sum_funcs2(NULL),
 
279
      having(NULL),
 
280
      tmp_having(NULL),
 
281
      having_history(NULL),
 
282
      select_options(select_options_arg),
 
283
      result(result_arg),
 
284
      lock(session_arg->lock),
 
285
      tmp_join(NULL),
 
286
      all_fields(fields_arg),
 
287
      error(0),
 
288
      cond_equal(NULL),
 
289
      return_tab(NULL),
 
290
      ref_pointer_array(NULL),
 
291
      items0(NULL),
 
292
      items1(NULL),
 
293
      items2(NULL),
 
294
      items3(NULL),
 
295
      ref_pointer_array_size(0),
 
296
      zero_result_cause(NULL),
 
297
      sortorder(NULL),
 
298
      table_reexec(NULL),
 
299
      join_tab_reexec(NULL)
 
300
  {
 
301
    select_distinct= test(select_options & SELECT_DISTINCT);
 
302
    if (&fields_list != &fields_arg) /* only copy if not same*/
 
303
      fields_list= fields_arg;
 
304
    memset(&keyuse, 0, sizeof(keyuse));
 
305
    tmp_table_param.init();
 
306
    tmp_table_param.end_write_records= HA_POS_ERROR;
 
307
    rollup.state= ROLLUP::STATE_NONE;
 
308
  }
 
309
 
 
310
  /** 
 
311
   * This method is currently only used when a subselect EXPLAIN is performed.
 
312
   * I pulled out the init() method and have simply reset the values to what
 
313
   * was previously in the init() method.  See the note about the hack in 
 
314
   * sql_union.cc...
 
315
   */
 
316
  inline void reset(Session *session_arg, 
 
317
       List<Item> &fields_arg, 
 
318
       uint64_t select_options_arg,
 
319
       select_result *result_arg)
 
320
  {
 
321
    join_tab= NULL;
 
322
    best_ref= NULL;
 
323
    map2table= NULL;
 
324
    join_tab_save= NULL;
 
325
    table= NULL;
 
326
    all_tables= NULL;
 
327
    sort_by_table= NULL;
 
328
    tables= 0;
 
329
    outer_tables= 0;
 
330
    const_tables= 0;
 
331
    send_group_parts= 0;
 
332
    sort_and_group= false;
 
333
    first_record= false;
 
334
    full_join= false;
 
335
    group= false;
 
336
    no_field_update= false;
 
337
    do_send_rows= true;
 
338
    resume_nested_loop= false;
 
339
    no_const_tables= false;
 
340
    select_distinct= false;
 
341
    group_optimized_away= false;
 
342
    simple_order= false;
 
343
    simple_group= false;
 
344
    no_order= false;
 
345
    skip_sort_order= false;
 
346
    union_part= false;
 
347
    optimized= false;
 
348
    need_tmp= false;
 
349
    hidden_group_fields= false;
 
350
    const_table_map= 0;
 
351
    found_const_table_map= 0;
 
352
    outer_join= 0;
 
353
    send_records= 0;
 
354
    found_records= 0;
 
355
    examined_rows= 0;
 
356
    row_limit= 0;
 
357
    select_limit= 0;
 
358
    fetch_limit= HA_POS_ERROR;
 
359
    session= session_arg;
 
360
    fields_list= fields_arg; 
 
361
    join_list= NULL;
 
362
    unit= NULL;
 
363
    select_lex= NULL;
 
364
    select= NULL;
 
365
    exec_tmp_table1= NULL;
 
366
    exec_tmp_table2= NULL;
 
367
    sum_funcs= NULL;
 
368
    sum_funcs2= NULL;
 
369
    having= NULL;
 
370
    tmp_having= NULL;
 
371
    having_history= NULL;
 
372
    select_options= select_options_arg;
 
373
    result= result_arg;
 
374
    lock= session_arg->lock;
 
375
    tmp_join= NULL;
 
376
    all_fields= fields_arg;
 
377
    error= 0;
 
378
    cond_equal= NULL;
 
379
    return_tab= NULL;
 
380
    ref_pointer_array= NULL;
 
381
    items0= NULL;
 
382
    items1= NULL;
 
383
    items2= NULL;
 
384
    items3= NULL;
 
385
    ref_pointer_array_size= 0;
 
386
    zero_result_cause= NULL;
 
387
    sortorder= NULL;
 
388
    table_reexec= NULL;
 
389
    join_tab_reexec= NULL;
 
390
    select_distinct= test(select_options & SELECT_DISTINCT);
 
391
    if (&fields_list != &fields_arg) /* only copy if not same*/
 
392
      fields_list= fields_arg;
 
393
    memset(&keyuse, 0, sizeof(keyuse));
 
394
    tmp_table_param.init();
 
395
    tmp_table_param.end_write_records= HA_POS_ERROR;
 
396
    rollup.state= ROLLUP::STATE_NONE;
 
397
  }
 
398
 
 
399
  int prepare(Item ***rref_pointer_array, 
 
400
              TableList *tables,
 
401
              uint32_t wind_num,
 
402
              COND *conds,
 
403
              uint32_t og_num,
 
404
              order_st *order,
 
405
              order_st *group,
 
406
              Item *having,
 
407
              Select_Lex *select,
 
408
              Select_Lex_Unit *unit);
 
409
  int optimize();
 
410
  int reinit();
 
411
  void exec();
 
412
  int destroy();
 
413
  void restore_tmp();
 
414
  bool alloc_func_list();
 
415
  bool setup_subquery_materialization();
 
416
  bool make_sum_func_list(List<Item> &all_fields, 
 
417
                          List<Item> &send_fields,
 
418
                                          bool before_group_by,
 
419
                          bool recompute= false);
 
420
 
 
421
  inline void set_items_ref_array(Item **ptr)
 
422
  {
 
423
    memcpy(ref_pointer_array, ptr, ref_pointer_array_size);
 
424
    current_ref_pointer_array= ptr;
 
425
  }
 
426
  inline void init_items_ref_array()
 
427
  {
 
428
    items0= ref_pointer_array + all_fields.elements;
 
429
    memcpy(items0, ref_pointer_array, ref_pointer_array_size);
 
430
    current_ref_pointer_array= items0;
 
431
  }
 
432
 
 
433
  bool rollup_init();
 
434
  bool rollup_make_fields(List<Item> &all_fields, 
 
435
                          List<Item> &fields,
 
436
                                          Item_sum ***func);
 
437
  int rollup_send_data(uint32_t idx);
 
438
  int rollup_write_data(uint32_t idx, Table *table);
 
439
  void remove_subq_pushed_predicates(Item **where);
 
440
  /**
 
441
    Release memory and, if possible, the open tables held by this execution
 
442
    plan (and nested plans). It's used to release some tables before
 
443
    the end of execution in order to increase concurrency and reduce
 
444
    memory consumption.
 
445
  */
 
446
  void join_free();
 
447
  /** Cleanup this JOIN, possibly for reuse */
 
448
  void cleanup(bool full);
 
449
  void clear();
 
450
  bool save_join_tab();
 
451
  bool init_save_join_tab();
 
452
  bool send_row_on_empty_set()
 
453
  {
 
454
    return (do_send_rows && tmp_table_param.sum_func_count != 0 &&
 
455
            !group_list);
 
456
  }
 
457
  bool change_result(select_result *result);
 
458
  bool is_top_level_join() const
 
459
  {
 
460
    return (unit == &session->lex->unit && (unit->fake_select_lex == 0 ||
 
461
                                        select_lex == unit->fake_select_lex));
 
462
  }
 
463
 
 
464
  /**
 
465
   * Copy the partial query plan into the optimal query plan.
 
466
   *
 
467
   * @param[in] size the size of the plan which is to be copied
 
468
   */
 
469
  void copyPartialPlanIntoOptimalPlan(uint32_t size)
 
470
  {
 
471
    memcpy(best_positions, positions, 
 
472
           sizeof(drizzled::optimizer::Position) * size);
 
473
  }
 
474
 
 
475
  /**
 
476
   * @param[in] index the index of the position to retrieve
 
477
   * @return a reference to the specified position in the optimal
 
478
   *         query plan
 
479
   */
 
480
  drizzled::optimizer::Position &getPosFromOptimalPlan(uint32_t index)
 
481
  {
 
482
    return best_positions[index];
 
483
  }
 
484
 
 
485
  /**
 
486
   * @param[in] index the index of the position to retrieve
 
487
   * @return a reference to the specified position in the partial
 
488
   *         query plan
 
489
   */
 
490
  drizzled::optimizer::Position &getPosFromPartialPlan(uint32_t index)
 
491
  {
 
492
    return positions[index];
 
493
  }
 
494
 
 
495
  /**
 
496
   * @param[in] index the index of the position to set
 
497
   * @param[in] in_pos the value to set the position to
 
498
   */
 
499
  void setPosInPartialPlan(uint32_t index, drizzled::optimizer::Position &in_pos)
 
500
  {
 
501
    positions[index]= in_pos;
 
502
  }
 
503
 
 
504
  /**
 
505
   * @return a pointer to the first position in the partial query plan
 
506
   */
 
507
  drizzled::optimizer::Position *getFirstPosInPartialPlan()
 
508
  {
 
509
    return positions;
 
510
  }
 
511
 
 
512
  /**
 
513
   * @param[in] index the index of the operator to retrieve from the partial
 
514
   *                  query plan
 
515
   * @return a pointer to the position in the partial query plan
 
516
   */
 
517
  drizzled::optimizer::Position *getSpecificPosInPartialPlan(int32_t index)
 
518
  {
 
519
    return positions + index;
 
520
  }
 
521
 
 
522
};
 
523
 
 
524
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error);
 
525
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab);
 
526
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last);
 
527
enum_nested_loop_state end_send(JOIN *join, JoinTable *join_tab, bool end_of_records);
 
528
enum_nested_loop_state end_write(JOIN *join, JoinTable *join_tab, bool end_of_records);
 
529
enum_nested_loop_state end_update(JOIN *join, JoinTable *join_tab, bool end_of_records);
 
530
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *join_tab, bool end_of_records);
 
531
 
 
532
#endif /* DRIZZLED_JOIN_H */