Numbers everyone should know

Implications for bigish data

Lets imagine we have a 10 GB flat data file and that we want to select certain rows based on a given criteria. This requires a sequential read across the entire data set.

If we can store the file in memory:

• \(10~GB \times (250~\mu s / 1~MB) = 0.25\) seconds

If we have to access the file from disk:

• \(10~GB \times (30~ms / 1~MB) = 30\) seconds

This is just for reading data, if we make any modifications (writing) things are much worse.

Blocks

So usually possible to grow our disk storage to accommodate our data. However, memory is usually the limiting resource, and if we can’t fit everything into memory?

Create blocks - group rows based on similar attributes and read in multiple rows at a time. Optimal size will depend on the task and the properties of the disk.

Linear vs Binary Search

Even with blocks, any kind of subsetting of rows requires a linear search, which requires \(\mathcal{O}(N)\) accesses where \(N\) is the number of blocks.

We can do much better if we are careful about how we structure our data, specifically sorting some or all of the columns.

• Sorting is expensive, \(\mathcal{O}(N \log N)\), but it only needs to be done once.

• After sorting, we can use a binary search for any subsetting tasks (\(\mathcal{O}(\log N)\)).

• These sorted columns are known as indexes.

• Indexes require additional storage, but usually small enough to be kept in memory while blocks stay on disk.

and then?

This is just barely scratching the surface,

• Efficiency gains are not just for disk, access is access

• In general, trade off between storage and efficiency

• Reality is a lot more complicated for everything mentioned so far, lots of very smart people have spent a lot of time thinking about and implementing tools

• Different tasks with different requirements require different implementations and have different criteria for optimization

SQL

Structures Query Language is a special purpose language for interacting with (querying and modifying) these indexed tabular data structures.

• ANSI Standard but with some dialect divergence

• This functionality maps very closely (but not exactly) with the data manipulation verbs present in dplyr.

• We will see this mapping in more detail in a bit.

data

library(dplyr)
library(readr)
library(lubridate)
library(stringr)

nyc = read_csv("/data/nyc_parking/NYParkingViolations.csv")

##  |================================================================================| 100% 1713 MB
##   
##  Warning: 654437 parsing failures.
##   row                  col   expected actual
##  2647 Violation Legal Code an integer      T
##  3792 Violation Legal Code an integer      T
##  4001 Violation Legal Code an integer      T
##  4002 Violation Legal Code an integer      T
##  4003 Violation Legal Code an integer      T
##  .... .................... .......... ......
##  .See problems(...) for more details.

SQL Query

class(addr)

## [1] "tbl_sqlite" "tbl_sql"    "tbl"  

addr$query

##  <Query> SELECT "Issue Date" AS "Issue Date", "Issuing Agency" AS "Issuing Agency", "Violation Precinct" AS "Violation ##  Precinct", "House Number" AS "House Number", "Street Name" AS "Street Name"
##  FROM "nyc"
##  WHERE "Violation Precinct" >= 1.0 AND "Violation Precinct" <= 34.0
##  <SQLiteConnection>

Limitations

addr %>% mutate(address = paste(`House Number`, `Street Name`))

##  Source: sqlite 3.8.6 [/data/nyc_parking/NYParkingViolations.sqlite]
##  Error in sqliteSendQuery(con, statement, bind.data) : 
##    error in statement: no such function: PASTE

addr %>% summarize(mean = mean(`Violation Precinct`, na.rm=TRUE))

##  Error: na.rm not needed in SQL: NULL are always dropped

addr %>% summarize(mean = mean(`Violation Precinct`))

##  Source: sqlite 3.8.6 [/data/nyc_parking/NYParkingViolations.sqlite]
##  From: <derived table> [?? x 1]
##  
##        mean
##       (dbl)
##  1  16.0982
##  ..     ...

SQL Query

addr %>% group_by(`Issuing Agency`, `Violation Precinct`) %>% summarize(n=n()) %>% .$query

##  <Query> SELECT "Issuing Agency", "Violation Precinct", "n"
##  FROM (SELECT "Issuing Agency", "Violation Precinct", COUNT() AS "n"
##  FROM "nyc"
##  WHERE "Violation Precinct" >= 1.0 AND "Violation Precinct" <= 34.0
##  GROUP BY "Issuing Agency", "Violation Precinct") AS "zzz4"
##  <SQLiteConnection>

Laziness

dplyr uses lazy evaluation as much as possible, particularly when working with non-local backends.

• When building a query, we don’t want the entire table, often we want just enough to check if our query is working.

• Since we would prefer to run one complex query over many simple queries, laziness allows for verbs to be strung together.

• Therefore, by default dplyr

  • won’t connect and query the database until absolutely necessary (e.g. show output),

  • and unless explicitly told to, will only query a handful of rows to give a sense of what the result will look like

Creating Indexes

(db_index = src_sqlite("/data/nyc_parking/NYParkingViolations_index.sqlite", create = TRUE))

## src:  sqlite 3.8.6 [/data/nyc_parking/NYParkingViolations_index.sqlite]
## tbls:

nyc_index = copy_to(db_index, nyc, temporary = FALSE,
                    index = list(`Violation Precinct`))

