[ovs-dev] [PATCH ovn 08/11] ovn-northd-ddlog: Avoid N*M crossproduct joining switches with routers.

Ben Pfaff blp at ovn.org
Thu Mar 4 04:10:09 UTC 2021


DDlog takes a literalist view of joins, executing them in the order that
are written without attempting much in the way of reordering or
optimization.  The FirstHopLogicalRouter rule as written here joined
LogicalRouterPort with LogicalSwitchPort without using any join key,
and then later eliminated some of the possibilities.  This meant that
if there were N router ports and M switch ports, DDlog actually
considered all N*M possibilities, which is expensive.

This commit improves the big-O of the situation by introducing an
intermediate table that contains only the switch port that connect to
router ports and by giving that table a column that can be used as a
join key.  This allows DDlog to join them efficiently.  (The new column
is needed because DDlog cannot join on a member of a map directly.)

Found via the DDlog profiling feature:
https://github.com/vmware/differential-datalog/blob/master/doc/tutorial/tutorial.md#Profiling

Suggested-by: Mihai Budiu <mbudiu at vmware.com>
Suggested-by: Leonid Ryhzyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
---
 northd/lrouter.dl | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/northd/lrouter.dl b/northd/lrouter.dl
index 7786ef137fc6..4c5cf321509e 100644
--- a/northd/lrouter.dl
+++ b/northd/lrouter.dl
@@ -86,12 +86,14 @@ PeerLogicalRouter(lrp_uuid, peer._uuid) :-
 relation FirstHopLogicalRouter(lrouter: uuid, lswitch: uuid)
 FirstHopLogicalRouter(lrouter, lswitch) :-
   LogicalRouterPort(lrp_uuid, lrouter),
-  lrp in nb::Logical_Router_Port(._uuid = lrp_uuid),
-  LogicalSwitchPort(lsp_uuid, lswitch),
-  lsp in nb::Logical_Switch_Port(._uuid = lsp_uuid),
-  lsp.__type == "router",
-  lsp.options.get("router-port") == Some{lrp.name},
-  lrp.peer == None.
+  lrp in nb::Logical_Router_Port(._uuid = lrp_uuid, .peer = None),
+  LogicalSwitchRouterPort(lsp_uuid, lrp.name, lswitch).
+
+relation LogicalSwitchRouterPort(lsp: uuid, lsp_router_port: string, ls: uuid)
+LogicalSwitchRouterPort(lsp, lsp_router_port, ls) :-
+  LogicalSwitchPort(lsp, ls),
+  nb::Logical_Switch_Port(._uuid = lsp, .__type = "router", .options = options),
+  Some{var lsp_router_port} = options.get("router-port").
 
 /*
  * Reachable routers.
-- 
2.29.2



More information about the dev mailing list