← Back to branch summary

~jlukas79/+junk/mysql-server

« back to all changes in this revision

Viewing changes to storage/maria/ma_range.c

manual merge 6.0-main --> 6.0-bka-review

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/maria/ma_range.c
 
1
/* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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 "maria_def.h"
 
22
#include "ma_rt_index.h"
 
23
 
 
24
static ha_rows _ma_record_pos(MARIA_HA *,const uchar *, key_part_map,
 
25
                              enum ha_rkey_function);
 
26
static double _ma_search_pos(MARIA_HA *, MARIA_KEY *, uint32, my_off_t);
 
27
static uint _ma_keynr(MARIA_HA *, MARIA_KEYDEF *, uchar *, uchar *, uint *);
 
28
 
 
29
 
 
30
/**
 
31
   @brief Estimate how many records there is in a given range
 
32
 
 
33
   @param  info            MARIA handler
 
34
   @param  inx             Index to use
 
35
   @param  min_key         Min key. Is = 0 if no min range
 
36
   @param  max_key         Max key. Is = 0 if no max range
 
37
 
 
38
   @note
 
39
     We should ONLY return 0 if there is no rows in range
 
40
 
 
41
   @return Estimated number of rows or error
 
42
     @retval HA_POS_ERROR  error (or we can't estimate number of rows)
 
43
     @retval number        Estimated number of rows
 
44
*/
 
45
 
 
46
ha_rows maria_records_in_range(MARIA_HA *info, int inx, key_range *min_key,
 
47
                            key_range *max_key)
 
