Random Sampling and Size Estimation Over Cyclic Joins
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Chen, Yu
Yi, Ke
Computing joins is expensive, and often unnecessary when the output size is large. In 1999, Chaudhuri et al. [Surajit Chaudhuri et al., 1999] posed the problem of random sampling over joins as a potentially effective approach to avoiding computing the join in full, while obtaining important statistical information about the join results. Unfortunately, no significant progress has been made in the last 20 years, except for the case of acyclic joins. In this paper, we present the first non-trivial result on sampling over cyclic joins. We show that after a linear-time preprocessing step, a join result can be drawn uniformly at random in expected time O(IN^ρ/OUT), where IN^ρ is known as the AGM bound of the join and OUT is its output size. This result holds for all joins on binary relations, as well as certain joins on relations of higher arity. We further show how this algorithm immediately leads to a join size estimation algorithm with the same running time.
 OK. The title of our paper is Random Sampling Over Cyclic Joints. So I assume everyone knows what a join query is. So what I'm showing here is what is called a two triangle join that consists of five attributes, ABCDD, and six relations. So this example, so every relation has two attributes. So this is also called an every T2 join. So here I'm showing an instance of the query where every edge represents a tuple. And every vertex represents a value in the corresponding domain of attribute. So I write in as total input size and out as the total output size, maybe the join size. So the problem we want to study in this paper is following. We want to pre-process the database instance in linear time, ideally, so that upon request, a tuple uniformly independently chosen from the query can be returned efficiently. So for example, if I ask a query, this join results showing blue may be returned. If I ask multiple times, then multiple samples can be returned independently. So why are we interested in this problem? So first of all, this is a theoretical clean problem. It is indeed first proposed in 1999. So second, computing the full join can be rather expensive. If the join is acyclic, it takes in plus out time. And when the query is acyclic, then the two approaches, one is known as the HN band. So where rho is the fractional edge cover. And I will also come back to this later in this talk. The other one is this width dependent band, where W essentially measures how acyclic the join is. So for example, for a two triangle join, the rho is 2.5 and W is 1.5. However, in the worst case, the output size can be as large as the AGM band into power rho. So this computing the full join can be very expensive, at least in the worst case. So however, in many applications, we don't really need the full join results. For example, in this paper, we actually also showed how to compute an estimate of join size only by a constant number of samples. And furthermore, another application is so-called online aggregation. Namely, we want to answer an aggregated query. However, exactly how it is not required. So this framework shows that if you can do sampling, then you can return more and more accurate answer as more samples are returned. So finally, so this new direction recently called database learning. So in this setting, we assume that the training data is represented as the join results of several relations. And a predominant approach in learning, in training algorithm, is a stochastic gradient descent, which essentially only relies on the sample. So if you can sample from the join, you can also run stochastic gradient descent over training data that is defined as a join over several relations. So the very 1999 paper indeed already proposed an algorithm for sampling from a two-relation join, say, AB, join BC. So their observation is the following. If you want to uniformly sample from all the join results, you cannot uniformly sample from the two relations, respectively, because the importance of the samples of the samples are not the same. So they proposed this idea called weighted sampling, which is actually very natural. So for example, in this instance, one sample in R1, the first one, joins with N samples on the other side. A0, B0, this sample is just more important than the rest. So therefore, the idea is to give them weights. So the weights, exactly, it's so-called degree, then how many samples it can join on the other side. So the way to do this is, OK, we start from sampling a type of in R1, and the sampling probably will be set as follows. The sampling probability of the first type of should be 1 1⁄2, and the sampling probability of each of the other N samples is 1 over 2N. So the weight given to the first type of is N times that of the rest of the samples. So let's say, suppose the first type of is indeed sampled. After that, then we want to sample one of its neighbors. The neighbors, in this case, will all have the same weight. So each sample, each type of will be sample with probably 1 over N after the first type of in the R1 has been sampled. So if you work out the math, you can convince yourself that by using these weights, each result, joint results, will be sampled with probability 1 over 2N. OK, 1 over 2N, and that's all the same. And OK, how do we implement this algorithm? And there is a kind of standard weight sampling algorithm that says, after linear time pre-processing, then a weight sample can be joined in constant time. So the very important final result is that after linear pre-processing time, you can draw uniform samples in constant time. So the same idea can be extended to a multi-weight join. So let's say a line join, in this case, R1, R2, and R3. The idea is to use the residual joint sizes as the weights. Is the number of joined results a tuple can lead to. So for example, every tuple in the last relation, they only lead to one joined result, because there's nothing further on the right side. So each tuple, in R2, for example, this tuple can join with four tuples in R3. So this will lead to four joined results. And this one will lead to three, and this one leads to two. And this tuple will lead to nine, because it can join with four plus three plus two results. And similarly, also this one. So the idea is we can start from the first R1 and do this kind of a weighted random walk. We sample each of these two tuples with probability nine over 18. And then from there, we pick one of these three tuples with probability proportional to four, three, and two, and et cetera. And then this can be further extended to any A6-linked joint. The observation is that all the residual joint sizes can be computed by dynamical program. That's actually a fairly standard technique. So now we go to the main problem we are trying to solve in this paper, namely, what if the joint is cyclic? So the difficulty in extending the previous idea to cyclic joints is that we don't know how to compute all the residual joint sizes in linear time. We can only do that when the query in the joint is acyclic. So the idea of getting around this difficulty is to use upper bounds on the residual joint sizes to guide something across us. But because we use an overestimate, so that means we may not always succeed. So more precisely, the success probability in reaching a true joint result in the sampling process, in the random walk process, is actually going to size out over essentially our overestimate, over the AGM bound of the query. So therefore, the expected sampling time, how many times we have to try until we succeed, is the inverse of the success probability. So then the running time will be AGM over out. And then the observation that this AGM end bound, we can compute the residual AGM bound in constant time per residual joint. And there are only linear number of residual joints. So we can pre-process. We can compute all the residual AGM bounds in linear time. And after that, our sampling time will be this way, so AGM bound over out. So this result holds for all the arity two joints, namely when the query is a graph. It also holds for certain higher arity joints. Because certain technical difficulties, we cannot extend this to all the higher arity joints. So finally, I'd like to conclude with two open problems. Of course, the first one is to extend this result to all the higher arity joints. So a good starting point will be the LW join. For the LW join, the fraction match cover is a fourth third. And however, we cannot achieve this ideal bound yet. Our bound is a n factor larger. So it will be nice to get rid of this one. The second, I think, another more interesting direction is to study a waste dependent bound. Because if you look at full drawing computation, this is full drawing computation, then for acyclic and cyclic, we have essentially two extremes. However, by using this GHD generalized type or tree decomposition framework, we can get a result running time that depends on the cyclicity of the query. So W is actually one when the query is acyclic. And W is high. It's W is low for very cyclic, for highly cyclic queries. However, for the joint sampling problem, well, for the acyclic case, we can achieve very nice results, linear time pre-processing, constant sampling time. For cyclic ones, on one extreme, we can compute the full drawing, which takes into the row time. And then we can do sampling very efficiently. So what we have shown in this paper is that we don't have to compute the full drawing. With only linear pre-processing, then we can still achieve some non-trivial sampling time. However, for queries that are not highly cyclic, but also not acyclic either, currently, we only have this kind of naive solution, which is to compute every node in the drawing tree. And then we can need so much running pre-processing time and space. And therefore, from that, we can just apply this result and get a constant time. It will be very nice if we can achieve some waste-dependent bound for sampling time, given only linear time pre-processing. And so that's all in the talk. Thank you.
 OK.  The title of our paper is Random Sampling Over Cyclic Joints.  So I assume everyone knows what a join query is.  So what I'm showing here is what is called a two triangle  join that consists of five attributes, ABCDD, and six  relations.  So this example, so every relation has two attributes.  So this is also called an every T2 join.  So here I'm showing an instance of the query  where every edge represents a tuple.  And every vertex represents a value  in the corresponding domain of attribute.  So I write in as total input size and out as the total output  size, maybe the join size.  So the problem we want to study in this paper is following.  We want to pre-process the database instance  in linear time, ideally, so that upon request,  a tuple uniformly independently chosen from the query  can be returned efficiently.  So for example, if I ask a query,  this join results showing blue may be returned.  If I ask multiple times, then multiple samples  can be returned independently.  So why are we interested in this problem?  So first of all, this is a theoretical clean problem.  It is indeed first proposed in 1999.  So second, computing the full join can be rather expensive.  If the join is acyclic, it takes in plus out time.  And when the query is acyclic, then the two approaches,  one is known as the HN band.  So where rho is the fractional edge cover.  And I will also come back to this later in this talk.  The other one is this width dependent band,  where W essentially measures how acyclic the join is.  So for example, for a two triangle join,  the rho is 2.5 and W is 1.5.  However, in the worst case, the output size  can be as large as the AGM band into power rho.  So this computing the full join can be very expensive,  at least in the worst case.  So however, in many applications,  we don't really need the full join results.  For example, in this paper, we actually  also showed how to compute an estimate of join size only  by a constant number of samples.  And furthermore, another application  is so-called online aggregation.  Namely, we want to answer an aggregated query.  However, exactly how it is not required.  So this framework shows that if you can do sampling,  then you can return more and more accurate answer  as more samples are returned.  So finally, so this new direction recently  called database learning.  So in this setting, we assume that the training data is  represented as the join results of several relations.  And a predominant approach in learning, in training algorithm,  is a stochastic gradient descent, which essentially only  relies on the sample.  So if you can sample from the join,  you can also run stochastic gradient descent over training  data that is defined as a join over several relations.  So the very 1999 paper indeed already  proposed an algorithm for sampling from a two-relation  join, say, AB, join BC.  So their observation is the following.  If you want to uniformly sample from all the join results,  you cannot uniformly sample from the two relations,  respectively, because the importance of the samples  of the samples are not the same.  So they proposed this idea called weighted sampling,  which is actually very natural.  So for example, in this instance, one  sample in R1, the first one, joins with N samples  on the other side.  A0, B0, this sample is just more important than the rest.  So therefore, the idea is to give them weights.  So the weights, exactly, it's so-called degree,  then how many samples it can join on the other side.  So the way to do this is, OK, we start from sampling a type  of in R1, and the sampling probably  will be set as follows.  The sampling probability of the first type of should be 1 1⁄2,  and the sampling probability of each of the other N samples  is 1 over 2N.  So the weight given to the first type of is N times  that of the rest of the samples.  So let's say, suppose the first type of is indeed sampled.  After that, then we want to sample one of its neighbors.  The neighbors, in this case, will all have the same weight.  So each sample, each type of will be sample  with probably 1 over N after the first type of in the R1  has been sampled.  So if you work out the math, you can convince yourself  that by using these weights, each result, joint results,  will be sampled with probability 1 over 2N.  OK, 1 over 2N, and that's all the same.  And OK, how do we implement this algorithm?  And there is a kind of standard weight sampling algorithm  that says, after linear time pre-processing,  then a weight sample can be joined in constant time.  So the very important final result  is that after linear pre-processing time,  you can draw uniform samples in constant time.  So the same idea can be extended to a multi-weight join.  So let's say a line join, in this case, R1, R2, and R3.  The idea is to use the residual joint sizes as the weights.  Is the number of joined results a tuple can lead to.  So for example, every tuple in the last relation,  they only lead to one joined result,  because there's nothing further on the right side.  So each tuple, in R2, for example, this tuple  can join with four tuples in R3.  So this will lead to four joined results.  And this one will lead to three, and this one leads to two.  And this tuple will lead to nine, because it  can join with four plus three plus two results.  And similarly, also this one.  So the idea is we can start from the first R1  and do this kind of a weighted random walk.  We sample each of these two tuples with probability  nine over 18.  And then from there, we pick one of these three tuples  with probability proportional to four, three, and two,  and et cetera.  And then this can be further extended to any A6-linked joint.  The observation is that all the residual joint sizes  can be computed by dynamical program.  That's actually a fairly standard technique.  So now we go to the main problem we  are trying to solve in this paper, namely,  what if the joint is cyclic?  So the difficulty in extending the previous idea  to cyclic joints is that we don't know  how to compute all the residual joint sizes in linear time.  We can only do that when the query in the joint is acyclic.  So the idea of getting around this difficulty  is to use upper bounds on the residual joint sizes  to guide something across us.  But because we use an overestimate,  so that means we may not always succeed.  So more precisely, the success probability  in reaching a true joint result in the sampling process,  in the random walk process, is actually  going to size out over essentially our overestimate,  over the AGM bound of the query.  So therefore, the expected sampling time,  how many times we have to try until we succeed,  is the inverse of the success probability.  So then the running time will be AGM over out.  And then the observation that this AGM end bound,  we can compute the residual AGM bound in constant time  per residual joint.  And there are only linear number of residual joints.  So we can pre-process.  We can compute all the residual AGM bounds in linear time.  And after that, our sampling time  will be this way, so AGM bound over out.  So this result holds for all the arity two joints, namely  when the query is a graph.  It also holds for certain higher arity joints.  Because certain technical difficulties,  we cannot extend this to all the higher arity joints.  So finally, I'd like to conclude with two open problems.  Of course, the first one is to extend this result  to all the higher arity joints.  So a good starting point will be the LW join.  For the LW join, the fraction match cover is a fourth third.  And however, we cannot achieve this ideal bound yet.  Our bound is a n factor larger.  So it will be nice to get rid of this one.  The second, I think, another more interesting direction  is to study a waste dependent bound.  Because if you look at full drawing computation,  this is full drawing computation, then for acyclic and cyclic,  we have essentially two extremes.  However, by using this GHD generalized type  or tree decomposition framework, we  can get a result running time that  depends on the cyclicity of the query.  So W is actually one when the query is acyclic.  And W is high.  It's W is low for very cyclic, for highly cyclic queries.  However, for the joint sampling problem,  well, for the acyclic case, we can  achieve very nice results, linear time pre-processing,  constant sampling time.  For cyclic ones, on one extreme, we  can compute the full drawing, which takes into the row time.  And then we can do sampling very efficiently.  So what we have shown in this paper  is that we don't have to compute the full drawing.  With only linear pre-processing, then  we can still achieve some non-trivial sampling time.  However, for queries that are not highly cyclic,  but also not acyclic either, currently, we only  have this kind of naive solution, which  is to compute every node in the drawing tree.  And then we can need so much running pre-processing time  and space.  And therefore, from that, we can just apply this result  and get a constant time.  It will be very nice if we can achieve some  waste-dependent bound for sampling time,  given only linear time pre-processing.  And so that's all in the talk.  Thank you.
Chen_Yi_0_119.png Chen_Yi_120_1115.png Chen_Yi_1116_1811.png Chen_Yi_1812_2063.png Chen_Yi_2064_3407.png Chen_Yi_3408_5459.png Chen_Yi_5460_5507.png Chen_Yi_5508_6203.png Chen_Yi_6204_7139.png Chen_Yi_7140_9275.png Chen_Yi_9276_11711.png Chen_Yi_11712_11843.png Chen_Yi_11844_11939.png Chen_Yi_11940_12203.png Chen_Yi_12204_12263.png Chen_Yi_12264_12527.png Chen_Yi_12528_13595.png Chen_Yi_13596_14663.png Chen_Yi_14664_15527.png Chen_Yi_15528_18251.png