From a4b291029fc79b143a94bfbda20a32ef52321539 Mon Sep 17 00:00:00 2001 From: Sean Bright Date: Thu, 7 Dec 2017 15:19:40 -0500 Subject: astdb: Improve prefix searches in astdb Using the LIKE operator requires a full table scan of 'astdb', whereas a comparison operation is able to use the primary key index. This patch adds a new function to the AstDB API for quick prefix matches and updates res_sorcery_astdb to utilize it. This showed substantial performance improvement in my test environment. Related to ASTERISK~26806, but does not completely resolve it. Change-Id: I7d37f9ba2aea139dabf2ca72d31fbe34bd9b2fa1 --- main/db.c | 121 ++++++++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 94 insertions(+), 27 deletions(-) (limited to 'main') diff --git a/main/db.c b/main/db.c index ab5f7a07c..1edbcacbf 100644 --- a/main/db.c +++ b/main/db.c @@ -129,6 +129,20 @@ DEFINE_SQL_STATEMENT(gettree_all_stmt, "SELECT key, value FROM astdb ORDER BY ke DEFINE_SQL_STATEMENT(showkey_stmt, "SELECT key, value FROM astdb WHERE key LIKE '%' || '/' || ? ORDER BY key") DEFINE_SQL_STATEMENT(create_astdb_stmt, "CREATE TABLE IF NOT EXISTS astdb(key VARCHAR(256), value VARCHAR(256), PRIMARY KEY(key))") +/* This query begs an explanation: + * + * First, the parameter binding syntax used here is slightly different then the other + * queries in that we use a numbered parameter so that we can bind once and get the same + * value substituted multiple times within the executed query. + * + * Second, the key comparison is being used to find all keys that are lexicographically + * greater than the provided key, but less than the provided key with a high (but + * invalid) Unicode codepoint appended to it. This will give us all keys in the database + * that have 'key' as a prefix and performs much better than the equivalent "LIKE key || + * '%'" operation. + */ +DEFINE_SQL_STATEMENT(gettree_prefix_stmt, "SELECT key, value FROM astdb WHERE key > ?1 AND key <= ?1 || X'ffff'") + static int init_stmt(sqlite3_stmt **stmt, const char *sql, size_t len) { ast_mutex_lock(&dblock); @@ -169,6 +183,7 @@ static void clean_statements(void) clean_stmt(&deltree_all_stmt, deltree_all_stmt_sql); clean_stmt(&gettree_stmt, gettree_stmt_sql); clean_stmt(&gettree_all_stmt, gettree_all_stmt_sql); + clean_stmt(&gettree_prefix_stmt, gettree_prefix_stmt_sql); clean_stmt(&showkey_stmt, showkey_stmt_sql); clean_stmt(&put_stmt, put_stmt_sql); clean_stmt(&create_astdb_stmt, create_astdb_stmt_sql); @@ -184,6 +199,7 @@ static int init_statements(void) || init_stmt(&deltree_all_stmt, deltree_all_stmt_sql, sizeof(deltree_all_stmt_sql)) || init_stmt(&gettree_stmt, gettree_stmt_sql, sizeof(gettree_stmt_sql)) || init_stmt(&gettree_all_stmt, gettree_all_stmt_sql, sizeof(gettree_all_stmt_sql)) + || init_stmt(&gettree_prefix_stmt, gettree_prefix_stmt_sql, sizeof(gettree_prefix_stmt_sql)) || init_stmt(&showkey_stmt, showkey_stmt_sql, sizeof(showkey_stmt_sql)) || init_stmt(&put_stmt, put_stmt_sql, sizeof(put_stmt_sql)); } @@ -475,19 +491,64 @@ int ast_db_deltree(const char *family, const char *keytree) return res; } +static struct ast_db_entry *db_gettree_common(sqlite3_stmt *stmt) +{ + struct ast_db_entry *head = NULL, *prev = NULL, *cur; + + while (sqlite3_step(stmt) == SQLITE_ROW) { + const char *key, *value; + size_t key_len, value_len; + + key = (const char *) sqlite3_column_text(stmt, 0); + value = (const char *) sqlite3_column_text(stmt, 1); + + if (!key || !value) { + break; + } + + key_len = strlen(key); + value_len = strlen(value); + + cur = ast_malloc(sizeof(*cur) + key_len + value_len + 2); + if (!cur) { + break; + } + + cur->next = NULL; + cur->key = cur->data + value_len + 1; + memcpy(cur->data, value, value_len + 1); + memcpy(cur->key, key, key_len + 1); + + if (prev) { + prev->next = cur; + } else { + head = cur; + } + prev = cur; + } + + return head; +} + struct ast_db_entry *ast_db_gettree(const char *family, const char *keytree) { char prefix[MAX_DB_FIELD]; sqlite3_stmt *stmt = gettree_stmt; - struct ast_db_entry *cur, *last = NULL, *ret = NULL; + size_t res = 0; + struct ast_db_entry *ret; if (!ast_strlen_zero(family)) { if (!ast_strlen_zero(keytree)) { /* Family and key tree */ - snprintf(prefix, sizeof(prefix), "/%s/%s", family, keytree); + res = snprintf(prefix, sizeof(prefix), "/%s/%s", family, keytree); } else { /* Family only */ - snprintf(prefix, sizeof(prefix), "/%s", family); + res = snprintf(prefix, sizeof(prefix), "/%s", family); + } + + if (res >= sizeof(prefix)) { + ast_log(LOG_WARNING, "Requested prefix is too long: %s\n", keytree); + return NULL; } } else { prefix[0] = '\0'; @@ -495,41 +556,47 @@ struct ast_db_entry *ast_db_gettree(const char *family, const char *keytree) } ast_mutex_lock(&dblock); - if (!ast_strlen_zero(prefix) && (sqlite3_bind_text(stmt, 1, prefix, -1, SQLITE_STATIC) != SQLITE_OK)) { - ast_log(LOG_WARNING, "Could bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb)); + if (res && (sqlite3_bind_text(stmt, 1, prefix, res, SQLITE_STATIC) != SQLITE_OK)) { + ast_log(LOG_WARNING, "Could not bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb)); sqlite3_reset(stmt); ast_mutex_unlock(&dblock); return NULL; } - while (sqlite3_step(stmt) == SQLITE_ROW) { - const char *key_s, *value_s; - if (!(key_s = (const char *) sqlite3_column_text(stmt, 0))) { - break; - } - if (!(value_s = (const char *) sqlite3_column_text(stmt, 1))) { - break; - } - if (!(cur = ast_malloc(sizeof(*cur) + strlen(key_s) + strlen(value_s) + 2))) { - break; - } - cur->next = NULL; - cur->key = cur->data + strlen(value_s) + 1; - strcpy(cur->data, value_s); - strcpy(cur->key, key_s); - if (last) { - last->next = cur; - } else { - ret = cur; - } - last = cur; - } + ret = db_gettree_common(stmt); sqlite3_reset(stmt); ast_mutex_unlock(&dblock); return ret; } +struct ast_db_entry *ast_db_gettree_by_prefix(const char *family, const char *key_prefix) +{ + char prefix[MAX_DB_FIELD]; + size_t res; + struct ast_db_entry *ret; + + res = snprintf(prefix, sizeof(prefix), "/%s/%s", family, key_prefix); + if (res >= sizeof(prefix)) { + ast_log(LOG_WARNING, "Requested key prefix is too long: %s\n", key_prefix); + return NULL; + } + + ast_mutex_lock(&dblock); + if (sqlite3_bind_text(gettree_prefix_stmt, 1, prefix, res, SQLITE_STATIC) != SQLITE_OK) { + ast_log(LOG_WARNING, "Could not bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb)); + sqlite3_reset(gettree_prefix_stmt); + ast_mutex_unlock(&dblock); + return NULL; + } + + ret = db_gettree_common(gettree_prefix_stmt); + sqlite3_reset(gettree_prefix_stmt); + ast_mutex_unlock(&dblock); + + return ret; +} + void ast_db_freetree(struct ast_db_entry *dbe) { struct ast_db_entry *last; -- cgit v1.2.3