DEV Community: zchtodd

#SQL30 Day 16: Dev Badges

zchtodd — Fri, 18 Oct 2019 12:10:53 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

I'm committing to publishing a SQL challenge every day for 30 days. In each post I'll describe my solution to the last day's challenge. I'll follow that up with a full description of the challenge for the next day.

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #16: Dev Badges

If you post a lot on dev.to you might have received one of their nifty badges. I just got my 4 week streak badge! It wasn't long until I started thinking about how you could identify posting streaks in SQL.

The day16 schema contains a post table with a handful of columns:

id
user_id
created_at

The challenge is this:

Can you write a query that will return all users that are currently eligible for the 4 week streak badge? (At least one post per week for the last 4 weeks.)

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the post table:

SELECT * FROM day16.post;

Solution to Challenge #15: Fuzzy Matching

Yesterday we dipped a toe into the world of fuzzy matching in databases. As a reminder, we had two tables full of info about movies, but from independent sources. We wanted to see what PostgreSQL and other databases offer when it comes to fuzzy matching.

This was the challenge from yesterday:

What fuzzy matching methods can be used to join the movie datasets together on keys such as the director name?

We have the movie and movie_plot tables that should contain quite a bit of overlapping data.

Let's try a naive approach first and join using strict equality:

SELECT count(*) from (
  SELECT DISTINCT director FROM day15.movie
) AS d1
JOIN (
  SELECT DISTINCT director FROM day15.movie_plot
) as d2
ON d1.director = d2.director;

Here I join the distinct set of directors from both tables together using a straightforward equality comparison. I get 478 directors in common using this technique.

What techniques can we try to discover more matches?

Levenshtein (Edit Distance)

Are we missing any potential matches due to small differences in spelling?

The Levenshtein distance between two strings defines the minimum number of insertions, substitutions, or deletions that would be required to make them equivalent. The Levenshtein function is also sometimes referred to as edit distance, because although there are other variations on edit distance, it is the most commonly used.

Before you can try out Levenshtein distance, however, you'll need to enable the fuzzystrmatch extension in PostgreSQL.

CREATE EXTENSION fuzzystrmatch;

Let's say we wanted to retry the query from above, but instead of requiring an exact match, we relax the comparison so that the strings can have an edit distance of 1.

SELECT count(*) FROM (
  SELECT DISTINCT director FROM day15.movie
) AS d1
JOIN (
  SELECT DISTINCT director FROM day15.movie_plot
) AS d2
ON levenshtein(d1.director, d2.director) <= 1;

This time I come up with 493 matches. Here are some of the extra matches that turned up with an edit distance of 1.

As a whole this seems to be a net improvement, but fuzzy matching is always a balancing act between improved accuracy and false positives. For example, it seems likely that Darren Aronofosky and Darren Arronofsky are the same person, while David Dobkin and David Doblin are probably not.

The usefulness of edit distance can depend on the data it is applied to. We can see with names, for example, that a single edit can be very important.

Soundex and Metaphone

Soundex belongs to a family of comparison functions that rely on the spoken sound of a word instead of comparing the characters themselves. Soundex was created almost a century ago to help with the U.S. census, and as a result, it doesn't handle non-English names very well.

The metaphone function is a more modern alternative. Let's take a look at an example:

SELECT
  count(*)
FROM
  (
    SELECT
      split_part(d.director, ' ', 1) AS first_name,
      split_part(d.director, ' ', 2) AS last_name,
      d.director
    FROM
      (
        SELECT
          DISTINCT director
        FROM
          day15.movie
      ) d
  ) AS d1
  JOIN (
    SELECT
      split_part(d.director, ' ', 1) AS first_name,
      split_part(d.director, ' ', 2) AS last_name,
      d.director
    FROM
      (
        SELECT
          DISTINCT director
        FROM
          day15.movie_plot
      ) d
  ) AS d2 ON dmetaphone(d1.first_name) = dmetaphone(d2.first_name)
  AND dmetaphone(d1.last_name) = dmetaphone(d2.last_name);

Most of the work here is involved in splitting up the director name so that I can run the metaphone function on first and last names separately.

Here's what I get back with the above query:

There are some good matches here, like Andrey and Andrei Gorlenko, but there are also a few inexplicable false positives, like Anna Biller and Wayne Blair.

PG_TRGM

PostgreSQL also supports trigram matching through the PG_TRGM extension. Trigrams are a simple, yet powerful, concept that involves breaking strings down to sets of 3 consecutive letters. The number of sets a pair of strings have in common determines their trigram score.

Getting started is pretty easy.

