Currently all OVSDB database queries except for UUID lookups all result in linear lookups over the entire table, even if an index is present.
This patch modifies ovsdb_query() to attempt an index lookup first, if possible. If no matching indexes are present then a linear index is still conducted. Reported-at: https://issues.redhat.com/browse/FDP-590 Signed-off-by: Mike Pattrick <[email protected]> --- NEWS | 3 ++ ovsdb/query.c | 102 +++++++++++++++++++++++++++++++++++---- ovsdb/row.h | 28 +++++++++++ ovsdb/transaction.c | 27 ----------- tests/ovsdb-execution.at | 34 ++++++++++++- tests/ovsdb-server.at | 2 +- tests/ovsdb-tool.at | 2 +- 7 files changed, 159 insertions(+), 39 deletions(-) diff --git a/NEWS b/NEWS index 5ae0108d5..616fd19a4 100644 --- a/NEWS +++ b/NEWS @@ -9,6 +9,9 @@ Post-v3.3.0 https://github.com/openvswitch/ovs.git - DPDK: * OVS validated with DPDK 23.11.1. + - OVSDB: + * Added support to lookup rows based on arbitrary indexes, instead of + only UUID indexes. v3.3.0 - 16 Feb 2024 diff --git a/ovsdb/query.c b/ovsdb/query.c index eebe56412..e3e50a034 100644 --- a/ovsdb/query.c +++ b/ovsdb/query.c @@ -21,32 +21,116 @@ #include "condition.h" #include "row.h" #include "table.h" +#include "transaction.h" + +static bool +ovsdb_query_index(struct ovsdb_table *table, + const struct ovsdb_condition *cnd, + const struct ovsdb_row **out) +{ + for (size_t idx = 0; idx < table->schema->n_indexes; idx++) { + const struct ovsdb_column_set *index = &table->schema->indexes[idx]; + struct hmap_node *node; + size_t matches = 0; + uint32_t hash = 0; + + if (index->n_columns != cnd->n_clauses) { + continue; + } + + /* The conditions may not be in the same order as the index. */ + for (size_t c = 0; c < cnd->n_clauses; c++) { + const struct ovsdb_clause *cnd_cls = &cnd->clauses[c]; + + if (cnd_cls->function != OVSDB_F_EQ) { + return false; + } + + for (size_t i = 0; i < index->n_columns; i++) { + const struct ovsdb_column *idx_col = index->columns[i]; + + if (cnd_cls->index == idx_col->index) { + hash = ovsdb_datum_hash(&cnd_cls->arg, &idx_col->type, + hash); + matches++; + break; + } + } + + /* If none of the indexed columns match, continue to the next + * index. */ + if (matches == c) { + break; + } + } + + if (matches != cnd->n_clauses) { + continue; + } + + for (node = hmap_first_with_hash(&table->indexes[idx], hash); node; + node = hmap_next_with_hash(node)) { + struct ovsdb_row *irow = ovsdb_row_from_index_node(node, table, + idx); + + for (size_t c = 0; c < cnd->n_clauses; c++) { + const struct ovsdb_clause *cnd_cls = &cnd->clauses[c]; + + if (!ovsdb_datum_equals(&cnd_cls->arg, + &irow->fields[cnd_cls->index], + &cnd_cls->column->type)) { + irow = NULL; + break; + } + } + + if (irow) { + *out = irow; + return true; + } + } + + /* In the case that there was a matching index but no matching row, the + * index check is still considered to be a success. */ + return true; + } + return false; +} void ovsdb_query(struct ovsdb_table *table, const struct ovsdb_condition *cnd, bool (*output_row)(const struct ovsdb_row *, void *aux), void *aux) { + const struct ovsdb_row *row = NULL; + if (cnd->n_clauses > 0 && cnd->clauses[0].column->index == OVSDB_COL_UUID && cnd->clauses[0].function == OVSDB_F_EQ) { /* Optimize the case where the query has a clause of the form "uuid == * <some-uuid>", since we have an index on UUID. */ - const struct ovsdb_row *row; row = ovsdb_table_get_row(table, &cnd->clauses[0].arg.keys[0].uuid); if (row && row->table == table && ovsdb_condition_match_every_clause(row, cnd)) { output_row(row, aux); } - } else { - /* Linear scan. */ - const struct ovsdb_row *row; + return; + } - HMAP_FOR_EACH_SAFE (row, hmap_node, &table->rows) { - if (ovsdb_condition_match_every_clause(row, cnd) && - !output_row(row, aux)) { - break; - } + /* Index check. */ + if (ovsdb_query_index(table, cnd, &row)) { + if (row) { + output_row(row, aux); + return; + } + return; + } + + /* Linear scan. */ + HMAP_FOR_EACH_SAFE (row, hmap_node, &table->rows) { + if (ovsdb_condition_match_every_clause(row, cnd) && + !output_row(row, aux)) { + break; } } } diff --git a/ovsdb/row.h b/ovsdb/row.h index 6f5e58acb..f585b9fdc 100644 --- a/ovsdb/row.h +++ b/ovsdb/row.h @@ -22,6 +22,7 @@ #include "openvswitch/hmap.h" #include "openvswitch/list.h" #include "ovsdb-data.h" +#include "table.h" struct ovsdb_column_set; @@ -152,6 +153,33 @@ ovsdb_row_hash(const struct ovsdb_row *row) { return uuid_hash(ovsdb_row_get_uuid(row)); } + +/* Returns the offset in bytes from the start of an ovsdb_row for 'table' to + * the hmap_node for the index numbered 'i'. */ +static inline size_t +ovsdb_row_index_offset__(const struct ovsdb_table *table, size_t i) +{ + size_t n_fields = shash_count(&table->schema->columns); + return (offsetof(struct ovsdb_row, fields) + + n_fields * sizeof(struct ovsdb_datum) + + i * sizeof(struct hmap_node)); +} + +/* Returns the hmap_node in 'row' for the index numbered 'i'. */ +static inline struct hmap_node * +ovsdb_row_get_index_node(struct ovsdb_row *row, size_t i) +{ + return (void *) ((char *) row + ovsdb_row_index_offset__(row->table, i)); +} + +/* Returns the ovsdb_row given 'index_node', which is a pointer to that row's + * hmap_node for the index numbered 'i' within 'table'. */ +static inline struct ovsdb_row * +ovsdb_row_from_index_node(struct hmap_node *index_node, + const struct ovsdb_table *table, size_t i) +{ + return (void *) ((char *) index_node - ovsdb_row_index_offset__(table, i)); +} /* An unordered collection of rows. */ struct ovsdb_row_set { diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c index 484a88e1c..989d889cd 100644 --- a/ovsdb/transaction.c +++ b/ovsdb/transaction.c @@ -194,33 +194,6 @@ ovsdb_txn_row_abort(struct ovsdb_txn *txn OVS_UNUSED, return NULL; } -/* Returns the offset in bytes from the start of an ovsdb_row for 'table' to - * the hmap_node for the index numbered 'i'. */ -static size_t -ovsdb_row_index_offset__(const struct ovsdb_table *table, size_t i) -{ - size_t n_fields = shash_count(&table->schema->columns); - return (offsetof(struct ovsdb_row, fields) - + n_fields * sizeof(struct ovsdb_datum) - + i * sizeof(struct hmap_node)); -} - -/* Returns the hmap_node in 'row' for the index numbered 'i'. */ -static struct hmap_node * -ovsdb_row_get_index_node(struct ovsdb_row *row, size_t i) -{ - return (void *) ((char *) row + ovsdb_row_index_offset__(row->table, i)); -} - -/* Returns the ovsdb_row given 'index_node', which is a pointer to that row's - * hmap_node for the index numbered 'i' within 'table'. */ -static struct ovsdb_row * -ovsdb_row_from_index_node(struct hmap_node *index_node, - const struct ovsdb_table *table, size_t i) -{ - return (void *) ((char *) index_node - ovsdb_row_index_offset__(table, i)); -} - void ovsdb_txn_abort(struct ovsdb_txn *txn) { diff --git a/tests/ovsdb-execution.at b/tests/ovsdb-execution.at index 1ffa2b738..587604268 100644 --- a/tests/ovsdb-execution.at +++ b/tests/ovsdb-execution.at @@ -11,7 +11,7 @@ ordinal_schema () { "columns": { "number": {"type": "integer"}, "name": {"type": "string"}}, - "indexes": [["number"]]}}, + "indexes": [["number"], ["number", "name"]]}}, "version": "5.1.3", "cksum": "12345678 9"} EOF @@ -273,6 +273,38 @@ dnl Attempt to insert second row with same UUID (fails). [{"details":"This UUID would duplicate a UUID already present within the table or deleted within the same transaction.","error":"duplicate uuid","syntax":"\"ffffffff-971b-4cba-bf42-520515973b7e\""}] ]]) +OVSDB_CHECK_EXECUTION([insert rows, query by index], + [ordinal_schema], +dnl Insert initial rows. + [[[["ordinals", + {"op": "insert", + "table": "ordinals", + "row": {"number": 0, "name": "zero"}}]]], + [[["ordinals", + {"op": "insert", + "table": "ordinals", + "row": {"number": 1, "name": "one"}}]]], + [[["ordinals", + {"op": "insert", + "table": "ordinals", + "row": {"number": 2, "name": "two"}}]]], +dnl Query with first index. + [[["ordinals", + {"op": "select", + "table": "ordinals", + "where": [["number", "==", 1]]}]]], +dnl Query with second index. + [[["ordinals", + {"op": "select", + "table": "ordinals", + "where": [["name", "==", "two"], ["number", "==", 2]]}]]]], +[[[{"uuid":["uuid","<0>"]}] +[{"uuid":["uuid","<1>"]}] +[{"uuid":["uuid","<2>"]}] +[{"rows":[{"_uuid":["uuid","<1>"],"_version":["uuid","<3>"],"name":"one","number":1}]}] +[{"rows":[{"_uuid":["uuid","<2>"],"_version":["uuid","<4>"],"name":"two","number":2}]}] +]]) + OVSDB_CHECK_EXECUTION([insert rows, query by value], [ordinal_schema], [[[["ordinals", diff --git a/tests/ovsdb-server.at b/tests/ovsdb-server.at index ce6d32aee..7b4b280e1 100644 --- a/tests/ovsdb-server.at +++ b/tests/ovsdb-server.at @@ -1007,7 +1007,7 @@ ovsdb_check_online_compaction() { AT_CHECK([[uuidfilt db | grep -v ^OVSDB | \ sed 's/"_date":[0-9]*/"_date":0/' | sed 's/"_is_diff":true,//' | \ ovstest test-json --multiple -]], [0], -[[{"cksum":"12345678 9","name":"ordinals","tables":{"ordinals":{"columns":{"name":{"type":"string"},"number":{"type":"integer"}},"indexes":[["number"]]}},"version":"5.1.3"} +[[{"cksum":"12345678 9","name":"ordinals","tables":{"ordinals":{"columns":{"name":{"type":"string"},"number":{"type":"integer"}},"indexes":[["number"],["number","name"]]}},"version":"5.1.3"} {"_comment":"add row for zero 0","_date":0,"ordinals":{"<0>":{"name":"zero"}}} {"_comment":"delete row for 0","_date":0,"ordinals":{"<0>":null}} {"_comment":"add back row for zero 0","_date":0,"ordinals":{"<1>":{"name":"zero"}}} diff --git a/tests/ovsdb-tool.at b/tests/ovsdb-tool.at index d8d2b1c99..cf4a0fd2e 100644 --- a/tests/ovsdb-tool.at +++ b/tests/ovsdb-tool.at @@ -95,7 +95,7 @@ AT_CHECK( dnl Check that all the crap is in fact in the database log. AT_CHECK([[uuidfilt db | grep -v ^OVSDB | sed 's/"_date":[0-9]*/"_date":0/' | \ sed 's/"_is_diff":true,//' | ovstest test-json --multiple -]], [0], - [[{"cksum":"12345678 9","name":"ordinals","tables":{"ordinals":{"columns":{"name":{"type":"string"},"number":{"type":"integer"}},"indexes":[["number"]]}},"version":"5.1.3"} + [[{"cksum":"12345678 9","name":"ordinals","tables":{"ordinals":{"columns":{"name":{"type":"string"},"number":{"type":"integer"}},"indexes":[["number"],["number","name"]]}},"version":"5.1.3"} {"_comment":"add row for zero 0","_date":0,"ordinals":{"<0>":{"name":"zero"}}} {"_comment":"delete row for 0","_date":0,"ordinals":{"<0>":null}} {"_comment":"add back row for zero 0","_date":0,"ordinals":{"<1>":{"name":"zero"}}} -- 2.39.3 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