The indexed database takes up more disk space:

cr173@gort [~]$ ls -lh /data/nyc_parking/*.sqlite

-rw-r--r-- 1 cr173 visitor 1.8G Mar 30 11:56 NYParkingViolations_index.sqlite
-rw-r--r-- 1 cr173 visitor 1.7G Mar 30 11:28 NYParkingViolations.sqlite

Timings for filtering precincts

system.time(nyc_sql %>% filter(`Violation Precinct` <= 34, `Violation Precinct` >= 1) %>% collect())

##    user  system elapsed 
##  30.630   3.279  34.009 

system.time(nyc_index %>% filter(`Violation Precinct` <= 34, `Violation Precinct` >= 1) %>% collect())

##    user  system elapsed 
##  32.207   3.197  35.395 

Timings for grouping

system.time(nyc_sql %>% group_by(`Violation Precinct`) %>% summarize(n=n()) %>% collect())

##     user  system elapsed 
##   21.184   2.829  24.007 

system.time(nyc_index %>% group_by(`Violation Precinct`) %>% summarize(n=n()) %>% collect())

##   user  system elapsed 
##  1.288   0.102   1.389 

DBI

Low level package for interfacing R with Database management systems (DBMS) that provides a common interface to achieve the following functionality:

• connect/disconnect from DBMS
• create and execute statements in the DBMS
• extract results/output from statements
• error/exception handling
• information (meta-data) from database objects
• transaction management (optional)

RSQLite

Provides the implementation necessary to use DBI to interface with SQLite databases.

library(RSQLite)

## Loading required package: DBI

con = dbConnect(RSQLite::SQLite(), ":memory:")
str(con)

## Formal class 'SQLiteConnection' [package "RSQLite"] with 5 slots
##   ..@ Id                 :<externalptr> 
##   ..@ dbname             : chr ":memory:"
##   ..@ loadable.extensions: logi TRUE
##   ..@ flags              : int 6
##   ..@ vfs                : chr ""

Removing Tables

dbWriteTable(con, "employs", employees)

## [1] TRUE

dbListTables(con)

## [1] "employees" "employs"

dbRemoveTable(con,"employs")

## [1] TRUE

dbListTables(con)

## [1] "employees"

Querying Tables

res = dbSendQuery(con, "SELECT * FROM employees")
dbFetch(res)

##    name             email salary       dept
## 1 Alice alice@company.com  52000 Accounting
## 2   Bob   bob@company.com  40000 Accounting
## 3 Carol carol@company.com  30000      Sales
## 4  Dave  dave@company.com  33000 Accounting
## 5   Eve   eve@company.com  44000      Sales
## 6 Frank  frank@comany.com  37000      Sales

dbClearResult(res)

## [1] TRUE

Closing the connection

dbDisconnect(con)

## [1] TRUE

Table information

The following is specific to SQLite

sqlite> .tables

employees

sqlite> .schema employees

CREATE TABLE employees 
( "name" TEXT,
    "email" TEXT,
    "salary" REAL,
    "dept" TEXT 
);

sqlite> .indices employees

SELECT Statements

sqlite> SELECT * FROM employees;

Alice|alice@company.com|52000.0|Accounting
Bob|bob@company.com|40000.0|Accounting
Carol|carol@company.com|30000.0|Sales
Dave|dave@company.com|33000.0|Accounting
Eve|eve@company.com|44000.0|Sales
Frank|frank@comany.com|37000.0|Sales

Pretty Output

We can make this table output a little nicer with some additonal SQLite options:

sqlite> .mode column
sqlite> .headers on

sqlite> SELECT * FROM employees;

name        email              salary      dept      
----------  -----------------  ----------  ----------
Alice       alice@company.com  52000.0     Accounting
Bob         bob@company.com    40000.0     Accounting
Carol       carol@company.com  30000.0     Sales     
Dave        dave@company.com   33000.0     Accounting
Eve         eve@company.com    44000.0     Sales     
Frank       frank@comany.com   37000.0     Sales  

select using SELECT

We can subset for certain columns (and rename them) using SELECT

sqlite> SELECT name AS first_name, salary FROM employees;

first_name  salary    
----------  ----------
Alice       52000.0   
Bob         40000.0   
Carol       30000.0   
Dave        33000.0   
Eve         44000.0   
Frank       37000.0  

arrange using ORDER BY

We can sort our results by adding ORDER BY to our SELECT statement

sqlite> SELECT name AS first_name, salary FROM employees ORDER BY salary;

first_name  salary    
----------  ----------
Carol       30000.0   
Dave        33000.0   
Frank       37000.0   
Bob         40000.0   
Eve         44000.0   
Alice       52000.0  

We can sort in the opposite order by adding DESC

SELECT name AS first_name, salary FROM employees ORDER BY salary DESC;

first_name  salary    
----------  ----------
Alice       52000.0   
Eve         44000.0   
Bob         40000.0   
Frank       37000.0   
Dave        33000.0   
Carol       30000.0  

filter via WHERE

We can filter rows by adding WHERE to our statements

sqlite> SELECT * FROM employees WHERE salary < 40000;

name        email              salary      dept      
----------  -----------------  ----------  ----------
Carol       carol@company.com  30000.0     Sales     
Dave        dave@company.com   33000.0     Accounting
Frank       frank@comany.com   37000.0     Sales  

sqlite> SELECT * FROM employees WHERE salary < 40000 AND dept = "Sales";

name        email              salary      dept      
----------  -----------------  ----------  ----------
Carol       carol@company.com  30000.0     Sales     
Frank       frank@comany.com   37000.0     Sales 

group_by via GROUP BY

We can create groups for the purpose of summarizing using GROUP BY. As with dplyr it is not terribly useful by itself.

sqlite> SELECT * FROM employees GROUP BY dept;

name        email             salary      dept      
----------  ----------------  ----------  ----------
Dave        dave@company.com  33000.0     Accounting
Frank       frank@comany.com  37000.0     Sales     

sqlite> SELECT dept, AVG(salary) AS mean_salary, COUNT(*) AS n FROM employees GROUP BY dept;

dept        mean_salary       n         
----------  ----------------  ----------
Accounting  41666.6666666667  3         
Sales       37000.0           3   

head via LIMIT

We can limit the number of rows we get by using LIMIT.

sqlite> SELECT * FROM employees LIMIT 3;

name        email              salary      dept      
----------  -----------------  ----------  ----------
Alice       alice@company.com  52000.0     Accounting
Bob         bob@company.com    40000.0     Accounting
Carol       carol@company.com  30000.0     Sales 

sqlite> SELECT * FROM employees ORDER BY name DESC LIMIT 3;

name        email             salary      dept      
----------  ----------------  ----------  ----------
Frank       frank@comany.com  37000.0     Sales     
Eve         eve@company.com   44000.0     Sales     
Dave        dave@company.com  33000.0     Accounting

Import CSV files

sqlite> .mode csv
sqlite> .import phone.csv phone
sqlite> .tables

employees  phone   

sqlite> .mode column
sqlite> SELECT * FROM phone;

name        phone       
----------  ------------
Bob         919 555-1111
Carol       919 555-2222
Eve         919 555-3333
Frank       919 555-4444

Inner Join

If you want SQLite to find the columns to merge on automatically then we prefix the join with NATURAL.

sqlite> SELECT * FROM employees NATURAL JOIN phone;

name        email            salary      dept        phone       
----------  ---------------  ----------  ----------  ------------
Bob         bob@company.com  40000.0     Accounting  919 555-1111
Carol       carol@company.c  30000.0     Sales       919 555-2222
Eve         eve@company.com  44000.0     Sales       919 555-3333
Frank       frank@comany.co  37000.0     Sales       919 555-4444

Inner Join - Explicit

sqlite> SELECT * FROM employees JOIN phone ON employees.name = phone.name;

name        email            salary      dept        name        phone       
----------  ---------------  ----------  ----------  ----------  ------------
Bob         bob@company.com  40000.0     Accounting  Bob         919 555-1111
Carol       carol@company.c  30000.0     Sales       Carol       919 555-2222
Eve         eve@company.com  44000.0     Sales       Eve         919 555-3333
Frank       frank@comany.co  37000.0     Sales       Frank       919 555-4444

Left Join - Natural

sqlite> SELECT * FROM employees NATURAL LEFT JOIN phone;

name        email              salary      dept        phone     
----------  -----------------  ----------  ----------  ----------
Alice       alice@company.com  52000.0     Accounting            
Bob         bob@company.com    40000.0     Accounting  919 555-11
Carol       carol@company.com  30000.0     Sales       919 555-22
Dave        dave@company.com   33000.0     Accounting            
Eve         eve@company.com    44000.0     Sales       919 555-33
Frank       frank@comany.com   37000.0     Sales       919 555-44

Left Join - Explicit

sqlite> SELECT * FROM employees LEFT JOIN phone ON employees.name = phone.name;

name        email              salary      dept        name        phone     
----------  -----------------  ----------  ----------  ----------  ----------
Alice       alice@company.com  52000.0     Accounting                        
Bob         bob@company.com    40000.0     Accounting  Bob         919 555-11
Carol       carol@company.com  30000.0     Sales       Carol       919 555-22
Dave        dave@company.com   33000.0     Accounting                        
Eve         eve@company.com    44000.0     Sales       Eve         919 555-33
Frank       frank@comany.com   37000.0     Sales       Frank       919 555-44

Other Joins

Currently SQLite does not support RIGHT JOIN or OUTER JOIN.

Creating an index

sqlite> CREATE INDEX index_name ON employees (name);
sqlite> .indices

index_name

sqlite> CREATE INDEX index_name_email ON employees (name,email);
sqlite> .indices

index_name
index_name_email

Excercise - Stupid SQL Tricks

Lets try to create a table that has a new column - abv_avg which contains how much more (or less) than the average, for their department, each person is paid.

Hint - This will require joining a subquery.

employees.sqlite is available in /data/Sta523 on gort.

Acknowledgments

Above materials are derived in part from the following sources:

• dplyr - Introduction Vignette
• dplyr - Databases Vignette