Setup:
Results:
R-tree initial INSERT performance: 9.83088 seconds (1000000 entries) Multiple indexes initial INSERT performance: 13.5020 seconds (1000000 entries) Composite index initial INSERT performance: 5.91520 seconds (1000000 entries) R-tree SELECT performance: 0.22754 seconds (140589 entries) Multiple indexes SELECT performance: 1.75584 seconds (140589 entries) Composite index SELECT performance: 0.68012 seconds (140589 entries) R-tree INSERT performance: 12.7482 seconds (1000000 entries) Multiple indexes INSERT performance: 18.2651 seconds (1000000 entries) Composite index INSERT performance: 9.14901 seconds (1000000 entries) R-tree SELECT performance: 0.59834 seconds (281293 entries) Multiple indexes SELECT performance: 2.43166 seconds (281293 entries) Composite index SELECT performance: 0.45519 seconds (281293 entries) R-tree INSERT performance: 13.8786 seconds (1000000 entries) Multiple indexes INSERT performance: 21.0656 seconds (1000000 entries) Composite index INSERT performance: 11.4523 seconds (1000000 entries) R-tree SELECT performance: 0.95755 seconds (422372 entries) Multiple indexes SELECT performance: 4.74586 seconds (422372 entries) Composite index SELECT performance: 1.63059 seconds (422372 entries) R-tree INSERT performance: 15.3401 seconds (1000000 entries) Multiple indexes INSERT performance: 24.0225 seconds (1000000 entries) Composite index INSERT performance: 12.4100 seconds (1000000 entries) R-tree SELECT performance: 2.32179 seconds (562539 entries) Multiple indexes SELECT performance: 6.79548 seconds (562539 entries) Composite index SELECT performance: 2.13152 seconds (562539 entries) R-tree INSERT performance: 16.5647 seconds (1000000 entries) Multiple indexes INSERT performance: 26.8373 seconds (1000000 entries) Composite index INSERT performance: 10.3546 seconds (1000000 entries) R-tree SELECT performance: 1.70101 seconds (703136 entries) Multiple indexes SELECT performance: 6.64351 seconds (703136 entries) Composite index SELECT performance: 1.63922 seconds (703136 entries) R-tree size: 326.367 MiB Multiple indexes size: 621.426 MiB Composite index size: 499.426 MiB
Source code:
#include <cassert> #include <cstdint> #include <unistd.h> #include <iostream> #include <cstdlib> #include <chrono> #include <filesystem> #include <sqlite3.h> #define SEED (123) #define CYCLES (5) #define DB_A_PATH ("db_a.db") #define DB_B_PATH ("db_b.db") #define DB_C_PATH ("db_c.db") #define ENTRIES_COUNT (1'000'000) #define RANDOM_CHAR ((char)(32 + rand() % 95)) void fill_table(sqlite3 *, int, unsigned, const char *); void view_table(sqlite3 *db, const char *name); int main() { remove(DB_A_PATH); remove(DB_B_PATH); remove(DB_C_PATH); sqlite3 *db; int rc = sqlite3_open(DB_A_PATH, &db); assert(rc == SQLITE_OK); rc = sqlite3_exec( db, "CREATE VIRTUAL TABLE ranges USING rtree(" "id, " "xbegin, " "xend, " "ybegin, " "yend, " "+data1 INTEGER, " "+data2 TEXT" ");", nullptr, nullptr, nullptr ); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED, "R-tree initial"); sqlite3_close(db); rc = sqlite3_open(DB_B_PATH, &db); assert(rc == SQLITE_OK); rc = sqlite3_exec( db, "CREATE TABLE ranges(" "id INTEGER PRIMARY KEY, " "xbegin REAL, " "xend REAL, " "ybegin REAL, " "yend REAL, " "data1 INTEGER, " "data2 TEXT" ");" "CREATE INDEX idx_xbegin ON ranges(xbegin);" "CREATE INDEX idx_xend ON ranges(xend);" "CREATE INDEX idx_ybegin ON ranges(ybegin);" "CREATE INDEX idx_yend ON ranges(yend);", nullptr, nullptr, nullptr ); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED, "Multiple indexes initial"); sqlite3_close(db); rc = sqlite3_open(DB_C_PATH, &db); assert(rc == SQLITE_OK); rc = sqlite3_exec( db, "CREATE TABLE ranges(" "id INTEGER PRIMARY KEY, " "xbegin REAL, " "xend REAL, " "ybegin REAL, " "yend REAL, " "data1 INTEGER, " "data2 TEXT" ");" "CREATE INDEX idx_ranges ON ranges(" "xbegin, " "xend, " "ybegin, " "yend" ");", nullptr, nullptr, nullptr ); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED, "Composite index initial"); sqlite3_close(db); for (int i = 1; i <= CYCLES; ++i) { std::cout << std::endl; rc = sqlite3_open(DB_A_PATH, &db); assert(rc == SQLITE_OK); view_table(db, "R-tree"); sqlite3_close(db); rc = sqlite3_open(DB_B_PATH, &db); assert(rc == SQLITE_OK); view_table(db, "Multiple indexes"); sqlite3_close(db); rc = sqlite3_open(DB_C_PATH, &db); assert(rc == SQLITE_OK); view_table(db, "Composite index"); sqlite3_close(db); if (i == CYCLES) break; std::cout << std::endl; rc = sqlite3_open(DB_A_PATH, &db); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED + i, "R-tree"); sqlite3_close(db); rc = sqlite3_open(DB_B_PATH, &db); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED + i, "Multiple indexes"); sqlite3_close(db); rc = sqlite3_open(DB_C_PATH, &db); assert(rc == SQLITE_OK); fill_table(db, ENTRIES_COUNT, SEED + i, "Composite index"); sqlite3_close(db); } std::cout << std::endl; std::cout << std::setw(45) << std::left << "R-tree size: " << std::filesystem::file_size(DB_A_PATH) / 1024.0 / 1024.0 << " MiB" << std::endl; std::cout << std::setw(45) << std::left << "Multiple indexes size: " << std::filesystem::file_size(DB_B_PATH) / 1024.0 / 1024.0 << " MiB" << std::endl; std::cout << std::setw(45) << std::left << "Composite index size: " << std::filesystem::file_size(DB_C_PATH) / 1024.0 / 1024.0 << " MiB" << std::endl; return 0; } void fill_table(sqlite3 *db, int entries_count, unsigned seed, const char *name) { srand(seed); auto begin_fill = std::chrono::high_resolution_clock::now(); int rc = sqlite3_exec(db, "BEGIN TRANSACTION;", nullptr, nullptr, nullptr); assert(rc == SQLITE_OK); for (int i = 0; i < entries_count; ++i) { float xbegin = static_cast<float>(rand()) / RAND_MAX / 2; float xend = static_cast<float>(rand()) / RAND_MAX / 2 + xbegin; float ybegin = static_cast<float>(rand()) / RAND_MAX / 2; float yend = static_cast<float>(rand()) / RAND_MAX / 2 + ybegin; int64_t data1 = rand(); char data2[5] = {RANDOM_CHAR, RANDOM_CHAR, RANDOM_CHAR, RANDOM_CHAR}; sqlite3_stmt *stmt; rc = sqlite3_prepare_v2( db, "INSERT INTO ranges " "(xbegin,xend,ybegin,yend,data1,data2) " "VALUES (?, ?, ?, ?, ?, ?);", -1, &stmt, nullptr ); assert(rc == SQLITE_OK); sqlite3_bind_double(stmt, 1, xbegin); sqlite3_bind_double(stmt, 2, xend); sqlite3_bind_double(stmt, 3, ybegin); sqlite3_bind_double(stmt, 4, yend); sqlite3_bind_int64(stmt, 5, data1); sqlite3_bind_text(stmt, 6, data2, 4, SQLITE_STATIC); rc = sqlite3_step(stmt); if (rc != SQLITE_DONE) { printf("%s\n", sqlite3_errmsg(db)); } assert(rc == SQLITE_DONE); } rc = sqlite3_exec(db, "COMMIT TRANSACTION;", nullptr, nullptr, nullptr); assert(rc == SQLITE_OK); auto end_fill = std::chrono::high_resolution_clock::now(); std::cout << std::setw(45) << std::left << (std::string(name) + " INSERT performance: ") << (end_fill - begin_fill).count() / 1e9 << " seconds " << "(" << entries_count << " entries)" << std::endl; } void view_table(sqlite3 *db, const char *name) { auto begin_view = std::chrono::high_resolution_clock::now(); sqlite3_stmt *stmt; int rc = sqlite3_prepare_v2( db, "SELECT " "xbegin,xend,ybegin,yend,data1,data2 " "FROM ranges WHERE " "xbegin >= ? AND " "xend <= ? AND " "ybegin >= ? AND " "yend <= ?;", -1, &stmt, nullptr ); assert(rc == SQLITE_OK); sqlite3_bind_double(stmt, 1, 0.25); sqlite3_bind_double(stmt, 2, 0.75); sqlite3_bind_double(stmt, 3, 0.25); sqlite3_bind_double(stmt, 4, 0.75); uint64_t count = 0; while (true) { if ((rc = sqlite3_step(stmt)) == SQLITE_ROW) { count += 1; } else { break; } } assert(rc == SQLITE_DONE); auto end_view = std::chrono::high_resolution_clock::now(); std::cout << std::setw(45) << std::left << (std::string(name) + " SELECT performance: ") << (end_view - begin_view).count() / 1e9 << " seconds " << "(" << count << " entries)" << std::endl; }