Drizzled Public API Documentation

mi_range.cc
00001 /* Copyright (C) 2000-2004, 2006 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /*
00017   Gives a approximated number of how many records there is between two keys.
00018   Used when optimizing querries.
00019  */
00020 
00021 #include "myisam_priv.h"
00022 
00023 using namespace drizzled;
00024 
00025 static ha_rows _mi_record_pos(MI_INFO *, const unsigned char *, key_part_map,
00026                               enum ha_rkey_function);
00027 static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,unsigned char *, uint,uint,internal::my_off_t);
00028 static uint32_t _mi_keynr(MI_INFO *info,MI_KEYDEF *,unsigned char *, unsigned char *,uint32_t *);
00029 
00030 /*
00031   Estimate how many records there is in a given range
00032 
00033   SYNOPSIS
00034     mi_records_in_range()
00035     info    MyISAM handler
00036     inx     Index to use
00037     min_key   Min key. Is = 0 if no min range
00038     max_key   Max key. Is = 0 if no max range
00039 
00040   NOTES
00041     We should ONLY return 0 if there is no rows in range
00042 
00043   RETURN
00044     HA_POS_ERROR  error (or we can't estimate number of rows)
00045     number    Estimated number of rows
00046 */
00047 
00048 ha_rows mi_records_in_range(MI_INFO *info, int inx,
00049                             key_range *min_key, key_range *max_key)
00050 {
00051   ha_rows start_pos,end_pos,res;
00052 
00053   if ((inx = _mi_check_index(info,inx)) < 0)
00054     return(HA_POS_ERROR);
00055 
00056   if (fast_mi_readinfo(info))
00057     return(HA_POS_ERROR);
00058   info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
00059 
00060   switch(info->s->keyinfo[inx].key_alg){
00061   case HA_KEY_ALG_BTREE:
00062   default:
00063     start_pos= (min_key ?  _mi_record_pos(info, min_key->key,
00064                                           min_key->keypart_map, min_key->flag)
00065                         : (ha_rows) 0);
00066     end_pos=   (max_key ?  _mi_record_pos(info, max_key->key,
00067                                           max_key->keypart_map, max_key->flag)
00068                         : info->state->records + (ha_rows) 1);
00069     res= (end_pos < start_pos ? (ha_rows) 0 :
00070           (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
00071     if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
00072       res=HA_POS_ERROR;
00073   }
00074 
00075   fast_mi_writeinfo(info);
00076 
00077   return(res);
00078 }
00079 
00080 
00081   /* Find relative position (in records) for key in index-tree */
00082 
00083 static ha_rows _mi_record_pos(MI_INFO *info, const unsigned char *key,
00084                               key_part_map keypart_map,
00085             enum ha_rkey_function search_flag)
00086 {
00087   uint32_t inx=(uint) info->lastinx, nextflag, key_len;
00088   MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
00089   unsigned char *key_buff;
00090   double pos;
00091 
00092   assert(keypart_map);
00093 
00094   key_buff=info->lastkey+info->s->base.max_key_length;
00095   key_len=_mi_pack_key(info,inx,key_buff,(unsigned char*) key, keypart_map,
00096            (HA_KEYSEG**) 0);
00097   nextflag=myisam_read_vec[search_flag];
00098   if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
00099     key_len=USE_WHOLE_KEY;
00100 
00101   /*
00102     my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
00103     This is set in my_handler.c:ha_key_cmp() in dependence on the
00104     compare flags 'nextflag' and the column type.
00105 
00106     TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
00107     condition is skip_end_space= ((nextflag & (SEARCH_FIND |
00108     SEARCH_UPDATE)) == SEARCH_FIND).
00109 
00110     SEARCH_FIND is used for an exact key search. The combination
00111     SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
00112     operations with a comment like "Not real duplicates", whatever this
00113     means. From the condition above we can see that 'skip_end_space' is
00114     always false for these operations. The result is that trailing space
00115     counts in key comparison and hence, emtpy strings ('', string length
00116     zero, but not NULL) compare less that strings starting with control
00117     characters and these in turn compare less than strings starting with
00118     blanks.
00119 
00120     When estimating the number of records in a key range, we request an
00121     exact search for the minimum key. This translates into a plain
00122     SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
00123     compare. Empty strings would be expected above control characters.
00124     Their keys would not be found because they are located below control
00125     characters.
00126 
00127     This is the reason that we add the SEARCH_UPDATE flag here. It makes
00128     the key estimation compare in the same way like key write operations
00129     do. Olny so we will find the keys where they have been inserted.
00130 
00131     Adding the flag unconditionally does not hurt as it is used in the
00132     above mentioned condition only. So it can safely be used together
00133     with other flags.
00134   */
00135   pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
00136          nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
00137          info->s->state.key_root[inx]);
00138   if (pos >= 0.0)
00139   {
00140     return((uint32_t) (pos*info->state->records+0.5));
00141   }
00142   return(HA_POS_ERROR);
00143 }
00144 
00145 
00146   /* This is a modified version of _mi_search */
00147   /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
00148 
00149 static double _mi_search_pos(register MI_INFO *info,
00150            register MI_KEYDEF *keyinfo,
00151            unsigned char *key, uint32_t key_len, uint32_t nextflag,
00152            register internal::my_off_t pos)
00153 {
00154   int flag;
00155   uint32_t nod_flag, keynr, max_keynr= 0;
00156   bool after_key;
00157   unsigned char *keypos,*buff;
00158   double offset;
00159 
00160   if (pos == HA_OFFSET_ERROR)
00161     return(0.5);
00162 
00163   if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
00164     goto err;
00165   flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
00166             &keypos,info->lastkey, &after_key);
00167   nod_flag=mi_test_if_nod(buff);
00168   keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
00169 
00170   if (flag)
00171   {
00172     if (flag == MI_FOUND_WRONG_KEY)
00173       return(-1);       /* error */
00174     /*
00175       Didn't found match. keypos points at next (bigger) key
00176       Try to find a smaller, better matching key.
00177       Matches keynr + [0-1]
00178     */
00179     if (flag > 0 && ! nod_flag)
00180       offset= 1.0;
00181     else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
00182             _mi_kpos(nod_flag,keypos))) < 0)
00183       return(offset);
00184   }
00185   else
00186   {
00187     /*
00188       Found match. Keypos points at the start of the found key
00189       Matches keynr+1
00190     */
00191     offset=1.0;         /* Matches keynr+1 */
00192     if ((nextflag & SEARCH_FIND) && nod_flag &&
00193   ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
00194    key_len != USE_WHOLE_KEY))
00195     {
00196       /*
00197         There may be identical keys in the tree. Try to match on of those.
00198         Matches keynr + [0-1]
00199       */
00200       if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
00201          _mi_kpos(nod_flag,keypos))) < 0)
00202   return(offset);     /* Read error */
00203     }
00204   }
00205   return((keynr+offset)/(max_keynr+1));
00206 err:
00207   return (-1.0);
00208 }
00209 
00210 
00211   /* Get keynummer of current key and max number of keys in nod */
00212 
00213 static uint32_t _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
00214                       unsigned char *keypos, uint32_t *ret_max_key)
00215 {
00216   uint32_t nod_flag,keynr,max_key;
00217   unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
00218 
00219   end= page+mi_getint(page);
00220   nod_flag=mi_test_if_nod(page);
00221   page+=2+nod_flag;
00222 
00223   if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
00224   {
00225     *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
00226     return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
00227   }
00228 
00229   max_key=keynr=0;
00230   t_buff[0]=0;          /* Safety */
00231   while (page < end)
00232   {
00233     if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
00234       return 0;         /* Error */
00235     max_key++;
00236     if (page == keypos)
00237       keynr=max_key;
00238   }
00239   *ret_max_key=max_key;
00240   return(keynr);
00241 }