SQLite R*Tree: Konumsal İndeks ve Aralık Sorguları

Tablo yapısı

Her R*Tree tablosu 3 ile 11 arasında tek sayıda sütun içerir. İlk sütun her zaman 64 bit işaretli tamsayı birincil anahtardır; sonraki sütunlar her boyut için bir en küçük ve bir en büyük değer çiftidir. Bir boyutlu tablo 3, iki boyutlu 5, üç boyutlu 7 sütundur ve belgelere göre en fazla 5 boyut desteklenir. Tablo oluşturulduğunda içeriği tutan üç gölge tablo da oluşur: _node, _parent ve _rowid. Belgeler bu tabloları değiştirmenin dizini bozacağını, en iyisinin onları yok saymak olduğunu belirtir.

Aşağıdaki örnekte bir koordinat düzleminde beş kurgusal parsel tanımlıyoruz. Sayılar yalnızca örnek içindir; gerçek bir uygulamada boylam ve enlem, metre cinsinden harita koordinatları veya başka bir birim olabilir.

CREATE VIRTUAL TABLE parsel USING rtree(id, minX, maxX, minY, maxY);
INSERT INTO parsel VALUES
  (1,  0, 10,  0, 10),
  (2,  8, 20,  5, 15),
  (3, 30, 40, 30, 40),
  (4, 12, 18, 12, 18),
  (5, 50, 60,  0,  5);

-- (9, 7) noktasını içeren kutular
SELECT id FROM parsel
 WHERE minX <= 9 AND maxX >= 9 AND minY <= 7 AND maxY >= 7 ORDER BY id;
-- çıktı:
-- 1
-- 2

Sütun adlarına dikkat edin: belgelere göre R*Tree, her argümanın yalnızca ilk kelimesini sütun adı olarak alır ve geri kalanını sessizce yok sayar. minX REAL NOT NULL yazmak hata vermez ama hiçbir etkisi de olmaz. rtree tablosunda ilk sütunun eğilimi INTEGER, diğerlerinin REAL'dir. Belgelerin önerisi her argümanı tek bir ad olarak bırakmaktır.

R*Tree her aralık sorgusu için doğru araç değildir. Tek bir sütunda aralık arıyorsanız, örneğin yalnızca tarihe göre filtreliyorsanız, sıradan bir indeks yeterlidir. Koordinatların tam değerini korumanız gerekiyorsa da R*Tree tek başına yetmez: değerler 32 bit kayan nokta olarak saklandığı için özgün değerleri ayrı bir tabloda tutup R*Tree'yi yalnızca adayları daraltmak için kullanın. Belgelerin vurguladığı gibi R*Tree'nin görevi aday kümesini küçültmektir; kesin karşılaştırmayı sonraki adımda siz yaparsınız.

İçerme ve çakışma sorguları

R*Tree herhangi bir SQL sorgusunu çalıştırır, ancak asıl hızı koordinat aralığı koşullarında gösterir. İki temel kalıp vardır. İçerme (contained-within) sorgusu, kutuları bir bölgenin tamamen içinde kalanlarla sınırlar. Çakışma (overlapping) sorgusu ise bir kutuyla en az bir noktası ortak olan kutuları bulur; iki kutu, her eksende birinin en büyüğü diğerinin en küçüğünden büyük ya da eşitse ve tersi de doğruysa çakışır.

-- 2 numaralı parselle çakışan kutular (kendisi dahil)
SELECT A.id FROM parsel AS A, parsel AS B
 WHERE A.maxX >= B.minX AND A.minX <= B.maxX
   AND A.maxY >= B.minY AND A.minY <= B.maxY
   AND B.id = 2 ORDER BY A.id;
-- çıktı:
-- 1
-- 2
-- 4

-- Tamamen (5..25, 0..20) penceresinin içinde kalanlar
SELECT id FROM parsel
 WHERE minX >= 5 AND maxX <= 25 AND minY >= 0 AND maxY <= 20 ORDER BY id;
-- çıktı:
-- 2
-- 4

