mi_range.c 7.01 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 33 34 35 36 37 38 39 40 41 42

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);


	/* If start_key = 0 assume read from start */
	/* If end_key = 0 assume read to end */
	/* Returns HA_POS_ERROR on error */

ha_rows mi_records_in_range(MI_INFO *info, int inx, const byte *start_key,
			    uint start_key_len,
			    enum ha_rkey_function start_search_flag,
			    const byte *end_key, uint end_key_len,
			    enum ha_rkey_function end_search_flag)
{
43
  ha_rows start_pos,end_pos,res;
unknown's avatar
unknown committed
44 45 46 47 48
  DBUG_ENTER("mi_records_in_range");

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

unknown's avatar
unknown committed
49
  if (fast_mi_readinfo(info))
unknown's avatar
unknown committed
50 51 52 53
    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]);
54 55 56 57 58 59 60 61

  switch(info->s->keyinfo[inx].key_alg){
  case HA_KEY_ALG_RTREE:
    {
      uchar * key_buff;
      if (start_key_len == 0)
        start_key_len=USE_WHOLE_KEY;
      key_buff=info->lastkey+info->s->base.max_key_length;
unknown's avatar
unknown committed
62 63
      start_key_len= _mi_pack_key(info,inx,key_buff,(uchar*) start_key,
				  start_key_len, (HA_KEYSEG**) 0);
64 65 66 67 68 69 70
      res=rtree_estimate(info, inx, key_buff, start_key_len, myisam_read_vec[start_search_flag]);
      res=res?res:1;
      break;
    }
  case HA_KEY_ALG_BTREE:
  default:
    start_pos= (start_key ?
unknown's avatar
unknown committed
71 72
	      _mi_record_pos(info,start_key,start_key_len,start_search_flag) :
	      (ha_rows) 0);
73
    end_pos=   (end_key ?
unknown's avatar
unknown committed
74 75
	      _mi_record_pos(info,end_key,end_key_len,end_search_flag) :
	      info->state->records+ (ha_rows) 1);
76 77 78 79 80 81
    res=end_pos < start_pos ? (ha_rows) 0 :
	      (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos);
    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
      res=HA_POS_ERROR;
  }
  
unknown's avatar
unknown committed
82 83
  if (info->s->concurrent_insert)
    rw_unlock(&info->s->key_root_lock[inx]);
unknown's avatar
unknown committed
84
  fast_mi_writeinfo(info);
85 86 87
  
  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
  DBUG_RETURN(res);
unknown's avatar
unknown committed
88 89 90 91 92 93 94 95
}


	/* 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
96
  uint inx=(uint) info->lastinx, nextflag;
unknown's avatar
unknown committed
97 98 99 100 101 102 103 104 105 106
  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;
107
  key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key,key_len,
unknown's avatar
unknown committed
108
		       (HA_KEYSEG**) 0);
unknown's avatar
unknown committed
109 110
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
				    (uchar*) key_buff,key_len););
unknown's avatar
unknown committed
111 112 113 114
  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
115
  pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
unknown's avatar
unknown committed
116
		     nextflag | SEARCH_SAVE_BUFF,
unknown's avatar
unknown committed
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
		     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);

145
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
unknown's avatar
unknown committed
146 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
    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
174
    if ((nextflag & SEARCH_FIND) && nod_flag &&
unknown's avatar
unknown committed
175
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
unknown's avatar
unknown committed
176
	 key_len != USE_WHOLE_KEY))
unknown's avatar
unknown committed
177 178 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 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
    {
      /*
      ** 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);
}