#At file:///home/lsoares/Workspace/bzr/work/features/wl5597/mysql-next-mr/ based on revid:luis.soares@stripped
3209 Luis Soares 2010-11-22
WL#5597
Work-in-progress.
Improvements in this cset:
- fixing a couple of test cases that failed.
- improved and documented (doxygen) hash interface.
- better handling for hashing collisions.
modified:
sql/log_event.cc
sql/rpl_utility.cc
sql/rpl_utility.h
=== modified file 'sql/log_event.cc'
--- a/sql/log_event.cc 2010-11-19 22:44:52 +0000
+++ b/sql/log_event.cc 2010-11-22 02:11:25 +0000
@@ -8234,6 +8234,7 @@ int Rows_log_event::do_hash_scan_and_upd
const uchar *bi_ends= NULL;
const uchar *ai_start= NULL;
const uchar *ai_ends= NULL;
+ HASH_ROW_POS_ENTRY* entry;
DBUG_ENTER("Rows_log_event::do_hash_scan_and_update");
@@ -8263,11 +8264,13 @@ int Rows_log_event::do_hash_scan_and_upd
/* move BI to index 0 */
memcpy(m_table->record[0], m_table->record[1], m_table->s->reclength);
-
- m_hash.add_row(m_table, &m_cols,
- bi_start, bi_ends,
- ai_start, ai_ends);
-
+
+ /* create an entry to add to the hash table */
+ entry= m_hash.make_entry(bi_start, bi_ends, ai_start, ai_ends);
+
+ /* add it to the hash table */
+ m_hash.put(m_table, &m_cols, entry);
+
/**
Last row hashed. We are handling the last (pair of) row(s). So
now we do the table scan and match against the entries in the hash
@@ -8288,7 +8291,10 @@ int Rows_log_event::do_hash_scan_and_upd
goto err;
}
- /* Continue until we find the right record or reached the end of the table */
+ /*
+ Scan the table only once and compare against entries in hash.
+ When a match is found, apply the changes.
+ */
do
{
/* get the first record from the table */
@@ -8298,12 +8304,40 @@ int Rows_log_event::do_hash_scan_and_upd
switch (error) {
case 0:
{
- m_hash.search_and_remove_row(table, &m_cols, &bi_start, &bi_ends, &ai_start, &ai_ends);
+ entry= NULL;
+ m_hash.get(table, &m_cols, &entry);
store_record(table, record[1]);
- if (bi_start != NULL)
+ /**
+ If there are collisions we need to be sure that this is
+ indeed the record we want. Loop through all records for
+ the given key and explicitly compare them against the
+ record we got from the storage engine.
+ */
+ while(entry)
{
- /* At this point, both table->record[0] and
+ m_curr_row= entry->bi_start;
+ m_curr_row_end= entry->bi_ends;
+
+ if ((error= unpack_current_row(rli, &m_cols)))
+ goto close_table;
+
+ if (record_compare(m_table, &m_cols))
+ m_hash.next(&entry);
+ else
+ break; // we found a match
+ }
+
+ /**
+ We found the entry we needed, just apply the changes.
+ */
+ if (entry)
+ {
+ // just to be safe, copy the record from the SE to table->record[0]
+ memcpy(table->record[0], table->record[1], table->s->reclength);
+
+ /**
+ At this point, both table->record[0] and
table->record[1] have the SE row that matched the one
in the hash table.
@@ -8313,10 +8347,12 @@ int Rows_log_event::do_hash_scan_and_upd
unpacked correctly to table->record[0] in UPDATE
implementation of do_exec_row().
*/
+ m_curr_row= entry->bi_start;
+ m_curr_row_end= entry->bi_ends;
- m_curr_row= bi_start;
- m_curr_row_end= bi_ends;
-
+ /* we don't need this entry anymore, just delete it */
+ m_hash.del(entry);
+
if ((error= do_apply_row(rli)))
{
if (handle_idempotent_errors(rli, &error) || error)
@@ -8347,7 +8383,8 @@ int Rows_log_event::do_hash_scan_and_upd
(!error || (error == HA_ERR_RECORD_DELETED)));
close_table:
- m_table->file->print_error(error, MYF(0));
+ if (error)
+ m_table->file->print_error(error, MYF(0));
m_table->file->ha_rnd_end();
}
=== modified file 'sql/rpl_utility.cc'
--- a/sql/rpl_utility.cc 2010-11-19 23:00:43 +0000
+++ b/sql/rpl_utility.cc 2010-11-22 02:11:25 +0000
@@ -1062,27 +1062,90 @@ table_def::~table_def()
Utility methods for handling row based operations.
*/
-static uchar * hash_slave_rows_get_key(const uchar *record,
- size_t *length,
- my_bool not_used __attribute__((unused)))
+/**
+
+ Internal structure that acts as a preamble for HASH_ROW_POS_ENTRY
+ in memory structure. Allocation in make_entry is done as follows:
+
+ preamble_ptr= malloc (sizeof(preamble)+sizeof(entry));
+ entry_ptr= preamble_ptr+1;
+
+ preamble_ptr -----> |-------------------------|
+ | hash_slave_row_preamble |
+ | - key |
+ | - length |
+ | - state |
+ entry_ptr -----> |-------------------------|
+ | HASH_ROW_POS_ENTRY |
+ | - bi_start |
+ | - bi_ends |
+ | - ai_start |
+ | - ai_ends |
+ |-------------------------|
+
+
+ return entry_ptr;
+
+ When iterating over an entry with multiple records, we can just use
+ pointer arithmetic to retrieve the preamble pointer. This way we
+ hide from the hash table user the gory details of key bookeeping
+ for the hash (including collision handling).
+
+*/
+typedef struct hash_row_pos_preamble
+{
+
+ /**
+ The pointer to the hash table key.
+ */
+ uchar* key;
+
+ /**
+ Length of the key.
+ */
+ uint length;
+
+ /**
+ The actual key.
+ */
+ my_hash_value_type hash_value;
+
+ /**
+ The search state used to iterate over multiple entries for a
+ given key.
+ */
+ HASH_SEARCH_STATE search_state;
+
+ /**
+ Wether this search_state is usable or not.
+ */
+ bool is_search_state_inited;
+
+} HASH_ROW_POS_PREAMBLE;
+
+
+static uchar*
+hash_slave_rows_get_key(const uchar *record,
+ size_t *length,
+ my_bool not_used __attribute__((unused)))
{
DBUG_ENTER("get_key");
- hash_slave_rows_entry *entry=(hash_slave_rows_entry *) record;
- *length= entry->length;
+ HASH_ROW_POS_PREAMBLE *preamble=(HASH_ROW_POS_PREAMBLE *) record;
+ *length= preamble->length;
- DBUG_RETURN((uchar*) entry->key);
+ DBUG_RETURN((uchar*) preamble->key);
}
static void
-hash_slave_rows_free_entry(hash_slave_rows_entry *entry)
+hash_slave_rows_free_entry(HASH_ROW_POS_PREAMBLE *preamble)
{
DBUG_ENTER("free_entry");
- my_free(entry);
+ if (preamble)
+ my_free(preamble);
DBUG_VOID_RETURN;
}
-
bool Hash_slave_rows::is_empty(void)
{
return (m_hash.records == 0);
@@ -1096,7 +1159,7 @@ bool Hash_slave_rows::init(void)
{
my_hash_init(&m_hash,
&my_charset_bin, /* the charater set information */
- 16 /* FIXME */, /* growth size */
+ 16 /* TODO */, /* growth size */
0, /* key offset */
0, /* key length */
hash_slave_rows_get_key, /* get function pointer */
@@ -1104,7 +1167,6 @@ bool Hash_slave_rows::init(void)
MYF(0)); /* flags */
return 0;
-
}
bool Hash_slave_rows::deinit(void)
@@ -1120,71 +1182,160 @@ int Hash_slave_rows::size()
return m_hash.records;
}
+HASH_ROW_POS_ENTRY* Hash_slave_rows::make_entry(const uchar* bi_start, const uchar* bi_ends,
+ const uchar* ai_start, const uchar* ai_ends)
+{
+ DBUG_ENTER("Hash_slave_rows::make_entry");
+
+ size_t size= sizeof(struct hash_row_pos_preamble) +
+ sizeof(struct hash_row_pos_entry);
+
+ HASH_ROW_POS_PREAMBLE *preamble=
+ (HASH_ROW_POS_PREAMBLE*) my_malloc(size, MYF(0));
-bool
-Hash_slave_rows::search_and_remove_row(TABLE *table,
- MY_BITMAP *cols,
- const uchar **bi_start, const uchar **bi_ends,
- const uchar **ai_start, const uchar **ai_ends)
+ if (!preamble)
+ DBUG_RETURN(NULL);
+
+ HASH_ROW_POS_ENTRY* entry= (HASH_ROW_POS_ENTRY*) (preamble+1);
+
+ /**
+ Filling in the preamble.
+ */
+ preamble->key= (uchar*)&preamble->hash_value;
+ preamble->length= sizeof(my_hash_value_type);
+ preamble->search_state= -1;
+ preamble->hash_value= -1;
+ preamble->is_search_state_inited= false;
+
+ /**
+ Filling in the values.
+ */
+ entry->bi_start= (const uchar *) bi_start;
+ entry->bi_ends= (const uchar *) bi_ends;
+ entry->ai_start= (const uchar *) ai_start;
+ entry->ai_ends= (const uchar *) ai_ends;
+
+ DBUG_PRINT("debug", ("Added record to hash with key=%u", preamble->hash_value));
+
+ /**
+ Return the pointer to the entry. The caller should not
+ be exposed to the internal preamble.
+ */
+ DBUG_RETURN(entry);
+}
+
+bool
+Hash_slave_rows::put(TABLE *table,
+ MY_BITMAP *cols,
+ HASH_ROW_POS_ENTRY* entry)
{
- DBUG_ENTER("Hash_slave_rows::search_row");
+ DBUG_ENTER("Hash_slave_rows::put");
+
+ HASH_ROW_POS_PREAMBLE* preamble= ((HASH_ROW_POS_PREAMBLE*)entry)-1;
+
+ /**
+ Skip blobs from key calculation.
+ Handle X bits.
+ Handle nulled fields.
+ Handled fields not signaled.
+ */
+ make_hash_key(table, cols, &preamble->hash_value);
+ my_hash_insert(&m_hash, (uchar *) preamble);
+ DBUG_PRINT("debug", ("Added record to hash with key=%u", preamble->hash_value));
+ DBUG_RETURN(false);
+}
+bool
+Hash_slave_rows::get(TABLE *table,
+ MY_BITMAP *cols,
+ HASH_ROW_POS_ENTRY** entry)
+{
+ DBUG_ENTER("Hash_slave_rows::get");
HASH_SEARCH_STATE state;
- my_hash_value_type se_key; /* storage engine record based row key */
- *bi_start= *bi_ends= *ai_start= *ai_ends= NULL;
+ HASH_ROW_POS_PREAMBLE* preamble;
+ my_hash_value_type key;
- make_hash_key(table, cols, &se_key);
+ make_hash_key(table, cols, &key);
+
+ DBUG_PRINT("debug", ("Looking for record with key=%u in the hash.", key));
+
+ preamble= (HASH_ROW_POS_PREAMBLE*) my_hash_first(&m_hash,
+ (const uchar*) &key,
+ sizeof(my_hash_value_type),
+ &state);
+ if (preamble)
+ {
+ DBUG_PRINT("debug", ("Found record with key=%u in the hash.", key));
- DBUG_PRINT("debug", ("Looking for record with key=%u in the hash.", se_key));
-
- /**
- This is only needed because records are hashed without blobs, so
- we may have false positives.
- */
- hash_slave_rows_entry *entry= (hash_slave_rows_entry *) my_hash_first(&m_hash,
- (const uchar*) &se_key,
- sizeof(my_hash_value_type),
- &state);
- while (entry)
- {
- const uchar* key= (const uchar*) &entry->key;
-
/**
- unpack again the full BI record to table->record[0]. Now,
- both table->record[0] and table->record[1] should have
- approximately the same contents (except maybe for blobs
- - thence we need to do full comparison below).
+ Save the search state in case we need to go through entries for
+ the given key.
*/
-/* event->m_curr_row= entry->m_curr_row;
- if (!(error= event->unpack_current_row(rli, &cols)))
- {*/
- /*
- compare the row_entry with row taking into account
- blobs, if there is any. If there is a match do the
- operation and remove the entry from the hash table.
- */
-/* if (!record_compare(table, cols))
- {*/
- *bi_start= entry->bi_start;
- *bi_ends= entry->bi_ends;
- *ai_start= entry->ai_start;
- *ai_ends= entry->ai_ends;
-
- my_hash_delete(&m_hash, (uchar *)entry);
- DBUG_RETURN(0);
-/* }
- }
- else
- DBUG_RETURN(error);*/
+ preamble->search_state= state;
+ preamble->is_search_state_inited= true;
+
+ *entry= (HASH_ROW_POS_ENTRY*) (preamble+1);
+ }
+ else
+ *entry= NULL;
- /* Next row for the loop... */
- entry= (hash_slave_rows_entry *)my_hash_next(&m_hash,
- key,
- sizeof(my_hash_value_type),
- &state);
+ DBUG_RETURN(false);
+}
+
+bool Hash_slave_rows::next(HASH_ROW_POS_ENTRY** entry)
+{
+ DBUG_ENTER("Hash_slave_rows::next");
+
+ if (*entry)
+ {
+ HASH_ROW_POS_PREAMBLE* preamble=
+ ((HASH_ROW_POS_PREAMBLE*) *entry) - 1;
+
+ if (preamble->is_search_state_inited)
+ {
+ my_hash_value_type key= preamble->hash_value;
+ HASH_SEARCH_STATE state= preamble->search_state;
+ preamble->search_state= -1;
+ preamble->is_search_state_inited= false;
+
+ DBUG_PRINT("debug", ("Looking for record with key=%u in the hash (next).", key));
+
+ preamble= (HASH_ROW_POS_PREAMBLE*) my_hash_next(&m_hash,
+ (const uchar*) &key,
+ sizeof(my_hash_value_type),
+ &state);
+ if (preamble)
+ {
+ DBUG_PRINT("debug", ("Found record with key=%u in the hash (next).", key));
+ preamble->search_state= state;
+ preamble->is_search_state_inited= true;
+ *entry= (HASH_ROW_POS_ENTRY*) (preamble+1);
+ }
+ else
+ *entry= NULL;
+ }
+ else
+ DBUG_RETURN(true);
}
+ else
+ DBUG_RETURN(true);
- DBUG_RETURN(0);
+ DBUG_RETURN(false);
+}
+
+bool
+Hash_slave_rows::del(HASH_ROW_POS_ENTRY* entry)
+{
+ DBUG_ENTER("Hash_slave_rows::del");
+ if (entry)
+ {
+ HASH_ROW_POS_PREAMBLE* preamble=
+ ((HASH_ROW_POS_PREAMBLE*)entry)-1;
+ my_hash_delete(&m_hash, (uchar *) preamble);
+ }
+ else
+ DBUG_RETURN(true);
+ DBUG_RETURN(false);
}
bool
@@ -1232,28 +1383,11 @@ Hash_slave_rows::make_hash_key(TABLE *ta
ptr++)
{
Field *f= (*ptr);
- /* field is set in the read_set and is not a blob */
- if (bitmap_is_set(cols, f->field_index))
- {
- if (f->type() == MYSQL_TYPE_BLOB)
- {
- Field_blob *fb= (Field_blob*) f;
- uchar* ptr;
- uint32 length= fb->get_length();
- if (length)
- {
- fb->get_ptr(&ptr);
- crc= my_checksum(crc, ptr, length);
- }
- }
- else
- crc= my_checksum(crc, f->ptr, f->data_length());
-
- // TODO: what if the table only has blobs ?
- // Maybe don't use hash_scan approach or include
- // blobs in this calculation.
- }
+ /* field is set in the read_set and is not a blob */
+ if (bitmap_is_set(cols, f->field_index) &&
+ (f->type() != MYSQL_TYPE_BLOB))
+ crc= my_checksum(crc, f->ptr, f->data_length());
}
/*
@@ -1271,8 +1405,6 @@ Hash_slave_rows::make_hash_key(TABLE *ta
record[table->s->null_bytes - 1]= saved_filler;
}
-
-
DBUG_PRINT("debug", ("Created key=%u", crc));
DBUG_ASSERT(crc > 0);
@@ -1280,42 +1412,5 @@ Hash_slave_rows::make_hash_key(TABLE *ta
DBUG_RETURN(false);
}
-bool
-Hash_slave_rows::add_row(TABLE *table,
- MY_BITMAP *cols,
- const uchar *bi_start, const uchar *bi_ends,
- const uchar *ai_start, const uchar *ai_ends)
-{
- DBUG_ENTER("Hash_slave_rows::add_row");
-
- /**
- Insert the actual entry.
- */
- hash_slave_rows_entry *entry= (hash_slave_rows_entry*) malloc(sizeof(hash_slave_rows_entry));
- if (!entry)
- DBUG_RETURN(1);
-
- entry->key= (uchar*)&entry->hash_value;
- entry->length= sizeof(my_hash_value_type);
-
- /**
- Skip blobs from key calculation.
- Handle X bits.
- Handle nulled fields.
- Handled fields not signaled.
- */
- make_hash_key(table, cols, &entry->hash_value);
-
- entry->bi_start= (const uchar *) bi_start;
- entry->bi_ends= (const uchar *) bi_ends;
- entry->ai_start= (const uchar *) ai_start;
- entry->ai_ends= (const uchar *) ai_ends;
-
- DBUG_PRINT("debug", ("Added record to hash with key=%u", entry->hash_value));
-
- my_hash_insert(&m_hash, (uchar *) entry);
-
- DBUG_RETURN(0);
-}
#endif
=== modified file 'sql/rpl_utility.h'
--- a/sql/rpl_utility.h 2010-11-19 23:00:43 +0000
+++ b/sql/rpl_utility.h 2010-11-22 02:11:25 +0000
@@ -38,17 +38,8 @@ class Relay_log_info;
no index on the slave's table.
*/
-struct hash_slave_rows_entry
+typedef struct hash_row_pos_entry
{
- uchar* key;
-
- /**
- Length of the key.
- */
- uint length;
-
- my_hash_value_type hash_value;
-
/**
Points at the position where the row starts in the
event buffer (ie, area in memory before unpacking takes
@@ -59,48 +50,132 @@ struct hash_slave_rows_entry
const uchar *ai_start;
const uchar *ai_ends;
-};
+
+} HASH_ROW_POS_ENTRY;
+
class Hash_slave_rows
{
public:
+
+ /**
+ This member function allocates an entry to be added to the hash
+ table. It should be called before calling member function add.
+
+ @param bi_start the position to where in the rows buffer the
+ before image begins.
+ @param bi_ends the position to where in the rows buffer the
+ before image ends.
+ @param ai_start the position to where in the rows buffer the
+ after image starts (if any).
+ @param ai_ends the position to where in the rows buffer the
+ after image ends (if any).
+ @returns NULL if a problem occured, a valid pointer otherwise.
+ */
+ HASH_ROW_POS_ENTRY* make_entry(const uchar *bi_start, const uchar *bi_ends,
+ const uchar *ai_start, const uchar *ai_ends);
+
+ /**
+ Member function that puts data into the hash table.
+
+ @param table The table holding the buffer used to calculate the
+ key, ie, table->record[0].
+ @param cols The read_set bitmap signaling which columns are used.
+ @param entry The entry with the values to store.
+
+ @returns true if something went wrong, false otherwise.
+ */
+ bool put(TABLE* table, MY_BITMAP *cols, HASH_ROW_POS_ENTRY* entry);
+
/**
- @param table The table that is being scanned.
- @param cols The read_set bitmap signaling which columns are used.
- @param unpacked_record The position in memory where the unpacked record is.
+ This member function gets the entry, from the hash table, that
+ matches the data in table->record[0] and signaled using cols.
+
+ @param table The table holding the buffer containing data used to
+ make the entry lookup.
+ @param cols Bitmap signaling which columns, from
+ table->record[0], should be used.
+ @param entry Pointer that will hold a reference to the entry
+ fetched. If the entry is not found, then NULL
+ shall be returned.
+ @returns true if something went wrong, false otherwise.
*/
+ bool get(TABLE *table, MY_BITMAP *cols, HASH_ROW_POS_ENTRY** entry);
- bool add_row(TABLE* table,
- MY_BITMAP *cols,
- const uchar *bi_start, const uchar *bi_end,
- const uchar *ai_start, const uchar *ai_end);
+ /**
+ This member function gets the entry that stands next to the one
+ pointed to by *entry. Before calling this member function, the
+ entry that one uses as parameter must have: 1. been obtained
+ through get() or next() invocations; and 2. must have not been
+ used before in a next() operation.
+
+ @param entry[IN/OUT] contains a pointer to an entry that we can
+ use to search for another adjacent entry
+ (ie, that shares the same key).
+
+ @returns true if something went wrong, false otherwise. In the
+ case that this entry was already used in a next()
+ operation this member function returns true and does not
+ update the pointer.
+ */
+ bool next(HASH_ROW_POS_ENTRY** entry);
/**
- @param table
- @param cols
- @param unpacked_record
+ Deletes the entry pointed by entry. This is the only
+ safe way to free memory allocated for the structure
+ pointed to by entry.
+
+ @param entry Pointer to the entry to be deleted.
+ @returns true if something went wrong, false otherwise.
*/
- bool search_and_remove_row(TABLE *table,
- MY_BITMAP *cols,
- const uchar **bi_start, const uchar **bi_ends,
- const uchar **ai_start, const uchar **ai_ends);
+ bool del(HASH_ROW_POS_ENTRY* entry);
+ /**
+ Initializes the hash table.
+
+ @returns true if something went wrong, false otherwise.
+ */
bool init(void);
+
+ /**
+ De-initializes the hash table.
+
+ @returns true if something went wrong, false otherwise.
+ */
bool deinit(void);
+
+ /**
+ Checks if the hash table is empty or not.
+
+ @returns true if the hash table has zero entries, false otherwise.
+ */
bool is_empty(void);
+
+ /**
+ Returns the number of entries in the hash table.
+
+ @returns the number of entries in the hash table.
+ */
int size();
private:
+ /**
+ The hashtable itself.
+ */
HASH m_hash;
/**
+ Auxiliar and internal method used to create an hash key, based on
+ the data in table->record[0] buffer and signaled as used in cols.
+
@param table The table that is being scanned
@param cols The read_set bitmap signaling which columns are used.
@param key Output parameter where the key will be stored.
+
+ @retuns true if something went wrong, false otherwise.
*/
bool make_hash_key(TABLE *table, MY_BITMAP* cols, my_hash_value_type *key);
-
};
#endif
Attachment: [text/bzr-bundle] bzr/luis.soares@oracle.com-20101122021125-r1pgm9ey28ftt9lb.bundle
| Thread |
|---|
| • bzr commit into mysql-next-mr branch (luis.soares:3209) WL#5597 | Luis Soares | 22 Nov |