-- Yalnızca bir eksende kısıt: y = 3 çizgisini kesenler
SELECT id FROM parsel WHERE maxY >= 3 AND minY <= 3 ORDER BY id;
-- çıktı:
-- 1
-- 5

Belgeler, bütün koordinatların kısıtlanmasının şart olmadığını belirtir: son sorgu yalnızca y ekseninde kısıt verdi ve yine dizin kullanıldı. Genel kural, R*Tree modülüne ne kadar çok kısıt ve ne kadar küçük bir kutu verirseniz sonucun o kadar hızlı gelmesidir. Planı görmek için sorgunun başına EXPLAIN QUERY PLAN ekleyin:

EXPLAIN QUERY PLAN
SELECT id FROM parsel WHERE minX <= 9 AND maxX >= 9 AND minY <= 7 AND maxY >= 7;

Denememizde plan satırı SCAN parsel VIRTUAL TABLE INDEX 2:B0D1B2D3 oldu; dört koordinat kısıtı sanal tablo modülüne iletilmişti. Yalnızca id ile yapılan sorguda satır INDEX 1: olarak göründü. Kısıtı minX + 1 <= 9 gibi bir ifadeye çevirdiğimizde ise satır INDEX 2: biçiminde, kısıt listesi boş olarak göründü; yani modül bu koşulu kullanamadı. Plan çıktısını okumanın genel kuralları SQLite EXPLAIN QUERY PLAN yazısında.

Değerlerin saklanması ve kurallar

R*Tree, sıradan SQLite tablolarının esnek tiplerinden farklı olarak saklama tiplerini katı biçimde uygular. Belgelere göre rtree tablolarında koordinatlar 32 bit kayan nokta, rtree_i32 tablolarında 32 bit işaretli tamsayı olarak saklanır; başka tipte bir değer gelirse sessizce dönüştürülür. İlk sütuna NULL eklenirse benzersiz bir anahtar otomatik üretilir, tamsayı olmayan bir değer ise tamsayıya çevrilir. Her boyutta en küçük değerin en büyük değerden büyük olması ise reddedilir:

INSERT INTO parsel VALUES (6, 5, 1, 0, 1);          -- minX > maxX
-- hata: rtree constraint failed: parsel.(minX<=maxX)

INSERT INTO parsel VALUES (NULL, 70, 71, 70, 71);   -- id otomatik verilir
SELECT max(id) FROM parsel;
-- çıktı: 6

INSERT INTO parsel VALUES ('8.9', 1, 2, 1, 2);      -- tamsayıya çevrilir
SELECT id, typeof(id) FROM parsel WHERE minX = 1;
-- çıktı: 8|integer

CREATE VIRTUAL TABLE az USING rtree(id, x);
-- hata: Too few columns for an rtree table
CREATE VIRTUAL TABLE cift USING rtree(id, a, b, c);
-- hata: Wrong number of columns for an rtree table

Yuvarlama ve içerme sorguları

32 bit kayan nokta bütün ondalık sayıları tam olarak gösteremez. Belgelere göre böyle bir durumda alt sınırlar aşağıya, üst sınırlar yukarıya yuvarlanır; kutular biraz büyüyebilir ama asla küçülmez. Aşağıdaki denemede 0,1 değeri bir nokta olarak eklendi, ancak saklanan alt sınır 0,1'den küçük, üst sınır 0,1'den büyük çıktı ve iki değer artık eşit değil:

INSERT INTO parsel VALUES (9, 0.1, 0.1, 0, 0);
SELECT minX < 0.1, maxX > 0.1, minX = maxX FROM parsel WHERE id = 9;
-- çıktı: 1|1|0

Bu yuvarlama çakışma sorguları için tam istenen davranıştır: hiçbir geçerli kayıt kaçırılmaz, yalnızca kenarı sorgu kutusunun kenarıyla aynı olan birkaç fazla kayıt gelebilir. İçerme sorgularında ise tersi olur: kenarı tam sorgu kutusunun kenarına denk gelen bir kayıt, büyüyen kutusu yüzünden sonuçtan çıkabilir. Belgeler bu nedenle içerme sorgularında sorgu kutusunu her boyutta yüzde 0,000012 kadar genişletmeyi, yani alt sınırları biraz aşağı, üst sınırları biraz yukarı yuvarlamayı önerir.

