1 /*
2 Copyright (c) 2000, 2021, Oracle and/or its affiliates.
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 case HA_KEY_ALG_RTREE:
73 {
74 uchar * key_buff;
75 uint start_key_len;
76
77 /*
78 The problem is that the optimizer doesn't support
79 RTree keys properly at the moment.
80 Hope this will be fixed some day.
81 But now NULL in the min_key means that we
82 didn't make the task for the RTree key
83 and expect BTree functionality from it.
84 As it's not able to handle such request
85 we return the error.
86 */
87 if (!min_key)
88 {
89 res= HA_POS_ERROR;
90 break;
91 }
92 key_buff= info->lastkey+info->s->base.max_key_length;
93 start_key_len= _mi_pack_key(info,inx, key_buff,
94 (uchar*) min_key->key, min_key->keypart_map,
95 (HA_KEYSEG**) 0);
96 res= rtree_estimate(info, inx, key_buff, start_key_len,
97 myisam_read_vec[min_key->flag]);
98 res= res ? res : 1; /* Don't return 0 */
99 break;
100 }
101 case HA_KEY_ALG_BTREE:
102 default:
103 start_pos= (min_key ? _mi_record_pos(info, min_key->key,
104 min_key->keypart_map, min_key->flag)
105 : (ha_rows) 0);
106 end_pos= (max_key ? _mi_record_pos(info, max_key->key,
107 max_key->keypart_map, max_key->flag)
108 : info->state->records + (ha_rows) 1);
109 res= (end_pos < start_pos ? (ha_rows) 0 :
110 (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
111 if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
112 res=HA_POS_ERROR;
113 }
114
115 if (info->s->concurrent_insert)
116 mysql_rwlock_unlock(&info->s->key_root_lock[inx]);
117 fast_mi_writeinfo(info);
118
119 DBUG_PRINT("info",("records: %ld",(ulong) (res)));
120 DBUG_RETURN(res);
121 }
122
123
124 /* Find relative position (in records) for key in index-tree */
125
_mi_record_pos(MI_INFO * info,const uchar * key,key_part_map keypart_map,enum ha_rkey_function search_flag)126 static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
127 key_part_map keypart_map,
128 enum ha_rkey_function search_flag)
129 {
130 uint inx=(uint) info->lastinx, nextflag, key_len;
131 MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
132 uchar *key_buff;
133 double pos;
134
135 DBUG_ENTER("_mi_record_pos");
136 DBUG_PRINT("enter",("search_flag: %d",search_flag));
137 assert(keypart_map);
138
139 key_buff=info->lastkey+info->s->base.max_key_length;
140 key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key, keypart_map,
141 (HA_KEYSEG**) 0);
142 DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
143 (uchar*) key_buff,key_len););
144 nextflag=myisam_read_vec[search_flag];
145 if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
146 key_len=USE_WHOLE_KEY;
147
148 /*
149 my_compare.c:ha_compare_text() has a flag 'skip_end_space'.
150 This is set in my_compare.c:ha_key_cmp() in dependence on the
151 compare flags 'nextflag' and the column type.
152
153 TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
154 condition is skip_end_space= ((nextflag & (SEARCH_FIND |
155 SEARCH_UPDATE)) == SEARCH_FIND).
156
157 SEARCH_FIND is used for an exact key search. The combination
158 SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
159 operations with a comment like "Not real duplicates", whatever this
160 means. From the condition above we can see that 'skip_end_space' is
161 always false for these operations. The result is that trailing space
162 counts in key comparison and hence, emtpy strings ('', string length
163 zero, but not NULL) compare less that strings starting with control
164 characters and these in turn compare less than strings starting with
165 blanks.
166
167 When estimating the number of records in a key range, we request an
168 exact search for the minimum key. This translates into a plain
169 SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
170 compare. Empty strings would be expected above control characters.
171 Their keys would not be found because they are located below control
172 characters.
173
174 This is the reason that we add the SEARCH_UPDATE flag here. It makes
175 the key estimation compare in the same way like key write operations
176 do. Olny so we will find the keys where they have been inserted.
177
178 Adding the flag unconditionally does not hurt as it is used in the
179 above mentioned condition only. So it can safely be used together
180 with other flags.
181 */
182 pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
183 nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
184 info->s->state.key_root[inx]);
185 if (pos >= 0.0)
186 {
187 DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
188 DBUG_RETURN((ulong) (pos*info->state->records+0.5));
189 }
190 DBUG_RETURN(HA_POS_ERROR);
191 }
192
193
194 /* This is a modified version of _mi_search */
195 /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
196
_mi_search_pos(MI_INFO * info,MI_KEYDEF * keyinfo,uchar * key,uint key_len,uint nextflag,my_off_t pos)197 static double _mi_search_pos(MI_INFO *info,
198 MI_KEYDEF *keyinfo,
199 uchar *key, uint key_len, uint nextflag,
200 my_off_t pos)
201 {
202 int flag;
203 uint nod_flag, keynr, max_keynr= 0;
204 my_bool after_key;
205 uchar *keypos,*buff;
206 double offset;
207 DBUG_ENTER("_mi_search_pos");
208
209 if (pos == HA_OFFSET_ERROR)
210 DBUG_RETURN(0.5);
211
212 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
213 goto err;
214 flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
215 &keypos,info->lastkey, &after_key);
216 nod_flag=mi_test_if_nod(buff);
217 keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
218
219 if (flag)
220 {
221 if (flag == MI_FOUND_WRONG_KEY)
222 DBUG_RETURN(-1); /* error */
223 /*
224 Didn't found match. keypos points at next (bigger) key
225 Try to find a smaller, better matching key.
226 Matches keynr + [0-1]
227 */
228 if (flag > 0 && ! nod_flag)
229 offset= 1.0;
230 else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
231 _mi_kpos(nod_flag,keypos))) < 0)
232 DBUG_RETURN(offset);
233 }
234 else
235 {
236 /*
237 Found match. Keypos points at the start of the found key
238 Matches keynr+1
239 */
240 offset=1.0; /* Matches keynr+1 */
241 if ((nextflag & SEARCH_FIND) && nod_flag &&
242 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
243 key_len != USE_WHOLE_KEY))
244 {
245 /*
246 There may be identical keys in the tree. Try to match on of those.
247 Matches keynr + [0-1]
248 */
249 if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
250 _mi_kpos(nod_flag,keypos))) < 0)
251 DBUG_RETURN(offset); /* Read error */
252 }
253 }
254 DBUG_PRINT("info",("keynr: %d offset: %g max_keynr: %d nod: %d flag: %d",
255 keynr,offset,max_keynr,nod_flag,flag));
256 DBUG_RETURN((keynr+offset)/(max_keynr+1));
257 err:
258 DBUG_PRINT("exit",("Error: %d",my_errno()));
259 DBUG_RETURN (-1.0);
260 }
261
262
263 /* Get keynummer of current key and max number of keys in nod */
264
_mi_keynr(MI_INFO * info,MI_KEYDEF * keyinfo,uchar * page,uchar * keypos,uint * ret_max_key)265 static uint _mi_keynr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
266 uchar *keypos, uint *ret_max_key)
267 {
268 uint nod_flag,keynr,max_key;
269 uchar t_buff[MI_MAX_KEY_BUFF],*end;
270
271 end= page+mi_getint(page);
272 nod_flag=mi_test_if_nod(page);
273 page+=2+nod_flag;
274
275 if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
276 {
277 *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
278 return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
279 }
280
281 max_key=keynr=0;
282 t_buff[0]=0; /* Safety */
283 while (page < end)
284 {
285 if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
286 return 0; /* Error */
287 max_key++;
288 if (page == keypos)
289 keynr=max_key;
290 }
291 *ret_max_key=max_key;
292 return(keynr);
293 }
294