{"id":10006537,"date":"2022-09-19T17:48:27","date_gmt":"2022-09-19T09:48:27","guid":{"rendered":"https:\/\/ityet.com\/?p=10006537"},"modified":"2022-09-19T17:48:27","modified_gmt":"2022-09-19T09:48:27","slug":"polardb-x%e6%8b%86%e5%88%86%e9%94%ae%e6%8e%a8%e8%8d%90","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10006537","title":{"rendered":"PolarDB-X\u62c6\u5206\u952e\u63a8\u8350"},"content":{"rendered":"

\u7b80\u4ecb\uff1a\u00a0PolarDB-X 2.0\u63d0\u4f9b\u4e86\u900f\u660e\u5206\u5e03\u5f0f\u7684\u80fd\u529b\uff0c\u9ed8\u8ba4\u8fdb\u884c\u4e3b\u952e\u7684\u54c8\u5e0c\u62c6\u5206\uff0c\u8ba9\u7528\u6237\u65e0\u611f\u77e5\u7684\u4ece\u5355\u673a\u6570\u636e\u5e93\u8fc1\u79fb\u5230\u5206\u5e03\u5f0f\u6570\u636e\u5e93\u3002\u62c6\u5206\u952e\u7684\u9009\u62e9\u662f\u5b66\u672f\u754c\u548c\u5de5\u4e1a\u754c\u7814\u7a76\u5df2\u4e45\u7684\u95ee\u9898\uff0c\u4e00\u4e2a\u91cd\u8981\u9009\u578b\u662ftp\u4f18\u5148\u8fd8\u662fap\u4f18\u5148\uff0c\u4e24\u8005\u96be\u4ee5\u540c\u65f6\u517c\u987e\u3002\u524d\u8a00PolarDB-X2.0\u63d0\u4f9b\u4e86\u900f\u660e\u5206\u5e03\u5f0f\u7684\u80fd\u529b\uff0c\u9ed8\u8ba4\u8fdb\u884c\u4e3b\u952e\u62c6\u5206\uff0c\u8ba9\u7528\u6237\u65e0\u611f\u77e5\u7684\u4ece\u5355\u673a\u6570\u636e\u5e93\u8fc1\u79fb\u5230\u5206\u5e03\u5f0f\u6570\u636e\u5e93\u3002\u62c6\u5206\u952e\u7684\u9009\u62e9\u662f\u5b66\u672f\u754c\u548c\u5de5\u4e1a\u754c\u7814\u7a76\u5df2\u4e45\u7684\u95ee\u9898\uff0c\u4e00\u4e2a\u91cd\u8981\u9009\u578b\u662ftp\u4f18\u5148\u8fd8\u662fap\u4f18\u5148\uff0c\u4e24\u8005\u96be\u4ee5\u540c\u65f6\u517c\u987e\u3002tp\u4f18\u5148[1]\u7684\u76ee\u7684\u662f\u51cf\u5c11\u5206\u5e03\u5f0f\u4e8b\u52a1\u3002filter\u4f18\u5148\uff0c\u8ba9sql\u5c3d\u91cf\u4e0d\u8de8\u5e93\u3002ap\u4f18\u5148[2]\u7684\u76ee\u7684\u662f\u5229\u7528\u4e0b\u63a8\u7684\u4f18\u52bf\uff0c\u7f51\u7edc\u4f18\u5316\uff0c\u4f18\u5148\u5904\u7406\u7b49\u503cjoin\u3002PolarDB-X\u7684\u4e3b\u952e\u62c6\u5206\u5bf9\u4e8etp\u67e5\u8be2\u5f88\u53cb\u597d\uff0c\u4f46\u5bf9\u4e8eap\u67e5\u8be2\u5e76\u4e0d\u53cb\u597d\u3002\u56e0\u6b64\uff0c\u5728\u8fc1\u79fbPolarDB-X\u4e4b\u540e\u82e5\u53d1\u73b0\u9ed8\u8ba4\u7684\u62c6\u5206\u65b9\u5f0f\u4e0d\u80fd\u6ee1\u8db3\u504fap\u7684\u9700\u6c42\uff0c\u53ef\u4ee5\u57fa\u4e8e\u5b9e\u9645workload\u8fdb\u884c\u62c6\u5206\u952e\u63a8\u8350\uff0c\u7ed3\u5408PolarDB-X\u7684\u62c6\u5206\u53d8\u66f4\u80fd\u529b\u8fdb\u884c\u667a\u80fd\u7684\u62c6\u5206\u952e\u8c03\u6574\u3002ap\u4f18\u5148\u7684\u62c6\u5206\u952e\u63a8\u8350\u4e3b\u8981\u6709\u4e24\u79cd\u65b9\u5f0f\uff1a\u501f\u52a9\u4f18\u5316\u5668[3]\u7ed3\u679c\u6bd4\u8f83\u51c6\u786e\uff0c\u4f46\u662f\u8fd0\u884c\u65f6\u95f4\u592a\u957f\uff0c\u5c06\u4f18\u5316\u5668\u5f53\u6210\u9ed1\u76d2\u6216\u6df1\u5ea6\u4fee\u6539\u4f18\u5316\u5668\uff0c\u76f8\u5bf9\u5feb\u4e00\u70b9\uff0c\u4f46\u901f\u5ea6\u4f9d\u7136\u65e0\u6cd5\u4ee4\u4eba\u6ee1\u610f\uff1b\u4e0d\u501f\u52a9\u4f18\u5316\u5668[4]\u76f8\u5bf9\u8f83\u5feb\uff0c\u4f46\u4f9d\u7136\u9700\u8981\u7a77\u4e3e\u6240\u6709\u7684\u53ef\u80fd\uff0c\u4e14\u4ee3\u4ef7\u4f30\u4e0d\u51c6\u3002\u501f\u52a9\u4f18\u5316\u5668\u7684\u7b97\u6cd5\u96be\u4ee5\u4f18\u5316\u7684\u539f\u56e0\u662f\u76ee\u6807\u51fd\u6570\u7684\u7ed3\u679c\u65e0\u6cd5\u9884\u6d4b\uff0c\u6240\u4ee5\u65e0\u6cd5\u7ed9\u51fa\u6709\u6548\u7684\u526a\u679d\u3002\u4e3a\u4e86\u80fd\u591f\u5c3d\u91cf\u5feb\u7684\u8fdb\u884c\u63a8\u8350\uff0cPolarDB-X\u7684\u62c6\u5206\u952e\u63a8\u8350\u4e0d\u501f\u52a9\u4f18\u5316\u5668\uff0c\u5c11\u7528\u7edf\u8ba1\u4fe1\u606f\uff0c\u57fa\u4e8eAmazon RedShift\u5b9a\u4e49\u7684\u95ee\u9898\u8bbe\u8ba1\u4e86\u4e00\u4e2a\u9ad8\u6548\u7684\u63a8\u8350\u7b97\u6cd5\u3002\u95ee\u9898\u5b9a\u4e49\u672c\u8282\u5185\u5bb9\u53c2\u8003\u81eaAmazon RedShift\u7684\u8bba\u6587[4]\u3002\u62c6\u5206\u952e\u63a8\u8350\u95ee\u9898\u5b9a\u4e49\u4e3a\u6bcf\u4e2a\u8868\u9009\u62e9\u4e00\u4e2a\u62c6\u5206\u5217\uff0c\u4f7f\u5f97\u53ef\u4ee5\u8282\u7701\u7684\u7f51\u7edc\u4ee3\u4ef7\u6700\u5927\u3002join\u53ef\u4e0b\u63a8\u9700\u8981\u4e24\u4e2a\u8868\u4f7f\u7528\u7684\u62c6\u5206\u952e\u6070\u597d\u662f\u8fd9\u6761\u8fb9\u7684\u4e24\u4e2a\u5217\u3002\u4e0b\u56fe(b)\u4e2dA\u3001B\u3001C\u3001D\u3001E\u3001F\u5206\u522b\u7528a\u3001b1\u3001c\u3001d1\u3001c\u3001c\u505a\u62c6\u5206\u952e\uff0c\u5219<C,c,E,c,2>\u3001<C,c,F,c,2>\u3001<B,b1,D,d1,2>\u53ef\u4ee5\u4e0b\u63a8\uff0c\u8fd9\u79cd\u62c6\u5206\u53ef\u4ee5\u8282\u7701\u7684\u4ee3\u4ef7\u4e3a6\u3002Join Multi-Graph\u7ed9\u5b9an\u6761\u67e5\u8be2\uff0c\u7b2ci\u6761\u67e5\u8be2\u88ab\u770b\u4f5cm\u4e2a\u4e8c\u5143join $\/{j_{i1},j_{i2},…,j_{im}\/}$\u7684\u96c6\u5408\u3002\u6bcf\u4e2ajk\u662f\u4e00\u4e2a\u4e94\u5143\u7ec4\uff0c$jk=<t1_k,a1_k,t2_k,a2_k,w_{k}>$\uff0c\u8868\u793a\u8868$t1_{k}$\u7684$a1_{k}$\u5217\u4e0e\u8868$t2_{k}$\u7684$a2_{k}$\u5217\u7684\u7b49\u503cjoin\uff0c\u4e0d\u4e0b\u63a8\u7684\u7f51\u7edc\u4ee3\u4ef7\u662f$w_k$\u3002\u524d4\u5217\u76f8\u540c\u7684\u8fb9$<t1_{k},a1_{k},t2_{k},a2_{k},w1_{k}>$\u3001$<t1_{k},a1_{k},t2_{k},a2_{k},w2_{k}>$\u4f1a\u5408\u5e76\u4e3a$<t2_{k},a1_{k},t2_{k},a2_{k},w1_k+w2_k>$\u3002$<t1,a1,t2,a2,w>$\u4e2dw\u7684\u5b9a\u4e49\u4e3a\u4e24\u8868t1\u548ct2\u7684\u884c\u6570\u5206\u522b\u4e3ar1\u3001r2\uff0c$w=min(r1+r2,min(r1,r2)*shardCnt)*count$\u3002\u516c\u5f0f\u7684\u542b\u4e49\u662f\u82e5\u4e0d\u4e0b\u63a8\uff0c\u5219\u5bfc\u81f4\u7684\u7f51\u7edc\u4ee3\u4ef7\u662f\u5c06\u4e24\u8868\u62c9\u53d6\u5230CN\u8fdb\u884chash join\u6216\u8005\u5c06\u5c0f\u8868\u4f5c\u4e3a\u5e7f\u64ad\u8868\u6700\u540e\u4e58\u4ee5\u8fd9\u4e2a\u7b49\u503c\u6761\u4ef6\u51fa\u73b0\u7684\u6b21\u6570\u3002\u6784\u5efaJoin Multi-Graph\uff0c\u6bcf\u5f20\u8868\u662f\u4e00\u4e2a\u70b9\uff0c\u6bcf\u4e2ajk\u662f\u4e00\u6761\u8fb9\uff0c\u8fb9\u4e0a\u6709\u4e24\u4e2a\u5217\u540d\u548c\u4ee3\u4ef7\uff0c\u4e0b\u56fe(a)\u4e2d\u6700\u4e0a\u9762\u7684\u4e00\u6761\u8fb9\u5c31\u662f<C,c,E,c,2>\u3002\u8fd9\u4e2a\u56fe\u53ef\u91cd\u8fb9\uff0c\u4f8b\u5982BD\u4e4b\u95f4\u5c31\u6709\u4e24\u6761\u8fb9\uff08\u56e0\u4e3a\u5217\u540d\u4e0d\u540c\uff09\u3002
\"\u56fe\u7247\"
\u4e0d\u53ef\u8fd1\u4f3c\u6027\u8fd9\u4e2a\u95ee\u9898\u4e0d\u53ef\u8fd1\u4f3c\u6bd4\u4e3a$2^{log^{1-\/epsilon}n}$\uff0cn\u4e3a\u56fe\u4e2d\u6d89\u53ca\u7684\u5217\u6570\u3002\u8fd9\u5176\u5b9e\u662f\u4e2a\u5f88\u7cdf\u7cd5\u7684\u7ed3\u8bba\uff0c\u8fd9\u4e2a\u95ee\u9898\u7684\u7406\u8bba\u8fd1\u4f3c\u6bd4\u57fa\u672c\u7b49\u4e8e\u6ca1\u6709\u3002RedShift\u7684\u7b97\u6cd5\u4e3a\u6574\u6570\u7ebf\u6027\u89c4\u5212\uff0c\u82e5\u8d85\u65f6\u5219\u8c03\u7528\u56db\u4e2a\u968f\u673a\u7b97\u6cd5\u53d6\u4e2a\u5927\u7684\u3002\u8fd9\u4e2a\u7b97\u6cd5\u5b58\u5728\u968f\u673a\u7b97\u6cd5\u7f3a\u4e4f\u7a33\u5b9a\u6027\u3001\u8d85\u65f6\u65e0\u6cd5\u81ea\u4e3b\u63a7\u5236\u7b49\u95ee\u9898\u3002\u57fa\u4e8e\u4ee5\u4e0a\u7f3a\u70b9\uff0cPolarDB-X\u8bbe\u8ba1\u4e86\u4e00\u4e2a\u57fa\u4e8ebranch-and-bound\u7684\u7a77\u4e3e\u7b97\u6cd5\u3002\u7b97\u6cd5\u8bbe\u8ba1\u5148\u770b\u770b\u66b4\u529b\u7a77\u4e3e\u7684\u4f2a\u4ee3\u7801
\"\u56fe\u7247\"
\u8fd9\u4e2a\u7b97\u6cd5\u7684\u95ee\u9898\u5728\u4e8e\u7a77\u4e3e\u5230\u6700\u540e\u4e00\u5f20\u8868\u624d\u4f1a\u505a\u8ba1\u7b97\uff0c\u5f88\u591a\u62c6\u5206\u65b9\u6848\u5b8c\u5168\u6ca1\u7528\u5374\u88ab\u7a77\u4e3e\u4e86\u3002\u4ece\u8017\u65f6\u5c31\u53ef\u4ee5\u770b\u51fa\u6ca1\u6709\u5b9e\u9645\u4f7f\u7528\u4ef7\u503c\u3002\u8868\u5c5e\u6027\u65f6\u95f4(s)12\u8868 8\u5217\u5e73\u5747\u5ea6\u6570868.986redshift 13\u8868\u5e73\u5747\u5ea6\u65701072.81\u661f\u72b6\u56fe 17\u8868\u5e73\u5747\u5ea6\u65701632.696\u5bf9\u4e8e\u8fd9\u4e2a\u7b97\u6cd5\u8fd0\u884c\u8fc7\u6162\u7684\u95ee\u9898\uff0c\u6211\u4eec\u4ece\u4ee5\u4e0b\u56db\u4e2a\u5c42\u9762\u8fdb\u884c\u4f18\u5316\u3002\u57fa\u4e8ebranch-and-bound\u7684\u7a77\u4e3e\u7b97\u6cd5\u5bf9\u4e8e\u4e00\u4e2a\u7a77\u4e3e\u5230\u8868level\u7684\u65b9\u6848$Shard=\/{P,col\/}$\uff0c\u8ba1\u7b97\u4ee5\u8fd9\u4e2a\u65b9\u6848\u4e3a\u57fa\u7840\u7684\u6240\u6709\u62c6\u5206\u65b9\u6848weight\u7684\u4e0a\u754cupperBound\u3002\u82e5\u4e0a\u754c\u5c0f\u4e8e\u5f53\u524d\u627e\u5230\u7684\u6700\u4f18\u89e3\u5373\u4e0d\u6ee1\u8db3$upperBound(Shard)\u2265OPT$\uff0c\u5219\u8fd9\u4e2a\u65b9\u6848\u53ef\u4ee5\u76f4\u63a5\u5e9f\u5f03\u3002\u4e0a\u754c\u53ef\u4ee5\u5206\u4e3a4\u90e8\u5206\u8ba1\u7b97\uff1a\u5f53\u524dP\u7684weight\u3002col\u5bfc\u81f4\u7684weight\u3002\u8868level+1\u5230\u8868|V|\u7684\u6700\u4f73\u65b9\u6848\u7684weight\u3002\u8868level+1\u5230\u8868|V|\u7684\u53ea\u8003\u8651Shard\u5bfc\u81f4\u7684\u6700\u4f73\u65b9\u6848\u7684weight\uff0c\u5373\u6bcf\u5f20\u8868\u5206\u522b\u9009\u6700\u4f18\u5217\uff08\u533a\u95f4\u6c42\u548c\uff09\u30023\u4e0e4\u7684\u65b9\u6848\u53ef\u80fd\u4e0d\u662f\u540c\u4e00\u4e2a\u65b9\u6848\uff0c\u4f46$1+2+3+4$\u7684\u503c\u7edd\u5bf9\u662f\u4e00\u4e2a\u4e0a\u754c\u3002\u8ba1\u7b97\u5c42\u9762\uff0c3\u662f\u7531exactSearch\u51fd\u6570\u91cc\u5012\u5e8f\u641c\u7d22\u76f4\u63a5\u8fed\u4ee3\u8ba1\u7b97\u51fa\u6765\u7684\u30021\uff0c2\uff0c4\u53ef\u4ee5\u5728\u7a77\u4e3eShard\u65f6\u5728search\u51fd\u6570\u4e2d\u8fdb\u884c\u7ef4\u62a4\uff0c\u7528\u6811\u72b6\u6570\u7ec4\u7ef4\u62a44\u7684\u533a\u95f4\u548c\uff0c\u6bcf\u4e2a\u8868\u7684max\u503c\u7528\u6570\u7ec4\u8bb0\u5f55\u3002
\"\u56fe\u7247\"<\/p>\n

\"\u56fe\u7247\"
exactSearch\u4e0enaiveSearch\u76f8\u6bd4\u770b\u4e0a\u53bb\u641c\u7d22\u7a7a\u95f4\u53d8\u5927\u4e86\uff0c\u4f46\u8fd9\u662f\u526a\u679d\u7684\u5173\u952e\u3002\u4e0b\u56fe\u662f\u4e00\u4e2a\u526a\u679d\u7684\u793a\u4f8b\uff0cT1\u53ef\u9009\u62c6\u5206\u952e\u4e3a$\/{a,b\/}$\uff0cT2\u53ef\u9009\u62c6\u5206\u952e\u4e3a$\/{c,d\/}$\uff0cT3\u53ef\u9009\u62c6\u5206\u952e\u4e3a$\/{e,f\/}$\uff0cT4\u53ef\u9009\u62c6\u5206\u952e\u4e3a$\/{g,h\/}$\uff0c4\u5f20\u5b50\u56fe\u5206\u522b\u4ee3\u8868exactSearch\u51fd\u65702-7\u884c\u76844\u6b21\u5faa\u73af\uff0c\u5373\u9009\u62e9T4\u7684\u6700\u4f73\u62c6\u5206\u952e\u3001\u9009\u62e9T3,T4\u7684\u6700\u4f73\u62c6\u5206\u952e\u3001\u9009\u62e9T2,T3,T4\u7684\u6700\u4f73\u62c6\u5206\u952e\u3001\u9009\u62e9T1,T2,T3,T4\u7684\u6700\u4f73\u62c6\u5206\u952e\u3002\u7ea2\u8272\u8282\u70b9\u4e3a\u5f53\u524d\u8868\u96c6\u7684\u6700\u4f73\u62c6\u5206\u65b9\u6848\uff0c\u56fe3\u5f97\u51fa\u7684,T2,T3,T4\u7684\u6700\u4f73\u62c6\u5206\u952e\u662f{d,f,h}\u3002\u84dd\u8272\u4e3a\u641c\u7d22\u8fc7\u7a0b\u4e2d\u8bbf\u95ee\u5230\u7684\u8282\u70b9\uff0c\u672a\u904d\u5386\u5230\u5e95\u7684\u8282\u70b9\u5c31\u662f\u88ab\u526a\u679d\u7684\u90e8\u5206\u3002\u56fe4\u4e2d\uff0c\u7a77\u4e3e\u5230$T1=a,T2=d$\u53d1\u73b0\u6709$upperBound(T1=a,T2=d)<OPT$\uff0c\u5219\u8fdb\u884c\u4e86\u526a\u679d\uff0c\u4e0d\u518d\u7a77\u4e3eT3,T4\u7684\u62c6\u5206\u952e\u3002
\"\u56fe\u7247\"
\u526a\u679d\u7684\u80fd\u529b\u7531upperBound\u51fd\u6570\u3001OPT\u7684\u5927\u5c0f\u51b3\u5b9a\uff0c\u4ee5\u4e0b\u52a0\u5f3a\u526a\u679d\u7684\u80fd\u529b\u3002\u7a77\u4e3e\u987a\u5e8f\u6539\u6210\u7a77\u4e3e\u987a\u5e8f\u5bf9\u4e8e\u66b4\u529b\u641c\u7d22\u7684\u901f\u5ea6\u5f71\u54cd\u5f88\u5927\uff0c\u4f8b\u5982clique\u5217\u4e3e\u95ee\u9898\u4e2d\u7684\u5404\u79cd\u542f\u53d1\u5f0f[5]\u3002\u8003\u8651\u5ea6\u6570\u4e3a{1,9,10}\u7684\u5217\u8868\uff0c\u5217\u8868{10,9,1}\u7684\u603b\u7a77\u4e3e\u6570$\u4e3a1+9*1+10*9*1=100$\uff0c\u5217\u8868{1,9,10}\u7684\u603b\u7a77\u4e3e\u6570\u4e3a$10+9*10+1*9*10=190$\u3002\u53e6\u5916\u987a\u5e8f\u8fd8\u4f1a\u5f71\u54cdupperBound\u51fd\u6570\u7684\u503c\u3002\u4e00\u4e2a\u76f4\u89c2\u7684\u65b9\u6cd5\u662f\u6309\u7167\u70b9\u7684\u5ea6\u964d\u5e8f\u6392\u5e8f\uff0c\u8fd9\u91cc\u60f3\u6cd5\u7528\u4e0a\u8ff0{1,9,10}\u7684\u4f8b\u5b50\u53ef\u4ee5\u89e3\u91ca\u3002\u6ce8\u610f\u5230\u526a\u679d\u4e2d\u5f71\u54cd\u8f83\u5927\u7684\u90e8\u5206\u662f4\uff0c\u82e5\u8fde\u63a5\u5728\u4e00\u8d77\u7684\u70b9\u5728\u5217\u8868\u4e2d\u4f4d\u7f6e\u63a5\u8fd1\uff0c\u5219\u53ef\u4ee5\u8f83\u65e9\u51cf\u5c0f4\uff0cPolarDB-X\u91c7\u7528\u7684\u57fa\u4e8e\u5168\u5c40\u6700\u5c0f\u5272\u7684\u7a77\u4e3e\u7b97\u6cd5\u3002\u4ece\u5168\u5c40\u7684\u89d2\u5ea6\u8003\u8651\uff0c\u5c06\u56fe\u5206\u4e3a\u4e24\u5757\uff0c\u4f7f\u5f97\u5b83\u4eec\u4e4b\u95f4\u7684\u8fb9\u6743\u6700\u5c0f\uff0c\u5c06\u70b9\u591a\u7684\u90a3\u4e00\u5757\u653e\u5728\u524d\u9762\uff0c\u4e4b\u540e\u8fed\u4ee3\u5904\u7406\u524d\u540e\u4e24\u5757\u3002\u8fd9\u91cc\u7684\u6bcf\u4e00\u6b21\u5206\u5272\u90fd\u662f\u5168\u5c40\u6700\u5c0f\u5272\u95ee\u9898\uff0c\u9700\u8981\u8c03\u7528n\u6b21Stoer\u2013Wagner\u7b97\u6cd5\uff0c\u603b\u590d\u6742\u5ea6\u4e3a$O(n^2mlogn)$\u3002\u6700\u5c0f\u5272\u7684\u601d\u8def\u8fd8\u7528\u5728[6]\u4e2d\uff0c\u4f46\u662f\u5904\u7406\u7684\u5e76\u4e0d\u662f\u76f8\u5173\u95ee\u9898\u3002OPT\u4f18\u5316\u8ba1\u7b97\u51fa\u6bd4\u8f83\u5927\u7684OPT\u53ef\u52a0\u5f3a\u526a\u679d\u7684\u80fd\u529b\u3002\u5728extraSearch\u6bcf\u8f6e\u5faa\u73af\u5f00\u59cb\u65f6\u7a77\u4e3elevel\u8868\u6240\u6709\u53ef\u62c6\u5206\u7684\u5217\u4e0e\u540e\u7eed\u8868\u7684\u6700\u4f18\u65b9\u6848\u62fc\u63a5\uff0c\u521d\u59cb\u5316\u4e00\u4e2a\u8f83\u5927\u7684OPT\u3002\u5728search\u51fd\u6570\u4e2d\u5c06shard\u4e0eLopt[level+1]\u8fdb\u884c\u62fc\u63a5\u5f97\u5230\u4e00\u4e2a\u8f83\u5927\u7684OPT\u3002\u8fd9\u4e24\u4e2a\u4f18\u5316\u53ef\u4ee5\u76f4\u63a5\u5f97\u5230\u62c6\u5206\u65b9\u6848\uff0c\u5b9e\u9645\u4e0a\u662f\u671f\u671b\u4e2d\u771f\u6b63\u8ba1\u7b97\u51fa\u62c6\u5206\u65b9\u6848\u7684\u5730\u65b9\uff0c\u800c\u975e\u4f9d\u9760\u7a77\u4e3e\u5230\u6700\u540e\u4e00\u5f20\u8868\u3002
\"\u56fe\u7247\"
\u81ea\u9002\u5e94\u8fd1\u4f3c\u4ee5\u4e0a\u63d0\u51fa\u7684\u526a\u679d\u7b56\u7565\u5e76\u4e0d\u80fd\u6539\u53d8np-\u96be\u95ee\u9898\u7684\u672c\u8d28\uff0c\u6240\u4ee5\u4f7f\u7528\u8fd1\u4f3c\u52a0\u901f\u526a\u679d\uff0c\u5373\u526a\u679d\u4fee\u6539\u4e3a$upperBound(Shard)\u2265OPT*ratio$\u3002\u8fd9\u4e2a\u8fd1\u4f3c\u7684\u597d\u5904\u662fratio\u53ef\u4ee5\u4fdd\u8bc1\u8fd1\u4f3c\u6bd4\uff0cratio\u968f\u7740\u641c\u7d22\u65f6\u95f4\u9010\u6e10\u589e\u5927\u3002\u9700\u8981\u6ce8\u610f\u7684\u662f\u5728exactSearch\u4e2d\u4fdd\u5b58\u7ed3\u679c\u65f6\u9700\u8981\u5c06weight\u4fee\u6539\u4e3aweight*ratio\uff0c\u5426\u5219upperBound\u65f6\u4f1a\u8ba1\u7b97\u9519\u8bef\uff0c\u5931\u53bb\u8fd1\u4f3c\u6bd4\u3002\u5176\u4ed6\u7b97\u6cd5\u53ef\u80fd\u627e\u5230\u4e00\u4e2a\u6267\u884c\u8ba1\u5212\uff0c\u4f7f\u5f97\u6709\u4e9b\u8868\u65e0\u6cd5\u88ab\u4e0b\u63a8\uff0c\u8fd9\u6837\u7684\u8868\u4e0e\u672a\u88abjoin\u7684\u8868\u4e00\u8d77\u5148\u7528filter\u7684\u5217\u505a\u62c6\u5206\u952e\u3002\u5426\u5219\u56de\u9000\u5230\u4e3b\u952e\u62c6\u5206\u3002\u53e6\u5916\u884c\u6570\u5c0f\u4e8e\u9608\u503c\u7684\u8868\u4f1a\u88ab\u76f4\u63a5\u63a8\u8350\u4e3a\u5e7f\u64ad\u8868\uff0c\u4e0d\u53c2\u4e0e\u62c6\u5206\u952e\u63a8\u8350\u7684\u8fc7\u7a0b\u3002\u7531\u4e8e\u6574\u4e2a\u7b97\u6cd5\u4e0d\u501f\u52a9\u4f18\u5316\u5668\uff0c\u751f\u6210\u7684\u8ba1\u5212\u5e76\u4e0d\u4e00\u5b9a\u4f1a\u53d8\u4f18\uff0c\u6240\u4ee5\u6700\u540e\u4f1a\u6709\u4e00\u4e2awhatif\u7684\u8fc7\u7a0b\u8ba1\u7b97\u62c6\u5206\u65b9\u5f0f\u53d8\u66f4\u524d\u540e\u4f18\u5316\u5668\u8ba1\u7b97\u51fa\u7684sql\u4ee3\u4ef7\u7684\u53d8\u5316\u3002\u5982\u679c\u8bc4\u4f30\u53d1\u73b0\u4ee3\u4ef7\u5e76\u6ca1\u6709\u53d8\u4f18\uff0c\u7cfb\u7edf\u4f1a\u653e\u5f03\u6b64\u6b21\u63a8\u8350\u7684\u7ed3\u679c\u3002\u4eff\u771f\u9a8c\u8bc1\u8868\u5c5e\u6027\u65f6\u95f4(s)35\u8868 8\u5217\u5e73\u5747\u5ea6\u6570822.05845\u8868 8\u5217\u5e73\u5747\u5ea6\u6570858.575redshift 30\u8868\u5e73\u5747\u5ea6\u65701061.344redshift 40\u8868\u5e73\u5747\u5ea6\u65701098.689redshift 60\u8868\u5e73\u5747\u5ea6\u6570415.98\u661f\u72b6\u56fe 81\u8868\u5e73\u5747\u5ea6\u65701617.041\u661f\u72b6\u56fe 101\u8868\u5e73\u5747\u5ea6\u65701623.012\u7531\u4e8e\u526a\u679d\u80fd\u529b\u53d7\u56fe\u7684\u6027\u8d28\uff08\u968f\u673a\u79cd\u5b50\uff09\u5f71\u54cd\uff0c\u65f6\u95f4\u4e0d\u4e00\u5b9a\u968f\u7740\u56fe\u7684\u53d8\u5927\u800c\u53d8\u5927\u3002\u4e0d\u540c\u60c5\u51b5\u4e0b\u80fd\u5904\u7406\u7684\u8868\u6570\u76ee\u5dee\u5f02\u8f83\u5927\uff0c\u96be\u4ee5\u63d0\u524d\u9884\u6d4b\u65f6\u95f4\u3002\u65f6\u95f4\u6da8\u5e45\u4e0d\u662f\u592a\u5927\uff0c\u56e0\u4e3a\u81ea\u9002\u5e94\u8fd1\u4f3c\u5c06\u65f6\u95f4\u538b\u4e86\u4e0b\u6765\uff0c\u4e14\u5927\u56fe\u4e0a\u6811\u72b6\u6570\u7ec4\u7684\u4f5c\u7528\u6bd4\u8f83\u660e\u663e\u3002\u771f\u5b9e\u60c5\u51b5\u4e0b\u56fe\u7684\u5bc6\u5ea6\u4e0d\u4f1a\u50cf\u4eff\u771f\u4e2d\u8fd9\u4e48\u9ad8\uff0c\u80fd\u8f83\u5feb\u5904\u740640\u300150\u5f20\u8868\u3002\u4f7f\u7528\u793a\u4f8b\u5728PolarDB-X\u4e2d\u4f7f\u7528\u62c6\u5206\u952e\u63a8\u8350\uff0c\u53ea\u9700\u8981\u5728\u5bf9\u5e94\u7684\u5e93\u4e2d\u8f93\u5165sql\u201csharingadvise\u201d\u5373\u53ef\uff08\u7531\u4e8e\u9700\u8981\u8c03\u7528plan cache\u4e2d\u7684sql\u4f5c\u4e3aworkload\u4e14\u7b97\u6cd5\u5bf9\u4e8eCN\u538b\u529b\u8f83\u5927\uff0c\u5efa\u8bae\u5728\u538b\u6d4b\u9636\u6bb5\u8fdb\u884c\u62c6\u5206\u952e\u63a8\u8350\uff09\u3002\u4ee5\u4e0b\u4e3aworkload\u4e3atpcc 100\u4ed3\u65f6\u57fa\u4e8eplan cache\u8fdb\u884c\u62c6\u5206\u952e\u63a8\u8350\u7684\u8fc7\u7a0b\u6f14\u793a\u3002\u5c5e\u6027\u914d\u7f6ePolarDB-Xpolarx-kernel_5.4.14-16601976_xcluster-20220728CN2\u53f04C32GDN2\u53f04C32GTPCC100\u4ed3\u62c6\u5206\u65b9\u5f0fauto\u5e93\u968f\u673akey\u62c6\u5206warehouses100terminals50runMins30limitTxnsPerMin0terminalWarehouseFixedtruenewOrderWeight45paymentWeight43orderStatusWeight4deliveryWeight4stockLevelWeight4\u521d\u59cb\u7684\u60c5\u51b5
\"\u56fe\u7247\"
\u538b\u6d4b\u7ed3\u679c
\"\u56fe\u7247\"
\u62c6\u5206\u952e\u63a8\u8350sharingadvise\u6307\u4ee4\u4f1a\u6839\u636eplan cache\u7ed9\u51fa\u76f8\u5173\u7684sql\u5efa\u8bae\u4ee5\u53ca\u9884\u8ba1\u7684\u4ee3\u4ef7\u53d8\u5316\u3002
\"\u56fe\u7247\"
\u6267\u884c\u4e0a\u9762\u63a8\u8350\u51fa\u6765\u7684\u62c6\u5206\u952e\u53d8\u66f4\u8bed\u53e5
\"\u56fe\u7247\"
\u9a8c\u8bc1\u62c6\u5206\u952e\u53d8\u5316
\"\u56fe\u7247\"
\u518d\u6b21\u538b\u6d4bTPCC\uff0ctpmC\u63d0\u5347\u81f38\u500d
\"\u56fe\u7247\"
\u603b\u7ed3\u4ece\u4e0a\u9762\u7684\u5b9e\u9a8c\u53ef\u4ee5\u53d1\u73b0\uff0c\u5373\u4f7f\u662ftp\u67e5\u8be2\uff0c\u9519\u8bef\u7684\u62c6\u5206\u952e\u4e5f\u4f1a\u56e0\u4e3a\u5927\u91cf\u5f15\u5165\u5206\u5e03\u5f0f\u4e8b\u52a1\u5bfc\u81f4\u6027\u80fd\u53d7\u5230\u5f88\u5927\u7684\u5f71\u54cd\u3002PolarDB-X\u201c\u624b\u81ea\u4e00\u4f53\u201d\u7684\u65b9\u6848\u5bf9\u4e8e\u62c6\u5206\u952e\u7684\u9009\u62e9\u6709\u4e00\u5b9a\u8981\u6c42\uff0c\u62c6\u5206\u952e\u63a8\u8350\u63d0\u4f9b\u4e86\u624b\u52a8\u9009\u62e9\u62c6\u5206\u952e\u7684\u65b9\u6848\uff0c\u51cf\u8f7b\u4eba\u529b\u8d1f\u62c5\u3002\u53c2\u8003\u6587\u732e[1] Andrew Pavlo, Carlo Curino, and Stanley Zdonik. 2012. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD ’12). Association for Computing Machinery, New York, NY, USA, 61\u201372.[2] Erfan Zamanian, Carsten Binnig, and Abdallah Salama. 2015. Locality-aware Partitioning in Parallel Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 17\u201330.[3] Rimma Nehme and Nicolas Bruno. 2011. Automated partitioning design in parallel database systems. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD ’11). Association for Computing Machinery, New York, NY, USA, 1137\u20131148.[4] Panos Parchas, Yonatan Naamad, Peter Van Bouwel, Christos Faloutsos, and Michalis Petropoulos. 2020. Fast and effective distribution-key recommendation for amazon redshift. Proc. VLDB Endow. 13, 12 (August 2020), 2411\u20132423.[5] Rong-Hua Li, Sen Gao, Lu Qin, Guoren Wang, Weihua Yang, and Jeffrey Xu Yu. 2020. Ordering heuristics for k-clique listing. Proc. VLDB Endow. 13, 12 (August 2020), 2536\u20132548.[6] Carlo Curino, Evan Jones, Yang Zhang, and Sam Madden. 2010. Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow. 3, 1\u20132 (September 2010), 48\u201357\u539f\u6587\u94fe\u63a5\uff1ahttps:\/\/click.aliyun.com\/m\/10…<\/a>\u672c\u6587\u4e3a\u963f\u91cc\u4e91\u539f\u521b\u5185\u5bb9\uff0c\u672a\u7ecf\u5141\u8bb8\u4e0d\u5f97\u8f6c\u8f7d\u3002<\/p>\n

https:\/\/segmentfault.com\/a\/1190000042511386<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

\u7b80\u4ecb\uff1a\u00a0PolarDB-X 2.0\u63d0\u4f9b\u4e86\u900f\u660e\u5206\u5e03\u5f0f\u7684\u80fd\u529b\uff0c\u9ed8\u8ba4\u8fdb\u884c\u4e3b\u952e\u7684\u54c8\u5e0c\u62c6\u5206\uff0c\u8ba9\u7528\u6237\u65e0\u611f\u77e5\u7684\u4ece\u5355\u673a\u6570\u636e\u5e93\u8fc1 […]<\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[],"tags":[],"class_list":["post-10006537","post","type-post","status-publish","format-standard","hentry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006537","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10006537"}],"version-history":[{"count":0,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006537\/revisions"}],"wp:attachment":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10006537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10006537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10006537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}