やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

📌 ？
トップ > SQLite3 > SQLite3学習　R-Treeモジュール

SQLite3学習　R-Treeモジュール

SQLite3

　指定した空間座標に含まれるレコードを取得する。

成果物

R-Treeモジュール

　Rツリーは範囲クエリを実行するために設計された特別なインデックスである。X,Y座標をもった長方形の空間システムで最も使用される。長方形内に含まれるか重なるエントリを検索できるなど。

テーブル作成構文

CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);

CREATE VIRTUAL TABLE <name> USING rtree_i32(<column-names>);
Rツリー種別 型
rtree 単精度(4Byte)浮動小数点
rtree_i32 32bit(4Byte)符号付き整数

　たとえば2次元空間なら以下。

CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);

　自動的にいくつかのテーブルが作成される。これらはシャドーテーブルである。

.tables
demo_index         demo_index_parent
demo_index_node    demo_index_rowid

シャドーテーブルのスキーマ

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)

挿入

INSERT INTO demo_index VALUES(
    1,                   -- Primary key -- SQLite.org headquarters
    -80.7749, -80.7747,  -- Longitude range
    35.3776, 35.3778     -- Latitude range
);
INSERT INTO demo_index VALUES(
    2,                   -- NC 12th Congressional District in 2010
    -81.0, -79.6,
    35.0, 36.2
);

取得

SELECT * FROM demo_index WHERE id=1;

1|-80.77490234375|-80.7746963500977|35.3775939941406|35.3778038024902

　含まれるidを取得。

SELECT id FROM demo_index
 WHERE minX>=-81.08 AND maxX<=-80.58
   AND minY>=35.00  AND maxY<=35.44;

1

　重なるidを取得。

SELECT id FROM demo_index
 WHERE maxX>=-81.08 AND minX<=-80.58
   AND maxY>=35.00  AND minY<=35.44;

1
2

　範囲が小さいほうが速い。

SELECT id FROM demo_index
 WHERE maxY>=35.0  AND minY<=35.0;

2

効果的な使用

　Rツリーの長方形で大雑把に抽出した後は、より詳細な図形による判定をすることができる。

　たとえば以下のような補助テーブルを作成する。

CREATE TABLE demo_data(
  id INTEGER PRIMARY KEY,  -- primary key
  objname TEXT,            -- name of the object
  objtype TEXT,            -- object type
  boundary BLOB            -- detailed boundary of object
);

　以下のように2工程に分けることで高速に検索できる。

  1. 長方形で大雑把に抽出
  2. 抽出されたレコードに対して、より詳細に判定するcontained_in()
SELECT objname FROM demo_data, demo_index
 WHERE demo_data.id=demo_index.id
   AND contained_in(demo_data.boundary, :boundary)
   AND minX>=-81.0 AND maxX<=-79.6
   AND minY>=35.0 AND maxY>=36.2;

　以下のように長方形判定せずとも同じ結果を得られる。だが、詳細判定をするレコード数が多いため処理に時間がかかる。

SELECT objname FROM demo_data
 WHERE contained_in(demo_data.boundary, :boundary);

補助列

　SQLiteバージョン3.24.0（2018-06-04）以降、rツリーテーブルには、任意のデータを格納する補助列を含めることができる。demo_dataなどのセカンダリテーブルの代わりに、補助列を使用できる。列名の前に+を付与することで。

CREATE VIRTUAL TABLE demo_index2 USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY,      -- Minimum and maximum Y coordinate
   +objname TEXT,   -- name of the object
   +objtype TEXT,   -- object type
   +boundary BLOB   -- detailed boundary of object
);

　補助列を使えば、セカンダリテーブルとの結合が不要になる。よって以下のようなクエリで補助データを取得できる。

SELECT objname FROM demo_index2
 WHERE contained_in(boundary, :boundary)
   AND minX>=-81.0 AND maxX<=-79.6
   AND minY>=35.0 AND maxY>=36.2;

やってみる

create virtual table map using rtree_i32(id,minX,maxX,minY,maxY);
insert into map values(1,0,1,0,1);
insert into map values(2,3,5,3,5);

select id 
from map 
where -1<minX and maxX<10 and -1<minY and maxY<10;

1
2
select id 
from map 
where -1<minX and maxX<5 and -1<minY and maxY<5;

1
select id 
from map 
where 2<minX and maxX<6 and 2<minY and maxY<6;

2
select id 
from map 
where 2<minX and maxX<4 and 2<minY and maxY<4;







          |    +------+(5,5)
          |    |2     |
          |    |      |
          |    +------+
          |
          +-+
          |1|
----------+-+---------- X
     (0,0)|
          Y




情報源






対象環境






$ uname -a
Linux raspberrypi 4.19.42-v7+ #1218 SMP Tue May 14 00:48:17 BST 2019 armv7l GNU/Linux





前回まで