mi_range.c 7.81 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4 5 6
   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
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
unknown's avatar
unknown committed
7

unknown's avatar
unknown committed
8 9 10 11
   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
12

unknown's avatar
unknown committed
13 14 15 16 17 18 19 20 21 22
   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"
23
#include "rt_index.h"
unknown's avatar
unknown committed
24 25 26 27 28 29 30 31 32

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
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
/*
  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
54
{
55
  ha_rows start_pos,end_pos,res;
unknown's avatar
unknown committed
56 57 58 59 60
  DBUG_ENTER("mi_records_in_range");

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

unknown's avatar
unknown committed
61
  if (fast_mi_readinfo(info))
unknown's avatar
unknown committed
62 63 64 65
    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]);
66 67

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

74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
    /*
      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
89 90 91 92 93 94 95 96 97
    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;
  }
98
#endif
99 100
  case HA_KEY_ALG_BTREE:
  default:
unknown's avatar
unknown committed
101 102 103 104 105 106 107 108 109 110
    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));
111 112 113 114
    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
      res=HA_POS_ERROR;
  }
  
unknown's avatar
unknown committed
115 116
  if (info->s->concurrent_insert)
    rw_unlock(&info->s->key_root_lock[inx]);
unknown's avatar
unknown committed
117
  fast_mi_writeinfo(info);
118 119 120
  
  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
  DBUG_RETURN(res);
unknown's avatar
unknown committed
121 122 123 124 125 126 127 128
}


	/* 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
129
  uint inx=(uint) info->lastinx, nextflag;
unknown's avatar
unknown committed
130 131 132 133 134 135 136 137 138 139
  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;
140
  key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key,key_len,
unknown's avatar
unknown committed
141
		       (HA_KEYSEG**) 0);
unknown's avatar
unknown committed
142 143
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
				    (uchar*) key_buff,key_len););
unknown's avatar
unknown committed
144 145 146 147
  nextflag=myisam_read_vec[search_flag];
  if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
    key_len=USE_WHOLE_KEY;

unknown's avatar
unknown committed
148
  pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
unknown's avatar
unknown committed
149
		     nextflag | SEARCH_SAVE_BUFF,
unknown's avatar
unknown committed
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
		     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");

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

178
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
unknown's avatar
unknown committed
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
    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 */
    /*
    ** Didn't found match. keypos points at next (bigger) key
    *  Try to find a smaller, better matching key.
    ** Matches keynr + [0-1]
    */
    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
  {
    /*
    ** Found match. Keypos points at the start of the found key
    ** Matches keynr+1
    */
    offset=1.0;					/* Matches keynr+1 */
unknown's avatar
unknown committed
207
    if ((nextflag & SEARCH_FIND) && nod_flag &&
unknown's avatar
unknown committed
208
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
unknown's avatar
unknown committed
209
	 key_len != USE_WHOLE_KEY))
unknown's avatar
unknown committed
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
    {
      /*
      ** There may be identical keys in the tree. Try to match on of those.
      ** Matches keynr + [0-1]
      */
      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 */

static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page, uchar *keypos, uint *ret_max_key)
{
  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;

  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY| HA_BINARY_PACK_KEY)))
  {
    *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);
}