← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/join.h

  • Committer: Brian Aker
  • Date: 2010-02-10 18:04:24 UTC
  • mfrom: (1286.1.5 build)
  • Revision ID: brian@gaz-20100210180424-03ypoyifmlc2lgcp
Merge of Brian/Padraig

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