Oversolving

First attempt at trigram similarity function in BigQuery

2020-07-01T00:00:00+00:00

Here’s my first attempt at trigram matching in Google BigQuery:

CREATE TEMP FUNCTION trigram_similarity(a STRING, b STRING) AS (
  (
    WITH a_trigrams AS (
      SELECT
        DISTINCT tri_a
      FROM
        unnest(ML.NGRAMS(SPLIT(LOWER(a), ''), [3,3])) AS tri_a
    ),
    b_trigrams AS (
      SELECT
        DISTINCT tri_b
      FROM
        unnest(ML.NGRAMS(SPLIT(LOWER(b), ''), [3,3])) AS tri_b
    )
    SELECT
      COUNTIF(tri_b IS NOT NULL) / COUNT(*)
    FROM
      a_trigrams
      LEFT JOIN b_trigrams ON tri_a = tri_b
  )
);

I compared it to Postgres’s pg_trgm and it got similar results, but I must be missing something:

select trigram_similarity('saemus', 'seamus');
-- 0.25 vs. pg_trgm 0.272727

select trigram_similarity('shamus', 'seamus');
-- 0.5 vs. pg_trgm 0.4

I’ll update this if/when I figure out how to make it match pg_trgm, which is the gold standard. I already did that in Ruby pg_trgm gem.

Why are universities teaching this stuff? Stata, Java, no SQL...

2020-06-12T00:00:00+00:00

I’m the CTO at Faraday, where we do a lot of hard programming. I’ve been looking resumes of current and recently graduated students from really good universities like Middlebury and also scanning the current syllabus of COS 333 Advanced Programming Techniques, the advanced programming class at Princeton. Here’s what I’m finding.

Not enough SQL

How do you graduate somebody in a STEM degree without teaching them SQL? It should be an absolute requirement for CS majors, and arguably for many sister disciplines. Here I quote from an interview with the late great Jim Gray:

Frana: So who were the great populizers and the proselytizers for the relational model? Ted? Chris Date? Yourself?

Gray: […] What happened is that the academic community found DBTG and IMS pretty complicated […] And along came the relational model with query optimization, and transactions, and security. The data model was simple enough that you could state it and then start reasoning about it. […] There began to be academic departments, and those departments started producing students. Some of those students went off to form other departments, and some went to industry. It was a self-reinforcing system.

The reason we have excellent systems like Google BigQuery and Postgres is because SQL is theoretically interesting. OK, maybe all the necessary theorems have been proved, so it can’t be an advanced course for the go-getters, but maybe that’s a good thing. Just please graduate people who know SQL.

Too much Java

Why are universities still teaching Java? It forms the core of COS 333 Advanced Programming Techniques. Java teaches you

no memory management
little functional programming

As a student, if you want to pick up a hot new language like Rust, this is the double whammy - you just won’t understand. Java should be an elective for people who want to work in Java shops.

How about just follow MIT’s example and have students start in Python like 6.0001 Introduction to Computer Science and Programming in Python and then teach Lisp, again just like MIT’s 6.009 Fundementals of Programming? I can tell you that I would be very impressed to hear about this and see its results in code interviews.

Why would you ever teach proprietary software like Stata?

Often I see resumes that list Stata or ESRI GIS products front and center. Matlab appears a lot too. That’s fine, I think government statisticians and city planners and professional engineers really use these proprietary products in their places of work. But that is a terrible reason to start students on a proprietary system when such excellent open alternatives exist and in some cases are superseding their proprietary peers. Some examples:

Why teach Stata when you could teach R? I would be very impressed if an intern could talk to me about tidyverse.
Why teach ArcGIS when you could use Postgis and QGIS? Postgis is deployed across all of the major cloud databases (AWS RDS Postgres, AWS Aurora Postgres, Azure Postgres, GCP Cloud SQL Postgres, Azure Hyperscale (formerly Citus Data)) and you can use very similar ST_ method calls in Google BigQuery GIS.

Matlab gets a pass because Octave is really just free Matlab… in any work environment, I’m guessing you would get the real thing.

Conclusion

Universities pick a bizarre set of technologies that don’t reflect the modern world, or even respect the academic traditions that brought us wonderful things like SQL. As an employer, I wish I saw more candidates with these three basic qualities:

SQL
Experience in a language other than Java
R / Postgis / choose any one speciality in open software

Thank you! Omg.

[out of date, wrong] How to stream HTTPS in chunks with Ruby's Net::HTTP

2014-07-14T00:00:00+00:00

