Below is the list of changes that have just been committed into a local
6.0 repository of sergefp. When sergefp does a push these changes
will be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html
ChangeSet@stripped, 2008-05-01 23:32:15+04:00, sergefp@stripped +9 -0
ORDER BY ... LIMIT support for Falcon:
- add FalconOrderByLimitHandling code which arranges for Falcon to do
ordered index/range scans when SQL layer has LIMIT and ordering.
include/my_base.h@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +3 -1
ORDER BY ... LIMIT support for Falcon:
- Add HA_EXTRA_ORDERBY_LIMIT, HA_EXTRA_ORDERBY_NO_LIMIT
sql/field.cc@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +2 -1
ORDER BY ... LIMIT support for Falcon:
- add Field::part_of_key_wo_keyread
sql/field.h@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +16 -2
ORDER BY ... LIMIT support for Falcon:
- add Field::part_of_key_wo_keyread
- add comments to other fields
sql/handler.h@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +1 -0
ORDER BY ... LIMIT support for Falcon:
- add HA_CAN_READ_ORDER_IF_LIMIT table flag
sql/sql_bitmap.h@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +33 -26
ORDER BY ... LIMIT support for Falcon:
- add Bitmap<64>::Iterator class
sql/sql_select.cc@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +53 -10
ORDER BY ... LIMIT support for Falcon:
- add FalconOrderByLimitHandling code which tells Falcon to do
ordered index/range scan when the SQL layer relies on ordered index
reads to resolve ORDER BY ... LIMIT clause.
- The fix is not complete in the sense that we don't detect the case
where an unordered index read would also produce the required order,
e.g. for SELECT ... WHERE t.key=10 ORDER BY t.key LIMIT n
sql/table.cc@stripped, 2008-05-01 23:31:57+04:00, sergefp@stripped +1 -0
ORDER BY ... LIMIT support for Falcon:
- add Field::part_of_key_wo_keyread
storage/falcon/ha_falcon.cpp@stripped, 2008-05-01 23:31:58+04:00, sergefp@stripped +30 -3
ORDER BY ... LIMIT support for Falcon:
- add StorageInterface::ordered_index_reads flag and maintain it using
the SQL Layer's directions.
storage/falcon/ha_falcon.h@stripped, 2008-05-01 23:31:58+04:00, sergefp@stripped +2 -0
ORDER BY ... LIMIT support for Falcon:
- add StorageInterface::ordered_index_reads flag and maintain it using
the SQL Layer's directions.
diff -Nrup a/include/my_base.h b/include/my_base.h
--- a/include/my_base.h 2008-04-22 13:19:01 +04:00
+++ b/include/my_base.h 2008-05-01 23:31:57 +04:00
@@ -203,7 +203,9 @@ enum ha_extra_function {
begin and end of a statement.
*/
HA_EXTRA_ATTACH_CHILDREN,
- HA_EXTRA_DETACH_CHILDREN
+ HA_EXTRA_DETACH_CHILDREN,
+ HA_EXTRA_ORDERBY_LIMIT,
+ HA_EXTRA_NO_ORDERBY_LIMIT
};
/* Compatible option, to be deleted in 6.0 */
diff -Nrup a/sql/field.cc b/sql/field.cc
--- a/sql/field.cc 2008-03-27 21:58:37 +03:00
+++ b/sql/field.cc 2008-05-01 23:31:57 +04:00
@@ -1307,7 +1307,8 @@ Field::Field(uchar *ptr_arg,uint32 lengt
table(0), orig_table(0), table_name(0),
field_name(field_name_arg),
key_start(0), part_of_key(0), part_of_key_not_clustered(0),
- part_of_sortkey(0), unireg_check(unireg_check_arg),
+ part_of_sortkey(0), part_of_key_wo_keyread(0),
+ unireg_check(unireg_check_arg),
field_length(length_arg), null_bit(null_bit_arg),
is_created_from_null_item(FALSE)
{
diff -Nrup a/sql/field.h b/sql/field.h
--- a/sql/field.h 2008-03-27 21:58:37 +03:00
+++ b/sql/field.h 2008-05-01 23:31:57 +04:00
@@ -61,9 +61,23 @@ public:
struct st_table *orig_table; // Pointer to original table
const char **table_name, *field_name;
LEX_STRING comment;
- /* Field is part of the following keys */
- key_map key_start, part_of_key, part_of_key_not_clustered;
+ /* Bitmap of indexes that start with this field */
+ key_map key_start;
+ /* Bitmap of indexes allow HA_EXTRA_KEYREAD and cover the entire field */
+ key_map part_of_key;
+ /* Same as above, but not counting the HA_PRIMARY_KEY_IN_READ_INDEX effect */
+ key_map part_of_key_not_clustered;
+ /*
+ Bitmap of indexes that allow HA_READ_ORDER and fully cover this field
+ Note: this is a non-constant characterstic for Falcon, grep for
+ FalconOrderByLimitHandling.
+ */
key_map part_of_sortkey;
+ /*
+ Bitmap of indexes that cover the field, both those that allow
+ HA_EXTRA_KEYREAD and those that don't.
+ */
+ key_map part_of_key_wo_keyread;
/*
We use three additional unireg types for TIMESTAMP to overcome limitation
of current binary format of .frm file. We'd like to be able to support
diff -Nrup a/sql/handler.h b/sql/handler.h
--- a/sql/handler.h 2008-04-14 14:09:57 +04:00
+++ b/sql/handler.h 2008-05-01 23:31:57 +04:00
@@ -184,6 +184,7 @@ typedef Bitmap<HA_MAX_ALTER_FLAGS> HA_AL
#define HA_BINLOG_STMT_CAPABLE (LL(1) << 36)
#define HA_ONLINE_ALTER (LL(1) << 37)
+#define HA_CAN_READ_ORDER_IF_LIMIT (LL(1) << 38)
/*
Set of all binlog flags. Currently only contain the capabilities
diff -Nrup a/sql/sql_bitmap.h b/sql/sql_bitmap.h
--- a/sql/sql_bitmap.h 2008-03-27 20:44:47 +03:00
+++ b/sql/sql_bitmap.h 2008-05-01 23:31:57 +04:00
@@ -152,6 +152,34 @@ public:
}
};
+/* An iterator to quickly walk over bits in unlonglong bitmap. */
+class Table_map_iterator
+{
+ ulonglong bmp;
+ uint no;
+public:
+ Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
+ int next_bit()
+ {
+ static const char last_bit[16]= {32, 0, 1, 0,
+ 2, 0, 1, 0,
+ 3, 0, 1, 0,
+ 2, 0, 1, 0};
+ uint bit;
+ while ((bit= last_bit[bmp & 0xF]) == 32)
+ {
+ no += 4;
+ bmp= bmp >> 4;
+ if (!bmp)
+ return BITMAP_END;
+ }
+ bmp &= ~(1LL << bit);
+ return no + bit;
+ }
+ enum { BITMAP_END= 64 };
+};
+
+
template <> class Bitmap<64>
{
ulonglong map;
@@ -195,35 +223,14 @@ public:
my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
ulonglong to_ulonglong() const { return map; }
-};
-
-/* An iterator to quickly walk over bits in unlonglong bitmap. */
-class Table_map_iterator
-{
- ulonglong bmp;
- uint no;
-public:
- Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
- int next_bit()
+ class Iterator : public Table_map_iterator
{
- static const char last_bit[16]= {32, 0, 1, 0,
- 2, 0, 1, 0,
- 3, 0, 1, 0,
- 2, 0, 1, 0};
- uint bit;
- while ((bit= last_bit[bmp & 0xF]) == 32)
- {
- no += 4;
- bmp= bmp >> 4;
- if (!bmp)
- return BITMAP_END;
- }
- bmp &= ~(1LL << bit);
- return no + bit;
- }
- enum { BITMAP_END= 64 };
+ public:
+ Iterator(Bitmap<64> &bmp) : Table_map_iterator(bmp.map) {}
+ };
};
+
#if 0
diff -Nrup a/sql/sql_select.cc b/sql/sql_select.cc
--- a/sql/sql_select.cc 2008-04-14 14:10:03 +04:00
+++ b/sql/sql_select.cc 2008-05-01 23:31:57 +04:00
@@ -15465,6 +15465,18 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
*/
usable_keys= *map;
+ /*
+ FalconOrderByLimitHandling: specially for Falcon, as requested by Jim:
+ tell Falcon that the query has "LIMIT n" clause and we need ordering.
+ */
+ bool handle_index_flag_change= FALSE;
+ if (table->file->ha_table_flags() & HA_CAN_READ_ORDER_IF_LIMIT &&
+ select_limit != HA_POS_ERROR)
+ {
+ handle_index_flag_change= TRUE;
+ table->file->extra(HA_EXTRA_ORDERBY_LIMIT);
+ }
+
for (ORDER *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
{
Item *item= (*tmp_order->item)->real_item();
@@ -15473,9 +15485,37 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
usable_keys.clear_all();
DBUG_RETURN(0);
}
- usable_keys.intersect(((Item_field*) item)->field->part_of_sortkey);
+ if (handle_index_flag_change)
+ {
+ /*
+ FalconOrderByLimitHandling part 2: find the bitmap of keys that cover
+ @item and support ordered reads.
+ */
+ key_map part_of_sort_key;
+ part_of_sort_key.clear_all();
+ key_map::Iterator it((((Item_field*)item)->field->part_of_key_wo_keyread));
+ uint fieldnr = ((Item_field*)item)->field->field_index;
+ int i;
+ while ((i= it.next_bit()) != key_map::Iterator::BITMAP_END)
+ {
+ KEY_PART_INFO *part_info= table->key_info[i].key_part;
+ for(uint part= 0; part < table->key_info[i].key_parts; part++)
+ {
+ if (part_info[part].field->field_index == fieldnr)
+ {
+ /* Do like open_binary_frm() does with field->part_of_sortkey */
+ if ((table->file->index_flags(i, part, 1)) & HA_READ_ORDER)
+ part_of_sort_key.set_bit(i);
+ break;
+ }
+ }
+ }
+ usable_keys.intersect(part_of_sort_key);
+ }
+ else
+ usable_keys.intersect(((Item_field*) item)->field->part_of_sortkey);
if (usable_keys.is_clear_all())
- DBUG_RETURN(0); // No usable keys
+ goto use_filesort; // No usable keys
}
ref_key= -1;
@@ -15485,7 +15525,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
ref_key= tab->ref.key;
ref_key_parts= tab->ref.key_parts;
if (tab->type == JT_REF_OR_NULL || tab->type == JT_FT)
- DBUG_RETURN(0);
+ goto use_filesort;
}
else if (select && select->quick) // Range found by opt_range
{
@@ -15500,7 +15540,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
- DBUG_RETURN(0);
+ goto use_filesort;
ref_key= select->quick->index;
ref_key_parts= select->quick->used_key_parts;
}
@@ -15544,7 +15584,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
if (create_ref_for_key(tab->join, tab, keyuse,
tab->join->const_table_map))
- DBUG_RETURN(0);
+ goto use_filesort;
}
else
{
@@ -15567,7 +15607,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
tab->join->unit->select_limit_cnt,0,
TRUE) <=
0)
- DBUG_RETURN(0);
+ goto use_filesort;
}
ref_key= new_ref_key;
}
@@ -15614,7 +15654,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
index order and not using join cache
*/
if (tab->type == JT_ALL && tab->join->tables > tab->join->const_tables + 1)
- DBUG_RETURN(0);
+ goto use_filesort;
keys= *table->file->keys_to_use_for_scanning();
keys.merge(table->covering_keys);
@@ -15808,7 +15848,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
order_direction= best_key_direction;
}
else
- DBUG_RETURN(0);
+ goto use_filesort;
}
check_reverse_order:
@@ -15832,7 +15872,7 @@ check_reverse_order:
{
tab->limit= 0;
select->quick= save_quick;
- DBUG_RETURN(0); // Use filesort
+ goto use_filesort; // Use filesort
}
/* ORDER BY range_key DESC */
@@ -15843,7 +15883,7 @@ check_reverse_order:
delete tmp;
select->quick= save_quick;
tab->limit= 0;
- DBUG_RETURN(0); // Reverse sort not supported
+ goto use_filesort; // Reverse sort not supported
}
select->quick=tmp;
}
@@ -15864,6 +15904,9 @@ check_reverse_order:
else if (select && select->quick)
select->quick->sorted= 1;
DBUG_RETURN(1);
+use_filesort:
+ table->file->extra(HA_EXTRA_NO_ORDERBY_LIMIT);
+ DBUG_RETURN(0);
}
diff -Nrup a/sql/table.cc b/sql/table.cc
--- a/sql/table.cc 2008-04-16 11:53:14 +04:00
+++ b/sql/table.cc 2008-05-01 23:31:57 +04:00
@@ -1524,6 +1524,7 @@ static int open_binary_frm(THD *thd, TAB
}
if (handler_file->index_flags(key, i, 1) & HA_READ_ORDER)
field->part_of_sortkey.set_bit(key);
+ field->part_of_key_wo_keyread.set_bit(key);
}
if (!(key_part->key_part_flag & HA_REVERSE_SORT) &&
usable_parts == i)
diff -Nrup a/storage/falcon/ha_falcon.cpp b/storage/falcon/ha_falcon.cpp
--- a/storage/falcon/ha_falcon.cpp 2008-04-25 09:54:48 +04:00
+++ b/storage/falcon/ha_falcon.cpp 2008-05-01 23:31:58 +04:00
@@ -109,7 +109,8 @@ static const ulonglong default_table_fla
| HA_CAN_GEOMETRY
//| HA_AUTO_PART_KEY
| HA_ONLINE_ALTER
- | HA_BINLOG_ROW_CAPABLE);
+ | HA_BINLOG_ROW_CAPABLE
+ | HA_CAN_READ_ORDER_IF_LIMIT);
static struct st_mysql_show_var falconStatus[] =
{
@@ -383,7 +384,7 @@ typedef longlong dec2;
//////////////////////////////////////////////////////////////////////
StorageInterface::StorageInterface(handlerton *hton, st_table_share *table_arg)
- : handler(hton, table_arg)
+ : handler(hton, table_arg), ordered_index_reads(false)
{
ref_length = sizeof(lastRecord);
stats.records = 1000;
@@ -735,7 +736,8 @@ ulonglong StorageInterface::table_flags(
ulong StorageInterface::index_flags(uint idx, uint part, bool all_parts) const
{
DBUG_ENTER("StorageInterface::index_flags");
- DBUG_RETURN(HA_READ_RANGE | HA_KEY_SCAN_NOT_ROR);
+ DBUG_RETURN(HA_READ_RANGE | HA_KEY_SCAN_NOT_ROR |
+ ordered_index_reads ? HA_READ_ORDER : 0);
}
@@ -2737,6 +2739,31 @@ void StorageInterface::decodeRecord(ucha
int StorageInterface::extra(ha_extra_function operation)
{
DBUG_ENTER("StorageInterface::extra");
+ if (operation == HA_EXTRA_ORDERBY_LIMIT)
+ {
+ /*
+ SQL Layer informs us that it is considering an ORDER BY .. LIMIT
+ query. It's time we could
+ 1. start returning HA_READ_ORDER flag from index_flags() calls,
+ which will make the SQL layer consider using indexes to
+ satisfy ORDER BY ... LIMIT.
+ 2. If doing #1, every index/range scan must return records in
+ index order.
+ */
+ fprintf(stderr, "ha_falcon->extra(HA_EXTRA_ORDERBY_LIMIT)\n");
+ ordered_index_reads= TRUE;
+ }
+ if (operation == HA_EXTRA_NO_ORDERBY_LIMIT)
+ {
+ /*
+ SQL Layer figured it won't be able to use index to resolve the
+ ORDER BY ... LIMIT. This could happen for a number of reasons,
+ but the result is that we don't have to return records in index
+ order.
+ */
+ fprintf(stderr, "ha_falcon->extra(HA_EXTRA_NO_ORDERBY_LIMIT)\n");
+ ordered_index_reads= FALSE;
+ }
DBUG_RETURN(0);
}
diff -Nrup a/storage/falcon/ha_falcon.h b/storage/falcon/ha_falcon.h
--- a/storage/falcon/ha_falcon.h 2008-04-22 23:46:08 +04:00
+++ b/storage/falcon/ha_falcon.h 2008-05-01 23:31:58 +04:00
@@ -96,6 +96,7 @@ public:
virtual int optimize(THD* thd, HA_CHECK_OPT* check_opt);
virtual int check(THD* thd, HA_CHECK_OPT* check_opt);
virtual int repair(THD* thd, HA_CHECK_OPT* check_opt);
+ virtual int reset() { ordered_index_reads= false; return 0; }
virtual int check_if_supported_alter(TABLE *altered_table, HA_CREATE_INFO *create_info, HA_ALTER_FLAGS *alter_flags, uint table_changes);
virtual int alter_table_phase1(THD* thd, TABLE* altered_table, HA_CREATE_INFO* create_info, HA_ALTER_INFO* alter_info, HA_ALTER_FLAGS* alter_flags);
@@ -189,6 +190,7 @@ public:
key_range endKey;
uint64 insertCount;
ulonglong tableFlags;
+ bool ordered_index_reads;
};
class NfsPluginHandler
