{"action":"created","issue":{"url":"https://api.github.com/repos/cmu-db/peloton/issues/434","repository_url":"https://api.github.com/repos/cmu-db/peloton","labels_url":"https://api.github.com/repos/cmu-db/peloton/issues/434/labels{/name}","comments_url":"https://api.github.com/repos/cmu-db/peloton/issues/434/comments","events_url":"https://api.github.com/repos/cmu-db/peloton/issues/434/events","html_url":"https://github.com/cmu-db/peloton/issues/434","id":197528594,"number":434,"title":"Proposal on Changing IntsKey Design To Accelerate Key Comparison and Creation","user":{"login":"wangziqi2013","id":4521485,"avatar_url":"https://avatars.githubusercontent.com/u/4521485?v=3","gravatar_id":"","url":"https://api.github.com/users/wangziqi2013","html_url":"https://github.com/wangziqi2013","followers_url":"https://api.github.com/users/wangziqi2013/followers","following_url":"https://api.github.com/users/wangziqi2013/following{/other_user}","gists_url":"https://api.github.com/users/wangziqi2013/gists{/gist_id}","starred_url":"https://api.github.com/users/wangziqi2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wangziqi2013/subscriptions","organizations_url":"https://api.github.com/users/wangziqi2013/orgs","repos_url":"https://api.github.com/users/wangziqi2013/repos","events_url":"https://api.github.com/users/wangziqi2013/events{/privacy}","received_events_url":"https://api.github.com/users/wangziqi2013/received_events","type":"User","site_admin":false},"labels":[{"id":158835811,"url":"https://api.github.com/repos/cmu-db/peloton/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"state":"open","locked":false,"assignee":{"login":"wangziqi2013","id":4521485,"avatar_url":"https://avatars.githubusercontent.com/u/4521485?v=3","gravatar_id":"","url":"https://api.github.com/users/wangziqi2013","html_url":"https://github.com/wangziqi2013","followers_url":"https://api.github.com/users/wangziqi2013/followers","following_url":"https://api.github.com/users/wangziqi2013/following{/other_user}","gists_url":"https://api.github.com/users/wangziqi2013/gists{/gist_id}","starred_url":"https://api.github.com/users/wangziqi2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wangziqi2013/subscriptions","organizations_url":"https://api.github.com/users/wangziqi2013/orgs","repos_url":"https://api.github.com/users/wangziqi2013/repos","events_url":"https://api.github.com/users/wangziqi2013/events{/privacy}","received_events_url":"https://api.github.com/users/wangziqi2013/received_events","type":"User","site_admin":false},"assignees":[{"login":"wangziqi2013","id":4521485,"avatar_url":"https://avatars.githubusercontent.com/u/4521485?v=3","gravatar_id":"","url":"https://api.github.com/users/wangziqi2013","html_url":"https://github.com/wangziqi2013","followers_url":"https://api.github.com/users/wangziqi2013/followers","following_url":"https://api.github.com/users/wangziqi2013/following{/other_user}","gists_url":"https://api.github.com/users/wangziqi2013/gists{/gist_id}","starred_url":"https://api.github.com/users/wangziqi2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wangziqi2013/subscriptions","organizations_url":"https://api.github.com/users/wangziqi2013/orgs","repos_url":"https://api.github.com/users/wangziqi2013/repos","events_url":"https://api.github.com/users/wangziqi2013/events{/privacy}","received_events_url":"https://api.github.com/users/wangziqi2013/received_events","type":"User","site_admin":false}],"milestone":null,"comments":5,"created_at":"2016-12-26T03:11:36Z","updated_at":"2016-12-27T04:29:07Z","closed_at":null,"body":"Motivation\r\n=======\r\n\r\nCurrently IntsKey are represented using an array of uint64_t. When a value is inserted or extracted, an inter-word and intra-word offset must be maintained to extract bytes from the source using bitwise shift and bitwise OR. Comparison and equality checking relies on word-wise comparison using a hand written tight loop.\r\n\r\nThis design has few deficiencies:\r\n\r\n1. Inserting and Extracting a byte from a 64 bit word does excessively unnecessary jobs to extract a single byte. \r\n2. Comparison is now in the most efficient form because hand written loop does not utilize potentially faster SIMD extension\r\n3. Tight loops may penalize branch prediction as is the case with current implementation\r\n\r\nProposed Design\r\n===========\r\n\r\nIntsKey is represented using an array of 8 byte char, the length of which is still specified by the template argument (and is maintained to be backward compatible with the current one). This makes state maintenance easier because for external routines only one variable is needed. Also, an array of char type enables byte aligned addressing which makes data access simpler (not necessarily faster, because internally the processor could not perform byte addressing)\r\n\r\nEndianess\r\n------------\r\n All integers are stored in **BIG-ENDIAN** form, to facilitate comparison as we will see later. Integral keys of any length could be supported.\r\n\r\nWhen a key is inserted, it is first of all converted into **BIG-ENDIAN** by swapping bytes between two ends. After that the resulting big-endian is directly copied into the array using memcpy to avoid any loop (compiler knows the semantics of memcpy() and could optimize it into a single instruction for most of the time).\r\n\r\nSign Bit\r\n---------\r\nTo accommodate for negative numbers, all integers are stored in a **modified SIGN-MAGNITUTE** format, which flips the sign bit of the classical 2's complement representation. This is justified by the static nature of IntsKey - no modification is allowed on IntsKey directly. The **SIGN-MAGNITUTE** format enables us to compare the magnitude of two numbers based purely on binary comparison. If this is yet not clear, please refer to how radix tree alters its signed integer key to match the goal.\r\n\r\nFor example, assume we have two 1 byte integer 127 and -1, with classical binary representation 0x7F and 0xFF. Binary comparison would yield -1 > 127 because 0xFF > 0x7F. If we adopt sign magnitude format, then the high bit will be flipped, and now 127 and -1 are represented respectively as 0xFF and 0x7F which yields the correct result. For multi-byte integers in big-endian this is always true.\r\n\r\nComparison\r\n--------------\r\nThe comparison of IntsKey represented in big-endian and sign-magnitute format is a straightforward memcpy() on binary representation. As we have proved above the result of binary representation is sufficient for determining relationship between two IntsKey. The same applies for equality checking.\r\n\r\nThe best with memcpy() is that since compiler knows its semantics, there are chances that the compiler could optimize memcpy() into SIMD instructions, or reorder some instruction to favor super-scalar pipelines for potential intra-instruction parallelism. In addition, unrolling of tight loops avoids penalizing branch prediction.\r\n\r\nCompatibility\r\n-----------------\r\nAll member functions could be made back-ward compatible with the current implementation. However special care needs to be taken with the size of IntsKey, since currently the KeySize argument speficies key size in a unit of uint64_t rather than a single byte.\r\n\r\nReview\r\n--------\r\n@apavlo @malin1993ml \r\n\r\nReference\r\n-----------\r\n**On how ART transform its key**\r\n\r\na)  Unsigned  Integers:\r\nThe  binary  representation  of  unsigned  integers  already  has  the  desired  order.  However,  the endianness  of  the  machine  must  be  taken  into  account  when storing the value into main memory. On little endian machines, the  byte  order  must  be  swapped  to  ensure  that  the  result  is ordered from most to least significant byte.\r\n\r\nb)  Signed   Integers:\r\nSigned   two-complement   integers must  be  reordered  because  negative  integers  are  ordered  de-\r\nscending  and  are  greater  than  the  positive  values.  An b bit integer x is  transformed  very  efficiently by  flipping  the  sign bit (using x XOR 2^b)"},"comment":{"url":"https://api.github.com/repos/cmu-db/peloton/issues/comments/269268117","html_url":"https://github.com/cmu-db/peloton/issues/434#issuecomment-269268117","issue_url":"https://api.github.com/repos/cmu-db/peloton/issues/434","id":269268117,"user":{"login":"malin1993ml","id":5907405,"avatar_url":"https://avatars.githubusercontent.com/u/5907405?v=3","gravatar_id":"","url":"https://api.github.com/users/malin1993ml","html_url":"https://github.com/malin1993ml","followers_url":"https://api.github.com/users/malin1993ml/followers","following_url":"https://api.github.com/users/malin1993ml/following{/other_user}","gists_url":"https://api.github.com/users/malin1993ml/gists{/gist_id}","starred_url":"https://api.github.com/users/malin1993ml/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/malin1993ml/subscriptions","organizations_url":"https://api.github.com/users/malin1993ml/orgs","repos_url":"https://api.github.com/users/malin1993ml/repos","events_url":"https://api.github.com/users/malin1993ml/events{/privacy}","received_events_url":"https://api.github.com/users/malin1993ml/received_events","type":"User","site_admin":false},"created_at":"2016-12-27T04:29:07Z","updated_at":"2016-12-27T04:29:07Z","body":"@wangziqi2013 Thanks for explanation. I agree with that we should avoid constructing Value objects in Compare() by directly comparing the compact form for IntsKey. But it seems that we need to modify the interface for Compare() as well? Right now the Compare() function takes in a list of expressions and values for each column in the key. If we still use that interface, how could we apply those information on a compact form of IntsKey?\r\n\r\nI understand the example you gave on IndexScanPredicate might not be exact. It seems to me that the only circumstances that we may return irrelevant keys are on the two boundaries of the scan range, right? If that is true, then I'm thinking of two optimization:\r\n(1) I'm wondering given that we already have the scan conditions in the IndexScanPredicate, can we add some extra flags there to indicate whether we should include the two boundaries, and **only** check the two boundaries of the list of tuples returned by the index, instead of scanning all tuples again to check the condition for the second time?\r\n(2) If we do the above checking, it seems that we no longer need those arguments with the Compare() function? We just need to compare the low key with the beginning of the returned list (or high key with the end of the returned list) in the compact/generic form again for correctness."}}
{"actor":{"display_login":"malin1993ml"}}