← 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: 2008-07-28 18:01:38 UTC
  • Revision ID: brian@tangent.org-20080728180138-q2pxlq0qiapvqsdn
Remove YEAR field type

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 drizzled::memory::SqlAlloc
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
 
  drizzled::optimizer::SqlSelect *select; /**< created in optimization phase */
147
 
 
148
 
  /**
149
 
    Bitmap of nested joins embedding the position at the end of the current
150
 
    partial join (valid only during join optimizer run).
151
 
  */
152
 
  std::bitset<64> cur_embedding_map;
153
 
 
154
 
  /**
155
 
   * The cost for the final query execution plan chosen after optimization
156
 
   * has completed. The QEP is stored in the best_positions variable.
157
 
   */
158
 
  double best_read;
159
 
  List<Cached_item> group_fields;
160
 
  List<Cached_item> group_fields_cache;
161
 
  Table *tmp_table;
162
 
  /** used to store 2 possible tmp table of SELECT */
163
 
  Table *exec_tmp_table1;
164
 
  Table *exec_tmp_table2;
165
 
  Item_sum **sum_funcs;
166
 
  Item_sum ***sum_funcs_end;
167
 
  /** second copy of sumfuncs (for queries with 2 temporary tables */
168
 
  Item_sum **sum_funcs2;
169
 
  Item_sum ***sum_funcs_end2;
170
 
  Item *having;
171
 
  Item *tmp_having; /**< To store having when processed temporary table */
172
 
  Item *having_history; /**< Store having for explain */
173
 
  uint64_t select_options;
174
 
  select_result *result;
175
 
  Tmp_Table_Param tmp_table_param;
176
 
  DRIZZLE_LOCK *lock;
177
 
 
178
 
  JOIN *tmp_join; /**< copy of this JOIN to be used with temporary tables */
179
 
  ROLLUP rollup;                                /**< Used with rollup */
180
 
  DYNAMIC_ARRAY keyuse;
181
 
  Item::cond_result cond_value;
182
 
  Item::cond_result having_value;
183
 
  List<Item> all_fields; /**< to store all fields that used in query */
184
 
  /** Above list changed to use temporary table */
185
 
  List<Item> tmp_all_fields1;
186
 
  List<Item> tmp_all_fields2;
187
 
  List<Item> tmp_all_fields3;
188
 
  /** Part, shared with list above, emulate following list */
189
 
  List<Item> tmp_fields_list1;
190
 
  List<Item> tmp_fields_list2;
191
 
  List<Item> tmp_fields_list3;
192
 
  int error;
193
 
 
194
 
  order_st *order;
195
 
  order_st *group_list; /**< hold parameters of mysql_select */
196
 
  COND *conds;                            // ---"---
197
 
  Item *conds_history; /**< store WHERE for explain */
198
 
  TableList *tables_list; /**< hold 'tables' parameter of mysql_select */
199
 
  COND_EQUAL *cond_equal;
200
 
  JoinTable *return_tab; /**< used only for outer joins */
201
 
  Item **ref_pointer_array; /**< used pointer reference for this select */
202
 
  /** Copy of above to be used with different lists */
203
 
  Item **items0;
204
 
  Item **items1;
205
 
  Item **items2;
206
 
  Item **items3;
207
 
  Item **current_ref_pointer_array;
208
 
  uint32_t ref_pointer_array_size; ///< size of above in bytes
209
 
  const char *zero_result_cause; ///< not 0 if exec must return zero result
210
 
 
211
 
  /*
212
 
    storage for caching buffers allocated during query execution.
213
 
    These buffers allocations need to be cached as the thread memory pool is
214
 
    cleared only at the end of the execution of the whole query and not caching
215
 
    allocations that occur in repetition at execution time will result in
216
 
    excessive memory usage.
217
 
  */
218
 
  SORT_FIELD *sortorder;                        // make_unireg_sortorder()
219
 
  Table **table_reexec;                         // make_simple_join()
220
 
  JoinTable *join_tab_reexec;                    // make_simple_join()
221
 
  /* end of allocation caching storage */
222
 
 
223
 
  /** Constructors */
224
 
  JOIN(Session *session_arg, 
225
 
       List<Item> &fields_arg, 
226
 
       uint64_t select_options_arg,
227
 
       select_result *result_arg)
228
 
    :
229
 
      join_tab(NULL),
230
 
      best_ref(NULL),
231
 
      map2table(NULL),
232
 
      join_tab_save(NULL),
233
 
      table(NULL),
234
 
      all_tables(NULL),
235
 
      sort_by_table(NULL),
236
 
      tables(0),
237
 
      outer_tables(0),
238
 
      const_tables(0),
239
 
      send_group_parts(0),
