[MDEV-30660] COUNT DISTINCT seems unnecessarily slow when run on a PK Created: 2023-02-15  Updated: 2024-02-07

Status: In Progress
Project: MariaDB Server
Component/s: None
Affects Version/s: 10.6.11
Fix Version/s: 10.6

Type: Bug Priority: Critical
Reporter: Rob Schwyzer Assignee: Oleg Smirnov
Resolution: Unresolved Votes: 0
Labels: None
Environment:

CentOS 7 baremetal

Issue Links:
Duplicate
duplicates MDEV-10922 optimization on count distinct on pri... Confirmed
Relates
relates to MDEV-32870 Improve the performance of COUNT DIST... Open

 Description   

Repro-

alias mdb='/path/to/mariadb-client-binary --defaults-file=/path/to/my.cnf'
 
mdb -e 'CREATE DATABASE countdistinct;'
 
 
 
mdb countdistinct << 'EOF'
 
CREATE TABLE autoinc (
 
  c0 INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
 
  c1 int(11) DEFAULT NULL,
 
  c2 int(11) DEFAULT NULL,
 
  c3 int(11) DEFAULT NULL,
 
  KEY `k_c1` (`c1`),
 
  KEY `k_c2` (`c2`,`c1`),
 
  KEY `k_c3` (`c3`,`c2`,`c1`)
 
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb3 COLLATE=utf8mb3_general_ci;
 
EOF
 
 
 
# Load 1M rows of data
 
for ((i=0;i<1000;i++)); do
 
  for ((j=0;j<100;j++)); do
 
    curval=$(( (i * 100) + j ))
 
    mdb countdistinct -e 'INSERT INTO autoinc (c1) VALUES ('"${curval}"');' &
 
  done
 
done
 
 
 
# Prime buffers/caches
 
time mdb countdistinct -Nse 'SELECT c0 FROM autoinc;' >/dev/null
 
time mdb countdistinct -Nse 'SELECT c1 FROM autoinc;' >/dev/null
 
time mdb countdistinct -Nse 'SELECT c2 FROM autoinc;' >/dev/null
 
time mdb countdistinct -Nse 'SELECT c3 FROM autoinc;' >/dev/null
 
 
 
# Test various ways of obtaining COUNT data
 
time mdb countdistinct -Nse 'SELECT COUNT(*) FROM autoinc;'
 
time mdb countdistinct -Nse 'SELECT COUNT(c0) FROM autoinc;'
 
time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c0)) FROM autoinc;'
 
time mdb countdistinct -Nse 'SELECT c0, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1;'
 
time mdb information_schema -Nse 'SELECT TABLE_ROWS FROM TABLES WHERE TABLE_SCHEMA="countdistinct" AND TABLE_NAME="autoinc";'

The killer here is the GROUP BY ... HAVING ... query performing much faster than COUNT(DISTINCT... as the two are logically pretty similar in what they're doing.

Example uses an AUTO_INCREMENT PK to give a "best-case" scenario for this- performance is worse if the PK is unsorted.

Here are some sample test results-

time mdb countdistinct -Nse 'SELECT COUNT(*) FROM autoinc;'
 
100000
 
 
 
real    0m0.039s
 
user    0m0.019s
 
sys     0m0.006s
 
time mdb countdistinct -Nse 'SELECT COUNT(c0) FROM autoinc;'
 
100000
 
 
 
real    0m0.037s
 
user    0m0.019s
 
sys     0m0.004s
 
time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c0)) FROM autoinc;'
 
100000
 
 
 
real    0m0.053s
 
user    0m0.018s
 
sys     0m0.004s
 
time mdb countdistinct -Nse 'SELECT c0, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1;'
 
 
 
real    0m0.042s
 
user    0m0.019s
 
sys     0m0.003s
 
time mdb information_schema -Nse 'SELECT TABLE_ROWS FROM TABLES WHERE TABLE_SCHEMA="countdistinct" AND TABLE_NAME="autoinc";'
 
100131
 
 
 
real    0m0.022s
 
user    0m0.016s
 
sys     0m0.005s

Note that this slowness seems exclusive to PKs. Running on the roughly identical c1 column yields only a marginal slowdown for COUNT(DISTINCT(c1)) despite the contents of c0 and c1 being almost identical-

time mdb countdistinct -Nse 'SELECT COUNT(*) FROM autoinc;'
 
LECT COUNT(DISTINCT (c1)) FROM autoinc;'
 
100000
 
 
 
real    0m0.037s
 
user    0m0.021s
 
sys     0m0.003s
 