CREATE EXTENSION pg_trgm

The movie table has a comma delimited list of actors. Let's see if we can use trigrams to fuzzy match on a specific actor.

SELECT * FROM day15.movie WHERE 'Patrick Stewart' % ANY (string_to_array(actors, ','));

The % operator is used in place of the normal = to apply trigram matching. The ANY keyword means the expression is considered true if there is a trigram match on any of the actors in that movie.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 15: Fuzzy Matching

zchtodd — Thu, 17 Oct 2019 12:25:30 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #15: Fuzzy Matching

Today I'd like to tackle the subject of fuzzy matching in SQL. Not every problem is as black and white as a simple equality check. You might have used the SQL LIKE operator before, but there are times when even that won't suffice.

Imagine you have two totally separate data-sets that represent the same entities, and you want to join them together. Because they come from different sources, they don't share any kind of reliable key. You may need to join them using names, addresses, or other such "noisy" information.

For this challenge, I've populated two tables with data about movies. Both tables contain movie titles, director names, and names from the cast.

Here's the challenge itself:

What fuzzy matching methods can be used to join the movie datasets together on keys such as the director name?

I won't show a desired output for this challenge because it's more of an open-ended invitation to experiment. Tomorrow I'll show a number of ways you can fuzzy match in PostgreSQL.

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the movie table:

SELECT * FROM day15.movie;

Solution to Challenge #14: UFO Sightings

If you'll recall yesterday's challenge, we were trying to decipher any patterns that might exist when analyzing UFO sightings over time.

This was the challenge from yesterday:

Given UFO sightings from 1906 to present day, can you produce a monthly count of sightings by shape?

And as a reminder, this was the format of the output we were after:

It seems like July and August are a busy time for UFO sightings!

Here's the SQL that produces the above:

SELECT
  shape,
  sum(CASE WHEN sighting_m = 1 THEN 1 END) AS "Jan",
  sum(CASE WHEN sighting_m = 2 THEN 1 END) AS "Feb",
  sum(CASE WHEN sighting_m = 3 THEN 1 END) AS "Mar",
  sum(CASE WHEN sighting_m = 4 THEN 1 END) AS "Apr",
  sum(CASE WHEN sighting_m = 5 THEN 1 END) AS "May",
  sum(CASE WHEN sighting_m = 6 THEN 1 END) AS "Jun",
  sum(CASE WHEN sighting_m = 7 THEN 1 END) AS "Jul",
  sum(CASE WHEN sighting_m = 8 THEN 1 END) AS "Aug",
  sum(CASE WHEN sighting_m = 9 THEN 1 END) AS "Sep",
  sum(CASE WHEN sighting_m = 10 THEN 1 END) AS "Oct",
  sum(CASE WHEN sighting_m = 11 THEN 1 END) AS "Nov",
  sum(CASE WHEN sighting_m = 12 THEN 1 END) AS "Dec"
FROM (
  SELECT 
    date_sighted, 
    shape, 
    duration, 
    EXTRACT(MONTH FROM date_sighted) AS sighting_m 
  FROM day14.ufo WHERE shape IN (
    SELECT shape FROM day14.ufo GROUP BY shape HAVING count(*) >= 3000
  )
) AS sightings GROUP BY shape;

The main trick here, similar to the solution found in day 5, is to turn rows into columns using CASE WHEN statements, so that I can show the months across the top.

Some databases, such as SQL Server, provide a built-in PIVOT function that makes this a bit easier (or at least less verbose). In PostgreSQL, we'll have to settle for the CASE WHEN trick.

Each month has a sum with a conditional inside of it that produces a 1 only if the month of the input row matches. Whenever the row doesn't match, the output of the conditional is NULL, which is evaluated as zero in the sum.

Selecting from a subquery instead of directly from the UFO table is optional, and I do that only so I can avoid repeating the month extraction over and over in the CASE WHEN statements. Likewise, the WHERE clause is optional too, and just serves to eliminate a lot of noisy one-off shapes from the data.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 14: UFO Sightings

zchtodd — Wed, 16 Oct 2019 11:06:03 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #14: UFO Sightings

For a bit of fun I decided to load an open data-set of UFO sightings into PostgreSQL. Each row represents a reported sighting, including the date, shape of the object, and the duration of the sighting.

Let's see if we can deduce some kind of seasonal pattern to UFO sightings. Here's the challenge itself:

Given UFO sightings from 1906 to present day, can you produce a monthly count of sightings by shape?

Here's an example of the output we should get:

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the ufo table:

SELECT * FROM day14.ufo;

Solution to Challenge #13: Permutations

