SQL Database Optimization

Key Takeaways

hello world it's Suraj and what's the most efficient way to interact with the database anytime we want to create read update or delete data in a database will usually do so in the form of sequel queries sequel stands for structured query language and it's the standard language used to communicate with relational databases what about Haskell dB each query takes a certain amount of time to compute and ideally we can order our queries in the most computationally efficient way there are several techniques to do this and usually reinforcement learning isn't considered one of them but a recent paper showed that using a deep queue network researchers were able to perform queries twice as fast as using standard techniques we'll learn how they did it in this video but first we'll need to understand why they used reinforcement learning as opposed to other more common techniques we know that reinforcement learning works great for video games games are the perfect testbed for implementing orell algorithms since they're constrained environments where time is an element that allows for rapid experimentation the Markov decision process is the mathematical framework of choice for framing this decision problem that our AI or agent is facing it consists of a few variables that define our environment our agent and how our agent interacts with this environment in reinforcement learning an agent tries to come up with the best action to take given a state in the video game pac-man the state would be the 2d game world were in that includes the surrounding items like enemies walls and packed dots the action would be moving through this 2d space which would be going either up down left or right so given the state of our game world our agent will need to pick the best action to take in order to maximize rewards we know that eating packed dots gives us positive rewards and getting eaten by a ghost gives us a negative reward and a possible temper tantrum which we want to avoid through trial and error our agent will accumulate knowledge of the environment through state action pairs meaning it can tell if there would be a positive or negative reward given a state action pair we can represent this using the cue function where Q stands for quality as in it assesses the quality of a given state action pair we can actually learn what the optimal Q value will be at any given point and this is called Q learning by using what's called the bellman equation we can write out an equation that relates the value of one state to the value of another state in our environment because we are able to relate states across time to each other mathematically using the bellman equation we can use any number of methods to iteratively approximate our Q function but in the case of our pac-man environment the state action space can get really big in fact at some point it will no longer be feasible to store all the state action pairs of course we could still perform Q learning but it'll get harder to approximate the Q function over time luckily for us there exists a universal function approximator called a neural network if we give it enough input data it can learn any function if we use a neural network as an agent that predicts the Q value based on the input state action pair then we have a much more tractable solution than storing every possible value like we did previously and to capture all the intricate details of this knowledge present in our Q table we'll likely need to add a few hidden layers to our network making it a deep neural network the extra hidden layers allow the network to internally come up with features that can help it learn complex functions that would have been impossible using a more shallow network we can call this whole process deep reinforcement learning and more specifically deep Q learning now let's bring this theory back to reality you and I have neural networks in our head networks of neurons are firing in endlessly different combinations to approximate functions that help us perform a wide variety of tasks as we go about our lives and we can consider our reality a Markov decision process as neural network agents given a state we take actions to maximize reward for whatever task we are achieving using our function approximation capabilities to make predictions in that way we can consider our reality deep reinforcement learning anytime we use a neural network to approximate some reinforcement learning function get a value function a policy even the model itself we can call that deep reinforcement learning so how does this apply to the problem of query optimization well we know that sequel statements are used to perform a wide variety of tasks related to the database they can update data retrieve data merge data delete data each sequel query has its own function assume we have a database consisting of three tables employees salaries and taxes let's say we want to calculate the total tax owed by all employees under manager one we can write out a sequel query that does that we'll compute the tax owed by each employee by selecting their specific attributes and summing them all up this query is going to perform a three relation join we can use J to help denote the cost of accessing a base relation the cost of each query is the percentage of the total batch cost it's the time needed to execute a query it's computed different ways but almost always takes into account several computation factors such as input output CPU and communication we want to minimize this cost so that we perform our queries as fast as possible using dynamic programming we can iteratively calculate the cost of optimally accessing the three-base relations after the first iteration we can build off of this information that we previously computed and enumerate all two relations when we compute the best cost to join two relations we'll look up the relevant previously computed results and in the third iteration we'll proceed through the other two relation sets eventually finding the final best costs for joining all three tables once complete will see that this algorithm has a space and time complexity exponential in the number of relations which is why it's usually only used for queries between 10 and 20 relations when we have more relations than that we'll need to use a different query optimization technique instead of solving this join ordering problem using dynamic programming what if we formulated this problem as a Markov decision process and solved it using reinforcement learning if we do that the states can be considered the remaining relations to be joined the actions would be the valid joins out of the remaining relations the next states would be the old remaining relations set with two relations removed and the resultant join added lastly the reward would be the estimated cost of the new join because we defined these Markovian variables we can define a queue function using the bellman equation to describe the long-term cost of each join and since we've defined a queue function we can order joins in a greedy way we start with the initial query graph find the join with the lowest queue value then update the query graph and repeat the process this queue learning algorithm has a computational complexity of n cubed although that's high that's still much lower than the exponential run time complexity of dynamic programming in reality though we don't have access to the optimal queue function so we need to approximate it to do that we can use a neural network which would make this deep queue learning to learn the queue function we need to observe past execution data we can use it as training data for our neural network and since we're using a neural network to represent our queue function when to feed the state and actions into the network as fixed-length feature vectors this helps our network perform matrix multiplications gracefully as it accepts this kind of format will use one hot vectors to encode the set of all attributes present in the query graph and the participating attributes from both the left and right side of the join will use a simple two layer fully connected network as our agent and train it using the standard gradient descent optimization algorithm once trained it will accept a sequel query in plaintext parse it into an abstract syntax tree form feature the tree and use a neural network whenever a candidate join is scored and because databases are real-time used in production environments constantly being updated and changed we can periodically retune our network using the feedback from live execution across all cost models deep queue is competitive with the optimal solution without a priori knowledge of the index structure we can safely say that learning-based optimizers are more robust than hand designed algorithms because they can adapt to changes in data workload or cost models for the largest joins deep queue wins by up to 10,000 x compared to exhaustive enumeration three points to remember from this video deep reinforcement learning involves using a neural network to approximate reinforcement learning functions like the cue function we can assess the quality or cue of state action pairs by computing a cue table and cue learning involves approximating the relationship between state action pairs and Q values in this table using neural networks please subscribe for more programming videos and for now I've got to take a meeting so thanks for watching