query-plan-sankey

_.md

[ Launch: sankey-test-1 ] ff9cb26a35ad7c41501f08ebadf2be84 by whitelynx
[ Launch: sankey-test-1 ] 2446e1dc3bc789e7a4ca25872f621bd6 by whitelynx
[ Launch: diagonal-test-1 ] 1217283ecbd2093073d4 by jdutta
[ Launch: quick-chart-vert ] 2c8553335067321f44a4 by jdutta
[ Launch: quick-chart-1 ] 99181b7e0eb393be4380 by jdutta
[ Launch: scratchpad ] 9721189 by jdutta

config.json

{"description":"query-plan-sankey","endpoint":"","display":"svg","public":true,"require":[],"fileconfigs":{"inlet.js":{"default":true,"vim":false,"emacs":false,"fontSize":12},"_.md":{"default":true,"vim":false,"emacs":false,"fontSize":12},"config.json":{"default":true,"vim":false,"emacs":false,"fontSize":12},"s_action.csv":{"default":true,"vim":false,"emacs":false,"fontSize":12},"inlet.css":{"default":true,"vim":false,"emacs":false,"fontSize":12},"c_ip.csv":{"default":true,"vim":false,"emacs":false,"fontSize":12},"chart_data.csv":{"default":true,"vim":false,"emacs":false,"fontSize":12},"sankey.js":{"default":true,"vim":false,"emacs":false,"fontSize":12},"main.css":{"default":true,"vim":false,"emacs":false,"fontSize":12},"data1.json":{"default":true,"vim":false,"emacs":false,"fontSize":12},"data2.json":{"default":true,"vim":false,"emacs":false,"fontSize":12},"data3.json":{"default":true,"vim":false,"emacs":false,"fontSize":12},"parseQueryPlan.js":{"default":true,"vim":false,"emacs":false,"fontSize":12}},"fullscreen":false,"play":false,"loop":false,"restart":false,"autoinit":true,"pause":true,"loop_type":"pingpong","bv":false,"nclones":15,"clone_opacity":0.4,"duration":3000,"ease":"linear","dt":0.01,"ajax-caching":true,"thumbnail":"http://i.imgur.com/1im8jwg.gif"}

data1.json

