From patchwork Thu Mar 4 04:10:09 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Pfaff X-Patchwork-Id: 1447083 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4DrcqH6c5Zz9sRf for ; Thu, 4 Mar 2021 15:10:51 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id C11FF4EBC9; Thu, 4 Mar 2021 04:10:49 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5RtSUm1fVJdX; Thu, 4 Mar 2021 04:10:48 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp4.osuosl.org (Postfix) with ESMTP id 1F5164EBD9; Thu, 4 Mar 2021 04:10:47 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id E6BCAC0011; Thu, 4 Mar 2021 04:10:46 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 12AF9C0010 for ; Thu, 4 Mar 2021 04:10:45 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id A4F2B842A9 for ; Thu, 4 Mar 2021 04:10:33 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id E2INJRPVc2OT for ; Thu, 4 Mar 2021 04:10:32 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay9-d.mail.gandi.net (relay9-d.mail.gandi.net [217.70.183.199]) by smtp1.osuosl.org (Postfix) with ESMTPS id 4019584340 for ; Thu, 4 Mar 2021 04:10:31 +0000 (UTC) X-Originating-IP: 75.54.222.30 Received: from sigfpe.attlocal.net (75-54-222-30.lightspeed.rdcyca.sbcglobal.net [75.54.222.30]) (Authenticated sender: blp@ovn.org) by relay9-d.mail.gandi.net (Postfix) with ESMTPSA id 3156DFF806; Thu, 4 Mar 2021 04:10:28 +0000 (UTC) From: Ben Pfaff To: dev@openvswitch.org Date: Wed, 3 Mar 2021 20:10:09 -0800 Message-Id: <20210304041012.4128938-9-blp@ovn.org> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20210304041012.4128938-1-blp@ovn.org> References: <20210304041012.4128938-1-blp@ovn.org> MIME-Version: 1.0 Cc: Mihai Budiu , Leonid Ryhzyk , Ben Pfaff Subject: [ovs-dev] [PATCH ovn 08/11] ovn-northd-ddlog: Avoid N*M crossproduct joining switches with routers. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" 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 Suggested-by: Leonid Ryhzyk Signed-off-by: Ben Pfaff --- 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.