time mdb countdistinct -Nse 'SELECT COUNT(c1) FROM autoinc;'
 
100000
 
 
 
real    0m0.036s
 
user    0m0.019s
 
sys     0m0.003s
 
time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c1)) FROM autoinc;'
 
100000
 
 
 
real    0m0.040s
 
user    0m0.018s
 
sys     0m0.003s
 
time mdb countdistinct -Nse 'SELECT c1, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1;'
 
 
 
real    0m0.040s
 
user    0m0.017s
 
sys     0m0.004s
 
time mdb information_schema -Nse 'SELECT TABLE_ROWS FROM TABLES WHERE TABLE_SCHEMA="countdistinct" AND TABLE_NAME="autoinc";'
 
100131
 
 
 
real    0m0.022s
 
user    0m0.018s
 
sys     0m0.003s

And to just confirm the content is comparable as expected-

mdb countdistinct -e 'SELECT c0, c1 FROM autoinc ORDER BY c0 ASC LIMIT 5;'
 
+----+------+
 
| c0 | c1   |
 
+----+------+
 
|  1 |    0 |
 
|  2 |    1 |
 
|  3 |    2 |
 
|  4 |    3 |
 
|  5 |    4 |
 
+----+------+
 
mdb countdistinct -e 'SELECT c0, c1 FROM autoinc ORDER BY c0 DESC LIMIT 5;'
 
+--------+-------+
 
| c0     | c1    |
 
+--------+-------+
 
| 100000 | 99999 |
 
|  99999 | 99998 |
 
|  99998 | 99997 |
 
|  99997 | 99996 |
 
|  99996 | 99995 |
 
+--------+-------+

The good news is if the non-PK results hold up, that handles most realistic cases for COUNT(DISTINCT.... But it does seem like we should figure out why our PK implementation is such an outlier in case it is stealthily affecting other operations.

 Comments   
Comment by Daniel Black [ 2023-03-02 ]

This could get particularly important for WordPress users in the very near future - ref: https://github.com/WordPress/wordpress-develop/pull/3863

Comment by Daniel Black [ 2023-11-24 ]

I looked it up and effectively the execution is maintaining a tree of the DISTINCT items and counting that at the end.

Comment by Oleg Smirnov [ 2023-12-20 ]

rob.schwyzer@mariadb.com, I have tested the attached scenario on the recent 10.6-17 and haven't seen a dramatic difference between COUNT(DISTINCT) and GROUP BY HAVING. See my results below (dataset size is 500000 rows):

MariaDB [test]> SELECT COUNT(DISTINCT (c0)) FROM cdtest;
 
+----------------------+
 
| COUNT(DISTINCT (c0)) |
 
+----------------------+
 
|               500000 |
 
+----------------------+
 
1 row in set (1.386 sec)
 
 
 
MariaDB [test]> SELECT c0, COUNT(*) FROM cdtest GROUP BY 1 HAVING COUNT(*) <> 1;
 
Empty set (0.956 sec)
 
 
 
MariaDB [test]> SELECT COUNT(DISTINCT (c1)) FROM cdtest;
 
+----------------------+
 
| COUNT(DISTINCT (c1)) |
 
+----------------------+
 
|               500000 |
 
+----------------------+
 
1 row in set (0.812 sec)
 
 
 
MariaDB [test]> SELECT c1, COUNT(*) FROM cdtest GROUP BY 1 HAVING COUNT(*) <> 1;
 
Empty set (0.882 sec)

I'd suggest that the customer:

  • upgrades to the most recent release of their version, 10.6-16, for example (not necessary, but still)
  • increases their dataset, so the execution times are closer to something about one second or more. Comparing hundredths of second may lead to wrong conclusions
  • runs ANALYZE TABLE <name> PERSISTENT FOR ALL before running queries
  • attaches the output of EXPLAIN FORMAT=JSON for the problematic queries.
Comment by Rob Schwyzer [ 2023-12-20 ] 

 mdb -e 'SELECT @@version;'
 
+-----------------------------------------+
 
| @@version                               |
 
+-----------------------------------------+
 
| 10.6.16-MariaDB-1:10.6.16+maria~ubu2004 |
 
+-----------------------------------------+
 

mdb countdistinct -e 'ANALYZE TABLE autoinc PERSISTENT FOR ALL;'
 
+-----------------------+---------+----------+-----------------------------------------+
 
| Table                 | Op      | Msg_type | Msg_text                                |
 
+-----------------------+---------+----------+-----------------------------------------+
 
| countdistinct.autoinc | analyze | status   | Engine-independent statistics collected |
 
| countdistinct.autoinc | analyze | status   | OK                                      |
 
+-----------------------+---------+----------+-----------------------------------------+
 

time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c0)) FROM autoinc;'
 
