From f63352d37b3ffe7b4e420ee84830e18c45a9cf2c Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 13 May 2004 01:38:40 +0400 Subject: This is first cset for WL#1394 "Optimize index merge when all involved index ranges include only values with equal keys" The main idea is to exploit the fact that key scans for "key=const" return ordered sequences of rowids. include/my_base.h: Added HA_EXTRA_KEYREAD_PRESERVE_FIELDS flag include/my_bitmap.h: Added a couple of utility functions include/my_sys.h: Added my_conunt_bits_ushort function innobase/include/row0mysql.h: Added support for HA_EXTRA_KEYREAD_PRESERVE_FIELDS innobase/row/row0sel.c: Added support for HA_EXTRA_KEYREAD_PRESERVE_FIELDS mysys/my_bit.c: Added my_count_bits_ushort function mysys/my_bitmap.c: Added a couple of utility functions sql/ha_berkeley.cc: Added cmp_ref rowid comparison function. sql/ha_berkeley.h: Added cmp_ref rowid comparison function. sql/ha_heap.h: Added cmp_ref rowid comparison function. sql/ha_innodb.cc: Added cmp_ref rowid comparison function and support from HA_EXTRA_KEYREAD_PRESERVE_FIELDS sql/ha_innodb.h: Added cmp_ref rowid comparison function. sql/handler.h: Added cmp_ref rowid comparison function. sql/opt_range.cc: Added QUICK_ROR_{INTERSECT,UNION}_SELECT classes and related optimizer code sql/opt_range.h: Added QUICK_ROR_{INTERSECT,UNION}_SELECT classes sql/sql_delete.cc: Changed to use new ROWID comparison function also always call quick->reset() for quick selects sql/sql_select.cc: Account for new quick select types sql/sql_select.h: New, proper rowid ordering/comparison function to be used with Unique class etc. sql/sql_test.cc: Account for new quick select types sql/sql_update.cc: Account for new quick select types --- mysys/my_bitmap.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) (limited to 'mysys/my_bitmap.c') diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index da16457c299..3c4caa413a9 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -330,3 +330,59 @@ void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2) bitmap_unlock(map); } + +/* + Get number of set bits in the bitmap +*/ +uint bitmap_bits_set(const MY_BITMAP *map) +{ + uchar *m= map->bitmap, + *end= map->bitmap+map->bitmap_size; + uint res= 0; + + DBUG_ASSERT(map->bitmap); + + bitmap_lock((MY_BITMAP *)map); + while (m < end) + { + res+= my_count_bits_ushort(*m++); + } + + bitmap_unlock((MY_BITMAP *)map); + return res; +} + + +/* + Return number of first zero bit or MY_BIT_NONE if all bits are set. +*/ + +uint bitmap_get_first(const MY_BITMAP *map) +{ + uchar *bitmap=map->bitmap; + uint bit_found = MY_BIT_NONE; + uint bitmap_size=map->bitmap_size*8; + uint i; + + DBUG_ASSERT(map->bitmap); + bitmap_lock((MY_BITMAP *)map); + for (i=0; i < bitmap_size ; i++, bitmap++) + { + if (*bitmap != 0xff) + { /* Found slot with free bit */ + uint b; + for (b=0; ; b++) + { + if (!(*bitmap & (1 << b))) + { + bit_found = (i*8)+b; + break; + } + } + break; /* Found bit */ + } + } + bitmap_unlock((MY_BITMAP *)map); + return bit_found; +} + -- cgit v1.2.1 From 2da9c631e27ee83bade4bd0ee082d94c51c751aa Mon Sep 17 00:00:00 2001 From: unknown Date: Sat, 29 May 2004 02:04:01 +0400 Subject: * New index_merge EXPLAIN output format * Fixed a problem with wrong query results for partially covering keys in ROR-index_merge * ROR-intersection retrieval plan choice algorithm now uses less disk IO - and properly processes clustered PK range scans * Fixed several minor range optimizer problems * Added more comments * Code cleanup mysql-test/r/index_merge.result: New index_merge EXPLAIN output format changes mysql-test/r/index_merge_innodb.result: New index_merge EXPLAIN output format changes mysql-test/r/index_merge_ror.result: New index_merge EXPLAIN output format changes Added test for scans on keys that cover fields partially Fixed a minor ROR optimizer problem mysql-test/r/index_merge_ror_cpk.result: More tests added mysql-test/t/index_merge_ror.test: New index_merge EXPLAIN output format changes Added test for scans on keys that cover fields partially Fixed a minor ROR optimizer problem mysql-test/t/index_merge_ror_cpk.test: More tests added mysys/my_bitmap.c: Comments added, code cleanup sql/opt_range.cc: Comments added, code cleanup Numerous fixes, see changeset description sql/opt_range.h: Comments added, code cleanup New index_merge EXPLAIN output format related changes sql/sql_select.cc: Comments added, code cleanup New index_merge EXPLAIN output --- mysys/my_bitmap.c | 22 ++++++++++++++++------ 1 file changed, 16 insertions(+), 6 deletions(-) (limited to 'mysys/my_bitmap.c') diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index 3c4caa413a9..a6a37fd5441 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -28,6 +28,9 @@ * when both arguments are bitmaps, they must be of the same size * bitmap_intersect() is an exception :) (for for Bitmap::intersect(ulonglong map2buff)) + + If THREAD is defined all bitmap operations except bitmap_init/bitmap_free + are thread-safe. TODO: Make assembler THREAD safe versions of these using test-and-set instructions @@ -332,29 +335,36 @@ void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2) /* - Get number of set bits in the bitmap + SYNOPSIS + bitmap_bits_set() + map + RETURN + Number of set bits in the bitmap. */ + uint bitmap_bits_set(const MY_BITMAP *map) { - uchar *m= map->bitmap, - *end= map->bitmap+map->bitmap_size; + uchar *m= map->bitmap; + uchar *end= m + map->bitmap_size; uint res= 0; DBUG_ASSERT(map->bitmap); - bitmap_lock((MY_BITMAP *)map); while (m < end) { res+= my_count_bits_ushort(*m++); } - bitmap_unlock((MY_BITMAP *)map); return res; } /* - Return number of first zero bit or MY_BIT_NONE if all bits are set. + SYNOPSIS + bitmap_get_first() + map + RETURN + Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set. */ uint bitmap_get_first(const MY_BITMAP *map) -- cgit v1.2.1