This was the challenge from yesterday:

Can you generate all of the permutations of a given set in SQL?

Specifically, we wanted all of the permutations from the set {1, 2, 3}. My first thought here was to use a CROSS JOIN, as that kind of join will produce every possible pairing between two tables.

That's not quite what we want, however, because we'd like each item in the permutation to be distinct. In other words, {1, 1, 1} is not a valid permutation. Luckily, that's not too hard to enforce by means of a WHERE clause.

Let's take a look.

WITH v AS (
  SELECT generate_series(1, 3) AS n
)
SELECT * FROM v AS v1 
CROSS JOIN v AS v2
CROSS JOIN v AS v3
WHERE 
v1 NOT IN (v2, v3) AND
v2 NOT IN (v1, v3) AND
v3 NOT IN (v1, v2);

The WHERE clause checks that each element of the permutation does not equal any other element, thus ensuring that there's no repetition.

You would need to add more joins to account for a larger set. Can anyone think of an approach that works no matter the size of the input set?

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 13: Permutations

zchtodd — Tue, 15 Oct 2019 10:45:19 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #13: Permutations

This is a seemingly simple, yet somewhat tricky challenge for today.

Can you generate all of the permutations of a given set in SQL?

There is no table available on the sandbox server for today's challenge, but the source data is easy to create using something like the generate_series function in PostgreSQL.

For this challenge I'm using the set {1, 2, 3}. Here's an example of the output we should get:

Solution to Challenge #12: Greatest Discount

The key trick to solving yesterday's challenge is to think in terms of events, rather than ranges of times. In other words, a discount starting is an event, and a discount ending is an event. When a discount starts the overall cumulative rate rises, and conversely, the rate falls when a discount ends.

To break down a range into separate events we can use UNION ALL to combine queries that select the start and end dates.

SELECT start_date AS dt, rate FROM day12.discount
UNION ALL
SELECT end_date AS dt, -rate FROM day12.discount

Negating the rate in the second query will allow us to do a running total on the rates, thus giving the cumulative rate at each point in time.

Whenever a phrase like "running total" or "rolling average" appears, it's a safe bet that window functions are part of the solution. Let's look at how we can combine the first query with a window function to find the cumulative discount rate:

SELECT sum(rate) OVER (ORDER BY dt) AS cumulative_disc, dts.dt FROM (
  SELECT start_date AS dt, rate FROM day12.discount
  UNION ALL
  SELECT end_date AS dt, -rate FROM day12.discount
) AS dts ORDER BY cumulative_disc DESC;

The ORDER BY within the OVER clause limits the sum to the current row and all rows prior to it (sorted by date). From there it's just a matter of sorting the entire query to get the greatest possible discount.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 12: Greatest Discount

zchtodd — Mon, 14 Oct 2019 11:42:54 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #12: Greatest Discount

For today's challenge I'll pose a problem that involves finding date overlaps in the data. Here's the challenge itself:

Suppose you have a table of discount rates, each of which is only valid for a limited time, but discounts are cumulative. Can you find the greatest possible cumulative discount rate?

Here's an example of the data we have to play with:

The greatest cumulative discount, given the data above, would be 0.35.

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the discount table:

SELECT * FROM day12.discount;

Solution to Challenge #11: Soft Deletes

If you've read yesterday's challenge, you'll know I opted to change things up a bit, and instead of asking for an answer in the form of a query, I posed a more open-ended design question.

The challenge focused on how we could implement the soft delete pattern in a database, while asking a number of questions about possible issues that might affect the design:

What happens to related child data when a parent is soft deleted? If a user deletes an "account" record, what happens to all of the related "order" records?
The entire application is now responsible for making sure that queries filter out all "deleted" records. Write enough queries, and sooner or later someone will forget to filter out the deleted records.
What affect will deleted records have on constraints that might be in place? If I have a unique constraint on a field called name, should users be able to create new records that re-use an existing name on a soft-deleted record?

As I thought through this problem, I realized that there are many complications that come with adding soft deletes. In fact, if you look at the most popular StackOverflow answer regarding soft deletes, quite a few people advocate avoiding this pattern if at all possible.

Assuming we believe the complexity is worthwhile, how can we implement soft deletes in a way that doesn't add a great deal of bug-prone overhead?

Let's talk through some possible solutions.

Adding a deleted_on column

In this scenario a deleted_on date-time column would be added to any table that allows soft deletes. A null value indicates a currently active record.

The pros:

Solution is easy to implement.
Unique constraints can still function if the database supports partial indexes.

The cons:

