Changeset: e55673cd8efc for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=e55673cd8efc Modified Files: monetdb5/optimizer/opt_tarantula.mx Branch: default Log Message:
This code has become obsolete The octopus code base and new binary transport is more generic solution. diffs (truncated from 1240 to 300 lines): diff --git a/monetdb5/optimizer/opt_tarantula.mx b/monetdb5/optimizer/opt_tarantula.mx deleted file mode 100644 --- a/monetdb5/optimizer/opt_tarantula.mx +++ /dev/null @@ -1,1235 +0,0 @@ -@/ -The contents of this file are subject to the MonetDB Public License -Version 1.1 (the "License"); you may not use this file except in -compliance with the License. You may obtain a copy of the License at -http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html - -Software distributed under the License is distributed on an "AS IS" -basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the -License for the specific language governing rights and limitations -under the License. - -The Original Code is the MonetDB Database System. - -The Initial Developer of the Original Code is CWI. -Portions created by CWI are Copyright (C) 1997-July 2008 CWI. -Copyright August 2008-2011 MonetDB B.V. -All Rights Reserved. -@ - -@f opt_tarantula -@a M. Kersten -@- Multileg creatures -Query execution can be improved significantly using distributed processing. -Traditionally, this encompasses fragmentation and allocation of the base -tables over multiple sites and query plans that include on the fly transport -of intermediate results. - -Breaking the database into pieces itself is a well-studied area. -Most approaches consider the workload and search for a good split -of the base tables, such that the workload performance improves. - -The Tarantula optimizer, like the Octopus optimizer, use the -output of the mitosis+mergetable optimizer and produces the -actual plans for parallel execution. -The tarantula untangles the query plan into a controlling head -function and a series of subplans, one for each leg to execute concurrently. - -The target for breaking the plan are the blocking operations, -in particular mat.pack(). The flow graph leading to the -the pack arguments are extracted from the query plan and -each subgraph is cast into an independent plan. -Since the query plan is a DAG, it is perfectly possible that -a portion being extracted is shared amongst all legs. -The naive extraction then leads to a re-calculation of -shared intermediates in each leg. - -The subplan produces the argument to the blocking operator, whose -result will be assembled in the head. It is also perfectly possible -that variables assigned a value are used later on in the query graph. -These variables are identified and one leg becomes responsible to -return it also to the head to be used later on. - -The orginal pack operation is replaced by a call to a function -to orchestrate the distributed processing and return the final -result. Then the next pack operation is searched and its -subgraph is derived. Again, it may share portions produced -in the first pack subgraph. - -A potential more optimal scheme would be to detect each such case and -turn it into a splitting point as well. This can be detected by -looking for the last assignment and multiple use cases. [VARIANT TODO] - -The allocation of a subplan to leg depends on a bidding scheme. -Bidding can not depend on BAT arguments, because that would cause -significant communication overhead. Scalar values could be used and -would function well in terms of using the recycler to get involved into -precise bidding. - -A snippet of an tarantula plan with two legs is shown. -The main part of the query becomes a three step procedure of -1) remote registration of subplans, 2) obtaining bids and schedule design -and 3) execute the subplans. -Each plan does not contain duplicate node ids. -@verbatim -function reg_qry_0():int; - tarantula.register(0,"qry_0","qry_1"); - tarantula.register(1,"qry_0","qry_1"); - return 0; -end reg_qry; - -function bid_qry_0(hdl:int)(leg0:int,leg1:int,leg2:int,leg3:int); - (_4,_5) := tarantula.getBid(0,"qry_0","qry_1"); - (_6,_7) := tarantula.getBid(1,"qry_0","qry_1"); - return (leg0,leg1,leg2,leg3) := scheduler.schedule_0(_4,_5,_6,_7); -end bid_qry; - -function run_qry(node_0:int,node_1:int):bat[:oid,:int] - _87 := tarantula.execute(node_0,"leg0"); - _88 := tarantula.execute(node_1,"leg1"); - _15 := mat.pack(_87,_88); - return run_qry := _15; -end run_qry; - -function user.qry():void; - _3 := reg_qry_0(); - (_4,_5,_6,_7):= bid_qry_0(_3); - _15 := tarantula.run_qry(_4,_5,_6,_7); - _16 := sql.resultSet(1,1,_15); - sql.rsColumn(_16,"sys.squida","bid","int",32,0,_15); - _21 := io.stdout(); - sql.exportResult(_21,_16); -end qry; -@end verbatim -The nodes addressed by the tarentula are indices into a global catalog. -The number of subplans is derived by the Mitosis as the number of pieces to consider. -The tarantula may register the subplans to more nodes than pieces. - -@verbatim -function tarantula.exec_qry_0(node:str,fcn:str):bat[:oid,:int]; - conn:= remote.connect(node,"monetdb","monetdb"); - r:= remote.exec(conn,"tarantula",fcn); - b:bat[:oid,:int]:= remote.get(conn,r); - return b; -end exec_qry; -@end verbatim - -@verbatim -function tarantula.qry_0(version:int):bat[:oid,:int]; - _53:bat[:oid,:int] := attach.bind("file://export/scratch/mk/dbfarm/demo/bat/01/001"); - _54 := algebra.slice(_53,0@0,25@0); - _63:bat[:oid,:int] := attach.bind("file://export/scratch/mk/dbfarm/demo/bat/01/002"); - _64 := algebra.slice(_63,0@0,25@0); - _72 := algebra.kdifference(_54,_64); - _78 := algebra.kunion(_72,_64); - _13:bat[:oid,:oid] := attach.bind("file://export/scratch/mk/dbfarm/demo/bat/01/003"); - _14 := bat.reverse(_13); - _85 := algebra.kdifference(_78,_14); - return qry_0 := _85; -end tarantula.qry_0; - -function tarantula.qry_1(version:int):bat[:oid,:int]; - ... use second slice ... -end tarantula.qry_1; - -@end verbatim - -[Stability] -We assume that during a session, workers once started will remain alive. -No fault tolerance techniques are included. - -[Recycling] -The legs contain registered functions and possible partial results in its recycler pool. -In the first implementation we assume a read-only database, where all workers are -restarted when changes to the underlying database affect the recycler pool. -Alternative, the head can clear the recycler pool explicitly upon such state change. - -[Shared disk] -For a leg to work it needs access to its storage layer, which is a NAS. -It is encapsulated in the operation attach.bind("path",tuplecount,low_oid,high_oid). - -The code generation for the legs currently relies on a conceptual full replication of -the database over the servers. The next version should use the attach() functionality -or use the datacylcotron to access portions. - -These approaches are different from the Octopus, where the head is -the sole control over the persistent data. - -[Naming] -The legs received from the tarantula should be ensured -not to clash with those already known. Therefore, we simply -tag them by orginating site. - -[Caveats] -Any update invalidates the request to distributed processing. -In the same line, multi-statement SQL transactions and -updates to global variables are ignored. - -Global variables are tricky, because they are part of the -session context. To make it work, we need to be able to perform -an upcall to that context (=dangerous). -The solution is that any variable context should be -passed through a relation. - -[The hard world] The way plans are generated by mitosis leads to a large number of -mat.pack() operations, whose result is subsequently spread out over the legs again -for continual processing. This leads to a lot of transport, from leg->head->all-legs. -This situation can be circumvented by allowing each leg to call upon all tarantula legs -to solve the problem at hand. With recycling enabled in each leg, duplicate work will -be avoided and a direct copy of the data is obtained. - -To make this work, we have to keep track of what input variables for a leg -are effectively the result of a tarantula call and inject its materialisation -in the leg upon first use. -@{ -@mal -module tarantula; -pattern optimizer.tarantula():str -address OPTtarantula; -pattern optimizer.tarantula(mod:str, fcn:str):str -address OPTtarantula -comment "Map-execute-reduce parallelism optimizer"; - -@h -#ifndef _TAR_OCTOPUS_ -#define _TAR_OCTOPUS_ -#include "opt_prelude.h" -#include "opt_support.h" - -#ifdef WIN32 -#if !defined(LIBMAL) && !defined(LIBATOMS) && !defined(LIBKERNEL) && !defined(LIBMAL) && !defined(LIBOPTIMIZER) && !defined(LIBSCHEDULER) && !defined(LIBMONETDB5) -#define opt_export extern __declspec(dllimport) -#else -#define opt_export extern __declspec(dllexport) -#endif -#else -#define opt_export extern -#endif - -typedef struct REGMAL{ - str fcn; - struct REGMAL *nxt; -} *Registry; - -typedef struct { - str uri; - str usr; - str pwd; - Registry nxt; /* list of registered mal functions */ - bte active; - str conn; - int inuse; -} Peer; - -#include "opt_mitosis.h" -#define MINLEGSIZE 5 /* number of MAL instructions to consider for a leg */ -#define MAXSHARE 64 /* number of input output arguments to consider */ -#define VTOP 2 /* multiplier margin, theoretical each variable can be replaced by a new one */ -#define MAXSITES MAXSLICES /* should become dynamic at some point */ - -opt_export Peer peers[MAXSITES]; /* registry of peer servers */ -opt_export int TARnrpeers; -opt_export bte tarantulaLocal; - -opt_export int TARgetPeer(str uri); -opt_export int OPTtarantulaAdviceInternal(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci); - -@:exportOptimizer(tarantula)@ - -#define OPTDEBUGtarantula if ( optDebug & ((lng)1 <<DEBUG_OPT_TARANTULA) ) - -#endif -@c -#include "monetdb_config.h" -#include "mal_interpreter.h" /* for showErrors() */ -#include "mal_builder.h" -#include <mapi.h> -#include "remote.h" -#include "mal_sabaoth.h" -#include "opt_tarantula.h" -#include "opt_deadcode.h" - - -Peer peers[MAXSITES]; /* registry of peer servers */ -int TARnrpeers=0; -bte tarantulaLocal=0; - -#define SHAREDDISK 1 /* assume a shared file system */ -#define SHAREDINTERMEDIATES 2 /* propagate intermediates to head */ -int strategy = SHAREDDISK ; -@- -The algorithm consists of several steps. The first one -replaces the original query and creates the leg functions. -In the second phase the should be registered at the different sites. - -The key observation is that whenever we encounter a mat.pack, -there is a need to bring information together for inspection. -It indicates a blocking operation. -Therefore, we recursively break a plan by looking for the -pack instructions and collect all dependent instructions. -The original block is trimmed as far as needed. - -During the development we take the default number of pieces -to be equal to the thread count. -@c -int -OPTtarantulaAdviceInternal(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci) -{ - - (void) stk; - (void) pci; - if ( isOptimizerEnabled(mb,tarantulaRef) ) - return GDKnr_threads; - return -1; -} -static int -TARinitcode(Client cntxt, MalBlkPtr mb){ - InstrPtr p; - str s; - str l = NULL; - - (void) cntxt; - - /* _x := remote.connect(uri,"monetdb","monetdb","msql"); */ - p = newStmt(mb, remoteRef,connectRef); - s = GDKgetenv("merovingian_uri"); _______________________________________________ Checkin-list mailing list [email protected] http://mail.monetdb.org/mailman/listinfo/checkin-list