48
{
 
49
  ha_rows start_pos,end_pos,res;
 
50
  MARIA_SHARE *share= info->s;
 
51
  MARIA_KEY key;
 
52
  MARIA_KEYDEF *keyinfo;
 
53
  DBUG_ENTER("maria_records_in_range");
 
54
 
 
55
  if ((inx = _ma_check_index(info,inx)) < 0)
 
56
    DBUG_RETURN(HA_POS_ERROR);
 
57
 
 
58
  if (fast_ma_readinfo(info))
 
59
    DBUG_RETURN(HA_POS_ERROR);
 
60
  info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
 
61
  keyinfo= share->keyinfo + inx;
 
62
  if (share->lock_key_trees)
 
63
    rw_rdlock(&keyinfo->root_lock);
 
64
 
 
65
  switch (keyinfo->key_alg) {
 
66
#ifdef HAVE_RTREE_KEYS
 
67
  case HA_KEY_ALG_RTREE:
 
68
  {
 
69
    uchar *key_buff;
 
70
 
 
71
    /*
 
72
      The problem is that the optimizer doesn't support
 
73
      RTree keys properly at the moment.
 
74
      Hope this will be fixed some day.
 
75
      But now NULL in the min_key means that we
 
76
      didn't make the task for the RTree key
 
77
      and expect BTree functionality from it.
 
78
      As it's not able to handle such request
 
79
      we return the error.
 
80
    */
 
81
    if (!min_key)
 
82
    {
 
83
      res= HA_POS_ERROR;
 
84
      break;
 
85
    }
 
86
    key_buff= info->last_key.data + share->base.max_key_length;
 
87
    _ma_pack_key(info, &key, inx, key_buff,
 
88
                 min_key->key, min_key->keypart_map,
 
89
                 (HA_KEYSEG**) 0);
 
90
    res= maria_rtree_estimate(info, &key, maria_read_vec[min_key->flag]);
 
91
    res= res ? res : 1;                       /* Don't return 0 */
 
92
    break;
 
93
  }
 
94
#endif
 
95
  case HA_KEY_ALG_BTREE:
 
96
  default:
 
97
    start_pos= (min_key ?
 
98
                _ma_record_pos(info, min_key->key, min_key->keypart_map,
 
99
                               min_key->flag) :
 
100
                (ha_rows) 0);
 
101
    end_pos=   (max_key ?
 
102
                _ma_record_pos(info, max_key->key, max_key->keypart_map,
 
103
                               max_key->flag) :
 
104
                info->state->records + (ha_rows) 1);
 
105
    res= (end_pos < start_pos ? (ha_rows) 0 :
 
106
          (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
 
107
    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
 
108
      res=HA_POS_ERROR;
 
109
  }
 
110
 
 
111
  if (share->lock_key_trees)
 
112
    rw_unlock(&keyinfo->root_lock);
 
113
  fast_ma_writeinfo(info);
 
114
 
 
115
  /**
 
116
     @todo LOCK
 
117
     If res==0 (no rows), if we need to guarantee repeatability of the search,
 
118
     we will need to set a next-key lock in this statement.
 
119
     Also SELECT COUNT(*)...
 
120
  */
 
121
 
 
122
  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
 
123
  DBUG_RETURN(res);
 
124
}
 
125
 
 
126
 
 
127
        /* Find relative position (in records) for key in index-tree */
 
128
 
 
129
static ha_rows _ma_record_pos(MARIA_HA *info, const uchar *key_data,
 
130
                              key_part_map keypart_map,
 
131
                              enum ha_rkey_function search_flag)
 
132
{
 
133
  uint inx= (uint) info->lastinx;
 
134
  uint32 nextflag;
 
135
  uchar *key_buff;
 
136
  double pos;
 
137
  MARIA_KEY key;
 
138
  DBUG_ENTER("_ma_record_pos");
 
139
  DBUG_PRINT("enter",("search_flag: %d",search_flag));
 
140
  DBUG_ASSERT(keypart_map);
 
141
 
 
142
  key_buff= info->lastkey_buff+info->s->base.max_key_length;
 
143
  _ma_pack_key(info, &key, inx, key_buff, key_data, keypart_map,
 
144
                       (HA_KEYSEG**) 0);
 
145
  DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, &key););
 
146
  nextflag=maria_read_vec[search_flag];
 
147
 
 
148
  /*
 
149
    my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
 
150
    This is set in my_handler.c:ha_key_cmp() in dependence on the
 
151
    compare flags 'nextflag' and the column type.
 
152
 
 
153
    TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
 
154
    condition is skip_end_space= ((nextflag & (SEARCH_FIND |
 
155
    SEARCH_UPDATE)) == SEARCH_FIND).
 
156
 
 
157
    SEARCH_FIND is used for an exact key search. The combination
 
158
    SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
 
159
    operations with a comment like "Not real duplicates", whatever this
 
160
    means. From the condition above we can see that 'skip_end_space' is
 
161
    always false for these operations. The result is that trailing space
 
162
    counts in key comparison and hence, emtpy strings ('', string length
 
163
    zero, but not NULL) compare less that strings starting with control
 
164
    characters and these in turn compare less than strings starting with
 
165
    blanks.
 
166
 
 
167
    When estimating the number of records in a key range, we request an
 
168
    exact search for the minimum key. This translates into a plain
 
169
    SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
 
170
    compare. Empty strings would be expected above control characters.
 
171
    Their keys would not be found because they are located below control
 
172
    characters.
 
173
 
 
174
    This is the reason that we add the SEARCH_UPDATE flag here. It makes
 
175
    the key estimation compare in the same way like key write operations
 
176
    do. Olny so we will find the keys where they have been inserted.
 
177
 
 
178
    Adding the flag unconditionally does not hurt as it is used in the
 
179
    above mentioned condition only. So it can safely be used together
 
180
    with other flags.
 
181
  */
 
182
  pos= _ma_search_pos(info, &key,
 
183
                      nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
 
184
                      info->s->state.key_root[inx]);
 
185
  if (pos >= 0.0)
 
186
  {
 
187
    DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
 
188
    DBUG_RETURN((ulong) (pos*info->state->records+0.5));
 
189
  }
 
190
  DBUG_RETURN(HA_POS_ERROR);
 
191
}
 
192
 
 
193
 
 
194
/**
 
195
  Find offset for key on index page
 
196
 
 
197
  @notes
 
198
   Modified version of _ma_search()
 
199
 
 
200
  @return
 
201
  @retval 0.0 <= x <= 1.0
 
202
*/
 
203
 
 
204
static double _ma_search_pos(MARIA_HA *info, MARIA_KEY *key,
 
205
                             uint32 nextflag, my_off_t pos)
 