99552
 
 
 
real    0m0.028s
 
user    0m0.004s
 
sys     0m0.001s
 
 
 
mdb countdistinct -e 'EXPLAIN FORMAT=JSON SELECT COUNT(DISTINCT (c0)) FROM autoinc\G'
 
*************************** 1. row ***************************
 
EXPLAIN: {
 
  "query_block": {
 
    "select_id": 1,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "index",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "rows": 99552,
 
      "filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}

As compared to-

time mdb countdistinct -Nse 'SELECT c0, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1;'
 
 
 
real    0m0.020s
 
user    0m0.004s
 
sys     0m0.001s
 
 
 
mdb countdistinct -e 'EXPLAIN FORMAT=JSON SELECT c0, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1\G'
 
*************************** 1. row ***************************
 
EXPLAIN: {
 
  "query_block": {
 
    "select_id": 1,
 
    "having_condition": "count(0) <> 1",
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "index",
 
      "key": "PRIMARY",
 
      "key_length": "4",
 
      "used_key_parts": ["c0"],
 
      "rows": 99552,
 
      "filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}

Since the EXPLAIN is coming back differently, I kept it at the current dataset size.

Since I noticed "used_key_parts": ["c1"] on the slower of these two, I decided to run the following as well-

time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c1)) FROM autoinc;'
 
99552
 
 
 
real    0m0.019s
 
user    0m0.004s
 
sys     0m0.001s
 
 
 
mdb countdistinct -e 'EXPLAIN FORMAT=JSON SELECT COUNT(DISTINCT (c1)) FROM autoinc\G'
 
*************************** 1. row ***************************
 
EXPLAIN: {
 
  "query_block": {
 
    "select_id": 1,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "range",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "rows": 99553,
 
      "filtered": 100,
 
      "using_index_for_group_by": "scanning"
 
    }
 
  }
 
}
 
 
 
time mdb countdistinct -Nse 'SELECT c1, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1;'
 
 
 
real    0m0.021s
 
user    0m0.005s
 
sys     0m0.001s
 
 
 
mdb countdistinct -e 'EXPLAIN FORMAT=JSON SELECT c1, COUNT(*) FROM autoinc GROUP BY 1 HAVING COUNT(*) <> 1\G'
 
*************************** 1. row ***************************
 
EXPLAIN: {
 
  "query_block": {
 
    "select_id": 1,
 
    "having_condition": "count(0) <> 1",
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "index",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "rows": 99552,
 
      "filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}

That doesn't seem to be enough to explain it though.

I next ran the following to verify execution time of the bad query is consistent, which it is-

for ((i=0; i<30; i++)); do time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c0)) FROM autoinc;' ; done

Median output was-

99552
 
 
 
real    0m0.030s
 
user    0m0.005s
 
sys     0m0.001s

With real being no fewer than 0m0.028s and no larger than 0m0.030s.

For the other column...

for ((i=0; i<30; i++)); do time mdb countdistinct -Nse 'SELECT COUNT(DISTINCT (c1)) FROM autoinc;' ; done

Median output was-

99552
 
 
 
real    0m0.019s
 
user    0m0.004s
 
sys     0m0.001s

With real being no fewer than 0m0.018s and no larger than 0m0.022s.

Running ANALYZE on both variants-

 mdb countdistinct -e 'ANALYZE FORMAT=JSON SELECT COUNT(DISTINCT (c0)) FROM autoinc\G'
 
*************************** 1. row ***************************
 
ANALYZE: {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 26.571,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "index",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "r_loops": 1,
 
      "rows": 99552,
 
      "r_rows": 99552,
 
      "r_table_time_ms": 9.085,
 
      "r_other_time_ms": 17.481,
 
      "r_engine_stats": {
 
        "pages_accessed": 112
 
      },
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}
 
 
 
mdb countdistinct -e 'ANALYZE FORMAT=JSON SELECT COUNT(DISTINCT (c1)) FROM autoinc\G'
 
*************************** 1. row ***************************
 
ANALYZE: {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 16.603,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "range",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "r_loops": 1,
 
      "rows": 99553,
 
      "r_rows": 99552,
 
      "r_table_time_ms": 9.27,
 
      "r_other_time_ms": 7.328,
 
      "r_engine_stats": {
 
        "pages_accessed": 114
 
      },
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index_for_group_by": "scanning"
 
    }
 
  }
 
}

