Some sample SQL queries

Sample 1: https://leetcode.com/problems/rising-temperature/

Given a Weather table, write a SQL query to find all dates’ Ids with higher temperature compared to its previous (yesterday’s) dates.


select a.Id from Weather as a, Weather as b
where DATEDIFF(a.Date, b.Date) = 1 and a.Temperature > b.Temperature

 

Sample 2: https://leetcode.com/problems/consecutive-numbers/

Write a SQL query to find all numbers that appear at least three times consecutively.


select distinct(a.Num) as ConsecutiveNums from Logs a, Logs b, Logs c
where a.Num = b.Num and b.Num = c.Num
and a.Id = b.Id-1 and c.Id-1 = b.Id

 

Sample 3: https://leetcode.com/problems/trips-and-users/


select t.Request_at as Day,
round(sum(case when t.Status like 'cancelled_%' then 1 else 0 end)/count(*),2) as 'Cancellation Rate'
from Trips t
inner join Users u
on t.Client_Id = u.Users_Id and u.Banned='No'
where t.Request_at between '2013-10-01' and '2013-10-03'
group by t.Request_at

 

Sample 4: https://leetcode.com/problems/department-highest-salary/


SELECT d1.Name as Department
, e1.Name as Employee
, e1.Salary
FROM (
SELECT d.Id
, MAX(d.Name) AS Name
, MAX(e.Salary) AS Salary
FROM Department d
JOIN Employee e
ON e.DepartmentId = d.Id
GROUP BY d.Id
) d1
JOIN Employee e1
ON d1.Id = e1.DepartmentId AND e1.Salary = d1.Salary

Advertisements

What is indexing? What does it do?

Stackoverflow doesn’t have very good answers about this topic since it’s too broad.

This article is helpful: http://www.programmerinterview.com/index.php/database-sql/what-is-an-index/

  • Basically, without an index, if you’d like to find one certain row(s), you’ll have to do a full table scan, this is literally really inefficient, like human eye check
  • An index is a data structure (most commonly a B-tree) that stores the values of a specific column in the table, i.e. in index consists of column values from the table
  • Why B-tree?
    • This is due to their efficiency: insertion/deletion/lookup can all be done in O(logn) time.
    • Another major reason is that the values stored in B-tree can be sorted
  • How does Hash table indexes work?
    • Imagine that we store one column value as the key in the hashtable, and the row data as the value of the hashtable, the lookup time is very fast. Because basically, Hashtable is like an “associative array”.
  •  The disadvantages of Hashtable working as index:
    • Hashtable keys are not sorted, it only maintains a mapping between key and value, so it’s good for fast lookup, but it’s not good for queries such to find how many employees that are younger than 25 years old in a table.
  • Good analogy of database index:
    • It’s like the index of a book: if you’d like to find the Chapter describing Python decorators, you could either flip through the pages or just go to the index page where that Chapter is listed, also a page number of that chapter is listed as well. Apparently, using the index page is a lot faster.
  • What’s the cost of having a database index?
    • It takes up space, the larger your table is, the larger your index is.
    • Another performance hit is that whenever you do CRUD to your table, the same operations will have to be done to your index
  • As a general rule, an index should only be created, if the data on the indexed column will be queried frequently.

Inner Join/Left Join/Right Join/Full Join

The INNER JOIN keyword selects all rows from both tables as long as there is a match between the columns in both tables.

inner_join

 

The LEFT JOIN keyword returns ALL rows from the left table (table1), with the matching rows in the right table (table2). The result is NULL in the right side when there is no match.

left_join

The RIGHT JOIN keyword returns all rows from the right table (table2), with the matching rows in the left table (table1). The result is NULL in the left side when there is no match.

right_join

The FULL OUTER JOIN keyword returns all rows from the left table (table1) and from the right table (table2).

The FULL OUTER JOIN keyword combines the result of both LEFT and RIGHT joins.

full_outer_join

 

The SQL UNION operator combines the result of two or more SELECT statements.
The UNION operator is used to combine the result-set of two or more SELECT statements.
Notice that each SELECT statement within the UNION must have the same number of columns.

 

SQL Aggregate Functions
SQL aggregate functions return a single value, calculated from values in a column.

Useful aggregate functions:

AVG() – Returns the average value
COUNT() – Returns the number of rows
FIRST() – Returns the first value
LAST() – Returns the last value
MAX() – Returns the largest value
MIN() – Returns the smallest value
SUM() – Returns the sum

Normalization of Databases

Based on wikipedia: https://en.wikipedia.org/wiki/Database_normalization

Database normalization, or simply normalisation, is the process of organizing the columns (attributes) and tables (relations) of a relational database to minimize data redundancy.

Normalization involves decomposing a table into less redundant (and smaller) tables without losing information, and then linking the data back together by defining foreign keys in the old table referencing the primary keys of the new ones. The objective is to isolate data so that additions, deletions, and modifications of an attribute can be made in just one table and then propagated through the rest of the database using the defined foreign keys.
A typical example of normalization is that an entity’s unique ID is stored everywhere in the system but its name is held in only one table. The name can be updated more easily in one row of one table. A typical update in such an example would be the RIM company changing its name to BlackBerry. That update would be done in one place and immediately the correct “BlackBerry” name would be displayed throughout the system.

Following examples are adapted from: http://www.studytonight.com/dbms/database-normalization.php

