Drizzled Public API Documentation

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