1
/* Copyright (C) 2000-2006 MySQL AB
1
/* Copyright (C) 2000-2006 MySQL AB
3
3
This program is free software; you can redistribute it and/or modify
4
4
it under the terms of the GNU General Public License as published by
24
24
#include <drizzled/server_includes.h>
25
#include <drizzled/sql_sort.h>
26
#include <drizzled/error.h>
27
#include <drizzled/probes.h>
28
#include <drizzled/session.h>
29
#include <drizzled/table.h>
30
#include <drizzled/table_list.h>
26
#include <drizzled/drizzled_error_messages.h>
32
/* functions defined in this file */
28
/* functions defined in this file */
34
30
static char **make_char_array(char **old_pos, register uint32_t fields,
31
uint32_t length, myf my_flag);
36
32
static unsigned char *read_buffpek_from_file(IO_CACHE *buffer_file, uint32_t count,
37
33
unsigned char *buf);
38
34
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
47
43
uint32_t maxbuffer,IO_CACHE *tempfile,
48
44
IO_CACHE *outfile);
49
static bool save_index(SORTPARAM *param,unsigned char **sort_keys, uint32_t count,
45
static bool save_index(SORTPARAM *param,unsigned char **sort_keys, uint32_t count,
50
46
filesort_info_st *table_sort);
51
47
static uint32_t suffix_length(uint32_t string_length);
52
static uint32_t sortlength(Session *session, SORT_FIELD *sortorder, uint32_t s_length,
48
static uint32_t sortlength(THD *thd, SORT_FIELD *sortorder, uint32_t s_length,
53
49
bool *multi_byte_charset);
54
static SORT_ADDON_FIELD *get_addon_fields(Session *session, Field **ptabfield,
50
static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
55
51
uint32_t sortlength, uint32_t *plength);
56
52
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
57
53
unsigned char *buff);
67
63
The result set is stored in table->io_cache or
68
64
table->record_pointers.
70
@param session Current thread
66
@param thd Current thread
71
67
@param table Table to sort
72
68
@param sortorder How to sort the table
73
69
@param s_length Number of elements in sortorder
91
87
examined_rows will be set to number of examined rows
94
ha_rows filesort(Session *session, Table *table, SORT_FIELD *sortorder, uint32_t s_length,
90
ha_rows filesort(THD *thd, Table *table, SORT_FIELD *sortorder, uint32_t s_length,
95
91
SQL_SELECT *select, ha_rows max_rows,
96
92
bool sort_positions, ha_rows *examined_rows)
102
98
ha_rows records= HA_POS_ERROR;
103
99
unsigned char **sort_keys= 0;
104
IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile;
100
IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile;
106
102
bool multi_byte_charset;
115
111
Release InnoDB's adaptive hash index latch (if holding) before
118
ha_release_temporary_latches(session);
114
ha_release_temporary_latches(thd);
121
Don't use table->sort in filesort as it is also used by
122
QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end
117
Don't use table->sort in filesort as it is also used by
118
QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end
123
119
when index_merge select has finished with it.
125
121
memcpy(&table_sort, &table->sort, sizeof(filesort_info_st));
126
122
table->sort.io_cache= NULL;
128
124
outfile= table_sort.io_cache;
129
125
my_b_clear(&tempfile);
130
126
my_b_clear(&buffpek_pointers);
133
129
memset(¶m, 0, sizeof(param));
134
param.sort_length= sortlength(session, sortorder, s_length, &multi_byte_charset);
130
param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
135
131
param.ref_length= table->file->ref_length;
136
132
param.addon_field= 0;
137
133
param.addon_length= 0;
138
134
if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && !sort_positions)
141
Get the descriptors of all fields whose values are appended
137
Get the descriptors of all fields whose values are appended
142
138
to sorted fields and get its total length in param.spack_length.
144
param.addon_field= get_addon_fields(session, table->field,
140
param.addon_field= get_addon_fields(thd, table->field,
145
141
param.sort_length,
146
142
¶m.addon_length);
153
149
if (param.addon_field)
155
151
param.res_length= param.addon_length;
156
if (!(table_sort.addon_buf= (unsigned char *) malloc(param.addon_length)))
152
if (!(table_sort.addon_buf= (unsigned char *) my_malloc(param.addon_length,
161
158
param.res_length= param.ref_length;
163
The reference to the record is considered
160
The reference to the record is considered
164
161
as an additional sorted field
166
163
param.sort_length+= param.ref_length;
171
168
if (select && select->quick)
173
status_var_increment(session->status_var.filesort_range_count);
170
status_var_increment(thd->status_var.filesort_range_count);
177
status_var_increment(session->status_var.filesort_scan_count);
174
status_var_increment(thd->status_var.filesort_scan_count);
179
176
#ifdef CAN_TRUST_RANGE
180
177
if (select && select->quick && select->quick->records > 0L)
189
186
records= table->file->estimate_rows_upper_bound();
191
If number of records is not known, use as much of sort buffer
188
If number of records is not known, use as much of sort buffer
194
191
if (records == HA_POS_ERROR)
195
192
records--; // we use 'records+1' below.
199
196
if (multi_byte_charset &&
200
!(param.tmp_buffer= (char*) malloc(param.sort_length)))
197
!(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
203
memavl= session->variables.sortbuff_size;
200
memavl= thd->variables.sortbuff_size;
204
201
min_sort_memory= cmax((uint32_t)MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
205
202
while (memavl >= min_sort_memory)
209
206
param.keys=(uint32_t) cmin(records+1, keys);
210
207
if ((table_sort.sort_keys=
211
208
(unsigned char **) make_char_array((char **) table_sort.sort_keys,
212
param.keys, param.rec_length)))
209
param.keys, param.rec_length, MYF(0))))
214
211
old_memavl=memavl;
215
212
if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
221
218
my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
224
if (open_cached_file(&buffpek_pointers,drizzle_tmpdir,TEMP_PREFIX,
221
if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
225
222
DISK_BUFFER_SIZE, MYF(MY_WME)))
256
253
close_cached_file(&buffpek_pointers);
257
254
/* Open cached file if it isn't open */
258
255
if (! my_b_inited(outfile) &&
259
open_cached_file(outfile,drizzle_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
256
open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
262
259
if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
315
312
my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
316
313
MYF(ME_ERROR+ME_WAITTANG));
318
statistic_add(session->status_var.filesort_rows,
315
statistic_add(thd->status_var.filesort_rows,
319
316
(uint32_t) records, &LOCK_status);
320
317
*examined_rows= param.examined_rows;
321
318
memcpy(&table->sort, &table_sort, sizeof(filesort_info_st));
359
356
/** Make a array of string pointers. */
361
358
static char **make_char_array(char **old_pos, register uint32_t fields,
359
uint32_t length, myf my_flag)
364
361
register char **pos;
368
(old_pos= (char**) malloc((uint32_t) fields*(length+sizeof(char*)))))
365
(old_pos= (char**) my_malloc((uint32_t) fields*(length+sizeof(char*)),
370
368
pos=old_pos; char_pos=((char*) (pos+fields)) -length;
371
369
while (fields--) *(pos++) = (char_pos+= length);
385
383
if (count > UINT_MAX/sizeof(BUFFPEK))
386
384
return 0; /* sizeof(BUFFPEK)*count will overflow */
388
tmp= (unsigned char *)malloc(length);
386
tmp= (unsigned char *)my_malloc(length, MYF(MY_WME));
391
389
if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
446
444
unsigned char *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
448
446
Table *sort_form;
449
Session *session= current_session;
450
volatile Session::killed_state *killed= &session->killed;
447
THD *thd= current_thd;
448
volatile THD::killed_state *killed= &thd->killed;
452
450
MY_BITMAP *save_read_set, *save_write_set;
469
467
next_pos=(unsigned char*) 0; /* Find records in sequence */
470
468
file->ha_rnd_init(1);
471
469
file->extra_opt(HA_EXTRA_CACHE,
472
current_session->variables.read_buff_size);
470
current_thd->variables.read_buff_size);
475
473
READ_RECORD read_record_info;
478
476
if (select->quick->reset())
479
477
return(HA_POS_ERROR);
480
init_read_record(&read_record_info, current_session, select->quick->head,
478
init_read_record(&read_record_info, current_thd, select->quick->head,
631
626
rec_length= param->rec_length;
632
627
my_string_ptr_sort((unsigned char*) sort_keys, (uint32_t) count, sort_length);
633
628
if (!my_b_inited(tempfile) &&
634
open_cached_file(tempfile, drizzle_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
629
open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
636
631
goto err; /* purecov: inspected */
637
632
/* check we won't have more buffpeks than we can possibly keep in memory */
806
802
to[0]= (unsigned char) (value >> 56);
808
804
to[0]= (unsigned char) (value >> 56) ^ 128; /* Reverse signbit */
806
to[3]= (unsigned char) value;
807
to[2]= (unsigned char) (value >> 8);
808
to[1]= (unsigned char) (value >> 16);
809
if (item->unsigned_flag) /* Fix sign */
810
to[0]= (unsigned char) (value >> 24);
812
to[0]= (unsigned char) (value >> 24) ^ 128; /* Reverse signbit */
811
816
case DECIMAL_RESULT:
955
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count,
960
static bool save_index(SORTPARAM *param, unsigned char **sort_keys, uint32_t count,
956
961
filesort_info_st *table_sort)
958
963
uint32_t offset,res_length;
963
968
offset= param->rec_length-res_length;
964
969
if ((ha_rows) count > param->max_rows)
965
970
count=(uint32_t) param->max_rows;
966
if (!(to= table_sort->record_pointers=
967
(unsigned char*) malloc(res_length*count)))
971
if (!(to= table_sort->record_pointers=
972
(unsigned char*) my_malloc(res_length*count, MYF(MY_WME))))
968
973
return(1); /* purecov: inspected */
969
974
for (unsigned char **end= sort_keys+count ; sort_keys != end ; sort_keys++)
987
992
if (*maxbuffer < MERGEBUFF2)
988
993
return(0); /* purecov: inspected */
989
994
if (flush_io_cache(t_file) ||
990
open_cached_file(&t_file2,drizzle_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
995
open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
992
997
return(1); /* purecov: inspected */
1121
1126
qsort2_cmp cmp;
1122
1127
void *first_cmp_arg;
1123
volatile Session::killed_state *killed= ¤t_session->killed;
1124
Session::killed_state not_killable;
1128
volatile THD::killed_state *killed= ¤t_thd->killed;
1129
THD::killed_state not_killable;
1126
status_var_increment(current_session->status_var.filesort_merge_passes);
1131
status_var_increment(current_thd->status_var.filesort_merge_passes);
1127
1132
if (param->not_killable)
1129
1134
killed= ¬_killable;
1130
not_killable= Session::NOT_KILLED;
1135
not_killable= THD::NOT_KILLED;
1339
1344
Calculate length of sort key.
1341
@param session Thread handler
1346
@param thd Thread handler
1342
1347
@param sortorder Order of items to sort
1343
1348
@param s_length Number of items to sort
1344
1349
@param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
1356
1361
static uint32_t
1357
sortlength(Session *session, SORT_FIELD *sortorder, uint32_t s_length,
1362
sortlength(THD *thd, SORT_FIELD *sortorder, uint32_t s_length,
1358
1363
bool *multi_byte_charset)
1360
1365
register uint32_t length;
1388
1393
switch (sortorder->result_type) {
1389
1394
case STRING_RESULT:
1390
1395
sortorder->length=sortorder->item->max_length;
1391
set_if_smaller(sortorder->length, session->variables.max_sort_length);
1396
set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1392
1397
if (use_strnxfrm((cs=sortorder->item->collation.collation)))
1394
1399
sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1395
1400
sortorder->need_strxnfrm= 1;
1396
1401
*multi_byte_charset= 1;
1405
1410
case INT_RESULT:
1411
#if SIZEOF_LONG_LONG > 4
1406
1412
sortorder->length=8; // Size of intern int64_t
1414
sortorder->length=4;
1408
1417
case DECIMAL_RESULT:
1409
1418
sortorder->length=
1410
my_decimal_get_binary_size(sortorder->item->max_length -
1419
my_decimal_get_binary_size(sortorder->item->max_length -
1411
1420
(sortorder->item->decimals ? 1 : 0),
1412
1421
sortorder->item->decimals);
1423
1432
if (sortorder->item->maybe_null)
1424
1433
length++; // Place for NULL marker
1426
set_if_smaller(sortorder->length, session->variables.max_sort_length);
1435
set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1427
1436
length+=sortorder->length;
1429
1438
sortorder->field= (Field*) 0; // end marker
1438
1447
The function first finds out what fields are used in the result set.
1439
1448
Then it calculates the length of the buffer to store the values of
1440
these fields together with the value of sort values.
1449
these fields together with the value of sort values.
1441
1450
If the calculated length is not greater than max_length_for_sort_data
1442
1451
the function allocates memory for an array of descriptors containing
1443
1452
layouts for the values of the non-sorted fields in the buffer and
1446
@param session Current thread
1455
@param thd Current thread
1447
1456
@param ptabfield Array of references to the table fields
1448
1457
@param sortlength Total length of sorted fields
1449
1458
@param[out] plength Total length of appended fields
1461
1470
static SORT_ADDON_FIELD *
1462
get_addon_fields(Session *session, Field **ptabfield, uint32_t sortlength, uint32_t *plength)
1471
get_addon_fields(THD *thd, Field **ptabfield, uint32_t sortlength, uint32_t *plength)
1464
1473
Field **pfield;
1475
1484
Note for future refinement:
1476
1485
This this a too strong condition.
1477
1486
Actually we need only the fields referred in the
1478
result set. And for some of them it makes sense to use
1487
result set. And for some of them it makes sense to use
1479
1488
the values directly from sorted fields.
1490
1499
if (field->maybe_null())
1496
1505
length+= (null_fields+7)/8;
1498
if (length+sortlength > session->variables.max_length_for_sort_data ||
1499
!(addonf= (SORT_ADDON_FIELD *) malloc(sizeof(SORT_ADDON_FIELD)*
1507
if (length+sortlength > thd->variables.max_length_for_sort_data ||
1508
!(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
1509
(fields+1), MYF(MY_WME))))
1503
1512
*plength= length;