diff mbox series

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

Message ID 20210304041012.4128938-9-blp@ovn.org
State Deferred
Headers show
Series ovn-northd-ddlog improvements | expand

Commit Message

Ben Pfaff March 4, 2021, 4:10 a.m. UTC
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@vmware.com>
Suggested-by: Leonid Ryhzyk <lryzhyk@vmware.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
---
 northd/lrouter.dl | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)
diff mbox series

Patch

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.