{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/34088755","id":34088755,"diff_hunk":"@@ -0,0 +1,123 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.util.collection.unsafe.sort;\n+\n+import com.google.common.base.Charsets;\n+import com.google.common.primitives.Longs;\n+import org.apache.spark.annotation.Private;\n+import org.apache.spark.unsafe.types.UTF8String;\n+\n+@Private\n+public class PrefixComparators {\n+  private PrefixComparators() {}\n+\n+  public static final StringPrefixComparator STRING = new StringPrefixComparator();\n+  public static final IntPrefixComparator INTEGER = new IntPrefixComparator();\n+  public static final LongPrefixComparator LONG = new LongPrefixComparator();\n+  public static final FloatPrefixComparator FLOAT = new FloatPrefixComparator();\n+  public static final DoublePrefixComparator DOUBLE = new DoublePrefixComparator();\n+\n+  public static final class StringPrefixComparator extends PrefixComparator {\n+    @Override\n+    public int compare(long aPrefix, long bPrefix) {\n+      // TODO: this can certainly be done more efficiently\n+      byte[] a = Longs.toByteArray(aPrefix);\n+      byte[] b = Longs.toByteArray(bPrefix);\n+      for (int i = 0; i < 8; i++) {\n+        if (a[i] == b[i]) continue;\n+        if (a[i] > b[i]) return -1;\n+        else if (a[i] < b[i]) return 1;\n+      }\n+      return 0;\n+    }\n+\n+    public long computePrefix(UTF8String value) {\n+      // TODO: this can certainly be done more efficiently\n+      return value == null ? 0L : computePrefix(value.toString());\n+    }\n+\n+    public long computePrefix(String value) {\n+      // TODO: this can certainly be done more efficiently\n+      if (value == null || value.length() == 0) {\n+        return 0L;\n+      } else {\n+        String first4Chars = value.substring(0, Math.min(3, value.length() - 1));\n+        byte[] utf16Bytes = first4Chars.getBytes(Charsets.UTF_16);\n+        byte[] padded = new byte[8];\n+        if (utf16Bytes.length < 8) {\n+          System.arraycopy(utf16Bytes, 0, padded, 0, utf16Bytes.length);\n+        }\n+        return Longs.fromByteArray(padded);\n+      }\n+    }\n+  }\n+\n+  public static final class IntPrefixComparator extends PrefixComparator {\n+    @Override\n+    public int compare(long aPrefix, long bPrefix) {\n+      int a = (int) aPrefix;\n+      int b = (int) bPrefix;\n+      return (a < b) ? -1 : (a > b) ? 1 : 0;\n+    }\n+\n+    public final long NULL_PREFIX = computePrefix(Integer.MIN_VALUE);\n+\n+    public long computePrefix(int value) {\n+      return value & 0xffffffffL;\n+    }\n+  }\n+\n+  public static final class LongPrefixComparator extends PrefixComparator {\n+    @Override\n+    public int compare(long a, long b) {\n+      return (a < b) ? -1 : (a > b) ? 1 : 0;\n+    }\n+\n+    public final long NULL_PREFIX = Long.MIN_VALUE;","path":"core/src/main/java/org/apache/spark/util/collection/unsafe/sort/PrefixComparators.java","position":91,"original_position":91,"commit_id":"88aff1847dc8d896d4b8dac471206ba8729d9b13","original_commit_id":"88aff1847dc8d896d4b8dac471206ba8729d9b13","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"body":"Should `null` be less than Long.MIN_VALUE ?","created_at":"2015-07-07T20:49:04Z","updated_at":"2015-07-07T20:49:04Z","html_url":"https://github.com/apache/spark/pull/6444#discussion_r34088755","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/6444","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/34088755"},"html":{"href":"https://github.com/apache/spark/pull/6444#discussion_r34088755"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/6444"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/6444","id":36347686,"html_url":"https://github.com/apache/spark/pull/6444","diff_url":"https://github.com/apache/spark/pull/6444.diff","patch_url":"https://github.com/apache/spark/pull/6444.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/6444","number":6444,"state":"open","locked":false,"title":"[SPARK-7078] [SPARK-7079] [WIP] Binary processing sort for Spark SQL","user":{"login":"JoshRosen","id":50748,"avatar_url":"https://avatars.githubusercontent.com/u/50748?v=3","gravatar_id":"","url":"https://api.github.com/users/JoshRosen","html_url":"https://github.com/JoshRosen","followers_url":"https://api.github.com/users/JoshRosen/followers","following_url":"https://api.github.com/users/JoshRosen/following{/other_user}","gists_url":"https://api.github.com/users/JoshRosen/gists{/gist_id}","starred_url":"https://api.github.com/users/JoshRosen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoshRosen/subscriptions","organizations_url":"https://api.github.com/users/JoshRosen/orgs","repos_url":"https://api.github.com/users/JoshRosen/repos","events_url":"https://api.github.com/users/JoshRosen/events{/privacy}","received_events_url":"https://api.github.com/users/JoshRosen/received_events","type":"User","site_admin":false},"body":"This is a WIP commit towards implementing a binary processing cache aware external record sort for use in Spark SQL.  The code here is modeled after an early design of #5868, which supported pluggable functions for comparing key prefixes and comparing serialized records.\r\n\r\nI'll update this PR with a detailed design description later, similar to the detailed descriptions and comments posted at #5868; I'm only opening this now so that I can run some things through Jenkins and track some code review comments.\r\n\r\nThis is blocked on merging #7176.\r\n\r\nThis will address the following JIRAs (not putting the links in the title yet because I don't want to send an email blast): `[SPARK-7078] [SPARK-7079]`.\r\n\r\nTODOS:\r\n\r\n- [ ] Spill cleanup tests\r\n- [ ] Refactoring of string prefix code, plus more tests.\r\n- [ ] Comments + real PR description.\r\n\r\n\r\n\r\n<!-- Reviewable:start -->\r\n[<img src=\"https://reviewable.io/review_button.png\" height=40 alt=\"Review on Reviewable\"/>](https://reviewable.io/reviews/apache/spark/6444)\r\n<!-- Reviewable:end -->\r\n","created_at":"2015-05-27T20:55:55Z","updated_at":"2015-07-07T20:49:04Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ddf50f5d1aa570bef42baab37089e70ad2139a79","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/6444/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/6444/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/6444/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/88aff1847dc8d896d4b8dac471206ba8729d9b13","head":{"label":"JoshRosen:sql-external-sort","ref":"sql-external-sort","sha":"88aff1847dc8d896d4b8dac471206ba8729d9b13","user":{"login":"JoshRosen","id":50748,"avatar_url":"https://avatars.githubusercontent.com/u/50748?v=3","gravatar_id":"","url":"https://api.github.com/users/JoshRosen","html_url":"https://github.com/JoshRosen","followers_url":"https://api.github.com/users/JoshRosen/followers","following_url":"https://api.github.com/users/JoshRosen/following{/other_user}","gists_url":"https://api.github.com/users/JoshRosen/gists{/gist_id}","starred_url":"https://api.github.com/users/JoshRosen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoshRosen/subscriptions","organizations_url":"https://api.github.com/users/JoshRosen/orgs","repos_url":"https://api.github.com/users/JoshRosen/repos","events_url":"https://api.github.com/users/JoshRosen/events{/privacy}","received_events_url":"https://api.github.com/users/JoshRosen/received_events","type":"User","site_admin":false},"repo":{"id":22238710,"name":"spark","full_name":"JoshRosen/spark","owner":{"login":"JoshRosen","id":50748,"avatar_url":"https://avatars.githubusercontent.com/u/50748?v=3","gravatar_id":"","url":"https://api.github.com/users/JoshRosen","html_url":"https://github.com/JoshRosen","followers_url":"https://api.github.com/users/JoshRosen/followers","following_url":"https://api.github.com/users/JoshRosen/following{/other_user}","gists_url":"https://api.github.com/users/JoshRosen/gists{/gist_id}","starred_url":"https://api.github.com/users/JoshRosen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoshRosen/subscriptions","organizations_url":"https://api.github.com/users/JoshRosen/orgs","repos_url":"https://api.github.com/users/JoshRosen/repos","events_url":"https://api.github.com/users/JoshRosen/events{/privacy}","received_events_url":"https://api.github.com/users/JoshRosen/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/JoshRosen/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/JoshRosen/spark","forks_url":"https://api.github.com/repos/JoshRosen/spark/forks","keys_url":"https://api.github.com/repos/JoshRosen/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/JoshRosen/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/JoshRosen/spark/teams","hooks_url":"https://api.github.com/repos/JoshRosen/spark/hooks","issue_events_url":"https://api.github.com/repos/JoshRosen/spark/issues/events{/number}","events_url":"https://api.github.com/repos/JoshRosen/spark/events","assignees_url":"https://api.github.com/repos/JoshRosen/spark/assignees{/user}","branches_url":"https://api.github.com/repos/JoshRosen/spark/branches{/branch}","tags_url":"https://api.github.com/repos/JoshRosen/spark/tags","blobs_url":"https://api.github.com/repos/JoshRosen/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/JoshRosen/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/JoshRosen/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/JoshRosen/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/JoshRosen/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/JoshRosen/spark/languages","stargazers_url":"https://api.github.com/repos/JoshRosen/spark/stargazers","contributors_url":"https://api.github.com/repos/JoshRosen/spark/contributors","subscribers_url":"https://api.github.com/repos/JoshRosen/spark/subscribers","subscription_url":"https://api.github.com/repos/JoshRosen/spark/subscription","commits_url":"https://api.github.com/repos/JoshRosen/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/JoshRosen/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/JoshRosen/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/JoshRosen/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/JoshRosen/spark/contents/{+path}","compare_url":"https://api.github.com/repos/JoshRosen/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/JoshRosen/spark/merges","archive_url":"https://api.github.com/repos/JoshRosen/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/JoshRosen/spark/downloads","issues_url":"https://api.github.com/repos/JoshRosen/spark/issues{/number}","pulls_url":"https://api.github.com/repos/JoshRosen/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/JoshRosen/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/JoshRosen/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/JoshRosen/spark/labels{/name}","releases_url":"https://api.github.com/repos/JoshRosen/spark/releases{/id}","created_at":"2014-07-25T00:47:52Z","updated_at":"2015-05-01T22:45:32Z","pushed_at":"2015-07-07T08:36:52Z","git_url":"git://github.com/JoshRosen/spark.git","ssh_url":"git@github.com:JoshRosen/spark.git","clone_url":"https://github.com/JoshRosen/spark.git","svn_url":"https://github.com/JoshRosen/spark","homepage":null,"size":114024,"stargazers_count":1,"watchers_count":1,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":3,"mirror_url":null,"open_issues_count":0,"forks":3,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"1cb2629f1aa466f92246828c562ea6f35c89ab87","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-07-07T20:25:55Z","pushed_at":"2015-07-07T20:37:19Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1485318,"stargazers_count":4662,"watchers_count":4662,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":4133,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":341,"forks":4133,"open_issues":341,"watchers":4662,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/6444"},"html":{"href":"https://github.com/apache/spark/pull/6444"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/6444"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/6444/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/6444/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/6444/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/88aff1847dc8d896d4b8dac471206ba8729d9b13"}}}}