opt: the optimizer cost model should consider contention #79683

rytaft · 2022-04-08T18:44:55Z

Currently, CockroachDB's optimizer tries to find the best plan for a query in isolation and doesn't concern itself with the possibility that reading more rows than needed could cause write conflicts. Consider the following example:

CREATE TABLE tab (
  a INT,
  b INT,
  INDEX (b)
);
INSERT INTO tab SELECT generate_series(1,500), 1;
INSERT INTO tab SELECT generate_series(501,1000), 2;
ANALYZE tab;
EXPLAIN UPDATE tab SET a = 2000 WHERE b = 1;
                                             info
-----------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • update
  │ table: tab
  │ set: a
  │ auto commit
  │
  └── • render
      │ estimated row count: 500
      │
      └── • filter
          │ estimated row count: 500
          │ filter: b = 1
          │
          └── • scan
                estimated row count: 1,000 (100% of the table; stats collected 2 seconds ago)
                table: tab@tab_pkey
                spans: FULL SCAN

The optimizer chooses a full scan of the primary index instead of using the index on b, since in isolation, this is less expensive than performing an index join with half the rows in the table. However, it means that any other query that wants to update rows where b = 2 will block, even though technically there is no conflict.

Ideally, the optimizer would almost never choose a full scan for mutation queries such as this one where a suitable index is available, due to the impact on contention.

Epic CRDB-37836

Jira issue: CRDB-14977

gz#11932

gz#18109

The text was updated successfully, but these errors were encountered:

kenliu-crl · 2022-05-25T03:54:05Z

manually reviewed and updated

nvanbenschoten · 2022-08-19T18:55:36Z

One suggestion for users that run into this issue is that index hints are supported for mutation statements. This makes it possible to control the index used during the initial row scan of a mutation, which can be important to minimize false contention in some cases.

For example, without a hint:

demo@127.0.0.1:26257/movr> EXPLAIN UPDATE tab SET a = 2000 WHERE b = 1;
                                              info
------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • update
  │ table: tab
  │ set: a
  │ auto commit
  │
  └── • render
      │
      └── • filter
          │ estimated row count: 500
          │ filter: b = 1
          │
          └── • scan
                estimated row count: 1,000 (100% of the table; stats collected 36 seconds ago)
                table: tab@tab_pkey
                spans: FULL SCAN

With a hint:

demo@127.0.0.1:26257/movr> EXPLAIN UPDATE tab@tab_b_idx SET a = 2000 WHERE b = 1;
                                            info
---------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • update
  │ table: tab
  │ set: a
  │ auto commit
  │
  └── • render
      │
      └── • index join
          │ estimated row count: 500
          │ table: tab@tab_pkey
          │ locking strength: for update
          │
          └── • scan
                estimated row count: 500 (50% of the table; stats collected 39 seconds ago)
                table: tab@tab_b_idx
                spans: [/1 - /1]
                locking strength: for update

mgartner · 2022-09-29T15:56:16Z

@nvanbenschoten Do you know the reason for not propagating locking strength: for update to the full table scan in your first example above? We're considering using the locking strength of scans to penalize the cost of full table scans and scans with uncertain cardinality.

nvanbenschoten · 2022-09-29T16:11:41Z

We don't push down the implicit row-level locking mode if the initial row scan of an UPDATE statement is not precise (e.g. contains a filter). This is meant to avoid false contention, though I think you could argue that it's an unprincipled rule that falls out of the fact that we don't support shared locks.

Also update the error message to suggest adding a WHERE/LIMIT clause with appropriate index. Informs cockroachdb#79683 Release note (sql change): session setting `disallow_full_table_scans` and the cluster setting `sql.defaults.disallow_full_table_scans.enabled` now default to true.

Informs cockroachdb#79683 Release note (sql change): Added support for a new index hint, AVOID_FULL_SCAN, which will prevent the optimizer from planning a full scan for the specified table if any other plan is possible. The hint can be used in the same way as other existing index hints. For example, SELECT * FROM table_name@{AVOID_FULL_SCAN};. Note that a full scan of a partial index may still be preferred by the optimizer, unless AVOID_FULL_SCAN is used in combination with a specific partial index via FORCE_INDEX=index_name. This hint is similar to NO_FULL_SCAN, but will not error if a full scan cannot be avoided.