Seems to be entirely due to r_other_time_ms.

Time to fetch optimizer trace-

set optimizer_trace='enabled=on';
 
Query OK, 0 rows affected (0.000 sec)
 
 
 
SELECT COUNT(DISTINCT (c0)) FROM autoinc;
 
+----------------------+
 
| COUNT(DISTINCT (c0)) |
 
+----------------------+
 
|                99552 |
 
+----------------------+
 
1 row in set (0.026 sec)
 
 
 
select * from information_schema.optimizer_trace limit 1\G
 
*************************** 1. row ***************************
 
                            QUERY: SELECT COUNT(DISTINCT (c0)) FROM autoinc
 
                            TRACE: {
 
  "steps": [
 
    {
 
      "join_preparation": {
 
        "select_id": 1,
 
        "steps": [
 
          {
 
            "expanded_query": "select count(distinct autoinc.c0) AS `COUNT(DISTINCT (c0))` from autoinc"
 
          }
 
        ]
 
      }
 
    },
 
    {
 
      "join_optimization": {
 
        "select_id": 1,
 
        "steps": [
 
          {
 
            "table_dependencies": [
 
              {
 
                "table": "autoinc",
 
                "row_may_be_null": false,
 
                "map_bit": 0,
 
                "depends_on_map_bits": []
 
              }
 
            ]
 
          },
 
          {
 
            "rows_estimation": [
 
              {
 
                "table": "autoinc",
 
                "range_analysis": {
 
                  "table_scan": {
 
                    "rows": 99552,
 
                    "cost": 20137.4
 
                  },
 
                  "potential_range_indexes": [
 
                    {
 
                      "index": "PRIMARY",
 
                      "usable": true,
 
                      "key_parts": ["c0"]
 
                    },
 
                    {
 
                      "index": "k_c1",
 
                      "usable": true,
 
                      "key_parts": ["c1", "c0"]
 
                    },
 
                    {
 
                      "index": "k_c2",
 
                      "usable": true,
 
                      "key_parts": ["c2", "c1", "c0"]
 
                    },
 
                    {
 
                      "index": "k_c3",
 
                      "usable": true,
 
                      "key_parts": ["c3", "c2", "c1", "c0"]
 
                    }
 
                  ],
 
                  "best_covering_index_scan": {
 
                    "index": "k_c1",
 
                    "cost": 19995.37599,
 
                    "chosen": true
 
                  },
 
                  "group_index_range": {
 
                    "potential_group_range_indexes": [
 
                      {
 
                        "index": "PRIMARY",
 
                        "covering": true,
 
                        "usable": false,
 
                        "cause": "using unique index"
 
                      },
 
                      {
 
                        "index": "k_c1",
 
                        "covering": true
 
                      },
 
                      {
 
                        "index": "k_c2",
 
                        "covering": true
 
                      },
 
                      {
 
                        "index": "k_c3",
 
                        "covering": true
 
                      }
 
                    ]
 
                  }
 
                }
 
              }
 
            ]
 
          },
 
          {
 
            "considered_execution_plans": [
 
              {
 
                "plan_prefix": [],
 
                "table": "autoinc",
 
                "best_access_path": {
 
                  "considered_access_paths": [
 
                    {
 
                      "access_type": "scan",
 
                      "resulting_rows": 99552,
 
                      "cost": 225,
 
                      "chosen": true
 
                    }
 
                  ],
 
                  "chosen_access_method": {
 
                    "type": "scan",
 
                    "records": 99552,
 
                    "cost": 225,
 
                    "uses_join_buffering": false
 
                  }
 
                },
 
                "rows_for_plan": 99552,
 
                "cost_for_plan": 20135.4
 
              }
 
            ]
 
          },
 
          {
 
            "best_join_order": ["autoinc"]
 
          },
 
          {
 
            "attaching_conditions_to_tables": {
 
              "attached_conditions_computation": [],
 
              "attached_conditions_summary": [
 
                {
 
                  "table": "autoinc",
 
                  "attached": null
 
                }
 
              ]
 
            }
 
          }
 
        ]
 
      }
 
    },
 
    {
 
      "join_execution": {
 
        "select_id": 1,
 
        "steps": []
 
      }
 
    }
 
  ]
 
}
 
MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0
 
          INSUFFICIENT_PRIVILEGES: 0
 
1 row in set (0.001 sec)
 
 
 
SELECT COUNT(DISTINCT (c1)) FROM autoinc;
 
+----------------------+
 