Yardımcı sütunlar

3.24.0 sürümünden önce R*Tree tablosu yalnızca kimlik ve sınır kutusunu saklayabiliyordu; ad, tür gibi bilgiler ayrı bir tabloda tutulup kimlikle birleştiriliyordu. Belgelere göre 3.24.0 ile yardımcı sütunlar geldi: adının önüne + yazılan sütunlar herhangi bir veriyi tutabilir ve bütün koordinat sütunlarından sonra gelmelidir. Bir tablonun birincil anahtar, koordinatlar ve yardımcı sütunlar dahil en fazla 100 sütunu olabilir.

CREATE VIRTUAL TABLE magaza USING rtree(
  id,
  minX, maxX, minY, maxY,
  +ad, +tur                    -- yardımcı sütunlar
);
INSERT INTO magaza VALUES
  (1,  3,  3, 4, 4, 'Merkez Şube', 'şube'),
  (2,  7,  7, 1, 1, 'Depo A', 'depo'),
  (3, 15, 15, 9, 9, 'Sahil Şube', 'şube'),
  (4,  4,  4, 6, 6, 'Kiosk 1', 'kiosk');

-- (5, 5) çevresindeki 3 birimlik karede bulunan noktalar, uzaklık karesine göre
SELECT id, ad, (minX - 5) * (minX - 5) + (minY - 5) * (minY - 5) AS uzaklik2
  FROM magaza
 WHERE minX >= 2 AND maxX <= 8 AND minY >= 2 AND maxY <= 8
 ORDER BY uzaklik2;
-- çıktı:
-- 4|Kiosk 1|2.0
-- 1|Merkez Şube|5.0

SELECT sql FROM sqlite_schema WHERE name = 'magaza_rowid';
-- çıktı: CREATE TABLE "magaza_rowid"(rowid INTEGER PRIMARY KEY,nodeno,a0,a1)

Örnek, R*Tree'nin önemli bir özelliğini de gösteriyor. Belgelerin vurguladığı gibi R*Tree çoğu zaman kesin yanıtı vermez; aday kümesini milyonlardan düzinelere indirir. Kare bir pencereyle aday noktaları bulduktan sonra gerçek uzaklık koşulunu veya sıralamayı sıradan SQL ifadeleriyle uygularız. Yardımcı sütunların değerleri _rowid gölge tablosuna eklenen sütunlarda saklanır; belgeler bu sütunların adlarının sizin verdiğiniz adlarla aynı olmayabileceğini belirtir.

Yardımcı sütunlarda yalnızca ad önemlidir. Belgelere göre tip eğilimi ve NOT NULL, UNIQUE, REFERENCES, CHECK gibi kısıtlar yok sayılır; gelecekteki sürümler bunları dikkate almaya başlayabileceği için ikisini de boş bırakmanız önerilir. Kısıt gerekiyorsa bilgiyi sıradan bir tabloda tutun.

rtree_i32 ve zaman aralıkları

R*Tree yalnızca harita için değildir. Belgeler, çok sayıda etkinliğin başlangıç ve bitiş zamanını tutan bir tabloda belirli bir aralıkta süren, o aralıkta başlayan ya da tamamen o aralık içinde kalan etkinlikleri bulmayı da örnek kullanım olarak sayar. Bir boyutlu bir R*Tree bu iş için yeterlidir. Tamsayı koordinatlar istiyorsanız tabloyu rtree_i32 ile oluşturun; belgelere göre bu tablo değerleri tamsayı saklasa da algoritmanın içinde kayan nokta hesaplaması kullanır.

CREATE VIRTUAL TABLE etkinlik USING rtree_i32(id, baslangic, bitis);
INSERT INTO etkinlik VALUES (1, 900, 1030), (2, 1000, 1200), (3, 1300, 1400), (4, 1145, 1315);

-- 12:00 ile 12:30 arasında herhangi bir anda süren etkinlikler
SELECT id FROM etkinlik WHERE baslangic <= 1230 AND bitis >= 1200 ORDER BY id;
-- çıktı:
-- 2
-- 4

