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 "myisam_priv.h"
23
using namespace drizzled;
25
static ha_rows _mi_record_pos(MI_INFO *, const unsigned char *, key_part_map,
26
enum ha_rkey_function);
27
static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,unsigned char *, uint,uint,internal::my_off_t);
28
static uint32_t _mi_keynr(MI_INFO *info,MI_KEYDEF *,unsigned char *, unsigned char *,uint32_t *);
31
Estimate how many records there is in a given range
37
min_key Min key. Is = 0 if no min range
38
max_key Max key. Is = 0 if no max range
41
We should ONLY return 0 if there is no rows in range
44
HA_POS_ERROR error (or we can't estimate number of rows)
45
number Estimated number of rows
48
ha_rows mi_records_in_range(MI_INFO *info, int inx,
49
key_range *min_key, key_range *max_key)
51
ha_rows start_pos,end_pos,res;
53
if ((inx = _mi_check_index(info,inx)) < 0)
56
if (fast_mi_readinfo(info))
58
info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
59
if (info->s->concurrent_insert)
60
pthread_rwlock_rdlock(&info->s->key_root_lock[inx]);
62
switch(info->s->keyinfo[inx].key_alg){
63
case HA_KEY_ALG_BTREE:
65
start_pos= (min_key ? _mi_record_pos(info, min_key->key,
66
min_key->keypart_map, min_key->flag)
68
end_pos= (max_key ? _mi_record_pos(info, max_key->key,
69
max_key->keypart_map, max_key->flag)
70
: info->state->records + (ha_rows) 1);
71
res= (end_pos < start_pos ? (ha_rows) 0 :
72
(end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
73
if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
77
if (info->s->concurrent_insert)
78
pthread_rwlock_unlock(&info->s->key_root_lock[inx]);
79
fast_mi_writeinfo(info);
85
/* Find relative position (in records) for key in index-tree */
87
static ha_rows _mi_record_pos(MI_INFO *info, const unsigned char *key,
88
key_part_map keypart_map,
89
enum ha_rkey_function search_flag)
91
uint32_t inx=(uint) info->lastinx, nextflag, key_len;
92
MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
93
unsigned char *key_buff;
98
key_buff=info->lastkey+info->s->base.max_key_length;
99
key_len=_mi_pack_key(info,inx,key_buff,(unsigned char*) key, keypart_map,
101
nextflag=myisam_read_vec[search_flag];
102
if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
103
key_len=USE_WHOLE_KEY;
106
my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
107
This is set in my_handler.c:ha_key_cmp() in dependence on the
108
compare flags 'nextflag' and the column type.
110
TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
111
condition is skip_end_space= ((nextflag & (SEARCH_FIND |
112
SEARCH_UPDATE)) == SEARCH_FIND).
114
SEARCH_FIND is used for an exact key search. The combination
115
SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
116
operations with a comment like "Not real duplicates", whatever this
117
means. From the condition above we can see that 'skip_end_space' is
118
always false for these operations. The result is that trailing space
119
counts in key comparison and hence, emtpy strings ('', string length
120
zero, but not NULL) compare less that strings starting with control
121
characters and these in turn compare less than strings starting with
124
When estimating the number of records in a key range, we request an
125
exact search for the minimum key. This translates into a plain
126
SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
127
compare. Empty strings would be expected above control characters.
128
Their keys would not be found because they are located below control
131
This is the reason that we add the SEARCH_UPDATE flag here. It makes
132
the key estimation compare in the same way like key write operations
133
do. Olny so we will find the keys where they have been inserted.
135
Adding the flag unconditionally does not hurt as it is used in the
136
above mentioned condition only. So it can safely be used together
139
pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
140
nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
141
info->s->state.key_root[inx]);
144
return((uint32_t) (pos*info->state->records+0.5));
146
return(HA_POS_ERROR);
150
/* This is a modified version of _mi_search */
151
/* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
153
static double _mi_search_pos(register MI_INFO *info,
154
register MI_KEYDEF *keyinfo,
155
unsigned char *key, uint32_t key_len, uint32_t nextflag,
156
register internal::my_off_t pos)
159
uint32_t nod_flag, keynr, max_keynr= 0;
161
unsigned char *keypos,*buff;
164
if (pos == HA_OFFSET_ERROR)
167
if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
169
flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
170
&keypos,info->lastkey, &after_key);
171
nod_flag=mi_test_if_nod(buff);
172
keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
176
if (flag == MI_FOUND_WRONG_KEY)
177
return(-1); /* error */
179
Didn't found match. keypos points at next (bigger) key
180
Try to find a smaller, better matching key.
181
Matches keynr + [0-1]
183
if (flag > 0 && ! nod_flag)
185
else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
186
_mi_kpos(nod_flag,keypos))) < 0)
192
Found match. Keypos points at the start of the found key
195
offset=1.0; /* Matches keynr+1 */
196
if ((nextflag & SEARCH_FIND) && nod_flag &&
197
((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
198
key_len != USE_WHOLE_KEY))
201
There may be identical keys in the tree. Try to match on of those.
202
Matches keynr + [0-1]
204
if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
205
_mi_kpos(nod_flag,keypos))) < 0)
206
return(offset); /* Read error */
209
return((keynr+offset)/(max_keynr+1));
215
/* Get keynummer of current key and max number of keys in nod */
217
static uint32_t _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
218
unsigned char *keypos, uint32_t *ret_max_key)
220
uint32_t nod_flag,keynr,max_key;
221
unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
223
end= page+mi_getint(page);
224
nod_flag=mi_test_if_nod(page);
227
if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
229
*ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
230
return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
234
t_buff[0]=0; /* Safety */
237
if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
238
return 0; /* Error */
243
*ret_max_key=max_key;