| COUNT(DISTINCT (c1)) |
 
+----------------------+
 
|                99552 |
 
+----------------------+
 
1 row in set (0.013 sec)
 
 
 
select * from information_schema.optimizer_trace limit 1\G
 
*************************** 1. row ***************************
 
                            QUERY: SELECT COUNT(DISTINCT (c1)) FROM autoinc
 
                            TRACE: {
 
  "steps": [
 
    {
 
      "join_preparation": {
 
        "select_id": 1,
 
        "steps": [
 
          {
 
            "expanded_query": "select count(distinct autoinc.c1) AS `COUNT(DISTINCT (c1))` from autoinc"
 
          }
 
        ]
 
      }
 
    },
 
    {
 
      "join_optimization": {
 
        "select_id": 1,
 
        "steps": [
 
          {
 
            "table_dependencies": [
 
              {
 
                "table": "autoinc",
 
                "row_may_be_null": false,
 
                "map_bit": 0,
 
                "depends_on_map_bits": []
 
              }
 
            ]
 
          },
 
          {
 
            "rows_estimation": [
 
              {
 
                "table": "autoinc",
 
                "range_analysis": {
 
                  "table_scan": {
 
                    "rows": 99552,
 
                    "cost": 20137.4
 
                  },
 
                  "potential_range_indexes": [
 
                    {
 
                      "index": "PRIMARY",
 
                      "usable": false,
 
                      "cause": "not applicable"
 
                    },
 
                    {
 
                      "index": "k_c1",
 
                      "usable": true,
 
                      "key_parts": ["c1", "c0"]
 
                    },
 
                    {
 
                      "index": "k_c2",
 
                      "usable": true,
 
                      "key_parts": ["c2", "c1", "c0"]
 
                    },
 
                    {
 
                      "index": "k_c3",
 
                      "usable": true,
 
                      "key_parts": ["c3", "c2", "c1", "c0"]
 
                    }
 
                  ],
 
                  "best_covering_index_scan": {
 
                    "index": "k_c1",
 
                    "cost": 19995.37599,
 
                    "chosen": true
 
                  },
 
                  "group_index_range": {
 
                    "potential_group_range_indexes": [
 
                      {
 
                        "index": "k_c1",
 
                        "covering": true,
 
                        "rows": 99553,
 
                        "cost": 24961.25
 
                      },
 
                      {
 
                        "index": "k_c2",
 
                        "covering": true
 
                      },
 
                      {
 
                        "index": "k_c3",
 
                        "covering": true
 
                      }
 
                    ],
 
                    "index_scan": true
 
                  },
 
                  "best_group_range_summary": {
 
                    "type": "index_group",
 
                    "index": "k_c1",
 
                    "min_max_arg": null,
 
                    "min_aggregate": false,
 
                    "max_aggregate": false,
 
                    "distinct_aggregate": true,
 
                    "rows": 99553,
 
                    "cost": 0,
 
                    "key_parts_used_for_access": ["c1"],
 
                    "ranges": [],
 
                    "chosen": true
 
                  },
 
                  "chosen_range_access_summary": {
 
                    "range_access_plan": {
 
                      "type": "index_group",
 
                      "index": "k_c1",
 
                      "min_max_arg": null,
 
                      "min_aggregate": false,
 
                      "max_aggregate": false,
 
                      "distinct_aggregate": true,
 
                      "rows": 99553,
 
                      "cost": 0,
 
                      "key_parts_used_for_access": ["c1"],
 
                      "ranges": []
 
                    },
 
                    "rows_for_plan": 99553,
 
                    "cost_for_plan": 0,
 
                    "chosen": true
 
                  }
 
                }
 
              }
 
            ]
 
          },
 
          {
 
            "considered_execution_plans": [
 
              {
 
                "plan_prefix": [],
 
                "table": "autoinc",
 
                "best_access_path": {
 
                  "considered_access_paths": [
 
                    {
 
                      "access_type": "index_merge",
 
                      "resulting_rows": 99553,
 
                      "cost": 0,
 
                      "chosen": true
 
                    }
 
                  ],
 
                  "chosen_access_method": {
 
                    "type": "index_merge",
 
                    "records": 99553,
 
                    "cost": 0,
 
                    "uses_join_buffering": false
 
                  }
 
                },
 
                "rows_for_plan": 99553,
 
                "cost_for_plan": 19910.6
 
              }
 
            ]
 
          },
 
          {
 
            "best_join_order": ["autoinc"]
 
          },
 
          {
 
            "attaching_conditions_to_tables": {
 
              "attached_conditions_computation": [],
 
              "attached_conditions_summary": [
 
                {
 
                  "table": "autoinc",
 
                  "attached": null
 
                }
 
              ]
 
            }
 
          }
 
        ]
 
      }
 
    },
 
    {
 
      "join_execution": {
 
        "select_id": 1,
 
        "steps": []
 
      }
 
    }
 
  ]
 
}
 
MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0
 
          INSUFFICIENT_PRIVILEGES: 0
 
1 row in set (0.001 sec)

As a quick note, I also tried 11.2.2 to see if the 11.x optimizer might address the issue. It does not seem to (it was actually averaging a little slower than 10.6.16).

Comment by Oleg Smirnov [ 2023-12-22 ]

rob.schwyzer@mariadb.com, so the question is why SELECT COUNT(DISTINCT(c0)) uses index k_c1 instead of PRIMARY and performs slower than other queries , right?

Given it's InnoDB, the primary key on c0 is a clustered index, i.e. it's the table autoinc itself. We can compare the sizes occupied by the indexes on disk and see that PRIMARY is more than 2 times larger than k_c1, k_c2 or k_c3:

MariaDB [test]> SELECT database_name, table_name, index_name, ROUND(stat_value * @@innodb_page_size / 1024 / 1024, 2) size_in_mb FROM mysql.innodb_index_stats WHERE table_name= 'autoinc' and stat_name = 'size';
 
+---------------+------------+------------+------------+
 
| database_name | table_name | index_name | size_in_mb |
 
+---------------+------------+------------+------------+
 
| test          | autoinc    | PRIMARY    |       3.52 |
 
| test          | autoinc    | k_c1       |       1.52 |
 
| test          | autoinc    | k_c2       |       1.52 |
 
| test          | autoinc    | k_c3       |       1.52 |
 
+---------------+------------+------------+------------+
 
4 rows in set (0.002 sec)

If we look at the output of EXPLAIN we'll see "access_type": "index" which means the whole index file is read to perform an operation. The optimizer makes a correct decision to read 1.52 Mb instead of 3.52 Mb, and it can be tested by forcing the index usage:

MariaDB [test]> SELECT COUNT(DISTINCT (c0)) FROM autoinc;
 
+----------------------+
 
| COUNT(DISTINCT (c0)) |
 
+----------------------+
 
|               100000 |
 
+----------------------+
 
1 row in set (0.180 sec)
 
 
 
MariaDB [test]> SELECT COUNT(DISTINCT (c0)) FROM autoinc FORCE INDEX(PRIMARY);
 
+----------------------+
 
| COUNT(DISTINCT (c0)) |
 
+----------------------+
 
|               100000 |
 
+----------------------+
 
1 row in set (0.182 sec)

The performance of using the PRIMARY key is slightly worse.

Why it's possible to use a secondary index to SELECT COUNT(DISTINCT(<primary-key>)): because secondary indexes in InnoDB contain references to the primary (clustered) index, so all values of the primary key are present in the secondary key (see https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html).

Now let's look at the SELECTs on column c1, they really perform better than SELECTs on column c0:

MariaDB [test]> SELECT COUNT(DISTINCT (c1)) FROM autoinc;
 
+----------------------+
 
| COUNT(DISTINCT (c1)) |
 
+----------------------+
 
|               100000 |
 
+----------------------+
 
1 row in set (0.159 sec)
 
 
 
MariaDB [test]> SELECT COUNT(DISTINCT (c0)) FROM autoinc;
 
+----------------------+
 
| COUNT(DISTINCT (c0)) |
 
+----------------------+
 
|               100000 |
 
+----------------------+
 
1 row in set (0.183 sec)

It makes sense after examining the EXPLAIN which shows a more efficient access method "Using index for group-by (scanning)":

MariaDB [test]> EXPLAIN SELECT COUNT(DISTINCT (c1)) FROM autoinc;
 
+------+-------------+---------+-------+---------------+------+---------+------+--------+-------------------------------------+
 
| id   | select_type | table   | type  | possible_keys | key  | key_len | ref  | rows   | Extra                               |
 
+------+-------------+---------+-------+---------------+------+---------+------+--------+-------------------------------------+
 
|    1 | SIMPLE      | autoinc | range | NULL          | k_c1 | 5       | NULL | 100001 | Using index for group-by (scanning) |
 
+------+-------------+---------+-------+---------------+------+---------+------+--------+-------------------------------------+
 
1 row in set (0.001 sec)