206
{
 
207
  int flag;
 
208
  uint nod_flag,keynr,max_keynr;
 
209
  my_bool after_key;
 
210
  uchar *keypos, *buff;
 
211
  double offset;
 
212
  MARIA_KEYDEF *keyinfo= key->keyinfo;
 
213
  DBUG_ENTER("_ma_search_pos");
 
214
  LINT_INIT(max_keynr);
 
215
 
 
216
  if (pos == HA_OFFSET_ERROR)
 
217
    DBUG_RETURN(0.5);
 
218
 
 
219
  if (!(buff= _ma_fetch_keypage(info,keyinfo, pos,
 
220
                                PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS,
 
221
                                info->buff, 1, 0)))
 
222
    goto err;
 
223
  flag= (*keyinfo->bin_search)(key, buff, nextflag, &keypos,
 
224
                               info->lastkey_buff, &after_key);
 
225
  nod_flag=_ma_test_if_nod(info->s, buff);
 
226
  keynr= _ma_keynr(info,keyinfo,buff,keypos,&max_keynr);
 
227
 
 
228
  if (flag)
 
229
  {
 
230
    if (flag == MARIA_FOUND_WRONG_KEY)
 
231
      DBUG_RETURN(-1);                          /* error */
 
232
    /*
 
233
      Didn't found match. keypos points at next (bigger) key
 
234
      Try to find a smaller, better matching key.
 
235
      Matches keynr + [0-1]
 
236
    */
 
237
    if (flag > 0 && ! nod_flag)
 
238
      offset= 1.0;
 
239
    else if ((offset= _ma_search_pos(info, key, nextflag,
 
240
                                     _ma_kpos(nod_flag,keypos))) < 0)
 
241
      DBUG_RETURN(offset);
 
242
  }
 
243
  else
 
244
  {
 
245
    /*
 
246
      Found match. Keypos points at the start of the found key
 
247
      Matches keynr+1
 
248
    */
 
249
    offset=1.0;                                 /* Matches keynr+1 */
 
250
    if ((nextflag & SEARCH_FIND) && nod_flag &&
 
251
        ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
 
252
         (nextflag & (SEARCH_PREFIX | SEARCH_NO_FIND | SEARCH_LAST |
 
253
                      SEARCH_PART_KEY))))
 
254
    {
 
255
      /*
 
256
        There may be identical keys in the tree. Try to match on of those.
 
257
        Matches keynr + [0-1]
 
258
      */
 
259
      if ((offset= _ma_search_pos(info, key, SEARCH_FIND,
 
260
                                  _ma_kpos(nod_flag,keypos))) < 0)
 
261
        DBUG_RETURN(offset);                    /* Read error */
 
262
    }
 
263
  }
 
264
  DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
 
265
                     keynr,offset,max_keynr,nod_flag,flag));
 
266
  DBUG_RETURN((keynr+offset)/(max_keynr+1));
 
267
err:
 
268
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
269
  DBUG_RETURN (-1.0);
 
270
}
 
271
 
 
272
 
 
273
/* Get keynummer of current key and max number of keys in nod */
 
274
 
 
275
static uint _ma_keynr(MARIA_HA *info, register MARIA_KEYDEF *keyinfo,
 
276
                      uchar *page, uchar *keypos, uint *ret_max_key)
 
277
{
 
278
  uint page_flag, nod_flag, used_length, keynr, max_key;
 
279
  uchar t_buff[MARIA_MAX_KEY_BUFF],*end;
 
280
  MARIA_KEY key;
 
281
 
 
282
  page_flag= _ma_get_keypage_flag(info->s, page);
 
283
  _ma_get_used_and_nod_with_flag(info->s, page_flag, page, used_length,
 
284
                                 nod_flag);
 
285
  end= page+ used_length;
 
286
  page+= info->s->keypage_header + nod_flag;
 
287
 
 
288
  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
 
289
      ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
 
290
  {
 
291
    *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
 
292
    return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
 
293
  }
 
294
 
 
295
  max_key=keynr=0;
 
296
  t_buff[0]=0;                                  /* Safety */
 
297
  key.data= t_buff;
 
298
  key.keyinfo= keyinfo;
 
299
 
 
300
  while (page < end)
 
301
  {
 
302
    if (!(page= (*keyinfo->skip_key)(&key, page_flag, nod_flag, page)))
 
303
    {
 
304
      DBUG_ASSERT(0);
 
305
      return 0;                                 /* Error */
 
306
    }
 
307
    max_key++;
 
308
    if (page == keypos)
 
309
      keynr= max_key;
 
310
  }
 
311
  *ret_max_key=max_key;
 
312
  return(keynr);
 
313
}