Querying the table becomes more complex. Every query needs an additional criteria, or a view must be created to handle the filtering. This may not be an attractive solution because ORMs don't tend to have great support for creating, maintaining, or accessing data through views.
The behavior of relationships between tables is not very well defined. Foreign keys lose meaning if deleting a record does not really mean deleting it.

Archive tables

Instead of adding a deleted flag or timestamp, we can introduce archive tables that are (nearly) identical to the original version. Any deleted records are first inserted into an associated archive table prior to removal from the original.

Archive tables should have the same columns as their associated original, but would not have unique constraints. Copying records that are about to be deleted would need to be done in application code, or in the database itself via a trigger.

The pros:

Queries can operate without knowledge of soft deletes.
Foreign keys function as they normally would. Any cascading deletes or updates result in the expected behavior.

The cons:

Depending on how many tables need the soft delete pattern, the size of the schema can balloon. Maintaining the archive tables as schema migrations occur would be painful to do by hand. Some databases, such as PostgreSQL, support table inheritance, which could make maintenance easier.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 11: Soft Deletes

zchtodd — Sun, 13 Oct 2019 12:41:21 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

I'll add connection details for a PostgreSQL database containing test data for the challenge. Solutions are by no means limited to PostgreSQL, but it's there if you want an easy way to test your query!

Challenge #11: Soft Deletes

I'm changing things up a bit for this challenge and focusing more on database design instead of a specific query. Instead of posing a single challenge, I'll present a series of questions about a certain database design topic.

I hope you'll chime in! I have an answer to these questions, but I don't pretend to have the best answers.

This design challenge centers around the idea of soft deletes. Normally, when data is deleted in a database, it's irrevocably gone. It's not uncommon, however, that you might want to preserve a record while hiding it in your user interface.

A simple way to go about this is to add a deleted boolean field to your table. In some cases, it might really be just that simple, and there's not much else to worry about.

But here are some questions about this design:

What happens to related child data when a parent is soft deleted? If a user deletes an "account" record, what happens to all of the related "order" records?
The entire application is now responsible for making sure that queries filter out all "deleted" records. Write enough queries, and sooner or later someone will forget to filter out the deleted records.
What affect will deleted records have on constraints that might be in place? If I have a unique constraint on a field called name, should users be able to create new records that re-use an existing name on a soft-deleted record?

Solution to Challenge #10: Random Sampling

This is the question we were trying to answer with yesterday's SQL challenge:

Can you write a query to efficiently return a random sample of records from a table?

Before going any further, let's first look at the simplest possible way to achieve this.

SELECT * FROM day10.measurement ORDER BY random() LIMIT 10;

(The above works in PostgreSQL and MySQL, but in SQL Server you'll need to use the NEWID() function.)

If your table is of a reasonable size, you probably don't need to overthink this any further. But if you're dealing with millions of rows, this approach can become quite slow.

Why is that? This query will need to scan through every row in the table and generate a random number. Once every row has a random number, the entire table will need to be sorted on that value. If the table is big enough, that sort will most likely spill over into a temporary table stored on disk.

A more efficient solution would be to generate N random numbers first, and then select rows out of your table by ID. The random numbers could be generated outside of the database, and then put into a select like so:

SELECT * FROM day10.measurement WHERE idx IN (?)

This of course has some pitfalls, including the fact that your primary key could have gaps if you've deleted any rows.

More resources

There is a lot of discussion online about selecting random rows. Specifically for PostgreSQL, there is a fascinating answer on StackOverflow that delves into some very advanced ways to fetch random records.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 10: Random Sampling

zchtodd — Sat, 12 Oct 2019 11:17:14 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #10: Random Sampling

For today's challenge I'll delve into a topic that is simple on the surface, but also has a surprising amount of subtlety.

Here's the challenge itself:

Can you write a query to efficiently return a random sample of records from a table?

We'll re-visit the measurement table from the day 3 challenge. Obviously, your results will vary from mine, but the goal is to return a random sampling of records from the table.

Here's what my output looks like when grabbing 10 random records:

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the employee table:

SELECT * FROM day10.measurement;

Solution to Challenge #7: Grouping Sets

This is the question we were trying to answer with yesterday's SQL challenge:

Given supermarket sales history, can you display sales not only by location and category, but also at the month and yearly level?

Remember, in this challenge we wanted the output to appear something like this:

That is, we wanted sales summed up to the month, but with a yearly subtotal for each location and category.

Not long ago, I probably would have reached for Python to do this kind of multi-level aggregation, but it turns out there's a perfectly good way to do this in SQL.

Group by, apparently, has a hidden super power called grouping sets.

Grouping sets allow you to group at several different levels. Let's take a look at the query that produced the output above.

SELECT   s.city, 
         s.product_line, 
         Date_part('month', sale_date) AS monthly, 
         Date_part('year', sale_date)  AS yearly, 
         Sum(total) 
FROM     day7.supermarket s 
GROUP BY grouping sets (((city, product_line), yearly, monthly), ((city, product_line), yearly)) 
ORDER BY city, 
         product_line, 
         monthly, 
         yearly;

As you can see in the output, any row produced by a set missing columns (in this case month), will have a null value for that column.

SQL also has a few shorthand notations, such as ROLLUP and CUBE, that produce commonly needed grouping sets.

I could change the above query to use ROLLUP like so:

SELECT   s.city, 
         s.product_line, 
         Date_part('month', sale_date) AS monthly, 
         Date_part('year', sale_date)  AS yearly, 
         Sum(total) 
FROM     day7.supermarket s 
GROUP BY ROLLUP ((city, product_line), yearly, monthly)
ORDER BY city, 
         product_line, 
         monthly, 
         yearly;

This would actually be equivalent to the following sets:

((city, product_line), yearly, monthly): Sales broken down to the month.
((city, product_line), yearly)): Sales broken down to the year.
((city, product_line)): All sales for each city/product line.
(): All sales, for all time, for all city/product combinations.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 9: Longest Span

