2

次のMySQLクエリの理論的なBig-O分析に興味があります。

SELECT id, value FROM MyTable WHERE lat BETWEEN %s AND %s AND lon BETWEEN %s AND %s;

特に、BETWEEN句がこのクエリの複雑さにどのように影響するかを知りたいです。

MySQLのバージョンは5.1です

MyTableの定義：

CREATE TABLE MyTable (
    id VARCHAR(255) NOT NULL UNIQUE, \
    value DECIMAL(12,9) NOT NULL, \
    lat DECIMAL(9,6), \
    lon DECIMAL(9,6), \
PRIMARY KEY(id(50)), \
INDEX(lat, lon)) ENGINE=InnoDB;

Describe MyTable;
+----------+---------------------+------+-----+---------+-------+
| Field    | Type                | Null | Key | Default | Extra |
+----------+---------------------+------+-----+---------+-------+
| id       | varchar(255)        | NO   | PRI | NULL    |       |
| value    | decimal(12,9)       | NO   |     | NULL    |       |
| lat      | decimal(9,6)        | YES  | MUL | NULL    |       |
| lon      | decimal(9,6)        | YES  |     | NULL    |       |
+----------+---------------------+------+-----+---------+-------+

EXPLAIN EXTENDED SELECT id, value FROM MyTable WHERE lat BETWEEN '40' AND '60' AND lon BETWEEN '-10' AND '10';
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | MyTable    | ALL  | lat           | NULL | NULL    | NULL |    7 |    42.86 | Using where |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
4

1 に答える 1

4

type = ALLこれは、このクエリがテーブルに対してフルスキャンを実行することを意味します。key = NULLインデックスが使用されていないことを意味します。この場合はO(n)、です。ここnで、は行数です。

については、2つの比較操作（および）BETWEENを実行するのと同じです。それらがインデックス（MySQLのBツリー）で実行される場合、それは平均的な場合と最悪の場合の両方です。B-Treeは値を順番に格納するため、範囲検索などは非常に高速です。>=<=O(log n)

セカンダリインデックスについて知っているように、InnoDBはプライマリIDをセカンダリインデックス値と一緒に格納するため、SELECT id FROM MyTable WHERE lat ... AND lon ...（のみを選択してid）保存すると、実際の行の内部を見ることさえできません。

詳細はこちら：

あなたの場合、latフィールドとlonフィールドに（別々に）インデックスを設定し、データに最適な実験を行うことをお勧めします。おそらく、インデックスを高速化するために、ルーティングされたlat値とlon値（SMALL INTとして）を含むフィールドを追加する価値があります。その場合、そのフィールドに複数列のインデックスを追加できます。

于 2012-06-12T14:17:00.950 に答える