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