Fixes cockroachdb#79683 Release note (sql change): Added a new session setting avoid_full_table_scans_in_mutations, which when set to true, causes the optimizer to avoid planning full table scans for mutation queries if any other plan is possible. It now defaults to true.

Informs cockroachdb#79683 Release note (sql change): Added support for a new index hint, AVOID_FULL_SCAN, which will prevent the optimizer from planning a full scan for the specified table if any other plan is possible. The hint can be used in the same way as other existing index hints. For example, SELECT * FROM table_name@{AVOID_FULL_SCAN};. Note that a full scan of a partial index may still be preferred by the optimizer, unless AVOID_FULL_SCAN is used in combination with a specific partial index via FORCE_INDEX=index_name. This hint is similar to NO_FULL_SCAN, but will not error if a full scan cannot be avoided.

Fixes cockroachdb#79683 Release note (sql change): Added a new session setting avoid_full_table_scans_in_mutations, which when set to true, causes the optimizer to avoid planning full table scans for mutation queries if any other plan is possible. It now defaults to true.

Informs cockroachdb#79683 Release note (sql change): Added support for a new index hint, AVOID_FULL_SCAN, which will prevent the optimizer from planning a full scan for the specified table if any other plan is possible. The hint can be used in the same way as other existing index hints. For example, SELECT * FROM table_name@{AVOID_FULL_SCAN};. Note that a full scan of a partial index may still be preferred by the optimizer, unless AVOID_FULL_SCAN is used in combination with a specific partial index via FORCE_INDEX=index_name. This hint is similar to NO_FULL_SCAN, but will not error if a full scan cannot be avoided.

Fixes cockroachdb#79683 Release note (sql change): Added a new session setting avoid_full_table_scans_in_mutations, which when set to true, causes the optimizer to avoid planning full table scans for mutation queries if any other plan is possible. It now defaults to true.

Informs cockroachdb#79683 Release note (sql change): Added support for a new index hint, AVOID_FULL_SCAN, which will prevent the optimizer from planning a full scan for the specified table if any other plan is possible. The hint can be used in the same way as other existing index hints. For example, SELECT * FROM table_name@{AVOID_FULL_SCAN};. Note that a full scan of a partial index may still be preferred by the optimizer, unless AVOID_FULL_SCAN is used in combination with a specific partial index via FORCE_INDEX=index_name. This hint is similar to NO_FULL_SCAN, but will not error if a full scan cannot be avoided.

Fixes cockroachdb#79683 Release note (sql change): Added a new session setting avoid_full_table_scans_in_mutations, which when set to true, causes the optimizer to avoid planning full table scans for mutation queries if any other plan is possible. It now defaults to true.

Added a hint to avoid full scans (see release note below for details). To support this change, added a field to memo.Cost with a new type memo.CostFlags, which contains a number of boolean flags and supports "multi-dimensional costing". This allows the optimizer to compare plans based on the flags set in addition to the single-dimensional float64 cost. For example, plans with the new FullScanPenalty cost flag enabled will always be more expensive than plans without any cost flags, even if the base float64 cost is lower. The new CostFlags type also includes a flag for HugeCostPenalty, which must be set for plans with "hugeCost". This ensures that existing hints that use hugeCost still work if some other cost flags are set, since HugeCostPenalty takes precedence over other cost flags. This new CostFlags field is needed to support hints that do not cause an error if the optimizer cannot find a plan complying with the hint. This is needed because the previous approach of simply using "hugeCost" to avoid certain plans meant that if such plans were unavoidable, we could not effectively compare plans with cost greater than hugeCost due to loss of floating point precision. Informs cockroachdb#79683 Release note (sql change): Added support for a new index hint, AVOID_FULL_SCAN, which will prevent the optimizer from planning a full scan for the specified table if any other plan is possible. The hint can be used in the same way as other existing index hints. For example, SELECT * FROM table_name@{AVOID_FULL_SCAN};. This hint is similar to NO_FULL_SCAN, but will not error if a full scan cannot be avoided. Note that normally a full scan of a partial index would not be considered a "full scan" for the purposes of the NO_FULL_SCAN and AVOID_FULL_SCAN hints, but if the user has explicitly forced the partial index via FORCE_INDEX=index_name, we do consider it a full scan.