{"action":"created","issue":{"url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/107","labels_url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/107/labels{/name}","comments_url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/107/comments","events_url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/107/events","html_url":"https://github.com/MySQLOnRocksDB/mysql-5.6/issues/107","id":104966266,"number":107,"title":"DML statements over reverse-ordered CFs are very slow after #86.","user":{"login":"spetrunia","id":2734550,"avatar_url":"https://avatars.githubusercontent.com/u/2734550?v=3","gravatar_id":"","url":"https://api.github.com/users/spetrunia","html_url":"https://github.com/spetrunia","followers_url":"https://api.github.com/users/spetrunia/followers","following_url":"https://api.github.com/users/spetrunia/following{/other_user}","gists_url":"https://api.github.com/users/spetrunia/gists{/gist_id}","starred_url":"https://api.github.com/users/spetrunia/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spetrunia/subscriptions","organizations_url":"https://api.github.com/users/spetrunia/orgs","repos_url":"https://api.github.com/users/spetrunia/repos","events_url":"https://api.github.com/users/spetrunia/events{/privacy}","received_events_url":"https://api.github.com/users/spetrunia/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"spetrunia","id":2734550,"avatar_url":"https://avatars.githubusercontent.com/u/2734550?v=3","gravatar_id":"","url":"https://api.github.com/users/spetrunia","html_url":"https://github.com/spetrunia","followers_url":"https://api.github.com/users/spetrunia/followers","following_url":"https://api.github.com/users/spetrunia/following{/other_user}","gists_url":"https://api.github.com/users/spetrunia/gists{/gist_id}","starred_url":"https://api.github.com/users/spetrunia/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spetrunia/subscriptions","organizations_url":"https://api.github.com/users/spetrunia/orgs","repos_url":"https://api.github.com/users/spetrunia/repos","events_url":"https://api.github.com/users/spetrunia/events{/privacy}","received_events_url":"https://api.github.com/users/spetrunia/received_events","type":"User","site_admin":false},"milestone":null,"comments":3,"created_at":"2015-09-04T20:43:08Z","updated_at":"2015-09-08T17:40:59Z","closed_at":null,"body":"Finally figured out why some DELETE queries got very slow (about 100x slower) after fix for #86.\r\n\r\n```\r\ncreate table t4 (\r\n  id int, value int, value2 varchar(200), \r\n  primary key (id) comment 'rev:cf_i3', \r\n  index(value) comment 'rev:cf_i3'\r\n) engine=rocksdb;\r\n```\r\nConsider a query:\r\n```\r\ndelete from t4 where id <= 3000;\r\n```\r\n\r\nEXPLAIN is:\r\n```\r\n+----+-------------+-------+-------+---------------+---------+---------+-------+------+-------------+\r\n| id | select_type | table | type  | possible_keys | key     | key_len | ref   | rows | Extra       |\r\n+----+-------------+-------+-------+---------------+---------+---------+-------+------+-------------+\r\n|  1 | SIMPLE      | t4    | range | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |\r\n+----+-------------+-------+-------+---------------+---------+---------+-------+------+-------------+\r\n```\r\nMySQL will use the following algorithm\r\n\r\n```\r\n  h->index_init(PRIMARY);\r\n  for (res=h->index_first(); res != EOF && table.id<3000 ; h->index_next())\r\n  {\r\n    h->delete_row(); // deletes the row we've just read\r\n  }\r\n```\r\n\r\nThe table uses reverse column families, so this translates into these RocksDB\r\ncalls:\r\n\r\n```\r\n  trx= db->BeginTransaction();\r\n  iter= trx->NewIterator();\r\n  iter->Seek(index_number);\r\n  while ()\r\n  {\r\n    if (!iter->Valid() || key_value_in_table(iter->key()))\r\n    {\r\n      // No more rows in the range\r\n      break;\r\n    }\r\n\r\n    rowkey= iter->key();\r\n    trx->Delete(rowkey);  // (*)\r\n\r\n    iter->Prev();  // (**)\r\n  }\r\n```\r\nNote the lines (*) and (**).\r\n\r\ninclude/rocksdb/utilities/transaction.h has this comment:\r\n```\r\n  // The returned iterator is only valid until Commit(), Rollback(), or\r\n  // RollbackToSavePoint() is called.\r\n  // NOTE: Transaction::Put/Merge/Delete will currently invalidate this iterator\r\n  // until\r\n  // the following issue is fixed:\r\n  // https://github.com/facebook/rocksdb/issues/616\r\n  virtual Iterator* GetIterator(const ReadOptions& read_options) = 0;\r\n```\r\nI assume it refers to this comment in issue #616:\r\n```\r\n  it is not safe to mutate the WriteBatchWithIndex while iterating through \r\n  the iterator generated by NewIteratorWithBase()\r\n```\r\nSo I implemented 'class Stabilized_iterator', which wraps the iterator returned\r\nby GetIterator(), but keeps itself valid across Put/Merge/Delete calls.\r\n\r\nIt does so by \r\n- remembering the key it is pointing at\r\n- calling backend_iter->Seek(last_key) if Put or Delete operation happens.\r\n\r\nThis works, but in the above scenario it is very slow.\r\n\r\nHere's why.  The table is in reverse-ordered CF, so it stores the data in this physical order:\r\n```\r\n   TABLE \r\n  row10K\r\n  ...\r\n  row03\r\n  row02\r\n  row01\r\n  row00\r\n  another-table-row\r\n```\r\nHowever, DELETE works in the logical order. First it deletes row00, then row01, etc.  Eventually, Transaction's WriteBatchWithIndex has:\r\n```\r\n   kDeletedRecord  row03\r\n   kDeletedRecord  row02\r\n   kDeletedRecord  row01\r\n   kDeletedRecord  row00\r\n```\r\nWe read row04. We call \"trx->Delete(row04)\", and the WriteBatchWithIndex now is:\r\n```\r\n   kDeletedRecord  row04\r\n   kDeletedRecord  row03\r\n   kDeletedRecord  row02\r\n   kDeletedRecord  row01\r\n   kDeletedRecord  row00\r\n```\r\n\r\nThen, we call iter->Prev() (line (**)).  Stabilized_iterator notes that its underlying iterator is invalidated. In orer to restore it, it calls \r\n```\r\n  backend_iter->Seek(row04).\r\n```\r\n\r\nThis operation finds row04 in the table, but it also sees {kDeletedRecord, row04} in the WriteBatchWithIndex.  It advances both of its underlying iterators, until it reaches another-table-row.\r\n\r\nThen, Stabilized_iterator calls backend_iter->Prev(). In this call, the iterator walks back through the pairs of row00, row01, ... row04, until it finds row05 in the base table. \r\n\r\nThis works, but if one deletes N rows then it's O(N^2) operations.\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/comments/138644891","html_url":"https://github.com/MySQLOnRocksDB/mysql-5.6/issues/107#issuecomment-138644891","issue_url":"https://api.github.com/repos/MySQLOnRocksDB/mysql-5.6/issues/107","id":138644891,"user":{"login":"siying","id":5334567,"avatar_url":"https://avatars.githubusercontent.com/u/5334567?v=3","gravatar_id":"","url":"https://api.github.com/users/siying","html_url":"https://github.com/siying","followers_url":"https://api.github.com/users/siying/followers","following_url":"https://api.github.com/users/siying/following{/other_user}","gists_url":"https://api.github.com/users/siying/gists{/gist_id}","starred_url":"https://api.github.com/users/siying/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/siying/subscriptions","organizations_url":"https://api.github.com/users/siying/orgs","repos_url":"https://api.github.com/users/siying/repos","events_url":"https://api.github.com/users/siying/events{/privacy}","received_events_url":"https://api.github.com/users/siying/received_events","type":"User","site_admin":false},"created_at":"2015-09-08T17:40:59Z","updated_at":"2015-09-08T17:40:59Z","body":"@igorcanadi added a test case for mutating WriteBatchWithIndex: https://reviews.facebook.net/D39501\r\n\r\nSo you should be able to add/remove keys from it. You need to be careful about the way to do it. For example, the way in your example will not work:\r\n\r\n    rowkey= iter->key();\r\n    trx->Delete(rowkey);  // (*)\r\n\r\n    iter->Prev();  // (**)\r\n\r\n`rowkey` is a reference to memory location. In our implementation issuing Delete() with it will cause problem as it changes in the middle of deletion and cause wrong results. But if you do:\r\n\r\n    std::string rowkey= iter->key(); \r\n    trx->Delete(rowkey);  // (*)\r\n\r\n    iter->Prev();  // (**)\r\n\r\nIt will work."}}