mi_range.c 9.43 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000-2004, 2006 MySQL AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
6

unknown's avatar
unknown committed
7 8 9 10
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
unknown's avatar
unknown committed
11

unknown's avatar
unknown committed
12 13 14 15 16 17 18 19 20 21
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/*
  Gives a approximated number of how many records there is between two keys.
  Used when optimizing querries.
 */

#include "myisamdef.h"
22
#include "rt_index.h"
unknown's avatar
unknown committed
23 24 25 26 27 28 29 30 31

static ha_rows _mi_record_pos(MI_INFO *info,const byte *key,uint key_len,
			      enum ha_rkey_function search_flag);
static double _mi_search_pos(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,
			     uint key_len,uint nextflag,my_off_t pos);
static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *page,
		      uchar *keypos,uint *ret_max_key);


unknown's avatar
unknown committed
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
/*
  Estimate how many records there is in a given range

  SYNOPSIS
    mi_records_in_range()
    info		MyISAM handler
    inx			Index to use
    min_key		Min key. Is = 0 if no min range
    max_key		Max key. Is = 0 if no max range

  NOTES
    We should ONLY return 0 if there is no rows in range

  RETURN
    HA_POS_ERROR  error (or we can't estimate number of rows)
    number	  Estimated number of rows
*/
  

ha_rows mi_records_in_range(MI_INFO *info, int inx, key_range *min_key,
                            key_range *max_key)
unknown's avatar
unknown committed
53
{
54
  ha_rows start_pos,end_pos,res;
unknown's avatar
unknown committed
55 56 57 58 59
  DBUG_ENTER("mi_records_in_range");

  if ((inx = _mi_check_index(info,inx)) < 0)
    DBUG_RETURN(HA_POS_ERROR);

unknown's avatar
unknown committed
60
  if (fast_mi_readinfo(info))
unknown's avatar
unknown committed
61 62 63 64
    DBUG_RETURN(HA_POS_ERROR);
  info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
  if (info->s->concurrent_insert)
    rw_rdlock(&info->s->key_root_lock[inx]);
65 66

  switch(info->s->keyinfo[inx].key_alg){
67
#ifdef HAVE_RTREE_KEYS
68
  case HA_KEY_ALG_RTREE:
unknown's avatar
unknown committed
69 70 71 72
  {
    uchar * key_buff;
    uint start_key_len;

73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
    /*
      The problem is that the optimizer doesn't support
      RTree keys properly at the moment.
      Hope this will be fixed some day.
      But now NULL in the min_key means that we
      didn't make the task for the RTree key
      and expect BTree functionality from it.
      As it's not able to handle such request
      we return the error.
    */
    if (!min_key)
    {
      res= HA_POS_ERROR;
      break;
    }
unknown's avatar
unknown committed
88 89 90 91 92 93 94 95 96
    key_buff= info->lastkey+info->s->base.max_key_length;
    start_key_len= _mi_pack_key(info,inx, key_buff,
                                (uchar*) min_key->key, min_key->length,
                                (HA_KEYSEG**) 0);
    res= rtree_estimate(info, inx, key_buff, start_key_len,
                        myisam_read_vec[min_key->flag]);
    res= res ? res : 1;                       /* Don't return 0 */
    break;
  }
97
#endif
98 99
  case HA_KEY_ALG_BTREE:
  default:
unknown's avatar
unknown committed
100 101 102 103 104 105 106 107 108 109
    start_pos= (min_key ?
                _mi_record_pos(info, min_key->key, min_key->length, 
                               min_key->flag) :
                (ha_rows) 0);
    end_pos=   (max_key ?
                _mi_record_pos(info, max_key->key, max_key->length,
                               max_key->flag) :
                info->state->records+ (ha_rows) 1);
    res= (end_pos < start_pos ? (ha_rows) 0 :
          (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
110 111 112 113
    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
      res=HA_POS_ERROR;
  }
  
unknown's avatar
unknown committed
114 115
  if (info->s->concurrent_insert)
    rw_unlock(&info->s->key_root_lock[inx]);
unknown's avatar
unknown committed
116
  fast_mi_writeinfo(info);
117 118 119
  
  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
  DBUG_RETURN(res);
unknown's avatar
unknown committed
120 121 122 123 124 125 126 127
}


	/* Find relative position (in records) for key in index-tree */

static ha_rows _mi_record_pos(MI_INFO *info, const byte *key, uint key_len,
			      enum ha_rkey_function search_flag)
{
unknown's avatar
unknown committed
128
  uint inx=(uint) info->lastinx, nextflag;
unknown's avatar
unknown committed
129 130 131 132 133 134 135 136 137 138
  MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
  uchar *key_buff;
  double pos;

  DBUG_ENTER("_mi_record_pos");
  DBUG_PRINT("enter",("search_flag: %d",search_flag));

  if (key_len == 0)
    key_len=USE_WHOLE_KEY;
  key_buff=info->lastkey+info->s->base.max_key_length;
139
  key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key,key_len,
unknown's avatar
unknown committed
140
		       (HA_KEYSEG**) 0);
unknown's avatar
unknown committed
141 142
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
				    (uchar*) key_buff,key_len););
