DAN SUCIU: Hello.
Welcome everyone to the computer science colloquium.
Today it's my great pleasure to introduce six speakers
from the Database Group who will tell you
about their project in data management.
So in case you haven't noticed this,
big data is changing the world today.
It helps to make scientific discoveries.
It helps cars drive themselves.
It helps save the environment, and it helps make discoveries
in the medical field.
So the students in our group, they
conduct research that address the new challenges in big data
management.
We have a secret sauce, and the secret sauce
that exists in databases and data management in general
is a separation of the what from the how.
What is a declarative level.
This is a logic, theoretical level
where we express how we want the data to be managed and stored
and queried.
The how is a physical systems level, algorithmic level
where we design the effective methods for storing
and managing the big data.
So today you will hear six talks from students and postdocs
in our group.
The first four talks are more at the border
between the what and the how.
This is the beautiful stuff where
the two extremes are combined.
The last two talks are about the what.
They show you the power that we get from a high level
declarative approach to data management.
I should mention that Babak Salimi is--
he had presented a video because he's
stuck in Canada without a visa.
He's waiting for his visa renewal.
And I will also ask you to withhold your questions
until the end of these talks.
So the first talk will be by Brandon Haynes on LightDB.
BRANDON HAYNES: Hey, everyone.
So I'm Brandon Haynes.
Today I'll be talking about LightDB, a data management
system that targets virtual, augmented, and mixed reality
video applications.
This is work in conjunction with Amrita
in the architecture lab, Armin, who's
over at Oculus, along with Magda, Luis, and Alvin
who are all faculty here at CSC.
So you might be wondering why I didn't give a talk at the VR
session a couple of weeks ago.
It's actually not the case that I was kicked out
of the graphics lab, but we conceptualize these sorts
of video applications as being increasingly a data management
problem.
So we're seeing a lot of really exciting things come out
of these communities, and they're actually
being delivered to real users.
So we need to think about things like scaling,
being able to work on heterogeneous hardware,
and other aspects that us in the data management community
are really good at solving.
So there's a whole taxonomy of these sorts of VR and AR style
applications out there.
You know, this is kind of a very rough taxonomy
I have on the screen here where we have--
hopefully you guys are familiar with a couple of these types.
I'll just quickly talk about each one
in a little bit of detail.
So here we have a 360 video.
These are videos that are captured
at a fixed point in space, and then
when you go and view that video you can, of course,
adjust your orientation.
But you can't move away from the point in which that video was
captured.
And you can see here I'm using the mouse
to rotate my orientation, but in the real world,
we would have a headset on which would have tracking software
with it that would adjust our orientation automatically.
So these are all over the place, and these are pretty widely
deployed, even on mobile devices and things like that now.
But far more exciting are these things
called light field videos, a really exciting area
at the cutting edge of VR.
And here, it's a little bit difficult to tell,
but you can actually translate around in space.
And so you can see the user just moved
outside of the area that was captured in this light field
video.
Modern light field video cameras can
capture about a cubic meter of information,
which allows for a good amount of translation in space.
And this greatly increases immersion,
as you might imagine.
You can do things like experience parallax
for distant objects.
Mirrors reflect when you move, and you
can see the reflection adjust.
Iridescent things shine.
Super important for immersion and a really exciting area.
On the AR, MR side--
so here's a prototypical example of a mixed reality video where
we mix synthetic video with real world objects
like a table or a couch.
And then finally, here's kind of a Hello World augmented reality
application where we're in a pet store.
We've captured some kitten videos.
We're running some sort of classifier on top of that video
and overlaying bounding boxes.
So you may notice this is, in fact, not an elephant or a dog.
We in the data management community
consider that to be the ML people's problem and not ours.
So you can talk to them about that.
So as you might imagine, developing applications
of a space is truly terrifying.
So 360 videos are an order of magnitude
larger than their 2D Netflix counterpart
because you have to deliver that entire sphere of video
rather than just the part that you're looking at.
Light field video, another order of magnitude beyond that.
That cubic meter of light field camera I mentioned a moment ago
puts off about a half terabyte of video data
per second, which is a formidable challenge
to keep up with.
This leads to programs that are extremely difficult to program
and optimize.
They can only be developed by domain experts who are hand
crafting optimizations.
And perhaps the most concerning thing
is that as new innovations roll off the research pipeline,
shoehorning them into these giant brittle applications
is a substantial software engineering challenge.
So with that background in mind, we've
introduced a system we call LightDB, a data management
platform for these sorts of virtual, augmented, and mixed
reality video applications.
LightDB is a full stack data management
system where you give the system a declarative program.
You tell us what you want in your application.
And we leave it up to LightDB to figure out
an efficient execution plan to realize that intent,
This leads to programs that are much smaller and simpler
to express.
We'll see an example of that in a moment.
And we think it runs faster than everything except the most
expert programs out there.
And so just to motivate this in the couple of minutes
I have left, let's go back to this Hello World
augmented reality application and think about how
we might develop this.
So in today's world what would we do?
We would open up our favorite editor.
We might decide we want to use something
like FFmpeg, which is a popular video processing framework.
And we start writing some code.
And we start writing more code, and more code, and more code.
And this is the reality of these applications today.
And this is a minimal viable example
we're seeing scroll by here.
On the other hand, in LightDB you'd
write something that looks about like this,
well, actually, looks exactly like that.
Where it-- this is almost a one-to-one correspondence
between how we might describe solving the problem
and solving it, where we decode some inputs
from a remote source or from on disk.
We apply some sort of detection algorithm on top of it.
We union the resulting bounding boxes with the original input
video, and then we write it to disk or send it to a client.
Very succinct program, especially
compared to the imperative version.
And LightDB is able to actually efficiently execute this.
So compared to the version you guys see in the left,
is you get about a 3x performance benefit
relative to what we can get out of LightDB.
And you get all that for free by letting LightDB
convert this declarative program into an optimized execution
plan.
So how does LightDB perform that conversion?
Here is kind of a Hello World virtual reality
application I'm going to use to go through that
at a very high level.
And so here what we're doing is we're taking a 360 video,
overlaying a watermark, converting to grayscale,
and then writing to disk.
What LightDB does is it converts this
into a logical execution plan drawn from it's rather
modest set of operators.
And here there's a one-to-one correspondence
between the invocation and the declarative version
and the logical plan, but that's not always the case.
And it does what you'd expect, decode some input videos,
scan the watermark from disk-- it's a little bit hard to see
there--
union them together, transform it to grayscale, and encode it.
And now LightDB is going to take this logical version
and convert-- and explore a space of physical execution
plans and hopefully choose the most efficient one.
And so here's one potential execution plan
it could choose where it moves everything over to a GPU,
decodes everything in a GPU, runs some CUDA kernels,
and then re-encodes.
And that's a reasonable plan.
And that, in fact, this is exactly what FFmpeg does.
On the other hand, LightDB can explore a much richer space
of potential plan, such as this one, which I'm not going
to go over in great detail.
But the idea here is that if this Sharks video has
a temporal index associated with it, which is almost universally
the case, what we can do is we can
take small pieces of that video and shuffle it
to multiple GPUs, and then essentially run
a similar pipeline in parallel where we decode,
we run a CUDA kernel, and we re-encode.
On the other hand, the watermark is super tiny.
It's the same frame extended over an infinite time span.
So what we can do is we can just broadcast that to all the GPUs
and bring those things together.
In fact, we do that at the top were
we can catenate the resulting chunks together.
The performance of this-- so double the GPUs, we actually
get double the performance out of it
by allowing LightDB to explore this space of plans
relative to not using the index or using FFmpeg.
So I only have a few seconds left.
The architecture of LightDB is a rather straightforward data
management system.
I'm just going to highlight a couple of things.
So of course, we know we have this planner that
converts the logical plans to physical execution plans.
We know we have an optimizer that
draws from a rich set of physical operators
that target various hardware, et cetera.
And we have a storage manager that I don't have time
to talk about today that achieves
a considerable compression ratio for stored videos.
So just to summarize--
OK, so this has been LightDB, a data management
system for virtual, augmented, mixed reality videos.
Smaller declarative programs, free optimization,
more efficient execution than the state of the art
programs out there.
Thanks for listening.
DAN SUCIU: The next speaker Cong Yan.
She will tell us why the internet is slow,
and what you can do about it.
CONG YAN: Thanks for the introduction, Dan.
Hi, I'm Cong, and I work with Alvin Cheung.
So today I'm going to talk about designing in-memory data
storage for web applications.
So we use web applications every day.
We read news online and work with other people online.
But don't you hate them when it takes forever
to load, like this?
So this web application is slow, not because of a network.
Network is usually fast.
They are slow because they're allowed the interaction
with the database.
So the web app usually uses three tier architecture.
The front end is usually a web browser that--
it uses an HTTP request to the application server,
the middle tier.
And the back end is a database that
stores the data persistently.
Since the application logic is often
developed using object oriented language like Python or Java,
it often used an object relational mapping framework,
the OIM framework, to generate SQL queries
and translate relational data back to objects.
We performed 12 open source web applications--
we profiled 12 open source applications
to see how well they perform.
So these applications are popular with many Github stars.
Some of them are pretty well known
like GitLab and OpenStreetMap.
So for this applications, even with a small amount of data
less than one gigabyte, over three pages
takes more than two seconds to load.
And for these slow pages, they spend
over 80% on the application server, especially the OIM
framework and also the back end database.
Then we look into why this is slow.
So there are two major causes.
The first is how the queries are written because these RM
frameworks usually provide similar APIs with very
different performance.
For example, here, this is a foreign application
developed using Ruby on Rails.
It wants to show a list of certain stories
and then calculates a count of the stores.
So it first issues a SQL query to retrieve the stories
and then store them in this favorable s.
Then, if the application writes s.size,
the count of the stories is computed
using in-memory objects.
However, if the application writes s.count,
it performs the same thing, but the count
is done by you showing a count query to the database.
So these two APIs have the same functionality,
but the count is less efficient than size because
of this extra query issued.
So these APIs are usually very confusing
and they result in inefficient queries.
The second reason is how the data is stored.
For example, if the app wants to show a list of users
and each containing its stories.
So to answer this query, the back-end stores two tables,
the user table and the story table.
To answer this query it first performs
a join on these two tables.
And then converts this relational result
into nested objects.
So if there are a large number of users and stories,
both the join and the deserialization
can be very slow.
So if we can precompute and restore
this join without in-memory, we save the time to do the join.
And further, if we can store this nested object
theoretically, we save the time to de-serialize.
However these nested objects may not
be optimal for all the queries in the application, for example
a query that select the stories.
So it is challenging to figure out the best storage model
for the whole application.
To solve this challenge we built Chestnut, an in-memory storage
designer to optimize the overall query performance
subject to a memory bound.
Instead of the low level, inefficient interaction
used by today's OIM, Chestnut proposed a new language.
This declarative language is designed
to cleanly and easily express common object queries.
The query result are directly objects
instead of relational data.
Even better, this language can be used to optimize.
It can be used to leverage, to customize in-memory storage.
And the interaction with the database
is more efficient because the read queries can
be answered using this in-memory storage,
while only the write queries go to the back-end database.
This optimization is challenging because you
need to design a new search space and a new search
algorithm.
Chestnut proposed a new search space that includes--
that explores both relational and non-relational storage
options.
So it considers using normalized table and indexes
in the relational world, and the nested objects and the pointers
in the non-relational world.
It devises a new search algorithm
that use bounded verification to find out
the storage for each individual query,
and then formulates into the ILP to find out the sharing of data
structures among queries.
To use Chestnut, a developer simply
needs to provide classes and queries declared
using Chestnut language as well as a memory bound.
And Chestnut will generate C++ code for both the storage
and the queries.
We evaluated Chestnut on three open source applications
originally built with Ruby on Rails,
and used MySQL as a back-end.
These applications include Kandan, a HipChat-like chatting
application, Redmine, GitHub-like project management
application, and Lobsters, A Hackernews-like foreign
application.
For this reapplication-- this figure
shows the average time of these applications.
The query time is composed of the time
to retrieve the data for the query,
and the time to deserialize that data into Ruby objects.
So as we can see from this figure,
Chestnut is able to speed up the query up to 26 sects.
And it's faster in both the query answering
and the deserialization.
And for all of these applications,
it takes less than an hour to find out the best storage.
Next I'll show an example of what
data structures Chestnut is able to find
for an individual query.
So this is a query that shows a list of tags
and then counts the number of stories
written by a particular user for each tag.
To enter this query, the original application
needs to join three tables, the tag table, the mapping
table that says which story has reached tag, and then
the story table.
And then it performs an aggregation and--
performs a group and then an aggregation.
It takes 0.8 seconds to finish this query.
Instead, Chestnut stores only the active tags.
And inside each tag it stores the user ID and the story count
of that user.
So to answer this query it only needs to scan the tags
and then do a binary search on the story
ID to figure out the story count.
And it only takes seven milliseconds to finish.
So to conclude, we show that many web applications
have performance issues due to the mismatch between object
and relational data model.
So we built Chestnut, an in-memory storage designer.
Chestnut has a new declarative language,
and uses a new search algorithm to explore both relational
and non-relational storage options.
And it is able to significantly improve the query performance.
Thanks.
DAN SUCIU: Thank you, Cong.
The next speaker is Maaz Ahmad.
He will tell us how to generate automatically
very difficult programs on distributed data.
MAAZ AHMAD: Thank you, Dan.
Hi everyone.
So I'm Maaz.
I also work with Alvin.
And the problem that I want to talk about today
is-- basically, the high level problem that we want to fix
is that we have all these new data processing frameworks
and DSLs being developed for new hardware or new abstractions,
and we want people to be able to update or adapt
these systems more easily.
In specific, I'm going to be talking about Casper, which
is a tool for generating MapReduce applications
from sequential Java implementations.
So the first question is, why do we even
want to do this sort of translation?
So imagine if you have a sequential application
or legacy application that exists,
and you use this application to do some data processing,
maybe build some visualizations.
Now as the amount of data increases,
that application might become too slow or might stop working.
Of course, you can scale your application
by running it in a parallel and distributed setting.
The good news is the database community
has built a lot of tools that can run your applications
in this struserberg setting.
The problem is, for your sequential application
to leverage these optimizations, it
must be rewritten using the framework's provided API.
So in order to use these frameworks,
you then have to rewrite your applications.
The first option, of course, is that you could manually
sit down and rewrite all of your code.
This is, of course, time consuming.
It's tedious.
It requires expertise not only to understand the input code
but also the target frameworks that you want to use.
And of course, you could introduce bugs into your system
when you do this sort of translation.
So what we want to do is we want to just completely automate
this process by building a compiler that
does this translation for you.
Why is it difficult to build compilers in this manner?
So traditionally, whenever we're building compilers,
we use syntax directed rules.
What this means is the compiler will scan the input code
looking for code patterns.
For example, here's a code pattern that might look for.
And every time it finds a code pattern that
syntactically matches this--
a good parent that matches syntactically this parent
that you have, it will just simply rewrite
it using some operators from the target language.
So for example, in Spark, it will use filter and the union
operators.
For good fragments that are simple, it's easy.
However, as the data processing algorithms get really, really
large and they get more complex, the set
of rules that you need to do the translation become unobvious
and in fact reasoning about these rules
becomes almost impossible.
So the reason we believe It's hard to use re-write rules
to do this translation, is that the code that you
want to generate, the specifications for that code
are provided to you in terms of legacy code, which
is written in low-level, messy languages that
are very complex.
What if, instead of the specifications
were provided in this low-level language, what
if they were provided in a cleaner, high-level simpler
language?
For example, if the specification for the programs
provided in a functional language
that just had map and reduce of primitives.
Now generating the Spark code or Hadoop
or Flink code from this specification
is much, much easier.
However, we don't have the specification in that cleaner
form.
So essentially, what we need is a way
to convert the legacy programs and extract the specifications
out of them.
And the way we want to do this is by using program synthesis.
So a quick primer on what program synthesis is, so
if you have some piece of code and you
want to use program synthesis to do to the translation, the idea
is to consider the space of all possible MapReduce programs.
So say this shape represents all possible programs
or specifications that you can write
using MapReduce primitives.
And within this space maybe there
is a few programs that actually produce the same outputs given
the same inputs for all inputs.
In program synthesis, we simply search for these programs
that have the same outputs.
If you can find these programs, and if he
can verify that for all inputs they produce the same output,
we can essentially treat those programs
as a translation of the input code.
So the big question with this sort of approach is,
how can we make this scale?
Of course, the size of the search space that you are
considering is extremely large.
So how can you actually do this in a reasonable amount of time?
So I'm just going to show some quick high level
ideas for how you might make the search manageable.
The first and probably the most important idea
is to design, very carefully, an API for expressing
the specifications.
Since we're doing the search, you
can imagine doing the search directly
in the target framework's API.
So for example, if you to generate Spark code,
you could synthesize the program or search for the program
written in that API.
However, those APIs were not designed
with synthesis in mind.
So for example, Spark has over 80 high-level operators,
and searching in them is very expensive.
In this instance, for example, we
were able to design an API that could
capture the same semantics using only three operators.
And that reduces the search space significantly.
Secondly, you want to use some static program analysis.
What essentially this means is you look at the program code
automatically, and you try to generate heuristics about it.
So you might specialize the search
by saying that if the input type of the program
is a list of integers, you don't want
to consider any MapReduce program that
operates on a different type.
Similarly, you might want to specialize a search
or like bias a search by saying that only search for programs
or search for those programs first that
use the same operators like Edition.
Third, you can use incremental search.
And the idea here is to, instead of searching
for the entire space at the same time, you break this space down
and you search incrementally.
And this becomes really powerful when you
introduce cost-based pruning.
And the idea here is that you order these subspaces
by the cost of the programs that they generate.
So you can then search for more efficient programs first.
And if you can find one of those,
you can just prune away the rest of the search space.
So this idea or this technique that I've explained so far,
we actually implemented this in a tool called Casper.
Casper takes as input unannotated
Java sequential code and generates--
and is able to generate code in three MapReduced frameworks,
Spark, Hadoop, and Flink.
For evaluation, we accumulated a bunch of benchmarks, about 55,
from prior works and open source implementations
of different algorithms.
These include common statistical and mathematical functions,
as well as big data workloads that are popular.
Within these 55 benchmarks, about 100 code fragments
were found that were doing data processing.
And from those 100, about 82 Casper
was able to translate completely automatically.
The ones that failed were either because it was taking too long
to search or because the API that we had
was not expressive enough.
So the first evaluation that we did
was, of course, to compare with a rule-based compiler.
This is a prior work compiler called MOLD.
On the x-axis, as you can see, a subset
of the benchmarks that we've picked.
And on the y-axis you see the improvement
after compiling the code using Casper or the MOLD compiler.
The first thing you'll notice is that Casper,
which is in yellow, can translate
way more benchmarks than the rule-based compiler can.
This is not very surprising.
What's more interesting is that even for the benchmarks that
MOLD can compile, Casper finds more efficient implementations.
However, the ultimate sort of benchmark that we want to test
is against a human.
So how does Casper compare against a human?
We hired online developers through a freelancing platform.
We had them manually rewrite these applications.
And then we compared the performance
of the handwritten implementations
versus what we generated.
As you can see, in most cases the performance
was extremely competitive.
There were a few cases like the 3D histogram
where the user or the manual developer
exploited some domain specific knowledge to optimize
the program better than what Casper could do.
It takes Casper about 10 minutes on average
to translate one code fragment.
And the median time is even lower.
So for really simple programs, it can actually translate them
really, really fast.
And this does not count any of the overhead involved
in hiring these developers and making sure
that they do the work on time.
So the key takeaways are, you can actually
use compilers to do this sort of high-level transformations.
And with the speedup of about 16x,
Casper is even competitive with hand-written translations.
So here's a link if you want to read the paper or use the demo.
I'll take your questions at the end.
Thank you for listening.
DAN SUCIU: Thanks, Maaz.
The next speaker is Jennifer Ortiz.
She looks at the very difficult question,
how to convert from the what to how using deep learning.
JENNIFER ORTIZ: Thanks, Dan.
So today I'll be presenting a project called DeepQuery,
where we're learning subquery representations
for query optimization.
And this is joint work with my advisor Magda Ballazinska
Johannes Gehrke, and Sathiya Keerthi.
So generally, whenever we have questions about our data
we rely on our database systems to help answer these questions.
And these systems help us store, maintain, and manage our data.
But the setup of systems are generally
constrained by allocated resources.
And with this limitation, the database system
must come up with what we call an optimal query plan.
And you can think of this query plan
as essentially a program that is able to efficiently fetch data,
run computations on the data, before providing
the final result.
So just as a quick example, say we have,
for example, three relations, the Customers, Orders,
and Regions table.
We have this query where we, say,
we want to fetch all the customers
from Arizona that have orders within the last 10 years.
Now, to run this type of query, we
would need to join across all of these three relations.
And when the optimizer looks at this query plan,
it needs to consider, well, in what order should I actually
be running this join?
For example, we can first join the Customers and Orders table,
which will get us some intermediate result,
and follow that with a join with the Regions table.
Or we could first join the Customers and Regions table,
which could give us a smaller intermediate result,
and then follow that with a join with the Orders table.
As you can imagine, depending on your query or the number
of relations that you have in your data set,
you can have really complex query plans,
which makes it even harder for the optimizer
to come up with an efficient plan.
And essentially, the idea of query optimization
has been a core problem in the database community
for several years.
And this is especially hard because these optimizers
have to come up with these good plans with really
limited understanding about the underlying data.
And these plans need to be efficient with respect
to the resource consumption and also the runtime.
And essentially-- this problem essentially
boils down to what we call the Cardinality Estimation
Problem, where the cardinality estimation is
the process of estimating the number of rows
that are returned by a query.
And this is essential for producing
these optimal join orders.
And, unfortunately, because the optimizer needs to be efficient
it makes really simplifying assumptions about the data.
So for example, if we have this query where
we're joining across all these three relations
and we're filtering the Customers and Regions table,
it might make some assumptions about the correlations
of these columns in these relations, which
results in some inaccurate cardinality estimation for some
of the intermediate results, which then provides us
with a suboptimal query plan.
So there must be some other approach
that we can use to solve this problem.
So I likely don't need to motivate why deep learning has
been useful, but we've seen how it's been successful
in various applications such as image processing and also
natural language processing.
So in this work in particular, we
want to look at, well, what can deep learning do
but in the context of data management.
So our vision in this work is to say,
can we rethink about query optimization
but in the context of deep learning?
So say we have as input some data set and some query that we
want to run, can we use a model to describe
different properties of the query?
For example, can we have the model give us an optimal query
plan, describe the resource consumption of the query,
or estimate the query's cardinality?
Now, as a first step in this project,
we're just focusing on estimating
the cardinality of the query.
And one thing that we want to consider
is, well, how do we encode our inputs?
How can we encode the data and the query?
So for these models, essentially, the input
is this-- you can think of it as a long vector where
we can encode information about our inputs.
In this case we have our data in our query.
One approach to encode the data would
be to provide the model with really basic statistics
about the data.
For example, we can provide the model
with simple one dimensional histograms
across some of the columns that exist in our data.
And now for the query, one way we
can encode this would be to provide
the model with all possible--
some possible join predicates or possible selections that
could exist on this data set.
Now the problem with this approach
is that these vectors need to be really
long to encode all possible queries that we
could write on this data set.
So essentially what we need is a model
that will give us this ability to encode all possible queries
that we can run on this data.
So the intuition behind our approach
is to, instead, view this query plan
as a sequence of operations.
So for example, we can first filter the Customers relation
followed by a filter with the Region,
and then combine this to do a join, and so on.
And we can iterate through all the operations
until we've completed the query plan.
So essentially what we want to do
is to learn what we call these subquery representations where
we still want to use deep learning,
but we want to use it to describe specific properties
of these intermediate results.
So just as a really quick example,
say we have this query where we're joining tables a and b,
and we have two operations.
We have a join and a selection.
So the idea is that we can start with an encoding that
shows basically a representation over our data set
and one of the operations, in this case a selection.
Now given these inputs, we can use a deep learning model
to come up with a representation of the following intermediate
results.
So in this case, we applied a filter
and now we have some encoding of this subquery.
Now from this representation we can
extract information such as the distribution of the data
at that subquery or even the cardinality.
Now given this representation we can chain another operation,
in this case a join, and still use our deep learning function
to come up with a subsequent representation
of that subquery.
So essentially what we're learning is this risk recursive
function that takes us input some encoding
or some subquery representation along with a query operation
to come up with the representation
of the following result. But just to give you
a sense of what these models can do, we wanted to experiment
and see how well these models are
able to estimate the cardinalities compared
to a commercial database engine.
And for these experiments we use the IMDB data set,
which has some interesting correlations
across these columns.
So here, for example, in this graph,
we're showing the percentage error
in terms of cardinality on the y-axis.
And on the x-axis we're showing the database system
compared to the neural network.
For these queries, we only varied the selection predicate
for one of the columns on one of the relations.
So you can see that the database system generally
does pretty well, but our neural network is
able to get slightly more accurate cardinality estimation
results.
Now if we make this problem a little bit harder where we're
now selecting across several more of these columns,
in this case, we actually need to have the model learn
about the distribution and correlations
across these columns, it's harder for the network
and also for the database system.
But in the cases now where we're starting to chain more
of these representations together, for example,
in this case we are applying selections
on two different tables and also tying that with a join,
it becomes a lot harder for the system
and also for the network itself.
So what we're experimenting now is
thinking about what it actually means to do--
actually, to improve these results,
we want to see what it means to chain
and tie these representations together along
with these complex query operations.
So just to conclude, we've talked
about why cardinality estimation is a difficult problem
and how we should start looking at other new approaches.
And so in this work we propose this model
of learning these subquery representations
through a recursive function by using one of the deep learning
networks.
DAN SUCIU: Thanks, Jennifer.
So the next talk is by Babak Salimi.
He is in Vancouver.
He's waiting for his Visa.
He sent us a video of his talk.
He also has a cool demo.
It's about how to understand when your queries are not
returning what you thinking you are there returning,
and how to fix them.
BABAK SALIMI: Hi, everyone.
I'm Babak.
Today I'll be talking about bias in the context of decision
support SQL queries.
Decision support SQL queries are used today by knowledge workers
to make better and faster decisions.
However, inexperienced workers can easily
write SQL queries that are biased for decision making,
unless they're trained as statisticians, which
is typically not the case.
As we will see throughout this talk,
biased SQL queries can lead to wrong business decisions.
Let's go through a multi-weighting example.
Suppose a company has many business travels from four
particular airports and would like
to choose between business travel programs offered
by either American or United Airline,
depending on which one has a better performance in terms
of on time flight.
To find out, the knowledge worker
does some simple data analysis and writes
a SQL query that computes the average delay once for American
and once for United Airline.
The bar diagram on the left shows the result of this query.
You may acknowledge that this scenario is repeated over
and over in industry today.
Users write declarative queries, explore the results,
and make decisions based on the insights obtained
from these results.
In our example, the knowledge worker looks at the bar
and observed that American looks significantly better,
so she decides to contract with American.
However, any trained statisticians
would recognize that to make decisions regarding
the performance of the two airlines,
one needs to look into potential confounding
factors such as how frequently these airlines operate
at different airports.
Simply because one airline may have several flights
from an airport which has a high rate of weather-related flight
delays.
This clearly makes the comparison
between the two airlines with that SQL query
biased and unfair.
This is actually the case in our example.
Once we break down the delay by each airport,
it turns out that in each of the airports
it is actually United Airlines that has a better performance.
This trend reversal is known as Simpson's paradox in statistics
and happens because of overlooking the confounding
variables.
In this case, what the company really wants
is the causal effect of choosing American or United Airlines
on the delay of its travelers.
But the simple SQL query fails to answer that question
because it is biased.
Similar to the other projects that we have seen in this talk
so far, we leverage the declarative nature of SQL
and perform this complex causal analysis automatically
on top of the structure of the query.
Specifically, we propose HypDB, the first database
system which detects, explains, and removes bias
from SQL queries.
Instead of discussing the technical contribution,
I will demonstrate HypDB with two examples.
OK, so HypDB accepts as input a SQL group by query
and assumes that the query is being
used for making decisions.
Here with the simple group by query,
the goal is to find out the effect
of choosing one of the two carriers or airlines
on flight delays.
As we have discussed, the answers to this query,
they suggested American Airline performed significantly better.
However, HypDB takes advantage of the declarative nature
of SQL and performs some deep analysis on the SQL query
and automatically detects confounding factors
that are detected today only by trained statisticians.
These confounding factors make the query
biased for decision making.
Specifically, first HypDB warns the user
that they're grouping by some of the confounding factors, which
radically changes the insight obtained by the original SQL
query.
As you see in this case, HypDB automatically
identified origin airport as a confounding factor,
such that further grouping by origin
totally reverses the trend obtained by the original query.
The next step is to remove the bias from query.
HypDB does this by rewriting the query
to control for the confounding variables.
The query shown right here in this box
is the rewritten query associated to the group
by query we started with.
Please refer to the paper for more details
about this query rewriting, but for the moment note
that under certain assumptions the insight obtained
from the answer to this rewritten query
are unbiased and support decision making.
The bar diagram here shows the answers
to the rewritten query right here on the left.
The answers reveal that it is actually
United Airline which performs better than American Airline.
So there is no Simpson's Paradox anymore.
Finally, HypDB generates two kinds of explanations
for the biased query.
We argue that these explanations are crucial for decision making
and reveal illuminating insight about the domain and the data
collection process.
HypDB generates coarse grain explanations
by ranking the detected confounding factors
in terms of their responsibility for making the query biased.
In this case, as you observe here,
origin airport has the highest responsibility.
And the fine grain explanation generated by HypDB TB
is essentially a ranking system which
derails down into a particular confounding factor
and explain how the interaction of the ground
levels of the attributes involved in a SQL query
contribute to the bias.
In this case, the top floor of fine grain explanations
for origin airport indicate that United Airline frequently
flies from airports such as Rochester airport
that has a lot of weather-related flight delay.
Whereas American Airline frequently
flies from airports such as McAllen Miller,
that has fewer delay.
And this simply explains why the initial SQL
query that we started with was biased
toward American Airlines.
OK, for the second example I'm going
to use the famous adult income data set from the UCI Machine
Learning Repository.
Actually using this data set, several prior works
on discrimination discovery and fairness
have reported gender discrimination
in favor of males.
To replicate these experiments, let's use
HypDB to compute the effect of gender
on income with this sample group by query, which essentially
computes the average of males and females with high income.
As you see right here the results of this SQL query,
indeed, suggest a strong disparity with respect
to females' income.
However, not surprisingly, HypDB detects
that this query is biased and identifies
attributes such as marital status
as confounding variables.
To remove the bias from the initial SQL query,
HypDB rewrites the query to control for the confounding
variables.
Here you see the routine query associated with the net one
that you started with.
In this bar diagram you see the answers to this routine query.
As you observe the routine query answers,
they suggest that the disparity between males and females
is not nearly as drastic as suggested by the naive SQL
query.
To see what's going on here, let's check out
the explanations generated by HypDB.
the coarse grained explanation, they
showed that marital status accounted for most of the bias,
followed by the occupation.
Let's take a deeper look into marital status
and see why it makes the query biased.
The top four fine grained explanations
reveal a surprising fact.
They say there are more married males
in adult data than married females,
and marriage has a strong positive association
with high income.
To understand why this is actually
the case in adult data, we check the provenance of this data
set, and it turns out that the adult income attribute
in adult data--
it reports the adjusted gross income
as indicated in the individual's tax forms,
which depends on filing status.
It could be actually household income.
Therefore adult data is essentially inconsistent.
And should not be used for investigating
gender discrimination.
With this I will conclude.
We have shown that SQL queries can be biased and misleading.
We've proposed HypDB as a system to detect, explain, or resolve
bias from SQL queries.
We've shown that HypDB is useful for making
causal analysis accessible for nonstatisticians,
avoiding false discoveries, and detecting
errors in data collection.
Thank you for listening, and I hope
to see you soon in Seattle.
DAN SUCIU: And I thank Babak.
He's online watching and he can take questions at the end.
The last talk is by Shumo Chu, who's
going to tell us how to check if two SQL queries are equivalent,
a fundamental task in grid optimization.
SHUMO CHU: Hello everyone.
My name is Shumo, and today I'm going
to talk about automated reasoning of database queries.
And this is joint work with a few folks from our Database
Group and PL Group.
So first I will show you a figure.
So this is a survey by Stack Overflow
that shows language popularity.
Actually it tells you JavaScript is the best programming
language in the world, while SQL is the second.
And so is PHP is far behind.
So talking about the actual stuff,
I mean SQL is really a popular language that's
supported by all the relational database systems
and now supported by almost all the big data systems.
While SQL is great, because this is actually
a restricted abstraction, enabling
powerful optimizations.
The database community spent almost like more than 30 years
to develop many powerful optimizations
based on the semantic equivalent of SQL rewrites.
The problem here is that we are really
lacking tools that can actually reason about SQL equivalence.
So here I will use a self-driving car analogy.
It's really embarrassing that we have
self-driving car right now, we don't have a automated solver
for SQL.
And what is a automated solver for SQL?
It means that for any possible input can
we actually check whether those two SQL queries are
semantically equivalent.
And this has many applications.
For example, it can be used to verify
the correctness of a query rewrite
to make your query optimizer more reliable.
It can also be used to build a semantic caching
layer for big data systems.
And what's more, it can be used for automated grading of SQL
assignment to SCALES' MOOC.
Well apparently this is a very challenging problem.
First, from a theoretical result 50 years ago deciding
two relational queries are equivalent are actually
undecidable.
In addition, if you think about SQL,
you might think just select from where,
but actually SQL has rich language features.
So you have aggregation and grouping.
You have index and integrity constraints,
and you can write like correlated subqueries
like exist.
So how can we solve this problem?
Well, we have two lights we can't shed on.
So from a gogus result, while a problem is undecidable,
it doesn't mean there is no proof.
And in fact, you can use an interactive theorem
prover that--
you can use it to validate mechanized proofs.
And second observation we can find
is that the model of inequivalent SQL queries
are usually not very large.
And in fact this is known to the formal massive community.
And this partially explains why the constraint solver nowadays
are extremely fast.
So we can use constraint solver to model checking SQL.
So based on these two observations
we built Cosette, the first automated solver for SQL,
by combining interactive theorem proving and constraint solving.
While it takes me almost three years to build this tool,
it can be concluded in these simple slides.
So for a given pair of SQL queries, we did two things.
First, we compiled the SQL queries
to propositions that can be checked
by the interactive theorem prover.
And then we developed a proof search, or automated proof
generation procedure inside of the theorem prover
to try to find a mechanized proof for these equivalences.
And secondly, we compiled these SQL queries
to constraint solver and built a model checker
to check in order to find counterexamples
to inventing these SQL queries.
Without actually showing the code,
I will actually show you a demo.
So this is the tool that we built for checking equivalents
of SQL queries.
So you can see you can specify a schema for the table.
And then you basically right two SQL queries.
While you can see the first SQL query
joins the employee and payroll using the employee ID.
Well, the second query here we do kind of similar stuff,
but there is another join.
And there is two employee table.
So I mean I know it's really tricky to say whether--
it is really tricky to reason about whether it is equivalent.
So that's why we need our tool.
The solving takes some time, but this is really
the formal method researcher's fault.
So you can see that this two SQL query indeed equivalent.
It's hard to explain exactly why,
but intuitively it's that there is
a join in the second query that's kind of redundant.
So let's show you another example.
So in this example, similarly, you
can see there are two SQL queries.
It's kind of like a super lasting because there is join,
there is group by, and there is subqueries.
So whether these two SQL queries are equivalent.
Well it actually not, and returns a counter example.
If you actually ran this two SQL query
using this counter example, you will find exactly why.
But to give you a short story, this is actually--
people actually installed this two SQL query equivalent
and they published a paper in the top database journal
in 1982.
And after three years people find
this is actually incorrect.
And of course they published another paper to say,
this is incorrect.
But the high level idea is that the second career actually
ignores the extremely colored case when the group is empty.
So it takes three years for the database's researcher
to find this, but it takes our tool less than 10 seconds.
To conclude, I show you that SQL is the best programming
language next to JavaScript, and we
built Cosette, the first practical SQL
server based on the integration of interactive serum proving
and constraint solving techniques.
And I would say automated reasoning brought
by the integration of formal methods
and domain specific semantics, will
lead two more reliable and more optimized
future database systems.
DAN SUCIU: OK.
So let's thank Shumo.
And I would like to ask all the five
speakers to come to the front, and we have
like two minutes for questions.
So any questions?
Yes, please.
AUDIENCE: I had a question for Cong.
Really cool talk.
I'm curious, you mentioned that only rights end up
having to go to the database for a web application.
I know some web applications, multiple people
may be writing it at once.
Is there some easy mechanism for knowing when somebody else has
done something?
Or is that sort of out of scope here?
CONG YAN: Yeah, so basically the write
query both updates the in-memory storage
and the back-end database.
So the back-end database has a lot
of mechanics to handle concurrent write basically
using transactions.
And similarly like in our model, even
though I haven't implemented it yet,
we can use similar algorithms to use in-memory transaction
processing to make sure the update on the all the data
structures are automatic.
So when different people are doing different writes
on different data structures, I make
sure that they're not interweaving all of them.
DAN SUCIU: Yes, one more?
AUDIENCE: I have a question for Brandon.
So you have-- there's this--
you were talking about all these new methods
for capturing video in different ways from 360 or these cubes.
And I was wondering, are the like standards
for how to store--
the exact file formats, are they standardized at this point?
Are they changing?
Is your tool like designed to change with file formats?
Or is it pretty specific to one type?
BRANDON HAYNES: Right.
So that's a really good question.
So for anybody that didn't hear.
So the comment was that there's many, many formats
and projections, and all sorts of different VR and AR things
out there.
There's a giant zoo.
And are there standards?
Or how quickly is that changing?
And how do we handle that?
So when you run a SQL query you don't think about
whether your relation is stored as a B-tree, or as a heap,
or a flat file.
You let the database engine figure out how to manage it.
And so we do the same thing in LightDB.
So there is, as you suggested, a very large set
of formats and video codecs and for end
and 360 videos versus live fields,
and all sorts of ways to store these data.
And they're constantly evolving.
And some are more efficient for some types
of queries than others.
And we do our best a, to abstract
that so the user doesn't ever have to think about it.
So you don't worry about whether you're video is H264 encoded.
You just load it from the catalog.
And we'll actually make modifications as necessary
to minimize the storage footprint,
if you store it later on.
And if you run subsequent queries
it may run faster with those conversions.
So we try to pay attention to that.
I mean, of course, we don't at this time
cover every possible video codec, for example.
But the idea is that we could extend
that to support whatever is out there, if there's
a user demand for it.
It's a really good question.
DAN SUCIU: OK, so I think this is all the time we have.
So let's thank the speakers again.
And thanks, everyone, for coming.
For more infomation >> Mazda 3 Skyactive-G 120pk Aut navi/cruise/clima! - Duration: 1:05. 
For more infomation >> Mazda MX-5 2.0 Skyactiv-G 160pk i-ELOOP GT-M - Duration: 1:07. 
For more infomation >> Tiên Tri SÁO Dự Đoán Kết Quả Việt Nam Vs Philippines, Bán Kết AFF Cup 2018 Lượt Về Tại Mỹ Đình !!! - Duration: 10:45. 
For more infomation >> SignalBooster.com = Clear Cell Phone Calls + Fast Mobile Internet (Indoors and in Vehicles)
For more infomation >> How to Install New Software on Continuum Systems - Duration: 2:42. 
No comments:
Post a Comment