zchtodd — Fri, 11 Oct 2019 11:26:32 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #9: Longest Span

For this challenge we'll revisit the stock market data from #2, but this time we'll try something a bit more difficult.

Here's the challenge:

Given a table of daily trading data, can you find the longest stretch of consecutive days during which the stock price rose?

Here's an example output showing roughly what you're looking for.

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the stockprice table:

SELECT * FROM day9.stockprice;

Solution to Challenge #8: Duplicates

This is the question we were trying to answer with yesterday's SQL challenge:

Can you write a select query that could be used in a delete statement to make the rows of a table unique according to a natural key?

The solution to this question proved to be trickier than I would have thought. If we wanted to delete all instances of any employee that had duplicates, it would be fairly easy.

DELETE FROM day8.employee WHERE name IN (
  SELECT name FROM day8.employee GROUP BY name HAVING count(*) > 1
);

Unfortunately, the above query will remove any employee with duplicates entirely from the table. We want exactly one reference to each employee.

One means of doing this would be to group the employees by name, and then assign a rank to each row in the group. We could then delete all rows from each group that aren't the first occurrence.

WITH employee_rnk AS (
  SELECT row_number() OVER (PARTITION BY name) AS rnk, name FROM day8.employee
)
DELETE FROM day8.employee s USING employee_rnk r WHERE s.name = r.name AND r.rnk != 1;

The row_number() window function will assign an increasing integer value to each row of a partition.

The USING clause in a delete statement acts essentially the same as having multiple tables listed in the FROM part of a query.

Unlike SQL Server, you can't perform a join inside of a delete in PostgreSQL, but oddly enough, you can put tables together by combining USING and a WHERE clause. Once the table and the CTE are joined together, it's just a matter of filtering down to where the row number is not equal to 1, indicating a duplicate to be deleted.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 8: Deleting Duplicates

zchtodd — Thu, 10 Oct 2019 11:09:40 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #8: Deleting Duplicates

Today I'd like to pose a challenge focused on detecting duplicates within a table. The ultimate goal is to delete all duplicates from the table, while preserving one row from each group, such that we're left only with the unique values.

Deletes aren't allowed on the sandbox server, so I'll stop short of asking for the actual delete query, and instead ask only for the select query that could be passed to the delete.

Here's the challenge itself:

Can you write a select query that could be used in a delete statement to make the rows of a table unique according to a natural key?

We'll re-visit the employee table from day 5 for this challenge. Here's a sample from the table.

You can see that Hans Volkman is repeated 3 times. We'd like to end up with only one Hans Volkman after running the delete statement.

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the employee table:

SELECT * FROM day8.employee;

Solution to Challenge #7: Grouping Sets

This is the question we were trying to answer with yesterday's SQL challenge:

Given supermarket sales history, can you display sales not only by location and category, but also at the month and yearly level?

Remember, in this challenge we wanted the output to appear something like this:

That is, we wanted sales summed up to the month, but with a yearly subtotal for each location and category.

Not long ago, I probably would have reached for Python to do this kind of multi-level aggregation, but it turns out there's a perfectly good way to do this in SQL.

Group by, apparently, has a hidden super power called grouping sets.

Grouping sets allow you to group at several different levels. Let's take a look at the query that produced the output above.

