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