240
 
      sort_and_group(false),
241
 
      first_record(false),
242
 
      full_join(false),
243
 
      group(false),
244
 
      no_field_update(false),
245
 
      do_send_rows(true),
246
 
      resume_nested_loop(false),
247
 
      no_const_tables(false),
248
 
      select_distinct(false),
249
 
      group_optimized_away(false),
250
 
      simple_order(false),
251
 
      simple_group(false),
252
 
      no_order(false),
253
 
      skip_sort_order(false),
254
 
      union_part(false),
255
 
      optimized(false),
256
 
      need_tmp(false),
257
 
      hidden_group_fields(false),
258
 
      const_table_map(0),
259
 
      found_const_table_map(0),
260
 
      outer_join(0),
261
 
      send_records(0),
262
 
      found_records(0),
263
 
      examined_rows(0),
264
 
      row_limit(0),
265
 
      select_limit(0),
266
 
      fetch_limit(HA_POS_ERROR),
267
 
      session(session_arg),
268
 
      fields_list(fields_arg), 
269
 
      join_list(NULL),
270
 
      unit(NULL),
271
 
      select_lex(NULL),
272
 
      select(NULL),
273
 
      exec_tmp_table1(NULL),
274
 
      exec_tmp_table2(NULL),
275
 
      sum_funcs(NULL),
276
 
      sum_funcs2(NULL),
277
 
      having(NULL),
278
 
      tmp_having(NULL),
279
 
      having_history(NULL),
280
 
      select_options(select_options_arg),
281
 
      result(result_arg),
282
 
      lock(session_arg->lock),
283
 
      tmp_join(NULL),
284
 
      all_fields(fields_arg),
285
 
      error(0),
286
 
      cond_equal(NULL),
287
 
      return_tab(NULL),
288
 
      ref_pointer_array(NULL),
289
 
      items0(NULL),
290
 
      items1(NULL),
291
 
      items2(NULL),
292
 
      items3(NULL),
293
 
      ref_pointer_array_size(0),
294
 
      zero_result_cause(NULL),
295
 
      sortorder(NULL),
296
 
      table_reexec(NULL),
297
 
      join_tab_reexec(NULL)
298
 
  {
299
 
    select_distinct= test(select_options & SELECT_DISTINCT);
300
 
    if (&fields_list != &fields_arg) /* only copy if not same*/
301
 
      fields_list= fields_arg;
302
 
    memset(&keyuse, 0, sizeof(keyuse));
303
 
    tmp_table_param.init();
304
 
    tmp_table_param.end_write_records= HA_POS_ERROR;
305
 
    rollup.state= ROLLUP::STATE_NONE;
306
 
  }
307
 
 
308
 
  /** 
309
 
   * This method is currently only used when a subselect EXPLAIN is performed.
310
 
   * I pulled out the init() method and have simply reset the values to what
311
 
   * was previously in the init() method.  See the note about the hack in 
312
 
   * sql_union.cc...
313
 
   */
314
 
  inline void reset(Session *session_arg, 
315
 
       List<Item> &fields_arg, 
316
 
       uint64_t select_options_arg,
317
 
       select_result *result_arg)
318
 
  {
319
 
    join_tab= NULL;
320
 
    best_ref= NULL;
321
 
    map2table= NULL;
322
 
    join_tab_save= NULL;
323
 
    table= NULL;
324
 
    all_tables= NULL;
325
 
    sort_by_table= NULL;
326
 
    tables= 0;
327
 
    outer_tables= 0;
328
 
    const_tables= 0;
329
 
    send_group_parts= 0;
330
 
    sort_and_group= false;
331
 
    first_record= false;
332
 
    full_join= false;
333
 
    group= false;
334
 
    no_field_update= false;
335
 
    do_send_rows= true;
336
 
    resume_nested_loop= false;
337
 
    no_const_tables= false;
338
 
    select_distinct= false;
339
 
    group_optimized_away= false;
340
 
    simple_order= false;
341
 
    simple_group= false;
342
 
    no_order= false;
343
 
    skip_sort_order= false;
344
 
    union_part= false;
345
 
    optimized= false;
346
 
    need_tmp= false;
347
 
    hidden_group_fields= false;
348
 
    const_table_map= 0;
349
 
    found_const_table_map= 0;
350
 
    outer_join= 0;
351
 
    send_records= 0;
352
 
    found_records= 0;
353
 
    examined_rows= 0;
354
 
    row_limit= 0;
355
 
    select_limit= 0;
356
 
    fetch_limit= HA_POS_ERROR;
357
 
    session= session_arg;
358
 
    fields_list= fields_arg; 
359
 
    join_list= NULL;
360
 
    unit= NULL;
361
 
    select_lex= NULL;
362
 
    select= NULL;
363
 
    exec_tmp_table1= NULL;
364
 
    exec_tmp_table2= NULL;
365
 
    sum_funcs= NULL;
366
 
    sum_funcs2= NULL;
367
 
    having= NULL;
368
 
    tmp_having= NULL;
369
 
    having_history= NULL;
370
 
    select_options= select_options_arg;
371
 
    result= result_arg;
372
 
    lock= session_arg->lock;
373
 
    tmp_join= NULL;
374
 
    all_fields= fields_arg;
375
 
    error= 0;
376
 
    cond_equal= NULL;
377
 
    return_tab= NULL;
378
 
    ref_pointer_array= NULL;
379
 
    items0= NULL;
380
 
    items1= NULL;
381
 
    items2= NULL;
382
 
    items3= NULL;
383
 
    ref_pointer_array_size= 0;
384
 
    zero_result_cause= NULL;
385
 
    sortorder= NULL;
386
 
    table_reexec= NULL;
387
 
    join_tab_reexec= NULL;
388
 
    select_distinct= test(select_options & SELECT_DISTINCT);
389
 
    if (&fields_list != &fields_arg) /* only copy if not same*/
390
 
      fields_list= fields_arg;
391
 
    memset(&keyuse, 0, sizeof(keyuse));
392
 
    tmp_table_param.init();
393
 
    tmp_table_param.end_write_records= HA_POS_ERROR;
394
 
    rollup.state= ROLLUP::STATE_NONE;
395
 
  }
