{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/13505","repository_url":"https://api.github.com/repos/apache/spark","labels_url":"https://api.github.com/repos/apache/spark/issues/13505/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/13505/comments","events_url":"https://api.github.com/repos/apache/spark/issues/13505/events","html_url":"https://github.com/apache/spark/pull/13505","id":158476772,"number":13505,"title":"[SPARK-15764][SQL] Replace N^2 loop in BindReferences","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},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":21,"created_at":"2016-06-04T00:19:38Z","updated_at":"2016-06-06T06:57:43Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/13505","html_url":"https://github.com/apache/spark/pull/13505","diff_url":"https://github.com/apache/spark/pull/13505.diff","patch_url":"https://github.com/apache/spark/pull/13505.patch"},"body":"BindReferences contains a n^2 loop which causes performance issues when operating over large schemas: to determine the ordinal of an attribute reference, we perform a linear scan over the `input` array. Because input can sometimes be a `List`, the call to `input(ordinal).nullable` can also be O(n).\r\n\r\nInstead of performing a linear scan, we can convert the input into an array and build a hash map to map from expression ids to ordinals. The greater up-front cost of the map construction is offset by the fact that an expression can contain multiple attribute references, so the cost of the map construction is amortized across a number of lookups.\r\n\r\nPerf. benchmarks to follow. /cc @ericl"},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/223881916","html_url":"https://github.com/apache/spark/pull/13505#issuecomment-223881916","issue_url":"https://api.github.com/repos/apache/spark/issues/13505","id":223881916,"user":{"login":"AmplabJenkins","id":4031291,"avatar_url":"https://avatars.githubusercontent.com/u/4031291?v=3","gravatar_id":"","url":"https://api.github.com/users/AmplabJenkins","html_url":"https://github.com/AmplabJenkins","followers_url":"https://api.github.com/users/AmplabJenkins/followers","following_url":"https://api.github.com/users/AmplabJenkins/following{/other_user}","gists_url":"https://api.github.com/users/AmplabJenkins/gists{/gist_id}","starred_url":"https://api.github.com/users/AmplabJenkins/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AmplabJenkins/subscriptions","organizations_url":"https://api.github.com/users/AmplabJenkins/orgs","repos_url":"https://api.github.com/users/AmplabJenkins/repos","events_url":"https://api.github.com/users/AmplabJenkins/events{/privacy}","received_events_url":"https://api.github.com/users/AmplabJenkins/received_events","type":"User","site_admin":false},"created_at":"2016-06-06T06:57:43Z","updated_at":"2016-06-06T06:57:43Z","body":"Merged build finished. Test FAILed."}}
{"actor":{"display_login":"AmplabJenkins"}}