"Using index for group-by" means the "Loose index scan" optimization (https://dev.mysql.com/doc/refman/5.7/en/group-by-optimization.html#loose-index-scan) allowing to reduce the amount of data read from the index file and thus improving the performance.

If I'm answering a wrong question, please clarify what is the actual one.

Comment by Rob Schwyzer [ 2023-12-22 ]

No problem.

I think the easiest question to consider at this point is looking at ANALYZE FORMAT=JSON from SELECT COUNT(DISTINCT (c0)) FROM autoinc\G versus SELECT COUNT(DISTINCT (c1)) FROM autoinc\G. When we look at the output, we see-

c0

ANALYZE: {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 26.571,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "index",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "r_loops": 1,
 
      "rows": 99552,
 
      "r_rows": 99552,
 
      "r_table_time_ms": 9.085,
 
      "r_other_time_ms": 17.481,
 
      "r_engine_stats": {
 
        "pages_accessed": 112
 
      },
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}

c1

ANALYZE: {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 16.603,
 
    "table": {
 
      "table_name": "autoinc",
 
      "access_type": "range",
 
      "key": "k_c1",
 
      "key_length": "5",
 
      "used_key_parts": ["c1"],
 
      "r_loops": 1,
 
      "rows": 99553,
 
      "r_rows": 99552,
 
      "r_table_time_ms": 9.27,
 
      "r_other_time_ms": 7.328,
 
      "r_engine_stats": {
 
        "pages_accessed": 114
 
      },
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index_for_group_by": "scanning"
 
    }
 
  }
 
}

The c0 variant follows your logic for why "key": "k_c1" is better and as expected, "used_key_parts": ["c1"]. However, it significantly underperforms the c1 variant which makes the same selections there, but it executes differently by using "access_type": "range" instead of "access_type": "index", and in filtering it uses "using_index_for_group_by": "scanning" instead of "using_index": true.

I'm guessing since c1 here is not UNIQUE, when querying on c0, it is having to cross-reference from c1 to c0 and that is what is taking the extra time.

But in diving deeper into all of that, I think we're getting away from what the original question was.

So in its most basic form, the original question is thus:

Given an identifiable column constraint (ala PRIMARY KEY or UNIQUE) which nullifies the use of DISTINCT, why is MariaDB not recognizing that and using a branch to avoid the labor of DISTINCT? While the obvious answer here is to not use DISTINCT when you don't need it, many of our customers rely on automation tools which execute queries like these on each of their columns.

While we could sit here and ask why those tools don't apply logic-gating on the use of DISTINCT, what's being asked is why MariaDB does not do this foremost. So the easiest demonstration is the below-

 mdb countdistinct -e 'ANALYZE FORMAT=JSON SELECT COUNT(c0) FROM autoinc\G'
 
*************************** 1. row ***************************
 
ANALYZE: {
 
  "query_optimization": {
 
    "r_total_time_ms": 0.168676081
 
  },
 
  "query_block": {
 
    "select_id": 1,
 
    "cost": 14.65909515,
 
    "r_loops": 1,
 
    "r_total_time_ms": 20.50112296,
 
    "nested_loop": [
 
      {
 
        "table": {
 
          "table_name": "autoinc",
 
          "access_type": "index",
 
          "key": "k_c1",
 
          "key_length": "5",
 
          "used_key_parts": ["c1"],
 
          "loops": 1,
 
          "r_loops": 1,
 
          "rows": 99471,
 
          "r_rows": 99471,
 
          "cost": 14.65909515,
 
          "r_table_time_ms": 15.50811789,
 
          "r_other_time_ms": 4.977360511,
 
          "r_engine_stats": {
 
            "pages_accessed": 110
 
          },
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        }
 
      }
 
    ]
 
  }
 
}
 
mdb countdistinct -e 'ANALYZE FORMAT=JSON SELECT COUNT(DISTINCT(c0)) FROM autoinc\G'
 
*************************** 1. row ***************************
 
ANALYZE: {
 
  "query_optimization": {
 
    "r_total_time_ms": 0.190777287
 
  },
 
  "query_block": {
 
    "select_id": 1,
 
    "cost": 14.65909515,
 
    "r_loops": 1,
 
    "r_total_time_ms": 41.68516362,
 
    "nested_loop": [
 
      {
 
        "table": {
 
          "table_name": "autoinc",
 
          "access_type": "index",
 
          "key": "k_c1",
 
          "key_length": "5",
 
          "used_key_parts": ["c1"],
 
          "loops": 1,
 
          "r_loops": 1,
 
          "rows": 99471,
 
          "r_rows": 99471,
 
          "cost": 14.65909515,
 
          "r_table_time_ms": 14.78131832,
 
          "r_other_time_ms": 26.89157467,
 
          "r_engine_stats": {
 
            "pages_accessed": 110
 
          },
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        }
 
      }
 
    ]
 
  }
 
}

