1/*
2 Copyright (c) 2000, 2011, Oracle and/or its affiliates
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17/*
18 Gives a approximated number of how many records there is between two keys.
19 Used when optimizing querries.
20 */
21
22#include "myisamdef.h"
23#include "rt_index.h"
24
25static ha_rows _mi_record_pos(MI_INFO *, const uchar *, key_part_map,
26 enum ha_rkey_function);
27static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,uchar *, uint,uint,my_off_t);
28static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *,uchar *, uchar *,uint *);
29
30/*
31 Estimate how many records there is in a given range
32
33 SYNOPSIS
34 mi_records_in_range()
35 info MyISAM handler
36 inx Index to use
37 min_key Min key. Is = 0 if no min range
38 max_key Max key. Is = 0 if no max range
39
40 NOTES
41 We should ONLY return 0 if there is no rows in range
42
43 RETURN
44 HA_POS_ERROR error (or we can't estimate number of rows)
45 number Estimated number of rows
46*/
47
48ha_rows mi_records_in_range(MI_INFO *info, int inx,
49 key_range *min_key, key_range *max_key)
50{
51 ha_rows start_pos,end_pos,res;
52 DBUG_ENTER("mi_records_in_range");
53
54 if ((inx = _mi_check_index(info,inx)) < 0)
55 DBUG_RETURN(HA_POS_ERROR);
56
57 if (fast_mi_readinfo(info))
58 DBUG_RETURN(HA_POS_ERROR);
59 info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
60 if (info->s->concurrent_insert)
61 mysql_rwlock_rdlock(&info->s->key_root_lock[inx]);
62
63 switch(info->s->keyinfo[inx].key_alg){
64#ifdef HAVE_RTREE_KEYS
65 case HA_KEY_ALG_RTREE:
66 {
67 uchar * key_buff;
68 uint start_key_len;
69
70 /*
71 The problem is that the optimizer doesn't support
72 RTree keys properly at the moment.
73 Hope this will be fixed some day.
74 But now NULL in the min_key means that we
75 didn't make the task for the RTree key
76 and expect BTree functionality from it.
77 As it's not able to handle such request
78 we return the error.
79 */
80 if (!min_key)
81 {
82 res= HA_POS_ERROR;
83 break;
84 }
85 key_buff= info->lastkey+info->s->base.max_key_length;
86 start_key_len= _mi_pack_key(info,inx, key_buff,
87 (uchar*) min_key->key, min_key->keypart_map,
88 (HA_KEYSEG**) 0);
89 res= rtree_estimate(info, inx, key_buff, start_key_len,
90 myisam_read_vec[min_key->flag]);
91 res= res ? res : 1; /* Don't return 0 */
92 break;
93 }
94#endif
95 case HA_KEY_ALG_BTREE:
96 default:
97 start_pos= (min_key ? _mi_record_pos(info, min_key->key,
98 min_key->keypart_map, min_key->flag)
99 : (ha_rows) 0);
100 end_pos= (max_key ? _mi_record_pos(info, max_key->key,
101 max_key->keypart_map, max_key->flag)
102 : info->state->records + (ha_rows) 1);
103 res= (end_pos < start_pos ? (ha_rows) 0 :
104 (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
105 if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
106 res=HA_POS_ERROR;
107 }
108
109 if (info->s->concurrent_insert)
110 mysql_rwlock_unlock(&info->s->key_root_lock[inx]);
111 fast_mi_writeinfo(info);
112
113 DBUG_PRINT("info",("records: %ld",(ulong) (res)));
114 DBUG_RETURN(res);
115}
116
117
118 /* Find relative position (in records) for key in index-tree */
119
120static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
121 key_part_map keypart_map,
122 enum ha_rkey_function search_flag)
123{
124 uint inx=(uint) info->lastinx, nextflag, key_len;
125 MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
126 uchar *key_buff;
127 double pos;
128
129 DBUG_ENTER("_mi_record_pos");
130 DBUG_PRINT("enter",("search_flag: %d",search_flag));
131 DBUG_ASSERT(keypart_map);
132
133 key_buff=info->lastkey+info->s->base.max_key_length;
134 key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key, keypart_map,
135 (HA_KEYSEG**) 0);
136 DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
137 (uchar*) key_buff,key_len););
138 nextflag=myisam_read_vec[search_flag];
139 if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
140 key_len=USE_WHOLE_KEY;
141
142 /*
143 my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
144 This is set in my_handler.c:ha_key_cmp() in dependence on the
145 compare flags 'nextflag' and the column type.
146
147 TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
148 condition is skip_end_space= ((nextflag & (SEARCH_FIND |
149 SEARCH_UPDATE)) == SEARCH_FIND).
150
151 SEARCH_FIND is used for an exact key search. The combination
152 SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
153 operations with a comment like "Not real duplicates", whatever this
154 means. From the condition above we can see that 'skip_end_space' is
155 always false for these operations. The result is that trailing space
156 counts in key comparison and hence, empty strings ('', string length
157 zero, but not NULL) compare less that strings starting with control
158 characters and these in turn compare less than strings starting with
159 blanks.
160
161 When estimating the number of records in a key range, we request an
162 exact search for the minimum key. This translates into a plain
163 SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
164 compare. Empty strings would be expected above control characters.
165 Their keys would not be found because they are located below control
166 characters.
167
168 This is the reason that we add the SEARCH_UPDATE flag here. It makes
169 the key estimation compare in the same way like key write operations
170 do. Only so we will find the keys where they have been inserted.
171
172 Adding the flag unconditionally does not hurt as it is used in the
173 above mentioned condition only. So it can safely be used together
174 with other flags.
175 */
176 pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
177 nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
178 info->s->state.key_root[inx]);
179 if (pos >= 0.0)
180 {
181 DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
182 DBUG_RETURN((ulong) (pos*info->state->records+0.5));
183 }
184 DBUG_RETURN(HA_POS_ERROR);
185}
186
187
188 /* This is a modified version of _mi_search */
189 /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
190
191static double _mi_search_pos(register MI_INFO *info,
192 register MI_KEYDEF *keyinfo,
193 uchar *key, uint key_len, uint nextflag,
194 register my_off_t pos)
195{
196 int flag;
197 uint nod_flag,keynr,UNINIT_VAR(max_keynr);
198 my_bool after_key;
199 uchar *keypos,*buff;
200 double offset;
201 DBUG_ENTER("_mi_search_pos");
202
203 if (pos == HA_OFFSET_ERROR)
204 DBUG_RETURN(0.5);
205
206 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
207 goto err;
208 flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
209 &keypos,info->lastkey, &after_key);
210 nod_flag=mi_test_if_nod(buff);
211 keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
212
213 if (flag)
214 {
215 if (flag == MI_FOUND_WRONG_KEY)
216 DBUG_RETURN(-1); /* error */
217 /*
218 Didn't found match. keypos points at next (bigger) key
219 Try to find a smaller, better matching key.
220 Matches keynr + [0-1]
221 */
222 if (flag > 0 && ! nod_flag)
223 offset= 1.0;
224 else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
225 _mi_kpos(nod_flag,keypos))) < 0)
226 DBUG_RETURN(offset);
227 }
228 else
229 {
230 /*
231 Found match. Keypos points at the start of the found key
232 Matches keynr+1
233 */
234 offset=1.0; /* Matches keynr+1 */
235 if ((nextflag & SEARCH_FIND) && nod_flag &&
236 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
237 key_len != USE_WHOLE_KEY))
238 {
239 /*
240 There may be identical keys in the tree. Try to match on of those.
241 Matches keynr + [0-1]
242 */
243 if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
244 _mi_kpos(nod_flag,keypos))) < 0)
245 DBUG_RETURN(offset); /* Read error */
246 }
247 }
248 DBUG_PRINT("info",("keynr: %d offset: %g max_keynr: %d nod: %d flag: %d",
249 keynr,offset,max_keynr,nod_flag,flag));
250 DBUG_RETURN((keynr+offset)/(max_keynr+1));
251err:
252 DBUG_PRINT("exit",("Error: %d",my_errno));
253 DBUG_RETURN (-1.0);
254}
255
256
257 /* Get keynummer of current key and max number of keys in nod */
258
259static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
260 uchar *keypos, uint *ret_max_key)
261{
262 uint nod_flag,keynr,max_key;
263 uchar t_buff[HA_MAX_KEY_BUFF],*end;
264
265 end= page+mi_getint(page);
266 nod_flag=mi_test_if_nod(page);
267 page+=2+nod_flag;
268
269 if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
270 {
271 *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
272 return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
273 }
274
275 max_key=keynr=0;
276 t_buff[0]=0; /* Safety */
277 while (page < end)
278 {
279 if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
280 return 0; /* Error */
281 max_key++;
282 if (page == keypos)
283 keynr=max_key;
284 }
285 *ret_max_key=max_key;
286 return(keynr);
287}
288