« back to all changes in this revision
Viewing changes to drizzled/optimizer/sum.cc
- browse files at revision 1239
- compare with another revision
- compare with revision 2136
- download diff
- download tarball
- view history from revision 1239
- Committer: Brian Aker
- Date: 2009-12-06 01:55:53 UTC
- mfrom: (1238.1.5 push)
- Revision ID: brian@gaz-20091206015553-cva833q4gvwj11ob
Bundle for staging.
- files added:
- drizzled/optimizer/sum.h
- files renamed:
- drizzled/opt_range.cc => drizzled/optimizer/range.cc
- drizzled/opt_range.h => drizzled/optimizer/range.h
- drizzled/opt_sum.cc => drizzled/optimizer/sum.cc
- drizzled/time.cc => drizzled/time_functions.cc
- files modified:
- drizzled/Makefile.am
added
removed
drizzled/optimizer/sum.cc
1
/* Copyright (C) 2000-2003 MySQL AB
2
3
This program is free software; you can redistribute it and/or modify
4
it under the terms of the GNU General Public License as published by
5
the Free Software Foundation; version 2 of the License.
6
7
This program is distributed in the hope that it will be useful,
8
but WITHOUT ANY WARRANTY; without even the implied warranty of
9
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10
GNU General Public License for more details.
11
12
You should have received a copy of the GNU General Public License
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
15
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
*/
16
20
17
21
/**
18
22
@file
47
51
(assuming a index for column d of table t2 is defined)
48
52
*/
49
53
50
#include <drizzled/server_includes.h>
51
#include <drizzled/sql_select.h>
52
#include <drizzled/item/sum.h>
53
#include <drizzled/item/cmpfunc.h>
54
55
static bool find_key_for_maxmin(bool max_fl, table_reference_st *ref, Field* field,
56
COND *cond, uint32_t *range_fl,
54
#include "drizzled/server_includes.h"
55
#include "drizzled/sql_select.h"
56
#include "drizzled/item/sum.h"
57
#include "drizzled/item/cmpfunc.h"
58
#include "drizzled/optimizer/sum.h"
59
60
namespace drizzled
61
{
62
63
static bool find_key_for_maxmin(bool max_fl,
64
table_reference_st *ref,
65
Field* field,
66
COND *cond,
67
uint32_t *range_fl,
57
68
uint32_t *key_prefix_length);
58
static int reckey_in_range(bool max_fl, table_reference_st *ref, Field* field,
59
COND *cond, uint32_t range_fl, uint32_t prefix_len);
69
70
static int reckey_in_range(bool max_fl,
71
table_reference_st *ref,
72
Field* field,
73
COND *cond,
74
uint32_t range_fl,
75
uint32_t prefix_len);
76
60
77
static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
61
78
62
79
83
100
{
84
101
ha_rows tmp= tl->table->cursor->records();
85
102
if ((tmp == HA_POS_ERROR))
103
{
86
104
return UINT64_MAX;
105
}
87
106
count*= tmp;
88
107
}
89
108
return count;
90
109
}
91
110
92
111
93
/**
94
Substitutes constants for some COUNT(), MIN() and MAX() functions.
95
96
@param tables list of leaves of join table tree
97
@param all_fields All fields to be returned
98
@param conds WHERE clause
99
100
@note
101
This function is only called for queries with sum functions and no
102
GROUP BY part.
103
104
@retval
105
0 no errors
106
@retval
107
1 if all items were resolved
108
@retval
109
HA_ERR_KEY_NOT_FOUND on impossible conditions
110
@retval
111
HA_ERR_... if a deadlock or a lock wait timeout happens, for example
112
*/
113
114
int opt_sum_query(TableList *tables, List<Item> &all_fields,COND *conds)
112
int optimizer::sum_query(TableList *tables, List<Item> &all_fields, COND *conds)
115
113
{
116
114
List_iterator_fast<Item> it(all_fields);
117
115
int const_result= 1;
118
bool recalc_const_item= 0;
116
bool recalc_const_item= false;
119
117
uint64_t count= 1;
120
bool is_exact_count= true, maybe_exact_count= true;
121
table_map removed_tables= 0, outer_tables= 0, used_tables= 0;
118
bool is_exact_count= true;
119
bool maybe_exact_count= true;
120
table_map removed_tables= 0;
121
table_map outer_tables= 0;
122
table_map used_tables= 0;
122
123
table_map where_tables= 0;
123
124
Item *item;
124
125
int error;
125
126
126
127
if (conds)
128
{
127
129
where_tables= conds->used_tables();
130
}
128
131
129
132
/*
130
Analyze outer join dependencies, and, if possible, compute the number
131
of returned rows.
132
*/
133
Analyze outer join dependencies, and, if possible, compute the number
134
of returned rows.
135
*/
133
136
for (TableList *tl= tables; tl; tl= tl->next_leaf)
134
137
{
135
138
TableList *embedded;
139
142
break;
140
143
}
141
144
if (embedded)
142
/* Don't replace expression on a table that is part of an outer join */
145
/* Don't replace expression on a table that is part of an outer join */
143
146
{
144
147
outer_tables|= tl->table->map;
145
148
146
149
/*
147
We can't optimise LEFT JOIN in cases where the WHERE condition
148
restricts the table that is used, like in:
149
SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
150
WHERE t2.field IS NULL;
151
*/
150
We can't optimise LEFT JOIN in cases where the WHERE condition
151
restricts the table that is used, like in:
152
SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
153
WHERE t2.field IS NULL;
154
*/
152
155
if (tl->table->map & where_tables)
153
156
return 0;
154
157
}
155
158
else
159
{
156
160
used_tables|= tl->table->map;
161
}
157
162
158
163
/*
159
If the storage manager of 'tl' gives exact row count as part of
160
statistics (cheap), compute the total number of rows. If there are
161
no outer table dependencies, this count may be used as the real count.
162
Schema tables are filled after this function is invoked, so we can't
163
get row count
164
*/
165
if (!(tl->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)))
164
If the storage manager of 'tl' gives exact row count as part of
165
statistics (cheap), compute the total number of rows. If there are
166
no outer table dependencies, this count may be used as the real count.
167
Schema tables are filled after this function is invoked, so we can't
168
get row count
169
*/
170
if (! (tl->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)))
166
171
{
167
172
maybe_exact_count&= test(tl->table->cursor->getEngine()->check_flag(HTON_BIT_HAS_RECORDS));
168
173
is_exact_count= false;
169
count= 1; // ensure count != 0
174
count= 1; // ensure count != 0
170
175
}
171
176
else
172
177
{
181
186
}
182
187
183
188
/*
184
Iterate through all items in the SELECT clause and replace
185
COUNT(), MIN() and MAX() with constants (if possible).
186
*/
189
Iterate through all items in the SELECT clause and replace
190
COUNT(), MIN() and MAX() with constants (if possible).
191
*/
187
192
188
193
while ((item= it++))
189
194
{
190
195
if (item->type() == Item::SUM_FUNC_ITEM)
191
196
{
192
197
Item_sum *item_sum= (((Item_sum*) item));
193
switch (item_sum->sum_func()) {
194
case Item_sum::COUNT_FUNC:
195
/*
196
If the expr in COUNT(expr) can never be null we can change this
197
to the number of rows in the tables if this number is exact and
198
there are no outer joins.
199
*/
200
if (!conds && !((Item_sum_count*) item)->args[0]->maybe_null &&
201
!outer_tables && maybe_exact_count)
202
{
203
if (!is_exact_count)
204
{
205
if ((count= get_exact_record_count(tables)) == UINT64_MAX)
206
{
207
/* Error from handler in counting rows. Don't optimize count() */
208
const_result= 0;
209
continue;
210
}
211
is_exact_count= 1; // count is now exact
212
}
213
((Item_sum_count*) item)->make_const_count((int64_t) count);
214
recalc_const_item= 1;
215
}
216
else
217
const_result= 0;
218
break;
219
case Item_sum::MIN_FUNC:
220
{
221
/*
222
If MIN(expr) is the first part of a key or if all previous
223
parts of the key is found in the COND, then we can use
224
indexes to find the key.
225
*/
226
Item *expr=item_sum->args[0];
227
if (expr->real_item()->type() == Item::FIELD_ITEM)
228
{
229
unsigned char key_buff[MAX_KEY_LENGTH];
230
table_reference_st ref;
231
uint32_t range_fl, prefix_len;
232
233
ref.key_buff= key_buff;
234
Item_field *item_field= (Item_field*) (expr->real_item());
235
Table *table= item_field->field->table;
236
237
/*
238
Look for a partial key that can be used for optimization.
239
If we succeed, ref.key_length will contain the length of
240
this key, while prefix_len will contain the length of
241
the beginning of this key without field used in MIN().
242
Type of range for the key part for this field will be
243
returned in range_fl.
244
*/
245
if (table->cursor->inited || (outer_tables & table->map) ||
246
!find_key_for_maxmin(0, &ref, item_field->field, conds,
247
&range_fl, &prefix_len))
248
{
249
const_result= 0;
250
break;
251
}
252
error= table->cursor->ha_index_init((uint32_t) ref.key, 1);
253
254
if (!ref.key_length)
255
error= table->cursor->index_first(table->record[0]);
256
else
257
{
258
/*
259
Use index to replace MIN/MAX functions with their values
260
according to the following rules:
261
262
1) Insert the minimum non-null values where the WHERE clause still
263
matches, or
264
2) a NULL value if there are only NULL values for key_part_k.
265
3) Fail, producing a row of nulls
266
267
Implementation: Read the smallest value using the search key. If
268
the interval is open, read the next value after the search
269
key. If read fails, and we're looking for a MIN() value for a
270
nullable column, test if there is an exact match for the key.
271
*/
272
if (!(range_fl & NEAR_MIN))
273
/*
274
Closed interval: Either The MIN argument is non-nullable, or
275
we have a >= predicate for the MIN argument.
276
*/
277
error= table->cursor->index_read_map(table->record[0],
278
ref.key_buff,
279
make_prev_keypart_map(ref.key_parts),
280
HA_READ_KEY_OR_NEXT);
281
else
282
{
283
/*
284
Open interval: There are two cases:
285
1) We have only MIN() and the argument column is nullable, or
286
2) there is a > predicate on it, nullability is irrelevant.
287
We need to scan the next bigger record first.
288
*/
289
error= table->cursor->index_read_map(table->record[0],
290
ref.key_buff,
291
make_prev_keypart_map(ref.key_parts),
292
HA_READ_AFTER_KEY);
293
/*
294
If the found record is outside the group formed by the search
295
prefix, or there is no such record at all, check if all
296
records in that group have NULL in the MIN argument
297
column. If that is the case return that NULL.
298
299
Check if case 1 from above holds. If it does, we should read
300
the skipped tuple.
301
*/
302
if (item_field->field->real_maybe_null() &&
303
ref.key_buff[prefix_len] == 1 &&
304
/*
305
Last keypart (i.e. the argument to MIN) is set to NULL by
306
find_key_for_maxmin only if all other keyparts are bound
307
to constants in a conjunction of equalities. Hence, we
308
can detect this by checking only if the last keypart is
309
NULL.
310
*/
311
(error == HA_ERR_KEY_NOT_FOUND ||
312
key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
313
{
314
assert(item_field->field->real_maybe_null());
315
error= table->cursor->index_read_map(table->record[0],
316
ref.key_buff,
317
make_prev_keypart_map(ref.key_parts),
318
HA_READ_KEY_EXACT);
319
}
320
}
321
}
322
/* Verify that the read tuple indeed matches the search key */
323
if (!error && reckey_in_range(0, &ref, item_field->field,
324
conds, range_fl, prefix_len))
325
error= HA_ERR_KEY_NOT_FOUND;
326
if (table->key_read)
327
{
328
table->key_read= 0;
329
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
330
}
331
table->cursor->ha_index_end();
332
if (error)
333
{
334
if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
335
return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
336
/* HA_ERR_LOCK_DEADLOCK or some other error */
337
table->print_error(error, MYF(0));
338
return(error);
339
}
340
removed_tables|= table->map;
341
}
342
else if (!expr->const_item() || !is_exact_count)
343
{
344
/*
345
The optimization is not applicable in both cases:
346
(a) 'expr' is a non-constant expression. Then we can't
347
replace 'expr' by a constant.
348
(b) 'expr' is a costant. According to ANSI, MIN/MAX must return
349
NULL if the query does not return any rows. Thus, if we are not
350
able to determine if the query returns any rows, we can't apply
351
the optimization and replace MIN/MAX with a constant.
352
*/
353
const_result= 0;
354
break;
355
}
356
if (!count)
357
{
358
/* If count == 0, then we know that is_exact_count == true. */
359
((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
360
}
361
else
362
((Item_sum_min*) item_sum)->reset(); /* Set to the constant value. */
363
((Item_sum_min*) item_sum)->make_const();
364
recalc_const_item= 1;
365
break;
366
}
367
case Item_sum::MAX_FUNC:
368
{
369
/*
370
If MAX(expr) is the first part of a key or if all previous
371
parts of the key is found in the COND, then we can use
372
indexes to find the key.
373
*/
374
Item *expr=item_sum->args[0];
375
if (expr->real_item()->type() == Item::FIELD_ITEM)
376
{
377
unsigned char key_buff[MAX_KEY_LENGTH];
378
table_reference_st ref;
379
uint32_t range_fl, prefix_len;
380
381
ref.key_buff= key_buff;
382
Item_field *item_field= (Item_field*) (expr->real_item());
383
Table *table= item_field->field->table;
384
385
/*
386
Look for a partial key that can be used for optimization.
387
If we succeed, ref.key_length will contain the length of
388
this key, while prefix_len will contain the length of
389
the beginning of this key without field used in MAX().
390
Type of range for the key part for this field will be
391
returned in range_fl.
392
*/
393
if (table->cursor->inited || (outer_tables & table->map) ||
394
!find_key_for_maxmin(1, &ref, item_field->field, conds,
395
&range_fl, &prefix_len))
396
{
397
const_result= 0;
398
break;
399
}
400
error= table->cursor->ha_index_init((uint32_t) ref.key, 1);
401
402
if (!ref.key_length)
403
error= table->cursor->index_last(table->record[0]);
404
else
405
error= table->cursor->index_read_map(table->record[0], key_buff,
406
make_prev_keypart_map(ref.key_parts),
407
range_fl & NEAR_MAX ?
408
HA_READ_BEFORE_KEY :
409
HA_READ_PREFIX_LAST_OR_PREV);
410
if (!error && reckey_in_range(1, &ref, item_field->field,
411
conds, range_fl, prefix_len))
412
error= HA_ERR_KEY_NOT_FOUND;
413
if (table->key_read)
414
{
415
table->key_read=0;
416
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
417
}
418
table->cursor->ha_index_end();
419
if (error)
420
{
421
if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
422
return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
423
/* HA_ERR_LOCK_DEADLOCK or some other error */
424
table->print_error(error, MYF(ME_FATALERROR));
425
return(error);
426
}
427
removed_tables|= table->map;
428
}
429
else if (!expr->const_item() || !is_exact_count)
430
{
431
/*
432
The optimization is not applicable in both cases:
433
(a) 'expr' is a non-constant expression. Then we can't
434
replace 'expr' by a constant.
435
(b) 'expr' is a costant. According to ANSI, MIN/MAX must return
436
NULL if the query does not return any rows. Thus, if we are not
437
able to determine if the query returns any rows, we can't apply
438
the optimization and replace MIN/MAX with a constant.
439
*/
440
const_result= 0;
441
break;
442
}
443
if (!count)
444
{
445
/* If count != 1, then we know that is_exact_count == true. */
446
((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
447
}
448
else
449
((Item_sum_max*) item_sum)->reset(); /* Set to the constant value. */
450
((Item_sum_max*) item_sum)->make_const();
451
recalc_const_item= 1;
452
break;
453
}
454
default:
455
const_result= 0;
456
break;
198
switch (item_sum->sum_func())
199
{
200
case Item_sum::COUNT_FUNC:
201
/*
202
If the expr in COUNT(expr) can never be null we can change this
203
to the number of rows in the tables if this number is exact and
204
there are no outer joins.
205
*/
206
if (! conds && ! ((Item_sum_count*) item)->args[0]->maybe_null &&
207
! outer_tables && maybe_exact_count)
208
{
209
if (! is_exact_count)
210
{
211
if ((count= get_exact_record_count(tables)) == UINT64_MAX)
212
{
213
/* Error from handler in counting rows. Don't optimize count() */
214
const_result= 0;
215
continue;
216
}
217
is_exact_count= 1; // count is now exact
218
}
219
((Item_sum_count*) item)->make_const_count((int64_t) count);
220
recalc_const_item= 1;
221
}
222
else
223
{
224
const_result= 0;
225
}
226
break;
227
case Item_sum::MIN_FUNC:
228
{
229
/*
230
If MIN(expr) is the first part of a key or if all previous
231
parts of the key is found in the COND, then we can use
232
indexes to find the key.
233
*/
234
Item *expr=item_sum->args[0];
235
if (expr->real_item()->type() == Item::FIELD_ITEM)
236
{
237
unsigned char key_buff[MAX_KEY_LENGTH];
238
table_reference_st ref;
239
uint32_t range_fl, prefix_len;
240
241
ref.key_buff= key_buff;
242
Item_field *item_field= (Item_field*) (expr->real_item());
243
Table *table= item_field->field->table;
244
245
/*
246
Look for a partial key that can be used for optimization.
247
If we succeed, ref.key_length will contain the length of
248
this key, while prefix_len will contain the length of
249
the beginning of this key without field used in MIN().
250
Type of range for the key part for this field will be
251
returned in range_fl.
252
*/
253
if (table->cursor->inited ||
254
(outer_tables & table->map) ||
255
! find_key_for_maxmin(0,
256
&ref,
257
item_field->field,
258
conds,
259
&range_fl,
260
&prefix_len))
261
{
262
const_result= 0;
263
break;
264
}
265
error= table->cursor->ha_index_init(static_cast<uint32_t>(ref.key), 1);
266
267
if (! ref.key_length)
268
{
269
error= table->cursor->index_first(table->record[0]);
270
}
271
else
272
{
273
/*
274
Use index to replace MIN/MAX functions with their values
275
according to the following rules:
276
277
1) Insert the minimum non-null values where the WHERE clause still
278
matches, or
279
2) a NULL value if there are only NULL values for key_part_k.
280
3) Fail, producing a row of nulls
281
282
Implementation: Read the smallest value using the search key. If
283
the interval is open, read the next value after the search
284
key. If read fails, and we're looking for a MIN() value for a
285
nullable column, test if there is an exact match for the key.
286
*/
287
if (! (range_fl & NEAR_MIN))
288
/*
289
Closed interval: Either The MIN argument is non-nullable, or
290
we have a >= predicate for the MIN argument.
291
*/
292
error= table->cursor->index_read_map(table->record[0],
293
ref.key_buff,
294
make_prev_keypart_map(ref.key_parts),
295
HA_READ_KEY_OR_NEXT);
296
else
297
{
298
/*
299
Open interval: There are two cases:
300
1) We have only MIN() and the argument column is nullable, or
301
2) there is a > predicate on it, nullability is irrelevant.
302
We need to scan the next bigger record first.
303
*/
304
error= table->cursor->index_read_map(table->record[0],
305
ref.key_buff,
306
make_prev_keypart_map(ref.key_parts),
307
HA_READ_AFTER_KEY);
308
/*
309
If the found record is outside the group formed by the search
310
prefix, or there is no such record at all, check if all
311
records in that group have NULL in the MIN argument
312
column. If that is the case return that NULL.
313
314
Check if case 1 from above holds. If it does, we should read
315
the skipped tuple.
316
*/
317
if (item_field->field->real_maybe_null() &&
318
ref.key_buff[prefix_len] == 1 &&
319
/*
320
Last keypart (i.e. the argument to MIN) is set to NULL by
321
find_key_for_maxmin only if all other keyparts are bound
322
to constants in a conjunction of equalities. Hence, we
323
can detect this by checking only if the last keypart is
324
NULL.
325
*/
326
(error == HA_ERR_KEY_NOT_FOUND ||
327
key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
328
{
329
assert(item_field->field->real_maybe_null());
330
error= table->cursor->index_read_map(table->record[0],
331
ref.key_buff,
332
make_prev_keypart_map(ref.key_parts),
333
HA_READ_KEY_EXACT);
334
}
335
}
336
}
337
/* Verify that the read tuple indeed matches the search key */
338
if (! error &&
339
reckey_in_range(0,
340
&ref,
341
item_field->field,
342
conds,
343
range_fl,
344
prefix_len))
345
{
346
error= HA_ERR_KEY_NOT_FOUND;
347
}
348
if (table->key_read)
349
{
350
table->key_read= 0;
351
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
352
}
353
table->cursor->ha_index_end();
354
if (error)
355
{
356
if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
357
{
358
return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
359
}
360
/* HA_ERR_LOCK_DEADLOCK or some other error */
361
table->print_error(error, MYF(0));
362
return error;
363
}
364
removed_tables|= table->map;
365
}
366
else if (! expr->const_item() || ! is_exact_count)
367
{
368
/*
369
The optimization is not applicable in both cases:
370
(a) 'expr' is a non-constant expression. Then we can't
371
replace 'expr' by a constant.
372
(b) 'expr' is a costant. According to ANSI, MIN/MAX must return
373
NULL if the query does not return any rows. Thus, if we are not
374
able to determine if the query returns any rows, we can't apply
375
the optimization and replace MIN/MAX with a constant.
376
*/
377
const_result= 0;
378
break;
379
}
380
if (! count)
381
{
382
/* If count == 0, then we know that is_exact_count == true. */
383
((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
384
}
385
else
386
{
387
((Item_sum_min*) item_sum)->reset(); /* Set to the constant value. */
388
}
389
((Item_sum_min*) item_sum)->make_const();
390
recalc_const_item= 1;
391
break;
392
}
393
case Item_sum::MAX_FUNC:
394
{
395
/*
396
If MAX(expr) is the first part of a key or if all previous
397
parts of the key is found in the COND, then we can use
398
indexes to find the key.
399
*/
400
Item *expr= item_sum->args[0];
401
if (expr->real_item()->type() == Item::FIELD_ITEM)
402
{
403
unsigned char key_buff[MAX_KEY_LENGTH];
404
table_reference_st ref;
405
uint32_t range_fl, prefix_len;
406
407
ref.key_buff= key_buff;
408
Item_field *item_field= (Item_field*) (expr->real_item());
409
Table *table= item_field->field->table;
410
411
/*
412
Look for a partial key that can be used for optimization.
413
If we succeed, ref.key_length will contain the length of
414
this key, while prefix_len will contain the length of
415
the beginning of this key without field used in MAX().
416
Type of range for the key part for this field will be
417
returned in range_fl.
418
*/
419
if (table->cursor->inited ||
420
(outer_tables & table->map) ||
421
! find_key_for_maxmin(1,
422
&ref,
423
item_field->field,
424
conds,
425
&range_fl,
426
&prefix_len))
427
{
428
const_result= 0;
429
break;
430
}
431
error= table->cursor->ha_index_init(static_cast<uint32_t>(ref.key), 1);
432
433
if (! ref.key_length)
434
{
435
error= table->cursor->index_last(table->record[0]);
436
}
437
else
438
{
439
error= table->cursor->index_read_map(table->record[0],
440
key_buff,
441
make_prev_keypart_map(ref.key_parts),
442
range_fl & NEAR_MAX ?
443
HA_READ_BEFORE_KEY :
444
HA_READ_PREFIX_LAST_OR_PREV);
445
}
446
if (! error &&
447
reckey_in_range(1,
448
&ref,
449
item_field->field,
450
conds,
451
range_fl,
452
prefix_len))
453
{
454
error= HA_ERR_KEY_NOT_FOUND;
455
}
456
if (table->key_read)
457
{
458
table->key_read= 0;
459
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
460
}
461
table->cursor->ha_index_end();
462
if (error)
463
{
464
if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
465
{
466
return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
467
}
468
/* HA_ERR_LOCK_DEADLOCK or some other error */
469
table->print_error(error, MYF(ME_FATALERROR));
470
return error;
471
}
472
removed_tables|= table->map;
473
}
474
else if (! expr->const_item() || ! is_exact_count)
475
{
476
/*
477
The optimization is not applicable in both cases:
478
(a) 'expr' is a non-constant expression. Then we can't
479
replace 'expr' by a constant.
480
(b) 'expr' is a costant. According to ANSI, MIN/MAX must return
481
NULL if the query does not return any rows. Thus, if we are not
482
able to determine if the query returns any rows, we can't apply
483
the optimization and replace MIN/MAX with a constant.
484
*/
485
const_result= 0;
486
break;
487
}
488
if (! count)
489
{
490
/* If count != 1, then we know that is_exact_count == true. */
491
((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
492
}
493
else
494
{
495
((Item_sum_max*) item_sum)->reset(); /* Set to the constant value. */
496
}
497
((Item_sum_max*) item_sum)->make_const();
498
recalc_const_item= 1;
499
break;
500
}
501
default:
502
const_result= 0;
503
break;
457
504
}
458
505
}
459
506
else if (const_result)
460
507
{
461
508
if (recalc_const_item)
509
{
462
510
item->update_used_tables();
463
if (!item->const_item())
511
}
512
if (! item->const_item())
513
{
464
514
const_result= 0;
515
}
465
516
}
466
517
}
467
518
/*
468
If we have a where clause, we can only ignore searching in the
469
tables if MIN/MAX optimisation replaced all used tables
470
We do not use replaced values in case of:
471
SELECT MIN(key) FROM table_1, empty_table
472
removed_tables is != 0 if we have used MIN() or MAX().
473
*/
519
If we have a where clause, we can only ignore searching in the
520
tables if MIN/MAX optimisation replaced all used tables
521
We do not use replaced values in case of:
522
SELECT MIN(key) FROM table_1, empty_table
523
removed_tables is != 0 if we have used MIN() or MAX().
524
*/
474
525
if (removed_tables && used_tables != removed_tables)
526
{
475
527
const_result= 0; // We didn't remove all tables
528
}
476
529
return const_result;
477
530
}
478
531
479
532
480
/**
481
Test if the predicate compares a field with constants.
482
483
@param func_item Predicate item
484
@param[out] args Here we store the field followed by constants
485
@param[out] inv_order Is set to 1 if the predicate is of the form
486
'const op field'
487
488
@retval
489
0 func_item is a simple predicate: a field is compared with
490
constants
491
@retval
492
1 Otherwise
493
*/
494
495
bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
533
bool optimizer::simple_pred(Item_func *func_item, Item **args, bool *inv_order)
496
534
{
497
Item *item;
535
Item *item= NULL;
498
536
*inv_order= 0;
499
537
switch (func_item->argument_count()) {
500
538
case 0:
504
542
Item_equal_iterator it(*item_equal);
505
543
args[0]= it++;
506
544
if (it++)
507
return 0;
508
if (!(args[1]= item_equal->get_const()))
509
return 0;
545
{
546
return 0;
547
}
548
if (! (args[1]= item_equal->get_const()))
549
{
550
return 0;
551
}
510
552
}
511
553
break;
512
554
case 1:
513
555
/* field IS NULL */
514
556
item= func_item->arguments()[0];
515
557
if (item->type() != Item::FIELD_ITEM)
558
{
516
559
return 0;
560
}
517
561
args[0]= item;
518
562
break;
519
563
case 2:
523
567
{
524
568
args[0]= item;
525
569
item= func_item->arguments()[1];
526
if (!item->const_item())
570
if (! item->const_item())
571
{
527
572
return 0;
573
}
528
574
args[1]= item;
529
575
}
530
576
else if (item->const_item())
532
578
args[1]= item;
533
579
item= func_item->arguments()[1];
534
580
if (item->type() != Item::FIELD_ITEM)
581
{
535
582
return 0;
583
}
536
584
args[0]= item;
537
585
*inv_order= 1;
538
586
}
539
587
else
588
{
540
589
return 0;
590
}
541
591
break;
542
592
case 3:
543
593
/* field BETWEEN const AND const */
548
598
for (int i= 1 ; i <= 2; i++)
549
599
{
550
600
item= func_item->arguments()[i];
551
if (!item->const_item())
601
if (! item->const_item())
602
{
552
603
return 0;
604
}
553
605
args[i]= item;
554
606
}
555
607
}
556
608
else
609
{
557
610
return 0;
611
}
558
612
}
559
613
return 1;
560
614
}
590
644
1 We can use index to get MIN/MAX value
591
645
*/
592
646
593
static bool matching_cond(bool max_fl, table_reference_st *ref, KEY *keyinfo,
594
KEY_PART_INFO *field_part, COND *cond,
595
key_part_map *key_part_used, uint32_t *range_fl,
647
static bool matching_cond(bool max_fl,
648
table_reference_st *ref,
649
KEY *keyinfo,
650
KEY_PART_INFO *field_part,
651
COND *cond,
652
key_part_map *key_part_used,
653
uint32_t *range_fl,
596
654
uint32_t *prefix_len)
597
655
{
598
if (!cond)
656
if (! cond)
657
{
599
658
return 1;
659
}
600
660
Field *field= field_part->field;
601
661
602
662
field->setWriteSet();
603
663
604
if (!(cond->used_tables() & field->table->map))
664
if (! (cond->used_tables() & field->table->map))
605
665
{
606
666
/* Condition doesn't restrict the used table */
607
667
return 1;
609
669
if (cond->type() == Item::COND_ITEM)
610
670
{
611
671
if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
672
{
612
673
return 0;
674
}
613
675
614
676
/* AND */
615
677
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
616
678
Item *item;
617
679
while ((item= li++))
618
680
{
619
if (!matching_cond(max_fl, ref, keyinfo, field_part, item,
620
key_part_used, range_fl, prefix_len))
681
if (! matching_cond(max_fl,
682
ref,
683
keyinfo,
684
field_part,
685
item,
686
key_part_used,
687
range_fl,
688
prefix_len))
689
{
621
690
return 0;
691
}
622
692
}
623
693
return 1;
624
694
}
625
695
626
696
if (cond->type() != Item::FUNC_ITEM)
627
return 0; // Not operator, can't optimize
628
629
bool eq_type= 0; // =, <=> or IS NULL
630
bool noeq_type= 0; // < or >
631
bool less_fl= 0; // < or <=
632
bool is_null= 0;
633
bool between= 0;
634
635
switch (((Item_func*) cond)->functype()) {
697
{
698
return 0; // Not operator, can't optimize
699
}
700
701
bool eq_type= false; // =, <=> or IS NULL
702
bool noeq_type= false; // < or >
703
bool less_fl= false; // < or <=
704
bool is_null= false;
705
bool between= false;
706
707
switch (((Item_func*) cond)->functype())
708
{
636
709
case Item_func::ISNULL_FUNC:
637
710
is_null= 1; /* fall through */
638
711
case Item_func::EQ_FUNC:
655
728
eq_type= 1;
656
729
break;
657
730
default:
658
return 0; // Can't optimize function
731
return 0; // Can't optimize function
659
732
}
660
733
661
734
Item *args[3];
662
735
bool inv;
663
736
664
737
/* Test if this is a comparison of a field and constant */
665
if (!simple_pred((Item_func*) cond, args, &inv))
738
if (! optimizer::simple_pred((Item_func*) cond, args, &inv))
739
{
666
740
return 0;
741
}
667
742
668
if (inv && !eq_type)
669
less_fl= 1-less_fl; // Convert '<' -> '>' (etc)
743
if (inv && ! eq_type)
744
{
745
less_fl= 1 - less_fl; // Convert '<' -> '>' (etc)
746
}
670
747
671
748
/* Check if field is part of the tested partial key */
672
749
unsigned char *key_ptr= ref->key_buff;
673
KEY_PART_INFO *part;
750
KEY_PART_INFO *part= NULL;
674
751
for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
675
752
676
753
{
677
754
if (part > field_part)
755
{
678
756
return 0; // Field is beyond the tested parts
757
}
679
758
if (part->field->eq(((Item_field*) args[0])->field))
759
{
680
760
break; // Found a part of the key for the field
761
}
681
762
}
682
763
683
764
bool is_field_part= part == field_part;
684
if (!(is_field_part || eq_type))
765
if (! (is_field_part || eq_type))
766
{
685
767
return 0;
768
}
686
769
687
770
key_part_map org_key_part_used= *key_part_used;
688
771
if (eq_type || between || max_fl == less_fl)
694
777
ref->key_length= length;
695
778
ref->key_parts= (part - keyinfo->key_part) + 1;
696
779
}
697
if (!*prefix_len && part+1 == field_part)
780
if (! *prefix_len && part + 1 == field_part)
781
{
698
782
*prefix_len= length;
783
}
699
784
if (is_field_part && eq_type)
785
{
700
786
*prefix_len= ref->key_length;
787
}
701
788
702
789
*key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
703
790
}
704
791
705
792
if (org_key_part_used != *key_part_used ||
706
793
(is_field_part &&
707
(between || eq_type || max_fl == less_fl) && !cond->val_int()))
794
(between || eq_type || max_fl == less_fl) && ! cond->val_int()))
708
795
{
709
796
/*
710
797
It's the first predicate for this part or a predicate of the
725
812
store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
726
813
CHECK_FIELD_IGNORE);
727
814
if (part->null_bit)
815
{
728
816
*key_ptr++= (unsigned char) test(part->field->is_null());
817
}
729
818
part->field->get_key_image(key_ptr, part->length);
730
819
}
731
820
if (is_field_part)
732
821
{
733
822
if (between || eq_type)
823
{
734
824
*range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
825
}
735
826
else
736
827
{
737
828
*range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
738
829
if (noeq_type)
830
{
739
831
*range_fl|= (max_fl ? NEAR_MAX : NEAR_MIN);
832
}
740
833
else
834
{
741
835
*range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
836
}
742
837
}
743
838
}
744
839
}
745
840
else if (eq_type)
746
841
{
747
if ((!is_null && !cond->val_int()) ||
842
if ((! is_null && !cond->val_int()) ||
748
843
(is_null && !test(part->field->is_null())))
844
{
749
845
return 0; // Impossible test
846
}
750
847
}
751
848
else if (is_field_part)
849
{
752
850
*range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
851
}
753
852
return 1;
754
853
}
755
854
797
896
*/
798
897
799
898
800
static bool find_key_for_maxmin(bool max_fl, table_reference_st *ref,
801
Field* field, COND *cond,
802
uint32_t *range_fl, uint32_t *prefix_len)
899
static bool find_key_for_maxmin(bool max_fl,
900
table_reference_st *ref,
901
Field* field,
902
COND *cond,
903
uint32_t *range_fl,
904
uint32_t *prefix_len)
803
905
{
804
if (!(field->flags & PART_KEY_FLAG))
805
return 0; // Not key field
906
if (! (field->flags & PART_KEY_FLAG))
907
{
908
return 0; // Not key field
909
}
806
910
807
911
Table *table= field->table;
808
912
uint32_t idx= 0;
809
913
810
KEY *keyinfo,*keyinfo_end;
811
for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
914
KEY *keyinfo,*keyinfo_end= NULL;
915
for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys;
812
916
keyinfo != keyinfo_end;
813
917
keyinfo++,idx++)
814
918
{
815
KEY_PART_INFO *part,*part_end;
919
KEY_PART_INFO *part= NULL;
920
KEY_PART_INFO *part_end= NULL;
816
921
key_part_map key_part_to_use= 0;
817
922
/*
818
923
Perform a check if index is not disabled by ALTER Table
819
924
or IGNORE INDEX.
820
925
*/
821
if (!table->keys_in_use_for_query.test(idx))
926
if (! table->keys_in_use_for_query.test(idx))
927
{
822
928
continue;
929
}
823
930
uint32_t jdx= 0;
824
931
*prefix_len= 0;
825
for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts ;
826
part != part_end ;
932
for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts;
933
part != part_end;
827
934
part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
828
935
{
829
936
if (! (table->index_flags(idx) & HA_READ_ORDER))
937
{
830
938
return 0;
939
}
831
940
832
941
/* Check whether the index component is partial */
833
942
Field *part_field= table->field[part->fieldnr-1];
835
944
836
945
if ((part_field->flags & BLOB_FLAG) ||
837
946
part->length < part_field->key_length())
947
{
838
948
break;
949
}
839
950
840
951
if (field->eq(part->field))
841
952
{
844
955
ref->key_parts= 0;
845
956
key_part_map key_part_used= 0;
846
957
*range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
847
if (matching_cond(max_fl, ref, keyinfo, part, cond,
848
&key_part_used, range_fl, prefix_len) &&
849
!(key_part_to_use & ~key_part_used))
958
if (matching_cond(max_fl,
959
ref,
960
keyinfo,
961
part,
962
cond,
963
&key_part_used,
964
range_fl,
965
prefix_len) &&
966
! (key_part_to_use & ~key_part_used))
850
967
{
851
if (!max_fl && key_part_used == key_part_to_use && part->null_bit)
968
if (! max_fl && key_part_used == key_part_to_use && part->null_bit)
852
969
{
853
970
/*
854
971
The query is on this form:
905
1022
@retval
906
1023
1 WHERE was not true for the found row
907
1024
*/
908
909
static int reckey_in_range(bool max_fl, table_reference_st *ref, Field* field,
910
COND *cond, uint32_t range_fl, uint32_t prefix_len)
1025
static int reckey_in_range(bool max_fl,
1026
table_reference_st *ref,
1027
Field* field,
1028
COND *cond,
1029
uint32_t range_fl,
1030
uint32_t prefix_len)
911
1031
{
912
1032
if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
1033
{
913
1034
return 1;
914
if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
1035
}
1036
if (! cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
1037
{
915
1038
return 0;
1039
}
916
1040
return maxmin_in_range(max_fl, field, cond);
917
1041
}
918
1042
929
1053
@retval
930
1054
1 WHERE was not true for the found row
931
1055
*/
932
933
1056
static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
934
1057
{
935
1058
/* If AND/OR condition */
940
1063
while ((item= li++))
941
1064
{
942
1065
if (maxmin_in_range(max_fl, field, item))
1066
{
943
1067
return 1;
1068
}
944
1069
}
945
1070
return 0;
946
1071
}
947
1072
948
1073
if (cond->used_tables() != field->table->map)
1074
{
949
1075
return 0;
950
bool less_fl= 0;
951
switch (((Item_func*) cond)->functype()) {
1076
}
1077
bool less_fl= false;
1078
switch (((Item_func*) cond)->functype())
1079
{
952
1080
case Item_func::BETWEEN:
953
1081
return cond->val_int() == 0; // Return 1 if WHERE is false
954
1082
case Item_func::LT_FUNC:
959
1087
{
960
1088
Item *item= ((Item_func*) cond)->arguments()[1];
961
1089
/* In case of 'const op item' we have to swap the operator */
962
if (!item->const_item())
1090
if (! item->const_item())
1091
{
963
1092
less_fl= 1-less_fl;
1093
}
964
1094
/*
965
1095
We only have to check the expression if we are using an expression like
966
1096
SELECT MAX(b) FROM t1 WHERE a=const AND b>const
968
1098
SELECT MAX(b) FROM t1 WHERE a=const AND b<const
969
1099
*/
970
1100
if (max_fl != less_fl)
1101
{
971
1102
return cond->val_int() == 0; // Return 1 if WHERE is false
1103
}
972
1104
return 0;
973
1105
}
974
1106
case Item_func::EQ_FUNC:
981
1113
return 0;
982
1114
}
983
1115
1116
} /* namespace drizzled */
1117
Loggerhead is a web-based interface for Breezy
Version: 2.0.1