SELECT   s.city, 
         s.product_line, 
         Date_part('month', sale_date) AS monthly, 
         Date_part('year', sale_date)  AS yearly, 
         Sum(total) 
FROM     day7.supermarket s 
GROUP BY grouping sets (((city, product_line), yearly, monthly), ((city, product_line), yearly)) 
ORDER BY city, 
         product_line, 
         monthly, 
         yearly;

As you can see in the output, any row produced by a set missing columns (in this case month), will have a null value for that column.

SQL also has a few shorthand notations, such as ROLLUP and CUBE, that produce commonly needed grouping sets.

I could change the above query to use ROLLUP like so:

SELECT   s.city, 
         s.product_line, 
         Date_part('month', sale_date) AS monthly, 
         Date_part('year', sale_date)  AS yearly, 
         Sum(total) 
FROM     day7.supermarket s 
GROUP BY ROLLUP ((city, product_line), yearly, monthly)
ORDER BY city, 
         product_line, 
         monthly, 
         yearly;

This would actually be equivalent to the following sets:

((city, product_line), yearly, monthly): Sales broken down to the month.
((city, product_line), yearly)): Sales broken down to the year.
((city, product_line)): All sales for each city/product line.
(): All sales, for all time, for all city/product combinations.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

#SQL30 Day 7: Grouping Sets

zchtodd — Wed, 09 Oct 2019 10:39:25 +0000

Welcome to the SQL showdown series!

What is this and how does it work?

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #7: Grouping Sets

In this challenge we'll explore the idea of grouping sets by rolling up data in several different ways.

The question for today is:

Given supermarket sales history, can you display sales not only by location and category, but also at the month and yearly level?

Here's an example to give you a better idea of the output you're after:

As you can see above, sales are summed up at the month level, but each location/product combination also has a subtotal row for the year.

The day7 schema contains only the supermarket table. Here's a sample of that table:

Sandbox Connection Details

I have a PostgreSQL database ready for you to play with.

The password is the same as the username! To query the **** table:

SELECT * FROM day7.supermarket;

Solution for Challenge #6

This is the question we were trying to answer with yesterday's SQL challenge:

Given supermarket sales history by location and category, can you produce a report without gaps? In other words, if the Mandalay location had no sales in the home and lifestyle category on a certain day, we'd still like to see a row with zero.

If you've done data analysis for a while, you've probably had this requirement come up. Understandably, users would rather see a row with a default zero value than a missing time range on a report.

My solution is to generate all of the possible combinations first, and then join to the actual sales data to display that when it's available.

In this case, we have locations, categories, and dates. There are 3 stores and 6 categories, so that should produce 18 rows. Generating the dates is probably the trickiest part of this, but PostgreSQL provides a handy function that makes life easier in that regard.

First, let's take a look at the solution and then we'll work through it.

SELECT
  keys.city,
  keys.product_line,
  coalesce(total, 0) AS total,
  keys.sale_date
FROM
  (
    WITH date_range AS (
      SELECT
        min(sale_date) AS min_date,
        max(sale_date) AS max_date
      FROM
        day6.supermarket
    )
    SELECT
      *
    FROM
      (
        SELECT
          distinct city
        FROM
          day6.supermarket
      ) s1
      CROSS JOIN (
        SELECT
          distinct product_line
        FROM
          day6.supermarket
      ) AS s2
      CROSS JOIN (
        SELECT
          generate_series(min_date, max_date, INTERVAL '1 day') AS sale_date
        FROM
          date_range
      ) AS s3
  ) AS keys
  LEFT JOIN day6.supermarket s ON keys.city = s.city
  AND keys.product_line = s.product_line
  AND keys.sale_date = s.sale_date;

The final select uses coalesce to turn NULL into zero where there was no actual sales data. I then use a common table expression to get the first and last day of sales, which is fed into generate_series to produce every day between those dates.

That gives us every day, but we still need to pair that up with store locations and categories. This is where the reclusive, rarely seen CROSS JOIN comes into play. If you've never seen one, it's equivalent to writing a JOIN with an ON clause of 1=1 or true, which gives us every possible combination.

Now that we have every combination, we can LEFT JOIN to the sales data. I'm using a LEFT JOIN because I want a row even where there was no matching sale.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.

What database do you use?

zchtodd — Wed, 09 Oct 2019 01:01:05 +0000

I'm curious what databases people are using for their projects, and why you might have decided on that.

I'll list some of the databases I've used and my experiences with them.

PostgreSQL

