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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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);
26 : static double _ma_search_pos(MARIA_HA *, MARIA_KEY *, uint32, my_off_t);
27 : static 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 :
46 : ha_rows maria_records_in_range(MARIA_HA *info, int inx, key_range *min_key,
47 : key_range *max_key)
48 881 : {
49 : ha_rows start_pos,end_pos,res;
50 881 : MARIA_SHARE *share= info->s;
51 : MARIA_KEY key;
52 : MARIA_KEYDEF *keyinfo;
53 881 : DBUG_ENTER("maria_records_in_range");
54 :
55 881 : if ((inx = _ma_check_index(info,inx)) < 0)
56 0 : DBUG_RETURN(HA_POS_ERROR);
57 :
58 881 : if (fast_ma_readinfo(info))
59 0 : DBUG_RETURN(HA_POS_ERROR);
60 881 : info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
61 881 : keyinfo= share->keyinfo + inx;
62 881 : if (share->lock_key_trees)
63 0 : rw_rdlock(&keyinfo->root_lock);
64 :
65 881 : 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 0 : if (!min_key)
82 : {
83 0 : res= HA_POS_ERROR;
84 0 : break;
85 : }
86 0 : key_buff= info->last_key.data + share->base.max_key_length;
87 0 : _ma_pack_key(info, &key, inx, key_buff,
88 : min_key->key, min_key->keypart_map,
89 : (HA_KEYSEG**) 0);
90 0 : res= maria_rtree_estimate(info, &key, maria_read_vec[min_key->flag]);
91 0 : res= res ? res : 1; /* Don't return 0 */
92 0 : break;
93 : }
94 : #endif
95 : case HA_KEY_ALG_BTREE:
96 : default:
97 881 : 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 881 : 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 881 : res= (end_pos < start_pos ? (ha_rows) 0 :
106 : (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
107 881 : if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
108 0 : res=HA_POS_ERROR;
109 : }
110 :
111 881 : if (share->lock_key_trees)
112 0 : rw_unlock(&keyinfo->root_lock);
113 881 : 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 881 : DBUG_PRINT("info",("records: %ld",(ulong) (res)));
123 881 : DBUG_RETURN(res);
124 : }
125 :
126 :
127 : /* Find relative position (in records) for key in index-tree */
128 :
129 : static 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 1762 : {
133 1762 : uint inx= (uint) info->lastinx;
134 : uint32 nextflag;
135 : uchar *key_buff;
136 : double pos;
137 : MARIA_KEY key;
138 1762 : DBUG_ENTER("_ma_record_pos");
139 1762 : DBUG_PRINT("enter",("search_flag: %d",search_flag));
140 1762 : DBUG_ASSERT(keypart_map);
141 :
142 1762 : key_buff= info->lastkey_buff+info->s->base.max_key_length;
143 1762 : _ma_pack_key(info, &key, inx, key_buff, key_data, keypart_map,
144 : (HA_KEYSEG**) 0);
145 1762 : DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, &key););
146 1762 : nextflag=maria_read_vec[search_flag];
147 :
148 : /*
149 : my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
150 : This is set in my_handler.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 1762 : pos= _ma_search_pos(info, &key,
183 : nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
184 : info->s->state.key_root[inx]);
185 1762 : if (pos >= 0.0)
186 : {
187 1762 : DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
188 1762 : DBUG_RETURN((ulong) (pos*info->state->records+0.5));
189 : }
190 0 : DBUG_RETURN(HA_POS_ERROR);
191 : }
192 :
193 :
194 : /**
195 : Find offset for key on index page
196 :
197 : @notes
198 : Modified version of _ma_search()
199 :
200 : @return
201 : @retval 0.0 <= x <= 1.0
202 : */
203 :
204 : static double _ma_search_pos(MARIA_HA *info, MARIA_KEY *key,
205 : uint32 nextflag, my_off_t pos)
206 3442 : {
207 : int flag;
208 : uint keynr, max_keynr;
209 : my_bool after_key;
210 : uchar *keypos;
211 : double offset;
212 3442 : MARIA_KEYDEF *keyinfo= key->keyinfo;
213 : MARIA_PAGE page;
214 3442 : DBUG_ENTER("_ma_search_pos");
215 3442 : LINT_INIT(max_keynr);
216 :
217 3442 : if (pos == HA_OFFSET_ERROR)
218 486 : DBUG_RETURN(0.5);
219 :
220 2956 : if (_ma_fetch_keypage(&page, info, keyinfo, pos,
221 : PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS,
222 : info->buff, 1))
223 2956 : goto err;
224 2956 : flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos,
225 : info->lastkey_buff, &after_key);
226 2956 : keynr= _ma_keynr(&page, keypos, &max_keynr);
227 :
228 2956 : if (flag)
229 : {
230 2465 : if (flag == MARIA_FOUND_WRONG_KEY)
231 0 : DBUG_RETURN(-1); /* error */
232 : /*
233 : Didn't found match. keypos points at next (bigger) key
234 : Try to find a smaller, better matching key.
235 : Matches keynr + [0-1]
236 : */
237 3255 : if (flag > 0 && ! page.node)
238 790 : offset= 1.0;
239 1675 : else if ((offset= _ma_search_pos(info, key, nextflag,
240 : _ma_kpos(page.node,keypos))) < 0)
241 0 : DBUG_RETURN(offset);
242 : }
243 : else
244 : {
245 : /*
246 : Found match. Keypos points at the start of the found key
247 : Matches keynr+1
248 : */
249 491 : offset=1.0; /* Matches keynr+1 */
250 491 : if ((nextflag & SEARCH_FIND) && page.node &&
251 : ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
252 : (nextflag & (SEARCH_PREFIX | SEARCH_NO_FIND | SEARCH_LAST |
253 : SEARCH_PART_KEY))))
254 : {
255 : /*
256 : There may be identical keys in the tree. Try to match on of those.
257 : Matches keynr + [0-1]
258 : */
259 5 : if ((offset= _ma_search_pos(info, key, SEARCH_FIND,
260 : _ma_kpos(page.node,keypos))) < 0)
261 0 : DBUG_RETURN(offset); /* Read error */
262 : }
263 : }
264 2956 : DBUG_PRINT("info",("keynr: %d offset: %g max_keynr: %d nod: %d flag: %d",
265 : keynr,offset,max_keynr,page.node,flag));
266 2956 : DBUG_RETURN((keynr+offset)/(max_keynr+1));
267 0 : err:
268 0 : DBUG_PRINT("exit",("Error: %d",my_errno));
269 0 : DBUG_RETURN (-1.0);
270 : }
271 :
272 :
273 : /* Get keynummer of current key and max number of keys in nod */
274 :
275 : static uint _ma_keynr(MARIA_PAGE *page, uchar *keypos, uint *ret_max_key)
276 2956 : {
277 : uint page_flag, nod_flag, keynr, max_key;
278 : uchar t_buff[MARIA_MAX_KEY_BUFF], *pos, *end;
279 2956 : const MARIA_KEYDEF *keyinfo= page->keyinfo;
280 : MARIA_KEY key;
281 :
282 2956 : page_flag= page->flag;
283 2956 : nod_flag= page->node;
284 2956 : pos= page->buff + page->info->s->keypage_header + nod_flag;
285 2956 : end= page->buff + page->size;
286 :
287 2956 : if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
288 : ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
289 : {
290 1688 : *ret_max_key= (uint) (end - pos)/(keyinfo->keylength+nod_flag);
291 1688 : return (uint) (keypos - pos)/(keyinfo->keylength+nod_flag);
292 : }
293 :
294 1268 : max_key=keynr=0;
295 1268 : t_buff[0]=0; /* Safety */
296 1268 : key.data= t_buff;
297 1268 : key.keyinfo= (MARIA_KEYDEF*) keyinfo;
298 :
299 610941 : while (pos < end)
300 : {
301 608405 : if (!(pos= (*keyinfo->skip_key)(&key, page_flag, nod_flag, pos)))
302 : {
303 0 : DBUG_ASSERT(0);
304 : return 0; /* Error */
305 : }
306 608405 : max_key++;
307 608405 : if (pos == keypos)
308 878 : keynr= max_key;
309 : }
310 1268 : *ret_max_key=max_key;
311 1268 : return(keynr);
312 : }
|