396
 
 
397
 
  int prepare(Item ***rref_pointer_array, 
398
 
              TableList *tables,
399
 
              uint32_t wind_num,
400
 
              COND *conds,
401
 
              uint32_t og_num,
402
 
              order_st *order,
403
 
              order_st *group,
404
 
              Item *having,
405
 
              Select_Lex *select,
406
 
              Select_Lex_Unit *unit);
407
 
  int optimize();
408
 
  int reinit();
409
 
  void exec();
410
 
  int destroy();
411
 
  void restore_tmp();
412
 
  bool alloc_func_list();
413
 
  bool setup_subquery_materialization();
414
 
  bool make_sum_func_list(List<Item> &all_fields, 
415
 
                          List<Item> &send_fields,
416
 
                                          bool before_group_by,
417
 
                          bool recompute= false);
418
 
 
419
 
  inline void set_items_ref_array(Item **ptr)
420
 
  {
421
 
    memcpy(ref_pointer_array, ptr, ref_pointer_array_size);
422
 
    current_ref_pointer_array= ptr;
423
 
  }
424
 
  inline void init_items_ref_array()
425
 
  {
426
 
    items0= ref_pointer_array + all_fields.elements;
427
 
    memcpy(items0, ref_pointer_array, ref_pointer_array_size);
428
 
    current_ref_pointer_array= items0;
429
 
  }
430
 
 
431
 
  bool rollup_init();
432
 
  bool rollup_make_fields(List<Item> &all_fields, 
433
 
                          List<Item> &fields,
434
 
                                          Item_sum ***func);
435
 
  int rollup_send_data(uint32_t idx);
436
 
  int rollup_write_data(uint32_t idx, Table *table);
437
 
  void remove_subq_pushed_predicates(Item **where);
438
 
  /**
439
 
    Release memory and, if possible, the open tables held by this execution
440
 
    plan (and nested plans). It's used to release some tables before
441
 
    the end of execution in order to increase concurrency and reduce
442
 
    memory consumption.
443
 
  */
444
 
  void join_free();
445
 
  /** Cleanup this JOIN, possibly for reuse */
446
 
  void cleanup(bool full);
447
 
  void clear();
448
 
  bool save_join_tab();
449
 
  bool init_save_join_tab();
450
 
  bool send_row_on_empty_set()
451
 
  {
452
 
    return (do_send_rows && tmp_table_param.sum_func_count != 0 &&
453
 
            !group_list);
454
 
  }
455
 
  bool change_result(select_result *result);
456
 
  bool is_top_level_join() const
457
 
  {
458
 
    return (unit == &session->lex->unit && (unit->fake_select_lex == 0 ||
459
 
                                        select_lex == unit->fake_select_lex));
460
 
  }
461
 
 
462
 
  /**
463
 
   * Copy the partial query plan into the optimal query plan.
464
 
   *
465
 
   * @param[in] size the size of the plan which is to be copied
466
 
   */
467
 
  void copyPartialPlanIntoOptimalPlan(uint32_t size)
468
 
  {
469
 
    memcpy(best_positions, positions, 
470
 
           sizeof(drizzled::optimizer::Position) * size);
471
 
  }
472
 
 
473
 
  void cache_const_exprs();
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 */