The above query plans are identical and the output of the queries is identical, but the one with DISTINCT takes over 20ms longer thanks to r_other_time_ms which is ostensibly spent processing DISTINCT. Why not check if the column is PRIMARY KEY or UNIQUE which in turn make DISTINCT unnecessary to process and, accordingly, skip processing DISTINCT here?

Comment by Sergei Petrunia [ 2024-01-12 ]

Take-aways from Slack discussion:

The SELECT COUNT(DISTINCT(c0)) query does de-duplication:
https://gist.github.com/spetrunia/6a93a7ce5cfedf253dfa0ce22d22fb62

That is, it puts the values of c0 into a Unique object.

The query SELECT COUNT(DISTINCT(c1)) doesn't do de-duplication. It is handled by Loose Scan:

 "using_index_for_group_by": "scanning"

and prepare_sum_aggregators() disables de-duplication if Loose Scan is used.

The DISTINCT(c0) query is not handed by LooseScan because c0 is a distinct column already.

Comment by Oleg Smirnov [ 2024-01-18 ]

The following commit was made in bb-10.6-MDEV-30660:

    MDEV-30660 COUNT DISTINCT seems unnecessarily slow when run on a PK
 
    
    If we have a statement like SELECT AGGFN(DISTINCT c1, c2,..,cn) FROM t1,
 
    where AGGFN is an aggregate function like COUNT(), AVG(), SUM(),
 
    and there is a unique index on table t1 including all columns (c1, c2,..,cn),
 
    the values retrieved from the table are guaranteed to be unique.
 
    So we can optimize aggregation and avoid de-duplicating of values,
 
    in other words - ignore the DISTINCT clause.
 
    The restrictions are:
 
      - only one table involved in the join
 
      - all arguments of the aggregate function are fields
 
            (not functions/subqueries)

Comment by Oleg Smirnov [ 2024-01-18 ]

psergei, can you please review the PR? Now it's targeted against 10.6 but I can re-target it against 10.4 or 10.5. I don't think this should be done against 10.4 since we're closing to the EOL of that version but 10.5 might make sense.

Comment by Sergei Petrunia [ 2024-02-06 ]

(Note to self: The patch doesn't work with Item_func_group_concat because it returns with_distinct()==false. Item_func_group_concat has and uses {{Item_func_group_concat::with_distinct for some reason...

Comment by Sergei Petrunia [ 2024-02-06 ] 

CREATE TABLE `t10` (
 
  `a` int(11) NOT NULL,
 
  `b` int(11) DEFAULT NULL,
 
  PRIMARY KEY (`a`)
 
);
 
insert into t10 values (1,10),(2,10),(3,10);
 
create view v10 as select * from t10;


set optimizer_trace=1;
 
explain format=json select count(distinct a,b) from t10;
 
select json_pretty(json_extract(trace, '$**.prepare_sum_aggregators'))
 
from information_schema.optimizer_trace;

This shows 

        "type of aggregator": "simple"

Now, the same through a VIEW:

explain format=json select count(distinct a,b) from v10;
 
select json_pretty(json_extract(trace, '$**.prepare_sum_aggregators'))
 
from information_schema.optimizer_trace;

this shows

        "type of aggregator": "distinct"

Need to add real_item() calls before checking for Item_fields...

Comment by Sergei Petrunia [ 2024-02-06 ]

GROUP_CONCAT is interesting...

Take the dataset from above and run:

explain format=json select group_concat(distinct b) from t10;

it prints

        "function": "group_concat(distinct t10.b separator ',')",
 
        "type of aggregator": "simple"

which seems wrong as t10.b is not part of PK and has duplicates.

But the query output doesn't have duplicates. It turns out that Item_func_group_concat::add does its own duplicate removal.

Item_func_group_concat has an aggregator but it is always Aggregator_simple.

The query output is correct but the trace looks misleading.
I suggest to add 

virtual bool uses_aggregator_for_distinct(){ return true}

in Item_sum and overload it in Item_func_group_concat and print the output accordingly.

Note that JSON aggregate functions are also derived from Item_func_group_concat.

Comment by Sergei Petrunia [ 2024-02-06 ]

Review input provided in the https://github.com/MariaDB/server/pull/3012.

Generated at Thu Feb 08 10:17:55 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.