WARNING: This post is ancient and probably wrong.

Standard Net::HTTP usage pulled from the Ruby 1.9.3 docs for Net::HTTP:

require 'tmpdir'
require 'uri'
require 'net/http'

# works with either a query already in the URL or as a second argument
def download_to_tmp_path(url, query = nil)
  uri = URI(url)
  tmp_path = File.join Dir.mktmpdir(uri.to_s.gsub(/\W/, '_')), "out"
  if query
    uri.query = URI.encode_www_form query
  end
  Net::HTTP.start(uri.host, uri.port, :use_ssl => (uri.scheme == 'https')) do |http|
    request = Net::HTTP::Get.new uri.request_uri
    http.request request do |response|
      File.open tmp_path, 'w' do |io|
        response.read_body do |chunk|
          io.write chunk
        end
      end
    end
  end
  tmp_path
end

so for example

puts "HTTP"
url = 'http://s3.amazonaws.com/creative.faraday.io/logo.png'
logo = download_to_tmp_path(url)
system 'file', logo

puts
puts "HTTPS"
url = 'https://s3.amazonaws.com/creative.faraday.io/logo.png'
logo = download_to_tmp_path(url)
system 'file', logo

puts
puts "Inline query"
url = 'https://s3.amazonaws.com/creative.faraday.io/logo.png?greeting=hello+world'
logo = download_to_tmp_path(url)
system 'file', logo

puts
puts "Query as hash"
url = 'https://s3.amazonaws.com/creative.faraday.io/logo.png'
query = { greeting: 'hello world' }
logo = download_to_tmp_path(url, query)
system 'file', logo

gives

HTTP
http://s3.amazonaws.com/creative.faraday.io/logo.png
/var/folders/cw/h96jw4sj6b19gvk9cnsy15h40000gp/T/http___s3_amazonaws_com_creative_faraday_io_logo_png20140714-4167-miomm3/out: PNG image data, 134 x 40, 8-bit/color RGBA, non-interlaced

HTTPS
https://s3.amazonaws.com/creative.faraday.io/logo.png
/var/folders/cw/h96jw4sj6b19gvk9cnsy15h40000gp/T/https___s3_amazonaws_com_creative_faraday_io_logo_png20140714-4167-ud6zhp/out: PNG image data, 134 x 40, 8-bit/color RGBA, non-interlaced

Inline query
https://s3.amazonaws.com/creative.faraday.io/logo.png?greeting=hello+world
/var/folders/cw/h96jw4sj6b19gvk9cnsy15h40000gp/T/https___s3_amazonaws_com_creative_faraday_io_logo_png_greeting_hello_world20140714-4167-143mn3q/out: PNG image data, 134 x 40, 8-bit/color RGBA, non-interlaced

Query as hash
https://s3.amazonaws.com/creative.faraday.io/logo.png
/var/folders/cw/h96jw4sj6b19gvk9cnsy15h40000gp/T/https___s3_amazonaws_com_creative_faraday_io_logo_png20140714-4167-79adl/out: PNG image data, 134 x 40, 8-bit/color RGBA, non-interlaced

[wrong] How to move a distance in meters away from a point in Ruby using RGeo

2014-07-10T00:00:00+00:00

WARNING: This post is ancient and wrong.

Here’s a method that lets you move/offset/translate a certain distance (in meters) away from a point expressed in longitude and latitude:

a = move_point(-72.4861, 44.1853, 0, 0)     # POINT (-72.4861 44.18529999999999)
b = move_point(-72.4861, 44.1853, 100, 0)   # POINT (-72.48520168471588 44.18529999999999)
c = move_point(-72.4861, 44.1853, 0, 100)   # POINT (-72.4861 44.18594416889434)
puts a.distance(b)
puts a.distance(c)

This gives you:

99.99999999906868
99.99999999906868

It uses the RGeo library. Note the argument order is longitude, latitude!

require 'rgeo'

def move_point(lon, lat, x_offset_meters, y_offset_meters)
  wgs84 = RGeo::Geographic.simple_mercator_factory.point(lon, lat)
  wgs84_factory = wgs84.factory
  webmercator = wgs84_factory.project wgs84
  webmercator_factory = webmercator.factory
  webmercator_moved = webmercator_factory.point(webmercator.x+x_offset_meters, webmercator.y+y_offset_meters)
  wgs84_factory.unproject webmercator_moved
end

[out of date] How to install RVM as an unprivileged user in Vagrant

2014-04-22T00:00:00+00:00

