drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
mi_range.cc
1/* Copyright (C) 2000-2004, 2006 MySQL 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 St, Fifth Floor, Boston, MA 02110-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 "myisam_priv.h"
22#include <drizzled/message/table.h>
23
24using namespace drizzled;
25
26static ha_rows _mi_record_pos(MI_INFO *, const unsigned char *, key_part_map,
27 enum ha_rkey_function);
28static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,unsigned char *, uint,uint,internal::my_off_t);
29static uint32_t _mi_keynr(MI_INFO *info,MI_KEYDEF *,unsigned char *, unsigned char *,uint32_t *);
30
31/*
32 Estimate how many records there is in a given range
33
34 SYNOPSIS
35 mi_records_in_range()
36 info MyISAM handler
37 inx Index to use
38 min_key Min key. Is = 0 if no min range
39 max_key Max key. Is = 0 if no max range
40
41 NOTES
42 We should ONLY return 0 if there is no rows in range
43
44 RETURN
45 HA_POS_ERROR error (or we can't estimate number of rows)
46 number Estimated number of rows
47*/
48
49ha_rows mi_records_in_range(MI_INFO *info, int inx,
50 key_range *min_key, key_range *max_key)
51{
52 ha_rows start_pos,end_pos,res;
53
54 if ((inx = _mi_check_index(info,inx)) < 0)
55 return(HA_POS_ERROR);
56
57 if (fast_mi_readinfo(info))
58 return(HA_POS_ERROR);
59 info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
60
61 switch(info->s->keyinfo[inx].key_alg){
62 case message::Table::Index::BTREE:
63 default:
64 start_pos= (min_key ? _mi_record_pos(info, min_key->key,
65 min_key->keypart_map, min_key->flag)
66 : (ha_rows) 0);
67 end_pos= (max_key ? _mi_record_pos(info, max_key->key,
68 max_key->keypart_map, max_key->flag)
69 : info->state->records + (ha_rows) 1);
70 res= (end_pos < start_pos ? (ha_rows) 0 :
71 (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
72 if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
73 res=HA_POS_ERROR;
74 }
75
76 fast_mi_writeinfo(info);
77
78 return(res);
79}
80
81
82 /* Find relative position (in records) for key in index-tree */
83
84static ha_rows _mi_record_pos(MI_INFO *info, const unsigned char *key,
85 key_part_map keypart_map,
86 enum ha_rkey_function search_flag)
87{
88 uint32_t inx=(uint) info->lastinx, nextflag, key_len;
89 MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
90 unsigned char *key_buff;
91 double pos;
92
93 assert(keypart_map);
94
95 key_buff=info->lastkey+info->s->base.max_key_length;
96 key_len=_mi_pack_key(info,inx,key_buff,(unsigned char*) key, keypart_map,
97 (HA_KEYSEG**) 0);
98 nextflag=myisam_read_vec[search_flag];
99 if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
100 key_len=USE_WHOLE_KEY;
101
102 /*
103 my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
104 This is set in my_handler.c:ha_key_cmp() in dependence on the
105 compare flags 'nextflag' and the column type.
106
107 TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
108 condition is skip_end_space= ((nextflag & (SEARCH_FIND |
109 SEARCH_UPDATE)) == SEARCH_FIND).
110
111 SEARCH_FIND is used for an exact key search. The combination
112 SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
113 operations with a comment like "Not real duplicates", whatever this
114 means. From the condition above we can see that 'skip_end_space' is
115 always false for these operations. The result is that trailing space
116 counts in key comparison and hence, emtpy strings ('', string length
117 zero, but not NULL) compare less that strings starting with control
118 characters and these in turn compare less than strings starting with
119 blanks.
120
121 When estimating the number of records in a key range, we request an
122 exact search for the minimum key. This translates into a plain
123 SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
124 compare. Empty strings would be expected above control characters.
125 Their keys would not be found because they are located below control
126 characters.
127
128 This is the reason that we add the SEARCH_UPDATE flag here. It makes
129 the key estimation compare in the same way like key write operations
130 do. Olny so we will find the keys where they have been inserted.
131
132 Adding the flag unconditionally does not hurt as it is used in the
133 above mentioned condition only. So it can safely be used together
134 with other flags.
135 */
136 pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
137 nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
138 info->s->state.key_root[inx]);
139 if (pos >= 0.0)
140 {
141 return((uint32_t) (pos*info->state->records+0.5));
142 }
143 return(HA_POS_ERROR);
144}
145
146
147 /* This is a modified version of _mi_search */
148 /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
149
150static double _mi_search_pos(MI_INFO *info,
151 MI_KEYDEF *keyinfo,
152 unsigned char *key, uint32_t key_len, uint32_t nextflag,
153 internal::my_off_t pos)
154{
155 int flag;
156 uint32_t nod_flag, keynr, max_keynr= 0;
157 bool after_key;
158 unsigned char *keypos,*buff;
159 double offset;
160
161 if (pos == HA_OFFSET_ERROR)
162 return(0.5);
163
164 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
165 goto err;
166 flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
167 &keypos,info->lastkey, &after_key);
168 nod_flag=mi_test_if_nod(buff);
169 keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
170
171 if (flag)
172 {
173 if (flag == MI_FOUND_WRONG_KEY)
174 return(-1); /* error */
175 /*
176 Didn't found match. keypos points at next (bigger) key
177 Try to find a smaller, better matching key.
178 Matches keynr + [0-1]
179 */
180 if (flag > 0 && ! nod_flag)
181 offset= 1.0;
182 else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
183 _mi_kpos(nod_flag,keypos))) < 0)
184 return(offset);
185 }
186 else
187 {
188 /*
189 Found match. Keypos points at the start of the found key
190 Matches keynr+1
191 */
192 offset=1.0; /* Matches keynr+1 */
193 if ((nextflag & SEARCH_FIND) && nod_flag &&
194 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
195 key_len != USE_WHOLE_KEY))
196 {
197 /*
198 There may be identical keys in the tree. Try to match on of those.
199 Matches keynr + [0-1]
200 */
201 if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
202 _mi_kpos(nod_flag,keypos))) < 0)
203 return(offset); /* Read error */
204 }
205 }
206 return((keynr+offset)/(max_keynr+1));
207err:
208 return (-1.0);
209}
210
211
212 /* Get keynummer of current key and max number of keys in nod */
213
214static uint32_t _mi_keynr(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
215 unsigned char *keypos, uint32_t *ret_max_key)
216{
217 uint32_t nod_flag,keynr,max_key;
218 unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
219
220 end= page+mi_getint(page);
221 nod_flag=mi_test_if_nod(page);
222 page+=2+nod_flag;
223
224 if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
225 {
226 *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
227 return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
228 }
229
230 max_key=keynr=0;
231 t_buff[0]=0; /* Safety */
232 while (page < end)
233 {
234 if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
235 return 0; /* Error */
236 max_key++;
237 if (page == keypos)
238 keynr=max_key;
239 }
240 *ret_max_key=max_key;
241 return(keynr);
242}
TODO: Rename this file - func.h is stupid.