unknown's avatar
unknown committed
143 144 145 146
  nextflag=myisam_read_vec[search_flag];
  if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
    key_len=USE_WHOLE_KEY;

147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
  /*
    my_handler.c:mi_compare_text() has a flag 'skip_end_space'.
    This is set in my_handler.c:ha_key_cmp() in dependence on the
    compare flags 'nextflag' and the column type.

    TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
    condition is skip_end_space= ((nextflag & (SEARCH_FIND |
    SEARCH_UPDATE)) == SEARCH_FIND).

    SEARCH_FIND is used for an exact key search. The combination
    SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
    operations with a comment like "Not real duplicates", whatever this
    means. From the condition above we can see that 'skip_end_space' is
    always false for these operations. The result is that trailing space
    counts in key comparison and hence, emtpy strings ('', string length
    zero, but not NULL) compare less that strings starting with control
    characters and these in turn compare less than strings starting with
    blanks.

    When estimating the number of records in a key range, we request an
    exact search for the minimum key. This translates into a plain
    SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
    compare. Empty strings would be expected above control characters.
    Their keys would not be found because they are located below control
    characters.

    This is the reason that we add the SEARCH_UPDATE flag here. It makes
    the key estimation compare in the same way like key write operations
    do. Olny so we will find the keys where they have been inserted.

    Adding the flag unconditionally does not hurt as it is used in the
    above mentioned condition only. So it can safely be used together
    with other flags.
  */
unknown's avatar
unknown committed
181
  pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
182
		     nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
unknown's avatar
unknown committed
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
		     info->s->state.key_root[inx]);
  if (pos >= 0.0)
  {
    DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
    DBUG_RETURN((ulong) (pos*info->state->records+0.5));
  }
  DBUG_RETURN(HA_POS_ERROR);
}


	/* This is a modified version of _mi_search */
	/* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */

static double _mi_search_pos(register MI_INFO *info,
			     register MI_KEYDEF *keyinfo,
			     uchar *key, uint key_len, uint nextflag,
			     register my_off_t pos)
{
  int flag;
  uint nod_flag,keynr,max_keynr;
  my_bool after_key;
  uchar *keypos,*buff;
  double offset;
  DBUG_ENTER("_mi_search_pos");
207
  LINT_INIT(max_keynr);
unknown's avatar
unknown committed
208 209 210 211

  if (pos == HA_OFFSET_ERROR)
    DBUG_RETURN(0.5);

212
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
unknown's avatar
unknown committed
213 214 215 216 217 218 219 220 221 222 223
    goto err;
  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
			      &keypos,info->lastkey, &after_key);
  nod_flag=mi_test_if_nod(buff);
  keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);

  if (flag)
  {
    if (flag == MI_FOUND_WRONG_KEY)
      DBUG_RETURN(-1);				/* error */
    /*
224 225 226
      Didn't found match. keypos points at next (bigger) key
      Try to find a smaller, better matching key.
      Matches keynr + [0-1]
unknown's avatar
unknown committed
227 228 229 230 231 232 233 234 235 236
    */
    if (flag > 0 && ! nod_flag)
      offset= 1.0;
    else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
				    _mi_kpos(nod_flag,keypos))) < 0)
      DBUG_RETURN(offset);
  }
  else
  {
    /*
237 238
      Found match. Keypos points at the start of the found key
      Matches keynr+1
unknown's avatar
unknown committed
239 240
    */
    offset=1.0;					/* Matches keynr+1 */
unknown's avatar
unknown committed
241
    if ((nextflag & SEARCH_FIND) && nod_flag &&
unknown's avatar
unknown committed
242
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
unknown's avatar
unknown committed
243
	 key_len != USE_WHOLE_KEY))
unknown's avatar
unknown committed
244 245
    {
      /*
246 247
        There may be identical keys in the tree. Try to match on of those.
        Matches keynr + [0-1]
unknown's avatar
unknown committed
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
      */
      if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
				 _mi_kpos(nod_flag,keypos))) < 0)
	DBUG_RETURN(offset);			/* Read error */
    }
  }
  DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
		     keynr,offset,max_keynr,nod_flag,flag));
  DBUG_RETURN((keynr+offset)/(max_keynr+1));
err:
  DBUG_PRINT("exit",("Error: %d",my_errno));
  DBUG_RETURN (-1.0);
}


	/* Get keynummer of current key and max number of keys in nod */

unknown's avatar
unknown committed
265 266
static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                      uchar *keypos, uint *ret_max_key)
unknown's avatar
unknown committed
267 268 269 270 271 272 273 274
{
  uint nod_flag,keynr,max_key;
  uchar t_buff[MI_MAX_KEY_BUFF],*end;

  end= page+mi_getint(page);
  nod_flag=mi_test_if_nod(page);
  page+=2+nod_flag;

unknown's avatar
unknown committed
275
  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
unknown's avatar
unknown committed
276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
  {
    *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
    return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
  }

  max_key=keynr=0;
  t_buff[0]=0;					/* Safety */
  while (page < end)
  {
    if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
      return 0;					/* Error */
    max_key++;
    if (page == keypos)
      keynr=max_key;
  }
  *ret_max_key=max_key;
  return(keynr);
}