1
/* Copyright (C) 2000-2004, 2006 MySQL AB
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.
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.
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 */
17
Gives a approximated number of how many records there is between two keys.
18
Used when optimizing querries.
21
#include "myisamdef.h"
24
static ha_rows _mi_record_pos(MI_INFO *, const uchar *, key_part_map,
25
enum ha_rkey_function);
26
static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,uchar *, uint,uint,my_off_t);
27
static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *,uchar *, uchar *,uint *);
30
Estimate how many records there is in a given range
36
min_key Min key. Is = 0 if no min range
37
max_key Max key. Is = 0 if no max range
40
We should ONLY return 0 if there is no rows in range
43
HA_POS_ERROR error (or we can't estimate number of rows)
44
number Estimated number of rows
47
ha_rows mi_records_in_range(MI_INFO *info, int inx,
48
key_range *min_key, key_range *max_key)
50
ha_rows start_pos,end_pos,res;
51
DBUG_ENTER("mi_records_in_range");
53
if ((inx = _mi_check_index(info,inx)) < 0)
54
DBUG_RETURN(HA_POS_ERROR);
56
if (fast_mi_readinfo(info))
57
DBUG_RETURN(HA_POS_ERROR);
58
info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
59
if (info->s->concurrent_insert)
60
rw_rdlock(&info->s->key_root_lock[inx]);
62
switch(info->s->keyinfo[inx].key_alg){
63
#ifdef HAVE_RTREE_KEYS
64
case HA_KEY_ALG_RTREE:
70
The problem is that the optimizer doesn't support
71
RTree keys properly at the moment.
72
Hope this will be fixed some day.
73
But now NULL in the min_key means that we
74
didn't make the task for the RTree key
75
and expect BTree functionality from it.
76
As it's not able to handle such request
84
key_buff= info->lastkey+info->s->base.max_key_length;
85
start_key_len= _mi_pack_key(info,inx, key_buff,
86
(uchar*) min_key->key, min_key->keypart_map,
88
res= rtree_estimate(info, inx, key_buff, start_key_len,
89
myisam_read_vec[min_key->flag]);
90
res= res ? res : 1; /* Don't return 0 */
94
case HA_KEY_ALG_BTREE:
96
start_pos= (min_key ? _mi_record_pos(info, min_key->key,
97
min_key->keypart_map, min_key->flag)
99
end_pos= (max_key ? _mi_record_pos(info, max_key->key,
100
max_key->keypart_map, max_key->flag)
101
: info->state->records + (ha_rows) 1);
102
res= (end_pos < start_pos ? (ha_rows) 0 :
103
(end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
104
if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
108
if (info->s->concurrent_insert)
109
rw_unlock(&info->s->key_root_lock[inx]);
110
fast_mi_writeinfo(info);
112
DBUG_PRINT("info",("records: %ld",(ulong) (res)));
117
/* Find relative position (in records) for key in index-tree */
119
static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
120
key_part_map keypart_map,
121
enum ha_rkey_function search_flag)
123
uint inx=(uint) info->lastinx, nextflag, key_len;
124
MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
128
DBUG_ENTER("_mi_record_pos");
129
DBUG_PRINT("enter",("search_flag: %d",search_flag));
130
DBUG_ASSERT(keypart_map);
132
key_buff=info->lastkey+info->s->base.max_key_length;
133
key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key, keypart_map,
135
DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
136
(uchar*) key_buff,key_len););
137
nextflag=myisam_read_vec[search_flag];
138
if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
139
key_len=USE_WHOLE_KEY;
142
my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
143
This is set in my_handler.c:ha_key_cmp() in dependence on the
144
compare flags 'nextflag' and the column type.
146
TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
147
condition is skip_end_space= ((nextflag & (SEARCH_FIND |
148
SEARCH_UPDATE)) == SEARCH_FIND).
150
SEARCH_FIND is used for an exact key search. The combination
151
SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
152
operations with a comment like "Not real duplicates", whatever this
153
means. From the condition above we can see that 'skip_end_space' is
154
always false for these operations. The result is that trailing space
155
counts in key comparison and hence, emtpy strings ('', string length
156
zero, but not NULL) compare less that strings starting with control
157
characters and these in turn compare less than strings starting with
160
When estimating the number of records in a key range, we request an
161
exact search for the minimum key. This translates into a plain
162
SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
163
compare. Empty strings would be expected above control characters.
164
Their keys would not be found because they are located below control
167
This is the reason that we add the SEARCH_UPDATE flag here. It makes
168
the key estimation compare in the same way like key write operations
169
do. Olny so we will find the keys where they have been inserted.
171
Adding the flag unconditionally does not hurt as it is used in the
172
above mentioned condition only. So it can safely be used together
175
pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
176
nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
177
info->s->state.key_root[inx]);
180
DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
181
DBUG_RETURN((ulong) (pos*info->state->records+0.5));
183
DBUG_RETURN(HA_POS_ERROR);
187
/* This is a modified version of _mi_search */
188
/* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
190
static double _mi_search_pos(register MI_INFO *info,
191
register MI_KEYDEF *keyinfo,
192
uchar *key, uint key_len, uint nextflag,
193
register my_off_t pos)
196
uint nod_flag, keynr, max_keynr= 0;
200
DBUG_ENTER("_mi_search_pos");
202
if (pos == HA_OFFSET_ERROR)
205
if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
207
flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
208
&keypos,info->lastkey, &after_key);
209
nod_flag=mi_test_if_nod(buff);
210
keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
214
if (flag == MI_FOUND_WRONG_KEY)
215
DBUG_RETURN(-1); /* error */
217
Didn't found match. keypos points at next (bigger) key
218
Try to find a smaller, better matching key.
219
Matches keynr + [0-1]
221
if (flag > 0 && ! nod_flag)
223
else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
224
_mi_kpos(nod_flag,keypos))) < 0)
230
Found match. Keypos points at the start of the found key
233
offset=1.0; /* Matches keynr+1 */
234
if ((nextflag & SEARCH_FIND) && nod_flag &&
235
((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
236
key_len != USE_WHOLE_KEY))
239
There may be identical keys in the tree. Try to match on of those.
240
Matches keynr + [0-1]
242
if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
243
_mi_kpos(nod_flag,keypos))) < 0)
244
DBUG_RETURN(offset); /* Read error */
247
DBUG_PRINT("info",("keynr: %d offset: %g max_keynr: %d nod: %d flag: %d",
248
keynr,offset,max_keynr,nod_flag,flag));
249
DBUG_RETURN((keynr+offset)/(max_keynr+1));
251
DBUG_PRINT("exit",("Error: %d",my_errno));
256
/* Get keynummer of current key and max number of keys in nod */
258
static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
259
uchar *keypos, uint *ret_max_key)
261
uint nod_flag,keynr,max_key;
262
uchar t_buff[MI_MAX_KEY_BUFF],*end;
264
end= page+mi_getint(page);
265
nod_flag=mi_test_if_nod(page);
268
if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
270
*ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
271
return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
275
t_buff[0]=0; /* Safety */
278
if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
279
return 0; /* Error */
284
*ret_max_key=max_key;
added
removed
storage/myisam/mi_range.c