-- Tamamen 10:00 ile 14:00 arasında başlayıp biten etkinlikler
SELECT id FROM etkinlik WHERE baslangic >= 1000 AND bitis <= 1400 ORDER BY id;
-- çıktı:
-- 2
-- 3
-- 4

INSERT INTO etkinlik VALUES (5, 10.7, 20.2);
SELECT baslangic, bitis, typeof(baslangic) FROM etkinlik WHERE id = 5;
-- çıktı: 10|20|integer

Burada saatleri SSDD biçiminde tamsayı olarak yazdık. Gerçek bir uygulamada Unix zaman damgası gibi tek bir sayısal ölçek daha uygundur; ancak rtree_i32 32 bitlik işaretli tamsayı sakladığı için değer aralığını bu sınıra göre seçmeniz gerekir. Zaman değerlerini sayıya çevirmek için SQLite tarih ve saat fonksiyonları yazısındaki unixepoch() ve julianday() fonksiyonlarına bakabilirsiniz. Son satırda ondalık değerlerin tamsayıya çevrildiğini görüyorsunuz.

Sıradan tablolarla birleştirme

Yardımcı sütunlar yetmediğinde veya bilgi zaten başka bir tabloda durduğunda, R*Tree tablosunu birincil anahtar üzerinden sıradan bir tabloyla birleştirirsiniz. Belgelerdeki örnekte de R*Tree dış döngüde çalışarak aday satırları bulur, ardından her aday için diğer tablodaki kayda bakılır ve pahalı koşul yalnızca bu adaylara uygulanır.

CREATE TABLE tesis(id INTEGER PRIMARY KEY, ad TEXT, kapasite INTEGER);
INSERT INTO tesis VALUES (1, 'Merkez Şube', 40), (2, 'Depo A', 500),
                         (3, 'Sahil Şube', 25), (4, 'Kiosk 1', 2);

SELECT t.ad, t.kapasite
  FROM magaza AS m JOIN tesis AS t ON t.id = m.id
 WHERE m.minX <= 10 AND m.maxX >= 0 AND m.minY <= 10 AND m.maxY >= 0
   AND t.kapasite > 10
 ORDER BY t.id;
-- çıktı:
-- Merkez Şube|40
-- Depo A|500

JOIN türleri ve birleştirme sırası hakkında ayrıntılı bilgi SQLite JOIN türleri yazısında. Daha karmaşık bölgeler, örneğin daire veya çokgen için belgeler MATCH işleciyle kullanılan özel geometri fonksiyonlarını anlatır; bu fonksiyonlar C arayüzüyle kaydedildiği için bu yazının kapsamı dışındadır. Çokgenlerle çalışmak için belgelerde Geopoly modülü de anlatılır; bu modül R*Tree üzerine kurulur, GeoJSON gösterimiyle iki boyutlu basit çokgenleri işler ve SQLITE_ENABLE_GEOPOLY ile etkinleştirilir.

Aynı anda okuma ve yazma

Belgelerin özellikle vurguladığı bir sınır vardır: R*Tree üzerinde süren bir sorgu bitmeden aynı R*Tree'yi değiştirmek genellikle mümkün değildir, çünkü her yazma ağacı baştan düzenleyebilir ve sorgunun tarama sırasını bozabilir. Böyle bir deneme SQLITE_LOCKED ve "database table is locked" hatasıyla sonuçlanır. Örneğin bir sorgunun döndürdüğü her satır için, sorgu hâlâ açıkken aynı tabloya UPDATE göndermek bu hataya yol açabilir. Belgeler, karmaşık sorgu sonuçlarına göre güncelleme yapmanız gerekiyorsa önce sonuçları geçici bir tabloya yazmanızı, ardından güncellemeyi bu tablodan yapmanızı önerir. Bu sınır sıradan tablolar için geçerli değildir. Kilit hatalarının genel nedenleri database is locked hatası yazısında.

Bütünlük denetimi

