1 /* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
2
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.
6
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.
11
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
15
16 /*
17 Gives a approximated number of how many records there is between two keys.
18 Used when optimizing querries.
19 */
20
21 #include "maria_def.h"
22 #include "ma_rt_index.h"
23
24 static ha_rows _ma_record_pos(MARIA_HA *,const uchar *, key_part_map,
25 enum ha_rkey_function, ulonglong *);
26 static double _ma_search_pos(MARIA_HA *, MARIA_KEY *, uint32, my_off_t,
27 ulonglong *page);
28 static uint _ma_keynr(MARIA_PAGE *page, uchar *keypos, uint *ret_max_key);
29
30
31 /**
32 @brief Estimate how many records there is in a given range
33
34 @param info MARIA handler
35 @param inx Index to use
36 @param min_key Min key. Is = 0 if no min range
37 @param max_key Max key. Is = 0 if no max range
38
39 @note
40 We should ONLY return 0 if there is no rows in range
41
42 @return Estimated number of rows or error
43 @retval HA_POS_ERROR error (or we can't estimate number of rows)
44 @retval number Estimated number of rows
45 */
46
maria_records_in_range(MARIA_HA * info,int inx,const key_range * min_key,const key_range * max_key,page_range * pages)47 ha_rows maria_records_in_range(MARIA_HA *info, int inx,
48 const key_range *min_key,
49 const key_range *max_key, page_range *pages)
50 {
51 ha_rows start_pos,end_pos,res;
52 MARIA_SHARE *share= info->s;
53 MARIA_KEY key;
54 MARIA_KEYDEF *keyinfo;
55 DBUG_ENTER("maria_records_in_range");
56
57 if ((inx = _ma_check_index(info,inx)) < 0)
58 DBUG_RETURN(HA_POS_ERROR);
59
60 if (fast_ma_readinfo(info))
61 DBUG_RETURN(HA_POS_ERROR);
62 info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
63 keyinfo= share->keyinfo + inx;
64 if (share->lock_key_trees)
65 mysql_rwlock_rdlock(&keyinfo->root_lock);
66
67 switch (keyinfo->key_alg) {
68 #ifdef HAVE_RTREE_KEYS
69 case HA_KEY_ALG_RTREE:
70 {
71 uchar *key_buff;
72
73 /*
74 The problem is that the optimizer doesn't support
75 RTree keys properly at the moment.
76 Hope this will be fixed some day.
77 But now NULL in the min_key means that we
78 didn't make the task for the RTree key
79 and expect BTree functionality from it.
80 As it's not able to handle such request
81 we return the error.
82 */
83 if (!min_key)
84 {
85 res= HA_POS_ERROR;
86 break;
87 }
88 key_buff= info->last_key.data + share->base.max_key_length;
89 _ma_pack_key(info, &key, inx, key_buff,
90 min_key->key, min_key->keypart_map,
91 (HA_KEYSEG**) 0);
92 res= maria_rtree_estimate(info, &key, maria_read_vec[min_key->flag]);
93 res= res ? res : 1; /* Don't return 0 */
94 break;
95 }
96 #endif
97 case HA_KEY_ALG_BTREE:
98 default:
99 start_pos= (min_key ?
100 _ma_record_pos(info, min_key->key, min_key->keypart_map,
101 min_key->flag, &pages->first_page) :
102 (ha_rows) 0);
103 end_pos= (max_key ?
104 _ma_record_pos(info, max_key->key, max_key->keypart_map,
105 max_key->flag, &pages->last_page) :
106 info->state->records + (ha_rows) 1);
107 res= (end_pos < start_pos ? (ha_rows) 0 :
108 (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
109 if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
110 res=HA_POS_ERROR;
111 }
112
113 if (share->lock_key_trees)
114 mysql_rwlock_unlock(&keyinfo->root_lock);
115 fast_ma_writeinfo(info);
116
117 /**
118 @todo LOCK
119 If res==0 (no rows), if we need to guarantee repeatability of the search,
120 we will need to set a next-key lock in this statement.
121 Also SELECT COUNT(*)...
122 */
123
124 DBUG_PRINT("info",("records: %ld",(ulong) (res)));
125 DBUG_RETURN(res);
126 }
127
128
129 /* Find relative position (in records) for key in index-tree */
130
_ma_record_pos(MARIA_HA * info,const uchar * key_data,key_part_map keypart_map,enum ha_rkey_function search_flag,ulonglong * final_page)131 static ha_rows _ma_record_pos(MARIA_HA *info, const uchar *key_data,
132 key_part_map keypart_map,
133 enum ha_rkey_function search_flag,
134 ulonglong *final_page)
135 {
136 uint inx= (uint) info->lastinx;
137 uint32 nextflag;
138 uchar *key_buff;
139 double pos;
140 MARIA_KEY key;
141 DBUG_ENTER("_ma_record_pos");
142 DBUG_PRINT("enter",("search_flag: %d",search_flag));
143 DBUG_ASSERT(keypart_map);
144
145 key_buff= info->lastkey_buff+info->s->base.max_key_length;
146 _ma_pack_key(info, &key, inx, key_buff, key_data, keypart_map,
147 (HA_KEYSEG**) 0);
148 DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, &key););
149 nextflag=maria_read_vec[search_flag];
150
151 /* Indicate if we're doing a search on a key prefix */
152 if (((((key_part_map)1) << key.keyinfo->keysegs) - 1) != keypart_map)
153 nextflag |= SEARCH_PART_KEY;
154
155 /*
156 my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
157 This is set in my_handler.c:ha_key_cmp() in dependence on the
158 compare flags 'nextflag' and the column type.
159
160 TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
161 condition is skip_end_space= ((nextflag & (SEARCH_FIND |
162 SEARCH_UPDATE)) == SEARCH_FIND).
163
164 SEARCH_FIND is used for an exact key search. The combination
165 SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
166 operations with a comment like "Not real duplicates", whatever this
167 means. From the condition above we can see that 'skip_end_space' is
168 always false for these operations. The result is that trailing space
169 counts in key comparison and hence, empty strings ('', string length
170 zero, but not NULL) compare less that strings starting with control
171 characters and these in turn compare less than strings starting with
172 blanks.
173
174 When estimating the number of records in a key range, we request an
175 exact search for the minimum key. This translates into a plain
176 SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
177 compare. Empty strings would be expected above control characters.
178 Their keys would not be found because they are located below control
179 characters.
180
181 This is the reason that we add the SEARCH_UPDATE flag here. It makes
182 the key estimation compare in the same way like key write operations
183 do. Only so we will find the keys where they have been inserted.
184
185 Adding the flag unconditionally does not hurt as it is used in the
186 above mentioned condition only. So it can safely be used together
187 with other flags.
188 */
189 pos= _ma_search_pos(info, &key,
190 nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
191 info->s->state.key_root[inx], final_page);
192 if (pos >= 0.0)
193 {
194 DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
195 DBUG_RETURN((ulong) (pos*info->state->records+0.5));
196 }
197 DBUG_RETURN(HA_POS_ERROR);
198 }
199
200
201 /**
202 Find offset for key on index page
203
204 @notes
205 Modified version of _ma_search()
206
207 @return
208 @retval 0.0 <= x <= 1.0
209 */
210
_ma_search_pos(MARIA_HA * info,MARIA_KEY * key,uint32 nextflag,my_off_t pos,ulonglong * final_page)211 static double _ma_search_pos(MARIA_HA *info, MARIA_KEY *key,
212 uint32 nextflag, my_off_t pos,
213 ulonglong *final_page)
214 {
215 int flag;
216 uint keynr, UNINIT_VAR(max_keynr);
217 my_bool after_key;
218 uchar *keypos;
219 double offset;
220 MARIA_KEYDEF *keyinfo= key->keyinfo;
221 MARIA_PAGE page;
222 DBUG_ENTER("_ma_search_pos");
223
224 if (pos == HA_OFFSET_ERROR)
225 DBUG_RETURN(0.0);
226
227 if (_ma_fetch_keypage(&page, info, keyinfo, pos,
228 PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS,
229 info->buff, 1))
230 goto err;
231 *final_page= pos;
232 flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos,
233 info->lastkey_buff, &after_key);
234 keynr= _ma_keynr(&page, keypos, &max_keynr);
235
236 if (flag)
237 {
238 if (flag == MARIA_FOUND_WRONG_KEY)
239 DBUG_RETURN(-1); /* error */
240 /*
241 Didn't found match. keypos points at next (bigger) key
242 Try to find a smaller, better matching key.
243 Matches keynr + [0-1]
244 */
245 if (! page.node)
246 offset= 0.0;
247 else if ((offset= _ma_search_pos(info, key, nextflag,
248 _ma_kpos(page.node,keypos),
249 final_page)) < 0)
250 DBUG_RETURN(offset);
251 }
252 else
253 {
254 /*
255 Found match. Keypos points at the start of the found key.
256
257 For node pages, we are counting underlying trees and for key
258 pages we are counting keys.
259
260 If this is a node then we have to search backwards to find the
261 first occurrence of the key. The row position in a node tree
262 is keynr (starting from 0) + offset for sub tree. If there is
263 no sub tree to search, then we are at start of next sub tree.
264
265 If this is not a node, then the current key position is correct.
266 */
267 offset= (page.node) ? 1.0 : 0.0;
268 if ((nextflag & SEARCH_FIND) && page.node &&
269 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
270 (nextflag & (SEARCH_PREFIX | SEARCH_NO_FIND | SEARCH_LAST |
271 SEARCH_PART_KEY))))
272 {
273 /*
274 There may be identical keys in the tree. Try to match on of those.
275 Matches keynr + [0-1]
276 */
277 if ((offset= _ma_search_pos(info, key, SEARCH_FIND,
278 _ma_kpos(page.node,keypos),
279 final_page)) < 0)
280 DBUG_RETURN(offset); /* Read error */
281 }
282 }
283 DBUG_PRINT("info",("keynr: %d offset: %g max_keynr: %d nod: %d flag: %d",
284 keynr,offset,max_keynr,page.node,flag));
285 DBUG_RETURN((keynr + offset) / (max_keynr + MY_TEST(page.node)));
286 err:
287 DBUG_PRINT("exit",("Error: %d",my_errno));
288 DBUG_RETURN (-1.0);
289 }
290
291
292 /*
293 Get keynummer of current key and max number of keys in nod
294
295 keynr >= 0 && key_nr <= max_key
296 */
297
_ma_keynr(MARIA_PAGE * page,uchar * keypos,uint * ret_max_key)298 static uint _ma_keynr(MARIA_PAGE *page, uchar *keypos, uint *ret_max_key)
299 {
300 uint page_flag, nod_flag, keynr, max_key;
301 uchar t_buff[MARIA_MAX_KEY_BUFF], *pos, *end;
302 const MARIA_KEYDEF *keyinfo= page->keyinfo;
303 MARIA_KEY key;
304
305 page_flag= page->flag;
306 nod_flag= page->node;
307 pos= page->buff + page->info->s->keypage_header + nod_flag;
308 end= page->buff + page->size;
309
310 if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
311 ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
312 {
313 *ret_max_key= (uint) (end - pos)/(keyinfo->keylength+nod_flag);
314 return (uint) (keypos - pos)/(keyinfo->keylength+nod_flag);
315 }
316
317 max_key=keynr=0;
318 t_buff[0]=0; /* Safety */
319 key.data= t_buff;
320 key.keyinfo= (MARIA_KEYDEF*) keyinfo;
321
322 while (pos < end)
323 {
324 if (!(pos= (*keyinfo->skip_key)(&key, page_flag, nod_flag, pos)))
325 {
326 DBUG_ASSERT(0);
327 return 0; /* Error */
328 }
329 max_key++;
330 if (pos == keypos)
331 keynr= max_key;
332 }
333 *ret_max_key=max_key;
334 return(keynr);
335 }
336