{"push_id":2972599462,"size":9,"distinct_size":9,"ref":"refs/heads/master","head":"381384c7c5c96e009d3772a2474819eba0e79c28","before":"4422f4c69bd561de5f43e75b87e328c4b2e572bc","commits":[{"sha":"aa04065faf27ac53858f8e7c9de1aa04abc37403","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update test output format for easier review\n\nThis is an artificial commit designed to reformat test output to look\nmore like the test output of the new Opt Node representation. The only\ncode changes in this commit are changes to the formatting routines, and\nall tests were re-run to reflect the new format. Therefore, it's not\nnecessary to review the test file changes in this commit. However, it\nwill be *much* easier to review test diffs introduced by the next\ncommit in the PR, since they will now only consist of \"real\" changes\ncaused by the changes in behavior, rather than just due to formatting\ndifferences.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/aa04065faf27ac53858f8e7c9de1aa04abc37403"},{"sha":"117028dfa3803496e9628c894667f8ab2d626cbb","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Change Memo data structures\n\nChange how the Memo stores groups and expressions. Currently, both\nare stored in Go slices which are resized as new groups and expressions\nare added to the memo. Expressions store GroupIDs and PrivateIDs, which\nare indexes into slices holding memo groups and expression-specific  data.\n\nWhile this design has worked OK, it has several downsides:\n\n  1. There is very little type safety, since all expressions are stored\n     in identical 16 byte structs so they can be packed into slices.\n     This can also make debugging tedious, as the debugger does not\n     know how to decode the expressions.\n\n  2. Expressions can have only 3 fields, since we pack them into 16\n     bytes. For many operators this is fine, but it requires awkward\n     workarounds for operators than need >3 fields.\n\n  3. Many nodes have \"private\" data fields that require the allocation\n     of a separate object to store. This cancels what would otherwise\n     be an advantage of the current design, since it ends up allocating\n     about the same number of objects as the new design for this and\n     other reasons. It also requires tedious calls to InternPrivate\n     and LookupPrivate methods in order to map to and from slice\n     indexes.\n\n  4. When the optimizer decides on a lowest cost expression tree, it\n     must store that information \"off to the side\" in BestExpr\n     structures so that ExprView knows which of the trees in the forest\n     to traverse. This triggers additional allocations.\n\n  5. Traversal of the tree requires an auxiliary ExprView data structure\n     that holds onto context necessary for the traversal (i.e. the Memo).\n     This makes the current design harder to understand and use.\n\n  6. All expressions allocate and store logical properties. While this is\n     necessary for relational expressions, it is not required for most\n     scalar operators.\n\n  7. The memo expression storage format is not compatible with nodes used\n     in other parts of Cockroach, like AST and planNodes. This makes mixing\n     and matching nodes difficult, and requires \"wrapper\" nodes to map\n     between different representations.\n\nThe new memo expression representation solves these problems using a more\nnatural Go-friendly design. Each expression is a differently-typed Go\nstruct that implements the Expr interface:\n\n  type Expr interface {\n    Op() Operator\n    ChildCount() int\n    Child(nth int) Expr\n    Private() interface{}\n    String() string\n  }\n\nThis is similar to how AST nodes and planNodes work. Optgen generates a\nstruct definition for each operator, as well as implementations for the\nExpr interface methods. Private values are stored inline in the structs,\nreplacing the need for an additional allocation. Expressions can be\nconstructed using a very natural factory interface with no explicit\ninterning required.\n\nWhere it gets more interesting is for relational expressions, which are\npart of memo groups that can contain multiple logically equivalent\nexpressions. The new representation links together expressions in the\nsame group using \"next\" pointers. In addition, the first expression in\nthe memo is allocated with extra inline storage to store relational and\nphysical properties. This avoids separate allocation for the properties\nlike the current representation requires. For a simple expression tree\nwith 1 expression per group, the tree requires just 1 object per memo\ngroup.\n\nOverall, the new representation is between 10%-15% faster than the\ncurrent representation for basic construction and manipulation. More\nimportantly, it's quite a bit more useable and extensible.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/117028dfa3803496e9628c894667f8ab2d626cbb"},{"sha":"2c0fb70cb7adddbe407a122c567555a09f8b59ee","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update Optgen to generate new expression representation\n\nChange Optgen to generate the structs, methods, factory, and explorer\nused by the new expression representation. The new representation is\nstrongly-typed, so this requires more awareness of types. Accordingly,\na new \"metadata\" struct maps Optgen inferred types to corresponding Go\ntypes.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/2c0fb70cb7adddbe407a122c567555a09f8b59ee"},{"sha":"b2c4521c68de2dd71aa0bce13bffee31470af398","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update optbuilder to use the new expression representation\n\nChange optbuilder to use the new representation, including the new\nnormalization factory.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/b2c4521c68de2dd71aa0bce13bffee31470af398"},{"sha":"a77a23299cd8ab5f7f40fde2234d26bbb3fbb2e2","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update the norm package to use the new expression representation\n\nUpdate all rules and custom functions to use the new expressions. Much\nof the difficulty in doing this involves the change to use inlined slices\nto store Filters, Projections, and Aggregations, as well as changes to\nwhere scalar properties are stored (only on individual filter conjuncts,\nprojection expressions, and aggregates).\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/a77a23299cd8ab5f7f40fde2234d26bbb3fbb2e2"},{"sha":"f3c6ce9c3a0fd1cf351f6c7dbef1b10a6eb4a1cb","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update xform package to use new expression representation\n\nChange the explorer and exploration rules and custom functions to use\nthe new expression representation. The optimizer will now skip traversal\nof scalar expressions which do not contain subqueries. Also, after\nexploration is complete, the optimizer walks the expression forest and\nupdates child pointers so that the root points to lowest cost expression\ntree. Before, the \"best expression\" information was stored on the side,\nwhich required additional allocations and slowed traversal.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/f3c6ce9c3a0fd1cf351f6c7dbef1b10a6eb4a1cb"},{"sha":"e1260ad49ce658594eeceaf74a9e371cee4f4dae","author":{"name":"Andrew Kimball","email":"47fb46b442a7228b0951bd0a39a9bd256934d92d@cockroachlabs.com"},"message":"opt: Update exec-related and testing infra to use new expressions\n\nChange execbuilder to traverse the new expression representation. Update\nthe test infrastructure to support optsteps and exploretrace as well.\nChange SQL execution code paths to use the new expressions.\n\nRelease note: None","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/e1260ad49ce658594eeceaf74a9e371cee4f4dae"},{"sha":"04cba2800919bdcf6a8467e8da97ae44b77a9626","author":{"name":"craig[bot]","email":"3a2c29237f73c7cf88424b80e427b1884f346b35@cockroachlabs.com"},"message":"Merge #31173\n\n31173: opt: Change Memo data structures r=andy-kimball a=andy-kimball\n\nChange how the Memo stores groups and expressions. Currently, both\r\nare stored in Go slices which are resized as new groups and expressions\r\nare added to the memo. Expressions store GroupIDs and PrivateIDs, which\r\nare indexes into slices holding memo groups and expression-specific  data.\r\n\r\nWhile this design has worked OK, it has several downsides:\r\n\r\n  1. There is very little type safety, since all expressions are stored\r\n     in identical 16 byte structs so they can be packed into slices.\r\n     This can also make debugging tedious, as the debugger does not\r\n     know how to decode the expressions.\r\n\r\n  2. Expressions can have only 3 fields, since we pack them into 16\r\n     bytes. For many operators this is fine, but it requires awkward\r\n     workarounds for operators than need >3 fields.\r\n\r\n  3. Many nodes have \"private\" data fields that require the allocation\r\n     of a separate object to store. This cancels what would otherwise\r\n     be an advantage of the current design, since it ends up allocating\r\n     about the same number of objects as the new design for this and\r\n     other reasons. It also requires tedious calls to InternPrivate\r\n     and LookupPrivate methods in order to map to and from slice\r\n     indexes.\r\n\r\n  4. When the optimizer decides on a lowest cost expression tree, it\r\n     must store that information \"off to the side\" in BestExpr\r\n     structures so that ExprView knows which of the trees in the forest\r\n     to traverse. This triggers additional allocations.\r\n\r\n  5. Traversal of the tree requires an auxiliary ExprView data structure\r\n     that holds onto context necessary for the traversal (i.e. the Memo).\r\n     This makes the current design harder to understand and use.\r\n\r\n  6. All expressions allocate and store logical properties. While this is\r\n     necessary for relational expressions, it is not required for most\r\n     scalar operators.\r\n\r\n  7. The memo expression storage format is not compatible with nodes used\r\n     in other parts of Cockroach, like AST and planNodes. This makes mixing\r\n     and matching nodes difficult, and requires \"wrapper\" nodes to map\r\n     between different representations.\r\n\r\nThe new memo expression representation solves these problems using a more\r\nnatural Go-friendly design. Each expression is a differently-typed Go\r\nstruct that implements the Expr interface:\r\n```\r\n  type Expr interface {\r\n    Op() Operator\r\n    ChildCount() int\r\n    Child(nth int) Expr\r\n    Private() interface{}\r\n    String() string\r\n  }\r\n```\r\nThis is similar to how AST nodes and planNodes work. Optgen generates a\r\nstruct definition for each operator, as well as implementations for the\r\nExpr interface methods. Private values are stored inline in the structs,\r\nreplacing the need for an additional allocation. Expressions can be\r\nconstructed using a very natural factory interface with no explicit\r\ninterning required.\r\n\r\nWhere it gets more interesting is for relational expressions, which are\r\npart of memo groups that can contain multiple logically equivalent\r\nexpressions. The new representation links together expressions in the\r\nsame group using \"next\" pointers. In addition, the first expression in\r\nthe memo is allocated with extra inline storage to store relational and\r\nphysical properties. This avoids separate allocation for the properties\r\nlike the current representation requires. For a simple expression tree\r\nwith 1 expression per group, the tree requires just 1 object per memo\r\ngroup.\r\n\r\nHere are numbers for the old vs. new representations:\r\n```\r\nname                               old time/op  new time/op  delta\r\nPhases/kv-read/ExecBuild           15.5µs ± 3%  10.7µs ± 3%  -31.03%  (p=0.008 n=5+5)\r\nPhases/kv-read-no-prep/ExecBuild   38.1µs ± 3%  33.4µs ± 2%  -12.14%  (p=0.008 n=5+5)\r\nPhases/kv-read-const/ExecBuild      682ns ± 2%   622ns ± 2%   -8.71%  (p=0.008 n=5+5)\r\nPhases/tpcc-new-order/ExecBuild    53.2µs ± 5%  35.4µs ± 3%  -33.41%  (p=0.008 n=5+5)\r\nPhases/tpcc-delivery/ExecBuild     38.9µs ± 3%  23.8µs ± 5%  -38.72%  (p=0.008 n=5+5)\r\nPhases/tpcc-stock-level/ExecBuild   167µs ± 2%   114µs ± 3%  -31.34%  (p=0.008 n=5+5)\r\nExec/kv-read/ExecPlan               197µs ± 2%   193µs ± 2%     ~     (p=0.056 n=5+5)\r\nExec/kv-read/ExecOpt                186µs ± 4%   189µs ± 3%     ~     (p=0.421 n=5+5)\r\nExec/kv-read-no-prep/ExecPlan       318µs ± 3%   315µs ± 2%     ~     (p=0.548 n=5+5)\r\nExec/kv-read-no-prep/ExecOpt        340µs ± 8%   327µs ± 1%   -4.00%  (p=0.016 n=5+5)\r\nExec/kv-read-const/ExecPlan         194µs ± 3%   192µs ± 2%     ~     (p=0.421 n=5+5)\r\nExec/kv-read-const/ExecOpt          161µs ± 3%   161µs ± 4%     ~     (p=1.000 n=5+5)\r\nExec/tpcc-new-order/ExecPlan        301µs ± 8%   268µs ± 2%  -10.81%  (p=0.008 n=5+5)\r\nExec/tpcc-new-order/ExecOpt         269µs ± 1%   261µs ± 3%   -3.09%  (p=0.032 n=5+5)\r\nExec/tpcc-delivery/ExecPlan         243µs ± 2%   253µs ± 9%     ~     (p=0.690 n=5+5)\r\nExec/tpcc-delivery/ExecOpt          242µs ± 1%   245µs ± 6%     ~     (p=0.690 n=5+5)\r\nExec/tpcc-stock-level/ExecPlan      545µs ± 2%   525µs ± 2%   -3.53%  (p=0.008 n=5+5)\r\nExec/tpcc-stock-level/ExecOpt       532µs ± 3%   501µs ± 3%   -5.79%  (p=0.008 n=5+5)\r\n\r\nname                               old alloc/op   new alloc/op   delta\r\n\r\nPhases/kv-read/ExecBuild             5.39kB ± 0%    3.90kB ± 0%  -27.53%  (p=0.008 n=5+5)\r\n\r\nPhases/kv-read-no-prep/ExecBuild     10.3kB ± 0%     9.2kB ± 0%  -10.69%  (p=0.008 n=5+5)\r\n\r\nPhases/kv-read-const/ExecBuild         264B ± 0%      216B ± 0%  -18.18%  (p=0.008 n=5+5)\r\n\r\nPhases/tpcc-new-order/ExecBuild      14.9kB ± 0%     9.9kB ± 0%  -33.79%  (p=0.008 n=5+5)\r\n\r\nPhases/tpcc-delivery/ExecBuild       11.5kB ± 0%     6.4kB ± 0%  -43.83%  (p=0.000 n=5+4)\r\n\r\nPhases/tpcc-stock-level/ExecBuild    50.1kB ± 0%    30.1kB ± 0%  -40.08%  (p=0.008 n=5+5)\r\n\r\nExec/kv-read/ExecPlan                30.3kB ± 0%    26.7kB ± 0%  -11.77%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read/ExecOpt                 26.4kB ± 0%    24.9kB ± 0%   -5.65%  (p=0.008 n=5+5)\r\n\r\nExec/kv-read-no-prep/ExecPlan        43.3kB ± 2%    39.3kB ± 0%   -9.19%  (p=0.016 n=5+4)\r\n\r\nExec/kv-read-no-prep/ExecOpt         44.5kB ± 0%    39.8kB ± 0%  -10.50%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read-const/ExecPlan          29.9kB ± 0%    26.3kB ± 0%  -12.02%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read-const/ExecOpt           21.0kB ± 0%    20.9kB ± 0%   -0.24%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-new-order/ExecPlan         66.3kB ± 0%    57.9kB ± 0%  -12.68%  (p=0.016 n=4+5)\r\n\r\nExec/tpcc-new-order/ExecOpt          51.3kB ± 0%    46.3kB ± 0%   -9.88%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-delivery/ExecPlan          33.9kB ± 0%    30.1kB ± 0%  -11.13%  (p=0.016 n=5+4)\r\n\r\nExec/tpcc-delivery/ExecOpt           35.7kB ± 0%    30.7kB ± 0%  -14.07%  (p=0.016 n=4+5)\r\n\r\nExec/tpcc-stock-level/ExecPlan        150kB ± 0%     138kB ± 0%   -7.57%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-stock-level/ExecOpt         131kB ± 0%     111kB ± 0%  -15.31%  (p=0.016 n=5+4)\r\n\r\nname                               old allocs/op  new allocs/op  delta\r\n\r\nPhases/kv-read/ExecBuild               34.0 ± 0%      29.0 ± 0%  -14.71%  (p=0.008 n=5+5)\r\n\r\nPhases/kv-read-no-prep/ExecBuild       96.0 ± 0%      87.0 ± 0%   -9.38%  (p=0.008 n=5+5)\r\n\r\nPhases/kv-read-const/ExecBuild         6.00 ± 0%      5.00 ± 0%  -16.67%  (p=0.008 n=5+5)\r\n\r\nPhases/tpcc-new-order/ExecBuild        76.0 ± 0%      57.0 ± 0%  -25.00%  (p=0.008 n=5+5)\r\n\r\nPhases/tpcc-delivery/ExecBuild         62.0 ± 0%      43.0 ± 0%  -30.65%  (p=0.008 n=5+5)\r\n\r\nPhases/tpcc-stock-level/ExecBuild       217 ± 0%       171 ± 0%  -21.20%  (p=0.008 n=5+5)\r\n\r\nExec/kv-read/ExecPlan                   315 ± 0%       310 ± 0%   -1.59%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read/ExecOpt                    273 ± 0%       267 ± 0%   -2.05%  (p=0.008 n=5+5)\r\n\r\nExec/kv-read-no-prep/ExecPlan           460 ± 0%       456 ± 0%   -0.96%  (p=0.016 n=4+5)\r\n\r\nExec/kv-read-no-prep/ExecOpt            438 ± 0%       413 ± 0%   -5.71%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read-const/ExecPlan             308 ± 0%       303 ± 0%   -1.62%  (p=0.029 n=4+4)\r\n\r\nExec/kv-read-const/ExecOpt              238 ± 0%       237 ± 0%   -0.42%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-new-order/ExecPlan            414 ± 0%       401 ± 0%     ~     (p=0.079 n=4+5)\r\n\r\nExec/tpcc-new-order/ExecOpt             350 ± 0%       331 ± 0%   -5.43%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-delivery/ExecPlan             363 ± 0%       354 ± 0%   -2.48%  (p=0.000 n=5+4)\r\n\r\nExec/tpcc-delivery/ExecOpt              326 ± 0%       307 ± 0%     ~     (p=0.079 n=4+5)\r\n\r\nExec/tpcc-stock-level/ExecPlan        1.04k ± 0%     1.01k ± 0%   -2.22%  (p=0.029 n=4+4)\r\n\r\nExec/tpcc-stock-level/ExecOpt           763 ± 0%       717 ± 0%   -6.03%  (p=0.000 n=5+4)\r\n```\n\nCo-authored-by: Andrew Kimball <andyk@cockroachlabs.com>","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/04cba2800919bdcf6a8467e8da97ae44b77a9626"},{"sha":"381384c7c5c96e009d3772a2474819eba0e79c28","author":{"name":"Cockroach TeamCity","email":"fd37cc0f60f5654682bdc272adb420052001c7d2@cockroachlabs.com"},"message":"Snapshot 04cba2800919bdcf6a8467e8da97ae44b77a9626","distinct":true,"url":"https://api.github.com/repos/cockroachdb/cockroach-gen/commits/381384c7c5c96e009d3772a2474819eba0e79c28"}]}
{"actor":{"display_login":"cockroach-teamcity"}}