rtreecheck() fonksiyonu bir R*Tree tablosunun iç tutarlılığını denetler ve sorun yoksa ok, varsa sorunların açıklamasını döndürür. Belgelere göre her hücrede alt sınırın üst sınırdan büyük olmadığını, kök dışındaki hücrelerin üst düğümdeki hücrenin içinde kaldığını ve gölge tablolardaki eşlemelerin eksiksiz olduğunu kontrol eder. Bağlı bir veritabanındaki tablo için rtreecheck('sema', 'tablo') biçimi kullanılır.

SELECT name FROM sqlite_schema WHERE name LIKE 'parsel%' ORDER BY name;
-- çıktı:
-- parsel
-- parsel_node
-- parsel_parent
-- parsel_rowid

SELECT rtreecheck('parsel');
-- çıktı: ok

3.44.0 sürüm notlarına göre PRAGMA integrity_check de R*Tree tablolarının tutarlılığını denetler. Genel bütünlük denetimi ve bozuk dosya kurtarma için bozuk veritabanı kurtarma yazısına bakın.

Sık yapılan hatalar

• Çift sayıda sütun yazmak: Tablo 3 ile 11 arasında tek sayıda sütun ister; aksi hâlde oluşturma hata verir.
• Sütunlara tip ve kısıt eklemek: İlk kelimeden sonrası yok sayılır; kısıt koyduğunuzu sanabilirsiniz.
• Yuvarlamayı unutmak: İçerme sorgularında kenardaki kayıtlar kaçabilir; sorgu kutusunu çok az genişletin.
• Koordinatı ifadeye gömmek: minX + 1 <= 9 gibi koşullar R*Tree tarafından kullanılamaz ve tablo baştan sona taranır.
• Sorgu sürerken aynı tabloyu güncellemek: SQLITE_LOCKED hatası alabilirsiniz; sonuçları önce geçici tabloya yazın.
• Gölge tablolara dokunmak: _node, _parent ve _rowid tablolarını değiştirmek dizini bozar.

Sık Sorulan Sorular

R*Tree mesafe sorgusu yapabilir mi?

Doğrudan "en yakın N nokta" sorgusu sunmaz. Örnekte yaptığımız gibi önce bir kutu penceresiyle adayları bulur, ardından uzaklığı SQL ifadesiyle hesaplayıp sıralarsınız. Pencerenin yeterli aday getirmediği durumda pencereyi büyütürsünüz.

Noktaları nasıl saklarım?

Nokta, en küçük ve en büyük değerleri aynı olan bir kutudur: (id, x, x, y, y). Ondalık koordinatlarda yuvarlama nedeniyle saklanan kutu çok az büyüyebilir; bu çakışma sorgularında sorun çıkarmaz.

R*Tree yerine iki sütuna sıradan indeks koysam olmaz mı?

Tek sütunlu aralık koşulları için sıradan bir indeks yeterli olabilir. İki veya daha fazla eksende aynı anda aralık koşulu verdiğinizde sıradan indeks yetersiz kalır: belgelere göre çok sütunlu bir indekste baştaki sütunlar eşitlikle kısıtlanmalıdır ve eşitsizlik yalnızca kullanılan en sağdaki sütunda olabilir. R*Tree bu tür çok boyutlu sorgular için tasarlanmıştır. İndekslerin genel kullanımı SQLite index oluşturma yazısında.

Uygulama kodundan kullanabilir miyim?

Evet. R*Tree sıradan SQL ile kullanıldığı için her bağlayıcıdan çalışır; yeter ki bağlayıcının içerdiği SQLite derlemesinde modül etkin olsun. Bağlayıcılar için Python sqlite3 ve Node.js node:sqlite yazılarına bakabilirsiniz.

Marka adları sahiplerine aittir. Bu yazı bağımsız bir teknik rehberdir; adı geçen kuruluşlarla bayilik veya ortaklık ilişkisi bulunduğu anlamına gelmez.

İlgili içerikler: SQLite öğrenme rehberi · SQLite index oluşturma · SQLite EXPLAIN QUERY PLAN · SQLite FTS5 tam metin arama · SQLite JOIN türleri