1NF (First Normal Form): each set of column must have a unique value.

Name    Age    Subject

Adam    15        Biology, Networking

Alex       14        OS

 

Table like above is a violation against 1NF, to obey 1NF, it should be like below:

Name    Age    Subject

Adam    15        Biology

Adam    15        Networking

Alex       14        OS

Thus, with 1NF, data redundancy increases. But each row as a whole is unique.

 

2NF: there must NOT be any partial dependency of any column on primary key. It means that for a table that has concatenated primary key, each column in the table that is not part of the primary key should depend upon the ENTIRE primary key, not just part of it.

For the above table, which meets 1NF, and its candidate key (primary key) is {NameSubject}, but Age is only dependent on Name, which fails 2NF. To meet 2NF, we need to split out the above table into two tables:

Name    Age

Adam    15

Alex       14

and one more table for Subject:

Name    Subject

Adam    Biology

Adam    Networking

Alex       OS

3NF means that non-prime attributes of tables must be dependent on primary key, or in other words, any non-prime attributes should NOT be dependent on other non-prime attributes.

E.g.

Id    Name    Address    City    State    Zip

in the above table, Id is the primary key, however, Address, City and State depend on Zip which is a non-prime attribute, thus it fails 3NF.

To meet 3NF, the above table should be split into two tables:

Id    Name    Zip

and one more table:

Zip    Address    City    State

Also, as a side note, 2NF must have already conform to 1NF, 3NF must have already conform to 2NF.

 

For large databases, we might often need to de-normalize data, i.e. duplicate data in tables since join on large tables are very expensive/slow.

Sharding/Partition/Horizontal scaling

  • RDBMS:
    • This model organizes data into one or more tables (or “relations“) of columns and rows, with a unique key identifying each row. Rows are also called records or tuples.
  • In computer science, ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties that guarantee that database transactions are processed reliably.
  • Sharding is a type of database partitioning that separates very large databases the into smaller, faster, more easily managed parts called data shards. The word shard means a small part of a whole.
    • So each shard is just one small portion of the big database table, but each table has the same structure, it’s just that their rows/entries are different, this definitely improves search performance, since the amount in each shard is smaller.
    • The advantages are:
      • High availability. If one box goes down the others still operate.
      • Faster queries. Smaller amounts of data in each user group mean faster querying.
      • More write bandwidth. With no master database serializing writes you can write in parallel which increases your write throughput. Writing is major bottleneck for many websites.
      • You can do more work. A parallel backend means you can do more work simultaneously. You can handle higher user loads, especially when writing data
  • Difference between NoSQL and RDBMS?
    • SQL databases are table based databases whereas NoSQL databases are document based, key-value pairs, graph databases or wide-column stores.
      • This means that SQL databases represent data in form of tables which consists of n number of rows of data whereas NoSQL databases are the collection of key-value pair, documents, graph databases or wide-column stores which do not have standard schema definitions which it needs to adhered to.
    • SQL databases have predefined schema whereas NoSQL databases have dynamic schema for unstructured data.
    • SQL databases are vertically scalable whereas the NoSQL databases are horizontally scalable.
      • SQL databases are scaled by increasing the horse-power of the hardware.
      • NoSQL databases are scaled by increasing the databases servers in the pool of resources to reduce the load.
    • To scale horizontally (DynamoDB) (or scale out/in) means to add more nodes to (or remove nodes from) a system, such as adding a new computer to a distributed software application. An example might involve scaling out from one Web server system to three.
    • To scale vertically (MySQL) (or scale up/down) means to add resources to (or remove resources from) a single node in a system, typically involving the addition of CPUs or memory to a single computer.
    • In a database world horizontal-scaling is often based on partitioning of the data i.e. each node contains only part of the data , in vertical-scaling the data resides on a single node and scaling is done through multi-core i.e. spreading the load between the CPU and RAM resources of that machine.
    • With horizontal-scaling it is often easier to scale dynamically by adding more machines into the existing pool – Vertical-scaling is often limited to the capacity of a single machine, scaling beyond that capacity often involves downtime and comes with an upper limit.
    • A better illustration is here: https://medium.com/@jeeyoungk/how-sharding-works-b4dec46b3f6#.ocmqofqlx
      • vertical partitioning: store different tables & columns into separate databases;
      • horizontal partitioning: storing rows of a same table into multiple database nodes.
    • A good example for horizontal scaling is Cassandra , MongoDB .. and a good example for vertical scaling is MySQL – Amazon RDS (The cloud version of MySQL) provides an easy way to scale vertically by switching from small to bigger machines this process often involves downtime.
  • Then naturally, I had a question, how query works in a sharded database world? since the entry to be searched could be stored in any one of the shards?
    • This short slides: http://www.slideshare.net/mongodb/how-queries-work-with-sharding well illustrates it.
    • Different shards could share the same shard key, if the query specifies the shard key in the query, then we could directly go to that node and search.
    • If the query doesn’t contain the common shard key, then multiple/all nodes could process the query in parallel, so, still much faster than a single monolithic database server as the traditional ways.
  • What does “index mean and why do we need it?
    • from https://en.wikipedia.org/wiki/Database_index: A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row in a database table every time a database table is accessed.
    • In my own words, it’s basically creating a mapping, like for each folder/document/entry, we create one index for it, so next time, when clients query something about this folder/document/entry, we can quickly find its index and thus quickly return this folder/document/entry.