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