{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/21424","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/21424/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/21424/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/21424/events","html_url":"https://github.com/cockroachdb/cockroach/issues/21424","id":288231197,"number":21424,"title":"sql/sem/tree: investigate reducing allocations during expression evaluation","user":{"login":"petermattis","id":6201335,"avatar_url":"https://avatars0.githubusercontent.com/u/6201335?v=4","gravatar_id":"","url":"https://api.github.com/users/petermattis","html_url":"https://github.com/petermattis","followers_url":"https://api.github.com/users/petermattis/followers","following_url":"https://api.github.com/users/petermattis/following{/other_user}","gists_url":"https://api.github.com/users/petermattis/gists{/gist_id}","starred_url":"https://api.github.com/users/petermattis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/petermattis/subscriptions","organizations_url":"https://api.github.com/users/petermattis/orgs","repos_url":"https://api.github.com/users/petermattis/repos","events_url":"https://api.github.com/users/petermattis/events{/privacy}","received_events_url":"https://api.github.com/users/petermattis/received_events","type":"User","site_admin":false},"labels":[{"id":406290612,"url":"https://api.github.com/repos/cockroachdb/cockroach/labels/performance","name":"performance","color":"fef2c0","default":false}],"state":"open","locked":false,"assignee":{"login":"solongordon","id":679246,"avatar_url":"https://avatars1.githubusercontent.com/u/679246?v=4","gravatar_id":"","url":"https://api.github.com/users/solongordon","html_url":"https://github.com/solongordon","followers_url":"https://api.github.com/users/solongordon/followers","following_url":"https://api.github.com/users/solongordon/following{/other_user}","gists_url":"https://api.github.com/users/solongordon/gists{/gist_id}","starred_url":"https://api.github.com/users/solongordon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solongordon/subscriptions","organizations_url":"https://api.github.com/users/solongordon/orgs","repos_url":"https://api.github.com/users/solongordon/repos","events_url":"https://api.github.com/users/solongordon/events{/privacy}","received_events_url":"https://api.github.com/users/solongordon/received_events","type":"User","site_admin":false},"assignees":[{"login":"solongordon","id":679246,"avatar_url":"https://avatars1.githubusercontent.com/u/679246?v=4","gravatar_id":"","url":"https://api.github.com/users/solongordon","html_url":"https://github.com/solongordon","followers_url":"https://api.github.com/users/solongordon/followers","following_url":"https://api.github.com/users/solongordon/following{/other_user}","gists_url":"https://api.github.com/users/solongordon/gists{/gist_id}","starred_url":"https://api.github.com/users/solongordon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solongordon/subscriptions","organizations_url":"https://api.github.com/users/solongordon/orgs","repos_url":"https://api.github.com/users/solongordon/repos","events_url":"https://api.github.com/users/solongordon/events{/privacy}","received_events_url":"https://api.github.com/users/solongordon/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/13","html_url":"https://github.com/cockroachdb/cockroach/milestone/13","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/13/labels","id":2745639,"number":13,"title":"2.1","description":"","creator":{"login":"knz","id":642886,"avatar_url":"https://avatars3.githubusercontent.com/u/642886?v=4","gravatar_id":"","url":"https://api.github.com/users/knz","html_url":"https://github.com/knz","followers_url":"https://api.github.com/users/knz/followers","following_url":"https://api.github.com/users/knz/following{/other_user}","gists_url":"https://api.github.com/users/knz/gists{/gist_id}","starred_url":"https://api.github.com/users/knz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/knz/subscriptions","organizations_url":"https://api.github.com/users/knz/orgs","repos_url":"https://api.github.com/users/knz/repos","events_url":"https://api.github.com/users/knz/events{/privacy}","received_events_url":"https://api.github.com/users/knz/received_events","type":"User","site_admin":false},"open_issues":559,"closed_issues":57,"state":"open","created_at":"2017-09-05T15:30:49Z","updated_at":"2018-04-05T17:28:33Z","due_on":null,"closed_at":null},"comments":3,"created_at":"2018-01-12T20:03:14Z","updated_at":"2018-04-05T20:01:24Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"Scalar expression evaluation is currently allocation heavy because we treat the input `Datums` to every `tree.Expr` as immutable. So an expression like `a + 1` needs to allocate a datum for the result of the addition. Assuming `a` is an integer column type, that expression hits this code:\r\n\r\n```\r\n\t\tBinOp{\r\n\t\t\tLeftType:   types.Int,\r\n\t\t\tRightType:  types.Int,\r\n\t\t\tReturnType: types.Int,\r\n\t\t\tfn: func(_ *EvalContext, left Datum, right Datum) (Datum, error) {\r\n\t\t\t\ta, b := MustBeDInt(left), MustBeDInt(right)\r\n\t\t\t\tr, ok := AddWithOverflow(int64(a), int64(b))\r\n\t\t\t\tif !ok {\r\n\t\t\t\t\treturn nil, errIntOutOfRange\r\n\t\t\t\t}\r\n\t\t\t\treturn NewDInt(DInt(r)), nil\r\n\t\t\t},\r\n\t\t},\r\n```\r\n\r\nFor a given overload, the type of the return datum is known. Before evaluating an expression for the first time, we could walk over the expression and assign each node which needs to generate a new datum a \"slot\" in some structure in `EvalContext`. During execution, we would pass the slot (or slots) to the the evaluation function and it could grab the datum from `EvalContext` rather than allocating it. "},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/379058932","html_url":"https://github.com/cockroachdb/cockroach/issues/21424#issuecomment-379058932","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/21424","id":379058932,"user":{"login":"solongordon","id":679246,"avatar_url":"https://avatars1.githubusercontent.com/u/679246?v=4","gravatar_id":"","url":"https://api.github.com/users/solongordon","html_url":"https://github.com/solongordon","followers_url":"https://api.github.com/users/solongordon/followers","following_url":"https://api.github.com/users/solongordon/following{/other_user}","gists_url":"https://api.github.com/users/solongordon/gists{/gist_id}","starred_url":"https://api.github.com/users/solongordon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solongordon/subscriptions","organizations_url":"https://api.github.com/users/solongordon/orgs","repos_url":"https://api.github.com/users/solongordon/repos","events_url":"https://api.github.com/users/solongordon/events{/privacy}","received_events_url":"https://api.github.com/users/solongordon/received_events","type":"User","site_admin":false},"created_at":"2018-04-05T20:01:24Z","updated_at":"2018-04-05T20:01:24Z","author_association":"CONTRIBUTOR","body":"After doing some profiling here I'm somewhat unconvinced that we would see a big benefit from implementing this change. For queries like `SELECT COUNT(*) FROM table WHERE col1 + 1 = col2`, we allocate one int per row, which is a large number of allocations but a small fraction of the total space allocated during execution. (In a test query on a TPC-H table it was 70% of the allocated objects but 5% of the space.) `buildScanResults` and `decodeUntaggedDatum` dominate.\r\n\r\nThe exception was when I tried joins with scalar expressions in the ON condition, e.g. `SELECT COUNT(*) FROM t1 JOIN t2 ON t1.col + 1 = t2.col`. In that case there are so many allocations that it approached 50% of the allocated space in my test queries. However, this seems to be mainly an issue of hitting an unoptimized `HashJoiner` path. The join is O(nm) due to all rows ending up in the same hash bucket (as explained by @RaduBerinde), and furthermore it looks like the scalar expression is evaluated n*m times. If we address this inefficiency to make the join O(n+m), the allocation picture should look more like the previous case I described. (And these joins would not be as painfully slow as they are today.)\r\n\r\nMy only other thought is that we could see bigger benefits for operations with larger return types, like string concatenation or JSON operations. But I'm not sure those are typical enough to warrant optimization right now."}}
{"actor":{"display_login":"solongordon"}}