I'm using PostgreSQL for a Python project, alongside SQLAlchemy as the ORM. The data model for the project is fairly complex, so it's been good to have SQL for the flexibility.

One downside so far has been that some of the queries have gotten pretty gnarly, and modifying them can feel like moving blocks in a Jenga tower.

Performance can also be a little unpredictable. For instance, one query either took ~400ms or 20 seconds to execute. In that case, the query was executing immediately after a big insert, and the table statistics were out of date, causing the planner to generate a really poor plan.

Issuing an ANALYZE command refreshed the table stats, and the planner started producing the 400ms version of the query. As far as I know, it's not possible to pin a query plan in PostgreSQL.

Cassandra

My experience with Cassandra was mixed. I think this was because the project was not well suited to an eventually consistent key-value store. The application developers spent a lot of time coming to terms with eventual consistency, lack of transactions, and the rigidity of the data model.

Cassandra can, however, support an amazingly high write through-put. If you don't need the flexibility of SQL, and a single machine can't support your demands, then Cassandra might be a viable option.

What are you using?

I'd love to hear what databases you're using, as well as the positives and negatives that come with them.

Building parsers for fun and profit with Pyparsing

zchtodd — Tue, 08 Oct 2019 21:17:27 +0000

I sometimes need to either create a domain specific language, or at least be able to parse a subset of some existing language. This can be incredibly useful.

Recently, I worked on an application in which users create filters that classify data. The filters are boolean expressions that are constructed using a friendly web interface, but power users can directly edit the filters as text. This direct editing mode, however, means that we’ll need to parse the text to perform validations and to understand what the user intends.

Parsing is a huge subject and can be an equally huge undertaking. Luckily, this is well trodden ground, and there’s no need to start from scratch. The pyparsing module is a powerful toolkit that takes care of the time consuming and error prone aspects of parsing, allowing you to get directly to the essence of what you’re trying to do.

In my case, what I’m trying to do is parse a simplified version of the SQL where clause.

Building anything with Pyparsing involves starting with the basic building blocks of your desired grammar. The basic elements of my simplified SQL grammar are numbers, strings, operators and identifiers (the actual variables or column names).

import pyparsing as pp

lparen = pp.Suppress("(")
rparen = pp.Suppress(")")

and_ = pp.Literal("AND")
or_ = pp.Literal("OR")

operator = pp.oneOf(("=", "!=", ">", ">=", "<", "<="))

alphaword = pp.Word(pp.alphanums + "_")
string = pp.QuotedString(quoteChar="'")

number = (
    pp.Word(pp.nums) + pp.Optional("." + pp.OneOrMore(pp.Word(pp.nums)))
)

identifier = alphaword

Pyparsing takes advantage of operator overloading in Python to make grammar construction compact and elegant. Each time two Pyparsing objects are combined they will form a new object that is immediately returned, thus allowing you to build up a grammar. Every object has a parseString method, meaning all the subsets of your grammar can be independently tested.

>>> number.parseString("1.32")
(['1', '.', '32'], {})

The default result of calling parseString is comparable to what you’d expect to see during the lexing or tokenizing phase of a compiler. This is a useful and necessary step in the parsing process, but it leaves a ton of work for us to do.

At the end of the day, I need to understand the structure of the filter expression, which is best represented as a tree.

The setParseAction method is what you’ll need if you want to encode the structure of a grammar into a tree. The setParseAction method accepts any callable object, meaning you can pass functions or class objects. As your various subgrammars are encountered in an input, Pyparsing will invoke your setParseAction callables, with the results being passed into higher level grammar constructs.

Let’s look again at the last example:

class String(object):
    def __init__(self, result):
        self.value = result[0]

    def generate(self):
        return "'{}'".format(self.value)

class Number(object):
    def __init__(self, result):
        self.value = result[0]

    def generate(self):
        return self.value

class Identifier(object):
    def __init__(self, result):
        self.name = result[0]

    def generate(self):
        return self.name

class Condition(object):
    def __init__(self, tokens):
        self.identifier = tokens[0][0]
        self.op = tokens[0][1]
        self.rval = tokens[0][2]

    def generate(self):
        return " ".join((self.identifier.generate(), self.op, self.rval.generate()))

lparen = pp.Suppress("(")
rparen = pp.Suppress(")")

and_ = pp.Literal("AND")
or_ = pp.Literal("OR")

operator = pp.oneOf(("=", "!=", ">", ">=", "<", "<="))

alphaword = pp.Word(pp.alphanums + "_")
string = pp.QuotedString(quoteChar="'").setParseAction(String)

