Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-4145

Take into account the selectivity of single-table range predicates on non-indexed columns when searching for the best execution plan

    XMLWordPrintable

Details

    • Task
    • Status: Closed (View Workflow)
    • Major
    • Resolution: Fixed
    • None
    • None

    Description

      Description of the problem
      ==========================

      Currently the optimizer completely ignores any conditions on non-indexed columns when searching for the best execution plan. As a result in many cases it chooses a suboptimal plan.

      Let's consider the query:
      SELECT * FROM t1,t2 WHERE t1.a=t2.a and t2.b BETWEEN 1 AND 3
      assuming that:
      -table t1 contains 100 records
      -table t2 contains 1000 records
      -there is a primary index on t1(a)
      -there is a secondary index on t2(a)
      -there is no index defined on column t2.b
      -the selectivity of the condition t2.b BETWEEN (1,3) is high (~ 1%)

      Under these conditions currently the optimizer will choose the plan that

      • accesses t1 using a table scan
      • accesses t2 using index t2(a)
      • checks the condition t2.b BETWEEN 1 AND 3

      This plan examines all rows of both tables and it performs 100 index look-ups.

      The alternative plan that:

      • accesses table t2 in a table scan
      • checks the condition t2.b BETWEEN 1 AND 3
      • accesses t1 using index t1(a)
        also would examine all rows of t2, but it performs only ~10 look-ups
        to access ~10 rows of table t1.

      The second plan is expected to be more efficient and it is so.

      The plan to resolve the problem
      ===============================

      1. Build single-table range conditions over different columns of all tables of the join query.

      2. Calculate the selectivity of each such condition using persistent statistics on table columns.

      3. Take this statistics into account when calculated the cardinality of each partial join that are evaluated by the optimizer.

      Attachments

        Issue Links

          blocks

          Task - A task that needs to be done. MDEV-83 Cost-based choice for the pushdown of subqueries to joined tables

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Stalled
          relates to

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4348 MWL#253: Server crashes in Item_equal::contains with optimizer_use_condition_selectivity>1, merge view (or FROM SQ)

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4349 MWL#253: Server crashes in calculate_cond_selectivity_for_table with constant table, optimizer_use_condition_selectivity>1

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4350 Explain shows negative selectivity for Q8 from DBT3, MWL#253

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4357 Histogram_type is not saved in the histogram

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4359 Unable to create a DOUBLE_PREC_HB histogram?

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4360 ANALYZE shows "Table is already up to date" while updating stats

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4362 Selectivity estimates for IN (...) do not depend on whether the values are in range

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4363 Bad selectivity for col IS NULL OR col IS NOT NULL

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4364 Histograms show the same selectivity for col=rare_value and col=frequent_value

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4366 MWL#253: Server crashes in calculate_cond_selectivity_for_table on JOIN with AND conditions, optimizer_use_condition_selectivity > 2

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4367 MWL#253: Assertion `join->best_read < double(...)' fails in greedy_search with STRAIGHT_JOIN, constant table, optimizer_use_condition_selectivity>1, derived_merge=on

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4369 column_stats.histogram contents doesnt make sense

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4370 MWL#253: Server crashes in Histogram::get_value with use_stat_tables, optimizer_use_condition_selectivity=3, histogram_size>0

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4371 MWL#253: Assertion `join->best_read < double(...)' fails in greedy_search with InnoDB, constant table, optimizer_use_condition_selectivity>1, use_stat_tables

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4372 MWL#253: Server crashes in calculate_cond_selectivity_for_table with EXISTS subquery, use_condition_selectivity=3, stat tables

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4373 MWL#253: Valgrind warnings 'Use of uninitialised value' and 'Invalid read' in get_column_range_cardinality

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4378 MWL#253: Assertion `join->best_read < double(...)' fails in greedy_search with IN subquery, optimizer_use_condition_selectivity=4, use_stat_tables, histograms

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4380 MWL#253: Server hangs in table_cond_selectivity with optimizer_use_condition_selectivity>1, IN subquery with aggregate function

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-4389 MWL#253: Assertion `join->best_read < double(...)' failed in greedy_search with optimizer_use_condition_selectivity=3

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-5200 Server crashes in table_multi_eq_cond_selectivity with optimizer_use_condition_selectivity > 1, IN subquery, LEFT JOIN

          • Major - Major loss of function.
          • Closed

          Activity

            People

              igor Igor Babaev
              igor Igor Babaev
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.