WARNING: This post is ancient and probably wrong.

The RVM installation instructions for Vagrant install RVM as root.

If you want to install it as an unprivileged user, namely vagrant, do this:

# http://rvm.io/integration/vagrant - edited to install for "vagrant" user only
config.vm.provision :shell, path: '/host/path/to/install-rvm.sh',  args: 'stable', privileged: false # changed
config.vm.provision :shell, path: '/host/path/to/install-ruby.sh', args: '2.1.1',  privileged: false # changed

You can use an unmodified install-rvm.sh:

#!/usr/bin/env bash

curl -sSL https://get.rvm.io | bash -s $1

You should modify install-ruby.sh to be:

#!/usr/bin/env bash

source /home/vagrant/.rvm/scripts/rvm # changed, used to be /usr/local/rvm/scripts/rvm

rvm use --default --install $1        # changed, used to not set --default

shift

if (( $# ))
  then gem install $@
fi

That’s it!

Array#include? is slow; use Set#include?

2014-02-25T00:00:00+00:00

Don’t use Array#include? as a lookup table. Set#include? is way faster.

Here’s an example where it’s 150X faster:

require 'benchmark/ips'
require 'set'

ary = []
5000.times { ary << rand.round(6) }
set = ary.to_set

Benchmark.ips do |x|
  x.report("Array#include?") { ary.include?(rand.round(6))}
  x.report("Set#include?")   { set.include?(rand.round(6))}
end

And the benchmarking results:

Calculating -------------------------------------
      Array#include?       374 i/100ms
        Set#include?     60669 i/100ms
-------------------------------------------------
      Array#include?     3780.7 (±1.1%) i/s -      19074 in   5.045665s
        Set#include?  2078044.8 (±3.5%) i/s -   10374399 in   5.000050s

How to convert a Zip9 or Zip4 to a Zip5 if you're missing leading zeros

2014-02-08T00:00:00+00:00

For when Excel turns 057531234 into 57531234.0 (drops leading zeros and treats it like a number) and you just want 05753.

Here’s the problem in the form of an acceptance test:

require 'minitest/autorun'

describe 'zip5 disambiguation' do
  {
    999501234  => '99950',
  '99950-1234' => '99950',
     57531234  => '05753',
   '5753-1234' => '05753',
  '05753-1234' => '05753',
      5011234  => '00501',
    99950      => '99950',
     5753      => '05753',
     1000      => '01000',
      501      => '00501',
  }.each do |input, expected|
    it "parses #{input.inspect} as #{expected.inspect}" do
      zip5(input).must_equal expected
    end
    # here we also test 57531234.0, etc.
    if input.is_a?(Integer)
      input_f = input.to_f
      it "parses #{input_f.inspect} as #{expected.inspect}" do
        zip5(input_f).must_equal expected
      end
    end
  end
end

Here’s a quick Ruby method to solve it:

def zip5(input)
  input = input.to_i.to_s.delete('-')
  zip5 = case input.length
  when 9
    input[0,5]
  when 8
    '0' + input[0,4]
  when 7
    '00' + input[0,3]
  when 5
    input
  when 4
    '0' + input
  when 3
    '00' + input
  else
    raise "can't derive zip5 from #{input.inspect}"
  end
  unless (501..99950).include?(zip5.to_i)
    $stderr.puts "warning: looks like a bad zip5 (expected 00500..99950): #{zip5}"
  end
  zip5
end

Works:

Run options: --seed 32751

## Running:

.................

Finished in 0.002172s, 7826.8877 runs/s, 7826.8877 assertions/s.

17 runs, 17 assertions, 0 failures, 0 errors, 0 skips

You could take the warning out if you want - technically 501..99950 is full range of zip codes.

Ruby to_i considered harmful - what to do instead

2013-12-18T00:00:00+00:00

I recommend using to_f.round instead of to_i any day of the week.

>> '1.5'.to_i
=> 1
>> '1.5'.to_f.round
=> 2   # arguably better

Even stronger evidence:

>> '1.5e3'.to_i
=> 1
>> '1.5e3'.to_f.round
=> 1500 # incontrovertibly better

I think a lot of Rubyists were introduced to to_i from DHH’s slug hack involving redefining Post#to_param ("15-hello-world".to_i #=> 15), but I just don’t see many other uses for to_i.

[out of date] Super easy way to dump HStore to CSV

2013-09-25T00:00:00+00:00

WARNING: This post is ancient and probably wrong.

As of today, neither pgAdmin nor PG Commander display hstore data nicely. Here’s a 5-line Ruby script to stick in ~/bin/hscv that dumps a hstore column to a CSV:

#!/usr/bin/env ruby
# Usage: hcsv DBNAME TBLNAME HSTORECOL 
# Output columns will be id + all the hstore keys

dbname, tblname, hstorecol = ARGV[0..2]

# Get hstore keys
out = `psql #{dbname} --tuples --command "SELECT DISTINCT k FROM (SELECT skeys(#{hstorecol}) AS k FROM #{tblname}) AS dt ORDER BY k"`
headers = out.split(/\n/).map(&:strip)

# Dump CSV of id + all hstore keys
hstore_headers_sql = headers.map { |k| %{#{hstorecol}->'#{k}' AS "#{k}"} }.join(', ')
system 'psql', dbname, '--tuples', '--command', "COPY (SELECT id, #{hstore_headers_sql} FROM #{tblname}) TO STDOUT (FORMAT 'csv', HEADER)"

{.wide}

So in your showoff database you have a pets table with an hstore column called d:

$ createdb showoff
$ psql showoff
psql (9.1.9)
Type "help" for help.

showoff=# CREATE EXTENSION hstore;
CREATE EXTENSION
showoff=# CREATE TABLE pets (id SERIAL, d HSTORE);
CREATE TABLE
showoff=# INSERT INTO pets (d) VALUES ('"name"=>"Jerry","breed"=>"beagle","age"=>"6"');
INSERT 0 1
showoff=# INSERT INTO pets (d) VALUES ('"name"=>"Amigo","breed"=>"lizard","age"=>"15"');
INSERT 0 1
showoff=# select * from pets;
 id |                        d                        
----+-------------------------------------------------
  2 | "age"=>"6", "name"=>"Jerry", "breed"=>"beagle"
  3 | "age"=>"15", "name"=>"Amigo", "breed"=>"lizard"
(2 rows)

{.wide}

Then you can do:

$ hcsv showoff pets d
id,age,breed,name
2,6,beagle,Jerry
3,15,lizard,Amigo

{.wide}

Hinting Postgres and MySQL with OFFSET and LIMIT

2013-03-29T00:00:00+00:00

If your database is behaving irrationally, try white diamonds.

“These have always brought me luck”. No, JK, but maybe LIMIT and OFFSET can be used creatively to solve your problem. Here are two examples.

tl;dr

Tell Postgres not to inline with OFFSET 0:

SELECT COUNT(*) FROM (
  SELECT * FROM tbl WHERE id IN ('6d48fc431d21', 'd9e659e756ad') OFFSET 0
) AS t WHERE data ? 'building_floorspace'

In MySQL 5.5, create an in-memory temporary table with LIMIT 0:

CREATE TEMPORARY TABLE flight_segment_cohort_78990172264
  ENGINE=MEMORY
  AS (SELECT * FROM `flight_segments` LIMIT 0)

Prevent SQL inlining in Postgres 9.x with `OFFSET 0`

Sometimes the Postgres query optimizer does silly things like applying a more complex condition before paying attention to primary keys: (4.5 seconds, even though I’ve explicitly provided the primary keys)

EXPLAIN ANALYZE SELECT COUNT(*) FROM tbl WHERE id IN ('6d48fc431d21', 'd9e659e756ad') AND data ? 'building_floorspace' AND data ?| ARRAY['elec_mean_monthly_use', 'gas_mean_monthly_use'];
                                                                     QUERY PLAN                                                                     
----------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=4.09..4.09 rows=1 width=0) (actual time=4457.886..4457.887 rows=1 loops=1)
   ->  Index Scan using idx_tbl_on_data_gist on tbl  (cost=0.00..4.09 rows=1 width=0) (actual time=4457.880..4457.880 rows=0 loops=1)
         Index Cond: ((data ? 'building_floorspace'::text) AND (data ?| '{elec_mean_monthly_use,gas_mean_monthly_use}'::text[]))
         Filter: ((id)::text = ANY ('{6d48fc431d21,d9e659e756ad}'::text[]))
 Total runtime: 4457.948 ms
(5 rows)

{.wide}

If you try a subselect and it doesn’t help, the problem is inlining: (still 4.5 seconds because the subselect is inlined and therefore the query is exactly the same as above)

EXPLAIN ANALYZE SELECT COUNT(*) FROM (  SELECT * FROM tbl WHERE id IN ('6d48fc431d21', 'd9e659e756ad')  ) AS t WHERE data ? 'building_floorspace' AND data ?| ARRAY['elec_mean_monthly_use', 'gas_mean_monthly_use'];
                                                                     QUERY PLAN                                                                     
----------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=4.09..4.09 rows=1 width=0) (actual time=4854.170..4854.171 rows=1 loops=1)
   ->  Index Scan using idx_tbl_on_data_gist on tbl  (cost=0.00..4.09 rows=1 width=0) (actual time=4854.165..4854.165 rows=0 loops=1)
         Index Cond: ((data ? 'building_floorspace'::text) AND (data ?| '{elec_mean_monthly_use,gas_mean_monthly_use}'::text[]))
         Filter: ((id)::text = ANY ('{6d48fc431d21,d9e659e756ad}'::text[]))
 Total runtime: 4854.220 ms
(5 rows)

Even though you’re not supposed to need hinting, there is a way to tell Postgres not to inline: (much faster - 0.223ms!)

EXPLAIN ANALYZE SELECT COUNT(*) FROM (  SELECT * FROM tbl WHERE id IN ('6d48fc431d21', 'd9e659e756ad') OFFSET 0 ) AS t WHERE data ? 'building_floorspace' AND data ?| ARRAY['elec_mean_monthly_use', 'gas_mean_monthly_use'];
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=8.14..8.15 rows=1 width=0) (actual time=0.165..0.166 rows=1 loops=1)
   ->  Subquery Scan on t  (cost=4.14..8.14 rows=1 width=0) (actual time=0.160..0.160 rows=0 loops=1)
         Filter: ((t.data ? 'building_floorspace'::text) AND (t.data ?| '{elec_mean_monthly_use,gas_mean_monthly_use}'::text[]))
         ->  Limit  (cost=4.14..8.13 rows=2 width=496) (actual time=0.086..0.092 rows=2 loops=1)
               ->  Bitmap Heap Scan on tbl  (cost=4.14..8.13 rows=2 width=496) (actual time=0.083..0.086 rows=2 loops=1)
                     Recheck Cond: ((id)::text = ANY ('{6d48fc431d21,d9e659e756ad}'::text[]))
                     ->  Bitmap Index Scan on tbl_pkey  (cost=0.00..4.14 rows=2 width=0) (actual time=0.068..0.068 rows=2 loops=1)
                           Index Cond: ((id)::text = ANY ('{6d48fc431d21,d9e659e756ad}'::text[]))
 Total runtime: 0.223 ms
(9 rows)

The trick is OFFSET 0 in the subquery.

Background: I have a Postgres 9.1 table using hstore and with a GiST index on it.

Make sure temporary tables are created in memory in MySQL 5.5+ with `LIMIT 0`

I upgraded to MySQL 5.5 (from 5.1) and suddenly my server started thrashing like crazy. In the logs:

(3278.3ms)   CREATE TEMPORARY TABLE flight_segment_cohort_70219108888 LIKE `flight_segments`

It turns out that in MySQL 5.5+ it’s easy to accidentally create InnoDB temp tables. What’s more, you can’t use ENGINE=MEMORY with LIKE.

(3.1ms)   CREATE TEMPORARY TABLE flight_segment_cohort_23148488864 ENGINE=MEMORY AS (SELECT * FROM `flight_segments` LIMIT 0)

The trick is replacing LIKE with AS (SELECT [...] LIMIT 0).

Background: the flight impact model (source code) uses temp tables to perform aggregations over a subset of rows that changes for almost every API call.

Oversolving

First attempt at trigram similarity function in BigQuery

Why are universities teaching this stuff? Stata, Java, no SQL...

Not enough SQL

Too much Java

Why would you ever teach proprietary software like Stata?

Conclusion

[out of date, wrong] How to stream HTTPS in chunks with Ruby's Net::HTTP

[wrong] How to move a distance in meters away from a point in Ruby using RGeo

[out of date] How to install RVM as an unprivileged user in Vagrant

Array#include? is slow; use Set#include?

How to convert a Zip9 or Zip4 to a Zip5 if you're missing leading zeros

Ruby to_i considered harmful - what to do instead

[out of date] Super easy way to dump HStore to CSV

Hinting Postgres and MySQL with OFFSET and LIMIT

tl;dr

Prevent SQL inlining in Postgres 9.x with OFFSET 0

Make sure temporary tables are created in memory in MySQL 5.5+ with LIMIT 0

Prevent SQL inlining in Postgres 9.x with `OFFSET 0`

Make sure temporary tables are created in memory in MySQL 5.5+ with `LIMIT 0`