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