{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/23487","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/23487/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/23487/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/23487/events","html_url":"https://github.com/cockroachdb/cockroach/issues/23487","id":302813418,"number":23487,"title":"sql: index selection prefers reading from thinner indexes even at the cost of additional sorting","user":{"login":"arjunravinarayan","id":1565833,"avatar_url":"https://avatars0.githubusercontent.com/u/1565833?v=4","gravatar_id":"","url":"https://api.github.com/users/arjunravinarayan","html_url":"https://github.com/arjunravinarayan","followers_url":"https://api.github.com/users/arjunravinarayan/followers","following_url":"https://api.github.com/users/arjunravinarayan/following{/other_user}","gists_url":"https://api.github.com/users/arjunravinarayan/gists{/gist_id}","starred_url":"https://api.github.com/users/arjunravinarayan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/arjunravinarayan/subscriptions","organizations_url":"https://api.github.com/users/arjunravinarayan/orgs","repos_url":"https://api.github.com/users/arjunravinarayan/repos","events_url":"https://api.github.com/users/arjunravinarayan/events{/privacy}","received_events_url":"https://api.github.com/users/arjunravinarayan/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"RaduBerinde","id":16544120,"avatar_url":"https://avatars1.githubusercontent.com/u/16544120?v=4","gravatar_id":"","url":"https://api.github.com/users/RaduBerinde","html_url":"https://github.com/RaduBerinde","followers_url":"https://api.github.com/users/RaduBerinde/followers","following_url":"https://api.github.com/users/RaduBerinde/following{/other_user}","gists_url":"https://api.github.com/users/RaduBerinde/gists{/gist_id}","starred_url":"https://api.github.com/users/RaduBerinde/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RaduBerinde/subscriptions","organizations_url":"https://api.github.com/users/RaduBerinde/orgs","repos_url":"https://api.github.com/users/RaduBerinde/repos","events_url":"https://api.github.com/users/RaduBerinde/events{/privacy}","received_events_url":"https://api.github.com/users/RaduBerinde/received_events","type":"User","site_admin":false},"assignees":[{"login":"RaduBerinde","id":16544120,"avatar_url":"https://avatars1.githubusercontent.com/u/16544120?v=4","gravatar_id":"","url":"https://api.github.com/users/RaduBerinde","html_url":"https://github.com/RaduBerinde","followers_url":"https://api.github.com/users/RaduBerinde/followers","following_url":"https://api.github.com/users/RaduBerinde/following{/other_user}","gists_url":"https://api.github.com/users/RaduBerinde/gists{/gist_id}","starred_url":"https://api.github.com/users/RaduBerinde/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RaduBerinde/subscriptions","organizations_url":"https://api.github.com/users/RaduBerinde/orgs","repos_url":"https://api.github.com/users/RaduBerinde/repos","events_url":"https://api.github.com/users/RaduBerinde/events{/privacy}","received_events_url":"https://api.github.com/users/RaduBerinde/received_events","type":"User","site_admin":false}],"milestone":null,"comments":0,"created_at":"2018-03-06T18:24:44Z","updated_at":"2018-03-06T18:38:06Z","closed_at":null,"author_association":"OWNER","body":"In TPC-C, we have the following table definition for the `order_line` table:\r\n\r\n```\r\nshow create table order_line;\r\n+------------+--------------------------------------------------------------------------+\r\n|   Table    |                               CreateTable                                |\r\n+------------+--------------------------------------------------------------------------+\r\n| order_line | CREATE TABLE order_line (                                                |\r\n|            |                                                                          |\r\n|            |     ol_o_id INTEGER NOT NULL,                                            |\r\n|            |                                                                          |\r\n|            |     ol_d_id INTEGER NOT NULL,                                            |\r\n|            |                                                                          |\r\n|            |     ol_w_id INTEGER NOT NULL,                                            |\r\n|            |                                                                          |\r\n|            |     ol_number INTEGER NOT NULL,                                          |\r\n|            |                                                                          |\r\n|            |     ol_i_id INTEGER NOT NULL,                                            |\r\n|            |                                                                          |\r\n|            |     ol_supply_w_id INTEGER NULL,                                         |\r\n|            |                                                                          |\r\n|            |     ol_delivery_d TIMESTAMP NULL,                                        |\r\n|            |                                                                          |\r\n|            |     ol_quantity INTEGER NULL,                                            |\r\n|            |                                                                          |\r\n|            |     ol_amount DECIMAL(6,2) NULL,                                         |\r\n|            |                                                                          |\r\n|            |     ol_dist_info STRING(24) NULL,                                        |\r\n|            |                                                                          |\r\n|            |     CONSTRAINT \"primary\" PRIMARY KEY (ol_w_id ASC, ol_d_id ASC, ol_o_id  |\r\n|            | DESC, ol_number ASC),                                                    |\r\n|            |                                                                          |\r\n|            |     CONSTRAINT fk_ol_supply_w_id_ref_stock FOREIGN KEY (ol_supply_w_id,  |\r\n|            | ol_d_id) REFERENCES stock (s_w_id, s_i_id),                              |\r\n|            |                                                                          |\r\n|            |     INDEX order_line_fk (ol_supply_w_id ASC, ol_d_id ASC),               |\r\n|            |                                                                          |\r\n|            |     CONSTRAINT fk_ol_w_id_ref_order FOREIGN KEY (ol_w_id, ol_d_id,       |\r\n|            | ol_o_id) REFERENCES \"order\" (o_w_id, o_d_id, o_id),                      |\r\n|            |                                                                          |\r\n|            |     FAMILY \"primary\" (ol_o_id, ol_d_id, ol_w_id, ol_number, ol_i_id,     |\r\n|            | ol_supply_w_id, ol_delivery_d, ol_quantity, ol_amount, ol_dist_info)     |\r\n|            |                                                                          |\r\n|            | )                                                                        |\r\n+------------+--------------------------------------------------------------------------+\r\n```\r\n\r\nSelecting from the prefix of the primary key columns in primary key order results in the following explain plan, which is clearly suboptimal:\r\n\r\n```\r\nroot@:26257/tpcc> explain (verbose) select ol_w_id, ol_d_id, ol_o_id from tpcc.order_line order by ol_w_id, ol_d_id, ol_o_id desc;\r\n+----------------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n|      Tree      | Level |  Type  |  Field   |          Description           |                                 Columns                                  |                                 Ordering                                 |\r\n+----------------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n| sort           |     0 | sort   |          |                                | (ol_w_id, ol_d_id, ol_o_id)                                              | ol_w_id!=NULL; ol_d_id!=NULL; ol_o_id!=NULL; +ol_w_id,+ol_d_id,-ol_o_id  |\r\n|  │             |     0 |        | order    | +ol_w_id,+ol_d_id,-ol_o_id     |                                                                          |                                                                          |\r\n|  └── render    |     1 | render |          |                                | (ol_w_id, ol_d_id, ol_o_id)                                              | ol_w_id!=NULL; ol_d_id!=NULL; ol_o_id!=NULL                              |\r\n|       │        |     1 |        | render 0 | tpcc.public.order_line.ol_w_id |                                                                          |                                                                          |\r\n|       │        |     1 |        | render 1 | tpcc.public.order_line.ol_d_id |                                                                          |                                                                          |\r\n|       │        |     1 |        | render 2 | tpcc.public.order_line.ol_o_id |                                                                          |                                                                          |\r\n|       └── scan |     2 | scan   |          |                                | (ol_o_id, ol_d_id, ol_w_id, ol_number[omitted], ol_i_id[omitted],        | ol_o_id!=NULL; ol_d_id!=NULL; ol_w_id!=NULL; ol_number!=NULL;            |\r\n|                |       |        |          |                                | ol_supply_w_id[omitted], ol_delivery_d[omitted], ol_quantity[omitted],   | weak-key(ol_o_id,ol_d_id,ol_w_id,ol_number,ol_supply_w_id)               |\r\n|                |       |        |          |                                | ol_amount[omitted], ol_dist_info[omitted])                               |                                                                          |\r\n|                |     2 |        | table    | order_line@order_line_fk       |                                                                          |                                                                          |\r\n|                |     2 |        | spans    | ALL                            |                                                                          |                                                                          |\r\n+----------------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n(9 rows)\r\n```\r\n\r\nForcing reading from the primary index gives the desired plan, which does not have a SORT node:\r\n```\r\nroot@:26257/tpcc> explain (verbose) select ol_w_id, ol_d_id, ol_o_id from tpcc.order_line@primary order by ol_w_id, ol_d_id, ol_o_id desc;\r\n+-----------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n|   Tree    | Level |  Type  |  Field   |          Description           |                                 Columns                                  |                                 Ordering                                 |\r\n+-----------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n| render    |     0 | render |          |                                | (ol_w_id, ol_d_id, ol_o_id)                                              | ol_w_id!=NULL; ol_d_id!=NULL; ol_o_id!=NULL; +ol_w_id,+ol_d_id,-ol_o_id  |\r\n|  │        |     0 |        | render 0 | tpcc.public.order_line.ol_w_id |                                                                          |                                                                          |\r\n|  │        |     0 |        | render 1 | tpcc.public.order_line.ol_d_id |                                                                          |                                                                          |\r\n|  │        |     0 |        | render 2 | tpcc.public.order_line.ol_o_id |                                                                          |                                                                          |\r\n|  └── scan |     1 | scan   |          |                                | (ol_o_id, ol_d_id, ol_w_id, ol_number[omitted], ol_i_id[omitted],        | ol_o_id!=NULL; ol_d_id!=NULL; ol_w_id!=NULL; ol_number!=NULL;            |\r\n|           |       |        |          |                                | ol_supply_w_id[omitted], ol_delivery_d[omitted], ol_quantity[omitted],   | key(ol_o_id,ol_d_id,ol_w_id,ol_number); +ol_w_id,+ol_d_id,-ol_o_id       |\r\n|           |       |        |          |                                | ol_amount[omitted], ol_dist_info[omitted])                               |                                                                          |\r\n|           |     1 |        | table    | order_line@primary             |                                                                          |                                                                          |\r\n|           |     1 |        | spans    | ALL                            |                                                                          |                                                                          |\r\n+-----------+-------+--------+----------+--------------------------------+--------------------------------------------------------------------------+--------------------------------------------------------------------------+\r\n(7 rows)\r\n```\r\n\r\nThe index selection mechanism is preferring the former plan because it scans through a thinner index. However, the cost of sorting the data far outweighs the cost of reading through fatter column families.\r\n\r\nThis issue is reproducible using the TPC-C workload generator."},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/370883356","html_url":"https://github.com/cockroachdb/cockroach/issues/23487#issuecomment-370883356","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/23487","id":370883356,"user":{"login":"RaduBerinde","id":16544120,"avatar_url":"https://avatars1.githubusercontent.com/u/16544120?v=4","gravatar_id":"","url":"https://api.github.com/users/RaduBerinde","html_url":"https://github.com/RaduBerinde","followers_url":"https://api.github.com/users/RaduBerinde/followers","following_url":"https://api.github.com/users/RaduBerinde/following{/other_user}","gists_url":"https://api.github.com/users/RaduBerinde/gists{/gist_id}","starred_url":"https://api.github.com/users/RaduBerinde/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RaduBerinde/subscriptions","organizations_url":"https://api.github.com/users/RaduBerinde/orgs","repos_url":"https://api.github.com/users/RaduBerinde/repos","events_url":"https://api.github.com/users/RaduBerinde/events{/privacy}","received_events_url":"https://api.github.com/users/RaduBerinde/received_events","type":"User","site_admin":false},"created_at":"2018-03-06T18:38:06Z","updated_at":"2018-03-06T18:38:06Z","author_association":"OWNER","body":"We probably need to adjust the rudimentary formulas in opt_index_selection."}}
{"actor":{"display_login":"RaduBerinde"}}