number = (
 pp.Word(pp.nums) + pp.Optional("." + pp.OneOrMore(pp.Word(pp.nums)))
).setParseAction(Number)

identifier = alphaword.setParseAction(
 Identifier
)

condition = pp.Group(
 identifier + (operator + (string | number))
).setParseAction(Condition)

If we try parsing a test string again, we’ll see that the result is returned in terms of the classes defined above, instead of as a string that has been tokenized.

>>> result = condition.parseString("x = 4")
>>> result[0].identifier
<test.Identifier object at 0x7f327b9ed240>
>>> result[0].op
'='
>>> result[0].rval
<test.Number object at 0x7f327b9ed320>

The AND/OR part of the grammar is where things could start to become a little tricky, but it’s also where Pyparsing really shines. Up to this point, the grammar has been very simple. When we introduce AND/OR to this grammar, two important things have happened: the grammar now has operator precedence, and has also become recursive.

If you’re familiar with SQL you probably know that AND has higher precedence than OR, just as multiplication has higher precedence than addition. We’ll have to be careful how we construct our grammar so that operator precedence is encoded properly.

Let’s take a look at how to add operator precedence and nested expression parsing to this grammar:

class Expression(object):
    def __init__(self, tokens):
        self.and_conditions = tokens[::2]

    def generate(self):
        return (
            "("
            + " OR ".join(
                (and_condition.generate() for and_condition in self.and_conditions)
            )
            + ")"
        )

class AndCondition(object):
    def __init__(self, tokens):
        self.conditions = tokens[::2]

    def generate(self):
        result = " AND ".join((condition.generate() for condition in self.conditions))
        if len(self.conditions) > 1:
            result = "(" + result + ")"
        return result

class Condition(object):
    def __init__(self, tokens):
        self.identifier = tokens[0][0]
        self.op = tokens[0][1]
        self.rval = tokens[0][2]

    def generate(self):
        return " ".join((self.identifier.generate(), self.op, self.rval.generate()))

class String(object):
    def __init__(self, result):
        self.value = result[0]

    def generate(self):
        return "'{}'".format(self.value)

class Number(object):
    def __init__(self, result):
        self.value = result[0]

    def generate(self):
        return self.value

class Identifier(object):
    def __init__(self, result):
        self.name = result[0]

    def generate(self):
        return self.name

lparen = pp.Suppress("(")
rparen = pp.Suppress(")")

and_ = pp.Literal("AND")
or_ = pp.Literal("OR")

operator = pp.oneOf(("=", "!=", ">", ">=", "<", "<="))

alphaword = pp.Word(pp.alphanums + "_")
string = pp.QuotedString(quoteChar="'").setParseAction(String)

number = (
 pp.Word(pp.nums) + pp.Optional("." + pp.OneOrMore(pp.Word(pp.nums)))
).setParseAction(Number)

identifier = alphaword.setParseAction(
 Identifier
)

expr = pp.Forward()

condition = pp.Group(
 identifier + (operator + (string | number))
).setParseAction(Condition)

condition = condition | (lparen + expr + rparen)

and_condition = (condition + pp.ZeroOrMore(and_ + condition)).setParseAction(
 AndCondition
)

expr << (and_condition + pp.ZeroOrMore(or_ + and_condition))
expr = expr.setParseAction(Expression)

It can be helpful to plan out a grammar in terms of something like Backus Naur form before committing it to code. Sketching out this simplified SQL grammar, I came up with the following:

# OP := = | != | > | < | <= | >=
# CONDITION := <word> <op> <number> | (<expression>)
# AND_CONDITION := <condition> | <condition> AND <condition>
# EXPRESSION := <and_condition> | <and_condition> OR <and_condition>

The proper precedence is taken care of because the tree formed by our grammar places OR at a higher level, forcing AND conditions to be resolved first. You might also have noticed that conditions can contain expressions, while conditions are themselves part of expressions. This is a circular dependency, but is also required if we’re going to make nested expressions possible.

Luckily, Pyparsing provides the Forward class for just such cases, allowing us to use part of our grammar before we’ve actually defined it.

Now that we can parse this grammar, what can we do from here? As just one example, I’ve added generate methods to each component class that will produce a string representing that part of the tree. This will produce almost an exact replica of the input string, but in the AndCondition I’ve modified things slightly so that AND’d conditions are grouped together within parentheses in the output.

This is a simple example of the kinds of transformations you can do once you’re able to parse a grammar. Of course, you could also perform all kinds of validations, or even execute the logic itself.

Hopefully you’ve enjoyed this brief intro to Pyparsing. I may do more tutorials or examples in the future, because parsing is a pretty fun subject.