[{"Plan":{"Node Type":"Aggregate","Strategy":"Sorted","Startup Cost":71273.97,"Total Cost":71281.47,"Plan Rows":200,"Plan Width":8,"Actual Startup Time":1085.898,"Actual Total Time":1103.093,"Actual Rows":6,"Actual Loops":1,"Output":["count(*)","layout_count_by_map.max_layout_count"],"Group Key":["layout_count_by_map.max_layout_count"],"Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Aggregate","Strategy":"Sorted","Parent Relationship":"InitPlan","Subplan Name":"CTE layout_count_by_map","Startup Cost":60416.9,"Total Cost":71254.32,"Plan Rows":200,"Plan Width":12,"Actual Startup Time":908.495,"Actual Total Time":1055.728,"Actual Rows":12619,"Actual Loops":1,"Output":["max((count(*)))","ml.map_id"],"Group Key":["ml.map_id"],"Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Aggregate","Strategy":"Sorted","Parent Relationship":"Outer","Startup Cost":60416.9,"Total Cost":66193.66,"Plan Rows":144419,"Plan Width":10,"Actual Startup Time":908.486,"Actual Total Time":1012.562,"Actual Rows":41951,"Actual Loops":1,"Output":["count(*)","ml.map_id","ml.map_id","l.reinyear"],"Group Key":["ml.map_id","l.reinyear"],"Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Seq Scan","Parent Relationship":"InitPlan","Subplan Name":"InitPlan 1 (returns $0)","Relation Name":"layer_type","Schema":"mapping","Alias":"layer_type","Startup Cost":0,"Total Cost":1.2,"Plan Rows":1,"Plan Width":4,"Actual Startup Time":0.006,"Actual Total Time":0.007,"Actual Rows":1,"Actual Loops":1,"Output":["layer_type.id"],"Filter":"((layer_type.name)::text = 'layout'::text)","Rows Removed by Filter":6,"Shared Hit Blocks":1,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0},{"Node Type":"Sort","Parent Relationship":"Outer","Startup Cost":60415.7,"Total Cost":60776.75,"Plan Rows":144419,"Plan Width":10,"Actual Startup Time":908.473,"Actual Total Time":940.067,"Actual Rows":42517,"Actual Loops":1,"Output":["ml.map_id","l.reinyear"],"Sort Key":["ml.map_id","l.reinyear"],"Sort Method":"quicksort","Sort Space Used":4858,"Sort Space Type":"Memory","Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Hash Join","Parent Relationship":"Outer","Join Type":"Inner","Startup Cost":22833.55,"Total Cost":48039.07,"Plan Rows":144419,"Plan Width":10,"Actual Startup Time":117.542,"Actual Total Time":855.128,"Actual Rows":42517,"Actual Loops":1,"Output":["ml.map_id","l.reinyear"],"Hash Cond":"(ml.layer_id = l.id)","Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Seq Scan","Parent Relationship":"Outer","Relation Name":"map_layer","Schema":"mapping","Alias":"ml","Startup Cost":0,"Total Cost":14915.68,"Plan Rows":433256,"Plan Width":8,"Actual Startup Time":0.008,"Actual Total Time":314.4,"Actual Rows":433295,"Actual Loops":1,"Output":["ml.map_id","ml.layer_id"],"Shared Hit Blocks":1918,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0},{"Node Type":"Hash","Parent Relationship":"Inner","Startup Cost":18138.4,"Total Cost":18138.4,"Plan Rows":144466,"Plan Width":10,"Actual Startup Time":117.008,"Actual Total Time":117.008,"Actual Rows":42551,"Actual Loops":1,"Output":["l.reinyear","l.id"],"Hash Buckets":16384,"Hash Batches":1,"Original Hash Batches":1,"Peak Memory Usage":2161,"Shared Hit Blocks":4054,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Seq Scan","Parent Relationship":"Outer","Relation Name":"layer","Schema":"mapping","Alias":"l","Startup Cost":0,"Total Cost":18138.4,"Plan Rows":144466,"Plan Width":10,"Actual Startup Time":0.032,"Actual Total Time":81.602,"Actual Rows":42551,"Actual Loops":1,"Output":["l.reinyear","l.id"],"Filter":"(l.layer_type_id = $0)","Rows Removed by Filter":390778,"Shared Hit Blocks":4054,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0}]}]}]}]}]},{"Node Type":"Sort","Parent Relationship":"Outer","Startup Cost":19.64,"Total Cost":20.14,"Plan Rows":200,"Plan Width":8,"Actual Startup Time":1085.887,"Actual Total Time":1094.175,"Actual Rows":12619,"Actual Loops":1,"Output":["layout_count_by_map.max_layout_count"],"Sort Key":["layout_count_by_map.max_layout_count"],"Sort Method":"quicksort","Sort Space Used":976,"Sort Space Type":"Memory","Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"CTE Scan","Parent Relationship":"Outer","CTE Name":"layout_count_by_map","Alias":"layout_count_by_map","Startup Cost":0,"Total Cost":12,"Plan Rows":200,"Plan Width":8,"Actual Startup Time":908.5,"Actual Total Time":1075.683,"Actual Rows":12619,"Actual Loops":1,"Output":["layout_count_by_map.max_layout_count"],"Shared Hit Blocks":5972,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write Time":0}]}]},"Planning Time":0.315,"Triggers":[],"Execution Time":1103.468}]

data2.json

{
  "nodes": [
    {"name": "GoogleDrive"},
    {"name": "Dropbox"},
    {"name": "Box"},
    {"name": "Exposed"},
    {"name": "PCI"},
    {"name": "HIPAA"},
    {"name": "PII"}
  ],
  "links": [
    {"source": 0, "target": 3, "value": 730},
    {"source": 0, "target": 4, "value": 228},
    {"source": 0, "target": 5, "value": 25},
    {"source": 0, "target": 6, "value": 238},
    {"source": 1, "target": 3, "value": 133},
    {"source": 1, "target": 4, "value": 28},
    {"source": 1, "target": 5, "value": 11},
    {"source": 1, "target": 6, "value": 12},
    {"source": 2, "target": 3, "value": 51},
    {"source": 2, "target": 4, "value": 2},
    {"source": 2, "target": 5, "value": 2},
    {"source": 2, "target": 6, "value": 1}
  ]
}

data3.json

{
  "nodes": [
    {
      "Node Type": "Result",
      "Startup Cost": 0,
      "Total Cost": 50.13,
      "Plan Rows": 7,
      "Plan Width": 405,
      "Actual Startup Time": 0.139,
      "Actual Total Time": 0.231,
      "Actual Rows": 4,
      "Actual Loops": 1
    },
    {
      "Node Type": "Append",
      "Parent Relationship": "Outer",
      "Startup Cost": 0,
      "Total Cost": 50.11,
      "Plan Rows": 7,
      "Plan Width": 405,
      "Actual Startup Time": 0.131,
      "Actual Total Time": 0.218,
      "Actual Rows": 4,
      "Actual Loops": 1
    },
    {
      "Node Type": "Index Scan",
      "Parent Relationship": "Member",
      "Scan Direction": "NoMovement",
      "Index Name": "idx_paris_tags",
      "Relation Name": "paris",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 8.27,
      "Plan Rows": 1,
      "Plan Width": 450,
      "Actual Startup Time": 0.009,
      "Actual Total Time": 0.009,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Index Cond": "(tags ? 'tourism'::text)",
      "Filter": "(ar_num = 8)"
    },
    {
      "Node Type": "Seq Scan",
      "Parent Relationship": "Member",
      "Relation Name": "paris_linestrings",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 11.8,
      "Plan Rows": 1,
      "Plan Width": 450,
      "Actual Startup Time": 0.001,
      "Actual Total Time": 0.001,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Filter": "((tags ? 'tourism'::text) AND (ar_num = 8))"
    },
    {
      "Node Type": "Index Scan",
      "Parent Relationship": "Member",
      "Scan Direction": "NoMovement",
      "Index Name": "idx_paris_points_tags",
      "Relation Name": "paris_points",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 8.27,
      "Plan Rows": 1,
      "Plan Width": 450,
      "Actual Startup Time": 0.003,
      "Actual Total Time": 0.003,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Index Cond": "(tags ? 'tourism'::text)",
      "Filter": "(ar_num = 8)"
    },
    {
      "Node Type": "Index Scan",
      "Parent Relationship": "Member",
      "Scan Direction": "NoMovement",
      "Index Name": "idx_paris_polygons_tags",
      "Relation Name": "paris_polygons",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 8.27,
      "Plan Rows": 1,
      "Plan Width": 450,
      "Actual Startup Time": 0.002,
      "Actual Total Time": 0.002,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Index Cond": "(tags ? 'tourism'::text)",
      "Filter": "(ar_num = 8)"
    },
    {
      "Node Type": "Seq Scan",
      "Parent Relationship": "Member",
      "Relation Name": "paris_linestrings_ar_08",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 7.27,
      "Plan Rows": 1,
      "Plan Width": 513,
      "Actual Startup Time": 0.103,
      "Actual Total Time": 0.103,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Filter": "((tags ? 'tourism'::text) AND (ar_num = 8))"
    },
    {
      "Node Type": "Seq Scan",
      "Parent Relationship": "Member",
      "Relation Name": "paris_points_ar_08",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 5.16,
      "Plan Rows": 1,
      "Plan Width": 72,
      "Actual Startup Time": 0.009,
      "Actual Total Time": 0.085,
      "Actual Rows": 4,
      "Actual Loops": 1,
      "Filter": "((tags ? 'tourism'::text) AND (ar_num = 8))"
    },
    {
      "Node Type": "Seq Scan",
      "Parent Relationship": "Member",
      "Relation Name": "paris_polygons_ar_08",
      "Alias": "paris",
      "Startup Cost": 0,
      "Total Cost": 1.08,
      "Plan Rows": 1,
      "Plan Width": 450,
      "Actual Startup Time": 0.007,
      "Actual Total Time": 0.007,
      "Actual Rows": 0,
      "Actual Loops": 1,
      "Filter": "((tags ? 'tourism'::text) AND (ar_num = 8))"
    },
    {"Node Type": "total"}
  ],
  "links": [
    {"source":1,"target":0,"value":0.218},
    {"source":2,"target":1,"value":0.009},
    {"source":3,"target":1,"value":0.001},
    {"source":4,"target":1,"value":0.003},
    {"source":5,"target":1,"value":0.002},
    {"source":6,"target":1,"value":0.103},
    {"source":7,"target":1,"value":0.085},
    {"source":8,"target":1,"value":0.007},
    {"source":0,"target":9,"value":0.231}
  ]
}

inlet.js

// PostgreSQL query plan viewer (based loosely on d3.sankey)

try {
  // Configurable params
  // Click on the number and see a magic slider appears to tweak it.
  var config = {
    width: 700,
    height: 382,
    /*
    nameKey: 'name',
    valueKey: 'value',
    /*/
    nameKey: 'Node Type',
    valueKey: 'Actual Total Time',
    //*/
    padding: 10
  };

  var data = d3.parseQueryPlans(tributary.data1)[0];
  //var data = tributary.data2;
  //var data = tributary.data3;

  var getUid = (function () {
    var counter = 0;
    return function() {
      return 'uid-' + counter++;
    }
  })();

  function assignUid(data) {
    data.nodes.forEach(function (d) {
      d.uid = getUid();
    });
    data.links.forEach(function (d) {
      d.uid = getUid();
    });
    return data;
  }

  console.log(data)

  visualize(assignUid(data));
} catch(exc) {
  console.error('Error:', exc);
}


function visualize(data) {

  var svg = d3.select('svg')
    .on('dblclick.zoom', null);

  var width = parseInt(svg.style('width'), 10);
  var height = parseInt(svg.style('height'), 10);
  console.log(width, height);

  var zoom = d3.behavior.zoom()
    .scaleExtent([0.1, 1])
    .size([width, height])
    .translate([config.padding, config.padding])
    .on("zoom", function() {
      gRoot
        .interrupt('zoom')
        .transition('zoom')
        .duration(10)
        .ease('easeOutQuart')
      .attr('transform', `translate(${d3.event.translate}) scale(${d3.event.scale})`);
    });

  svg.call(zoom);
  var gRoot = svg.append('svg:g')
    .attr('transform', `translate(${config.padding}, ${config.padding})`);

  var color = d3.scale.category20();

  // Set the sankey diagram properties
  var sankey = d3.sankey()
      .nodeWidth(96)
      .curvature(0.6)
      .nodes(data.nodes)
      .links(data.links)
      .layout(32);

  /*
  addResizeListener(svg.node(), () => {
    width = parseInt(svg.style('width'), 10);
    height = parseInt(svg.style('height'), 10);
    console.log('on resize:', width, height);
    zoom.size([width, height]);
    sankey
      .size([width - 2 * config.padding, config.height])
      .relayout();
  });
  //*/

  var path = sankey.link(); // path function

  var link = gRoot.selectAll(".link")
      .data(data.links)
      .enter().append("path")
      .attr("class", "link")
      .attr('id', function (d) { return d.uid; })
      .attr("d", path)
      //.style('fill', 'none').style('stroke', '#000').style('stroke-opacity', 0.2)
      .style("stroke-width", function(d) { return Math.max(1, d.dy); })
      .sort(function(a, b) { return b.dy - a.dy; });

  link.append("title")
        .text(function(d) {
            return d.source[config.nameKey] + " → " + d.target[config.nameKey] + "\n" +
                d.source[config.valueKey];
			//return d.source.name + " → " + d.target.name + "\n" + d.value; 
        });

  var node = gRoot.selectAll(".node")
    .data(data.nodes)
    .enter().append("g")
      .attr("class", "node")
      .attr("transform", function(d) { 
		  return "translate(" + d.x + "," + d.y + ")"; });

  node.append("rect")
      .attr("height", sankey.nodeWidth())//function(d) { return d.dy; })
      .attr("width", sankey.nodeWidth())
      .style("fill", function(d) { 
		  return d.color = color(d[config.nameKey]); })
      .style("stroke", function(d) { 
		  return d3.rgb(d.color).darker(2); })
      .append("title")
      .text(function(d) { return d[config.nameKey] + "\n" + d[config.valueKey]; });

  node.append("text")
      .attr("x", sankey.nodeWidth() / 2)
      .attr("y", sankey.nodeWidth() / 2)
      .attr("dy", ".15em")
      .attr("text-anchor", "middle")
      .attr("transform", null)
      .text(function(d) { return d[config.nameKey]; });
  node.append("text")
      .attr('class', 'small')
      .attr("x", sankey.nodeWidth() / 2)
      .attr("y", sankey.nodeWidth() / 2)
      .attr("dy", "1.15em")
      .attr("text-anchor", "middle")
      .attr("transform", null)
      .text(function(d) { return d["Relation Name"]; });

  node.on('mouseover', function (d) {
    console.log(d);
    d3.selectAll('.link').classed('active', false);
    d.sourceLinks.forEach(function (x) {
      d3.select('#' + x.uid).classed('active', true);
    })
    d.targetLinks.forEach(function (x) {
      d3.select('#' + x.uid).classed('active', true);
    })
  });
  node.on('mouseout', function (d) {
    d3.selectAll('.link').classed('active', false);
  });
}

d3.selection.prototype.moveToFront = function() {
  return this.each(function() {
    this.parentNode.appendChild(this);
  });
};

main.css

.node rect {
  cursor: move;
  fill-opacity: .9;
  shape-rendering: crispEdges;
}

.node text {
  font-size: 12px;
  pointer-events: none;
  text-shadow: 0 1px 0 #fff;
}
.node text.small {
  font: 8px sans-serif;
}

.link {
  fill: none;
  stroke: #000;
  stroke-opacity: 0.1;
}

.link.active {
  stroke-opacity: 0.5;
}

.link:hover {
  stroke-opacity: 0.3;
}

parseQueryPlan.js

d3.parseQueryPlans = function(queryPlans) {
	return queryPlans.map(queryPlan => {
		var nodes = [], links = [];

		function visitNode(plan, parentPlanIdx) {
			var planIdx = nodes.push(_.omit(plan, 'Plans')) - 1;

			if(parentPlanIdx !== undefined) {
				links.push({
      				//*
					source: planIdx,
					target: parentPlanIdx,
      				/*/
					source: parentPlanIdx,
					target: planIdx,
                    //*/
					value: plan["Actual Total Time"],
				});
			}

			if(plan.Plans) {
				plan.Plans.forEach(subPlan => visitNode(subPlan, planIdx));
			}
		}

		visitNode(queryPlan.Plan);

		return { nodes, links };
	});
};

sankey.js

d3.sankey = function() {
	var sankey = {},
		nodeWidth = 96,
		horizontalPadding = 64,
		verticalPadding = 32,
		nodes = [],
		links = [],
		maxValue = 0,
		bbox = [Infinity, Infinity, -Infinity, -Infinity],
		defaultCurvature = 0.5;

	sankey.nodeWidth = function(_) {
		if (!arguments.length) return nodeWidth;
		nodeWidth = +_;
		return sankey;
	};

	sankey.horizontalPadding = function(_) {
		if (!arguments.length) return horizontalPadding;
		horizontalPadding = +_;
		return sankey;
	};

	sankey.verticalPadding = function(_) {
		if (!arguments.length) return verticalPadding;
		verticalPadding = +_;
		return sankey;
	};

	sankey.nodes = function(_) {
		if (!arguments.length) return nodes;
		nodes = _;
		return sankey;
	};

	sankey.links = function(_) {
		if (!arguments.length) return links;
		links = _;
		return sankey;
	};

	sankey.curvature = function(_) {
		if (!arguments.length) return defaultCurvature;
		defaultCurvature = +_;
		return sankey;
	};

	sankey.layout = function(iterations) {
		computeNodeLinks();
		computeNodeValues();
		computeNodeXPositions();
		computeNodeYPositions(iterations);
		computeLinkYPositions();
		computeBBox();
		return sankey;
	};

	sankey.relayout = function() {
		computeLinkYPositions();
		computeBBox();
		return sankey;
	};

	sankey.link = function() {
		var curvature = defaultCurvature;

		function link(d) {
			var x0 = d.source.x + d.source.dx,
				x1 = d.target.x,
				xi = d3.interpolateNumber(x0, x1),
				x2 = xi(curvature),
				x3 = xi(1 - curvature),
				y0 = d.source.y + d.sy + d.dy / 2,
				y1 = d.target.y + d.ty + d.dy / 2;
			return "M" + x0 + "," + y0
			+ "C" + x2 + "," + y0
			+ " " + x3 + "," + y1
			+ " " + x1 + "," + y1;
		}

		link.curvature = function(_) {
			if (!arguments.length) return curvature;
			curvature = +_;
			return link;
		};

		return link;
	};

	sankey.bbox = function() {
		return bbox;
	};

	function computeBBox() {
		bbox = [Infinity, Infinity, -Infinity, -Infinity];
		nodes.forEach(function(node) {
			bbox = [
				Math.min(bbox[0], node.x),
				Math.min(bbox[1], node.y),
				Math.max(bbox[2], node.x + node.dx),
				Math.max(bbox[3], node.y + node.dy)
			];
			node.sourceLinks = [];
			node.targetLinks = [];
		});
	}

	// Populate the sourceLinks and targetLinks for each node.
	// Also, if the source and target are not objects, assume they are indices.
	function computeNodeLinks() {
		nodes.forEach(function(node) {
			node.sourceLinks = [];
			node.targetLinks = [];
		});
		links.forEach(function(link) {
			var source = link.source,
				target = link.target;
			if (typeof source === "number") source = link.source = nodes[link.source];
			if (typeof target === "number") target = link.target = nodes[link.target];
			source.sourceLinks.push(link);
			target.targetLinks.push(link);
		});
	}

	// Compute the value of each node by summing the associated links.
	function computeNodeValues() {
		nodes.forEach(function(node) {
			node.value = Math.max(
				d3.sum(node.sourceLinks, value),
				d3.sum(node.targetLinks, value)
			);
		});
	}

	// Iteratively assign the X position of each node.
	// Nodes are assigned the maximum X position of incoming neighbors plus one;
	// nodes with no incoming links are assigned X position zero.
	function computeNodeXPositions() {
		var remainingNodes = nodes,
			nextNodes,
		x = 0;

		while (remainingNodes.length) {
			nextNodes = [];
			remainingNodes.forEach(function(node) {
				node.x = x;
				node.dx = nodeWidth;
				node.sourceLinks.forEach(function(link) {
					nextNodes.push(link.target);
				});
			});
			remainingNodes = nextNodes;
			x += nodeWidth + horizontalPadding;
		}

		//moveSinksRight(x);
		moveSourcesRight();
	}

	function moveSourcesRight() {
		nodes.forEach(function(node) {
			//if (!node.targetLinks.length) {
            if (node.sourceLinks.length) {
				node.x = d3.min(node.sourceLinks, function(d) { return d.target.x; }) -
					nodeWidth - horizontalPadding;
			}
		});
	}

	function moveSinksRight(x) {
		nodes.forEach(function(node) {
			if (!node.sourceLinks.length) {
				node.x = x - 1;
			}
		});
	}

	function computeNodeYPositions(iterations) {
		var nodesByX = d3.nest()
		.key(function(d) { return d.x; })
		.sortKeys(d3.ascending)
		.entries(nodes)
		.map(function(d) { return d.values; });

		//
		initializeNodeYPosition();
		resolveCollisions();
		for (var alpha = 1; iterations > 0; --iterations) {
			relaxRightToLeft(alpha *= 0.99);
			resolveCollisions();
			relaxLeftToRight(alpha);
			resolveCollisions();
		}

		function initializeNodeYPosition() {
			maxValue = d3.max(nodesByX, nodes => d3.max(nodes, value));

			nodesByX.forEach(function(nodes) {
				nodes.forEach(function(node, i) {
					node.y = i;
					node.dy = nodeWidth;
				});
			});

			links.forEach(function(link) {
				link.dy = link.value / maxValue * nodeWidth;
			});
		}

		function relaxLeftToRight(alpha) {
			nodesByX.forEach(function(nodes) {
				nodes.forEach(function(node) {
					if (node.targetLinks.length) {
						var y = d3.sum(node.targetLinks, weightedSource) / d3.sum(node.targetLinks, value);
						node.y += (y - center(node)) * alpha;
					}
				});
			});

			function weightedSource(link) {
				return center(link.source) * link.value;
			}
		}

		function relaxRightToLeft(alpha) {
			nodesByX.slice().reverse().forEach(function(nodes) {
				nodes.forEach(function(node) {
					if (node.sourceLinks.length) {
						var y = d3.sum(node.sourceLinks, weightedTarget) / d3.sum(node.sourceLinks, value);
						node.y += (y - center(node)) * alpha;
					}
				});
			});

			function weightedTarget(link) {
				return center(link.target) * link.value;
			}
		}

		function resolveCollisions() {
			var lastWeightedAvgY;
			nodesByX.forEach(function(nodes) {
				var node,
					dy,
					y0 = 0,
					n = nodes.length,
					i,
					totalValue = 0,
					weightedSumY = 0,
					totalValueWithSources = 0,
					weightedSumYWithSources = 0;

				// Pack nodes together in this rank.
				nodes.sort(ascendingY);
				for (i = 0; i < n; ++i) {
					node = nodes[i];
					dy = y0 - node.y;
					node.y += dy;
					totalValue += node.value;
					weightedSumY += (node.y + nodeWidth / 2) * node.value;
					if(node.sourceLinks.length > 0) {
						totalValueWithSources += node.value;
						weightedSumYWithSources += node.y * node.value;
					}
					y0 = node.y + node.dy + verticalPadding;
				}

				// Shift this rank to align its weighted average Y (only from nodes with sources)
				// to the previous rank's weighted average Y (including all nodes).
				var weightedAvgYWithSources = weightedSumYWithSources / (totalValueWithSources || 1);
				if(lastWeightedAvgY !== undefined) {
					for (i = 0; i < n; ++i) {
						node = nodes[i];
						node.y += lastWeightedAvgY - weightedAvgYWithSources;
					}
				} else {
					lastWeightedAvgY = weightedSumY / totalValue;
				}
			});
		}

		function ascendingY(a, b) {
			return a.y - b.y;
		}
	}

	function computeLinkYPositions() {
		nodes.forEach(function(node) {
			node.sourceLinks.sort(ascendingTargetY);
			node.targetLinks.sort(ascendingSourceY);
		});
		nodes.forEach(function(node) {
			var sy = (1 - d3.sum(node.sourceLinks, value) / maxValue) * nodeWidth / 2,
				ty = (1 - d3.sum(node.targetLinks, value) / maxValue) * nodeWidth / 2;
			node.sourceLinks.forEach(function(link) {
				link.sy = sy;
				sy += link.dy;
			});
			node.targetLinks.forEach(function(link) {
				link.ty = ty;
				ty += link.dy;
			});
		});

		function ascendingSourceY(a, b) {
			return a.source.y - b.source.y;
		}

		function ascendingTargetY(a, b) {
			return a.target.y - b.target.y;
		}
	}

	function center(node) {
		return node.y + node.dy / 2;
	}

	function value(link) {
		return link.value;
	}

	return sankey;
};