Philadelphia Software Developer

Tuning SQL queries is a useful skill, and while many people struggle to manage complex SQL, the work is actually a series of simple tricks.

For instance, refactoring a query often brings about algorithmic improvements, and if you tune enough queries, finding mathematically equivalent forms becomes muscle memory. This includes operations like inlining common table expressions, and knowing how to apply factoring (which you may need to try to remember from grade school).

When applying these operations, a few defects arise regularly. Consider the following:

SELECT 'Gary' AS customerName, '321 Street' AS customerAddress
UNION ALL
SELECT '111 Road' AS customerAddress, 'Bob' AS customerName

This is a valid query in Postgres – while it does type checking on each set in the union, it does not force you to name the columns the same.

This may look contrived, but it’s easier to make these happen in larger queries (e.g. long select lists)- the key point to understand is how easy it is to create subtle bugs.

Fortunately databases permit us to treat tables as sets, which allows you do do something like the following (note this assumes you have a unique key)

WITH a AS (
  ... BEFORE ...
), b AS (
  ... after ...
) 
SELECT COUNT(*) FROM a
UNION ALL
SELECT COUNT(*) FROM b
UNION ALL
SELECT * FROM (
   SELECT * FROM a 
   UNION
   SELECT * FROM b
)

The “union” causes the inputs to be treated as sets, so they will be de-duplicated, whereas “union all” treats the inputs as a list, which forces the ordering.

For this query, you expect to see the count(*) to be the same from the “before”, “after” and combined sets.

To see the difference in rows, you can also do set differences:

WITH a AS (
  ... BEFORE ...
), b AS (
  ... after ...
) 
SELECT * FROM a EXCEPT SELECT * FROM b
UNION 
SELECT * FROM b EXCEPT SELECT * FROM a

And this will show you every row that is unique to either before or after – if this returns no results, you’ve left the query the same. If you have a lot of data, this can take some time to run, although it is typically far less than manual testing, but if you wish, you can add an equivalent where clause to the before and after queries.

Ideally you should test this on a copy of production data. There are still classes of problems you could miss – but at least you know no one will be able to find them (yet).

There is one more problem:

Lets say you swapped two columns, as in my original example. The set difference query will give you all the rows in each query. If you start with 100k rows, now you have 200k, and how are you supposed to figure that out?

It turns out to be pretty simple:

WITH a AS (
  ... BEFORE ...
), b AS (
  ... after ...
) 
SELECT * FROM a EXCEPT SELECT * FROM b WHERE id = 12345
UNION 
SELECT * FROM b EXCEPT SELECT * FROM a WHERE id = 12345

Find one that might be of interest, then apply your unique identifier. Now, you have two rows:

Then scroll across the result until you spot the difference:

This works well, whether you have dozens or hundreds of columns.

This is a very simple manual workflow, requiring no special tools- while I’ve used Postgres, it should work essentially the same in any relational database. If you don’t work in this style, it will save you tons of testing time, re-opened tickets, and remove the fear of changing areas of your product. As a developer, it can take you from the point where you struggle with “large” queries to where the size doesn’t matter.

Stanford NLP is a library for text manipulation, which can parse and tokenize natural language texts. Typically applications which operate on text first split the text into words, then annotate the words with their part of speech, using a combination of heuristics and statistical rules. Other operations on the text build upon these results with the same techniques (heuristics and statistical algorithms on earlier data), which results in a pipeline model.

Here, for instance, we see two techniques for constructing a pipeline, one based on configuration, and one manual. Since this example is going to extract dates and times from text, we add the TimeAnnotator class to the end of the pipeline:

object Main {
  def main (args: Array[String]) {
    val props = new Properties();
    props.put("annotators", "tokenize, ssplit, pos, lemma, ner, parse, dcoref");
 
    val pipeline = new StanfordCoreNLP(props);
 
    val timeAnnotator = new TimeAnnotator()
    pipeline.addAnnotator(timeAnnotator)
 
    ...
  }
}

Once this is working, you simply tell the pipeline to annotate the text, and then wait for a bit.

val text =
  "Last summer, they met every Tuesday afternoon, from 1:00 pm to 3:00 pm."
val doc = new Annotation(text)
pipeline.annotate(doc)

The reason this takes time is that doing the actual work loads a handful of files from disk and works with them, and while they are small, they have large numbers of pre-defined rules. Consider the following sample, which is a small piece of the time matching piece of the library (there are around a thousand lines of this sort of thing).

 BASIC_NUMBER_MAP = {
    "one": 1,
    "two": 2,
    "three": 3,
    ...
 }
 
BASIC_ORDINAL_MAP = {
  "first": 1,
  "second": 2,
  "third": 3,
  ...
}
 
PERIODIC_SET = {
  "centennial": TemporalCompose(MULTIPLY, YEARLY, 100),
  "yearly": YEARLY,
  "annually": YEARLY,
  "annual": YEARLY,
  ...
}

This sample demonstrates two things – you can pull out more than just exact times (e.g. “last summer”, “next century”, ranges, times without dates), and the library handles a large number of equivalence classes for you.

One of the most likely issues you’ll run into trying to get this working is getting the classpath and parsing pipeline set up right – while simple to look at, if you try to customize it, you’ll need to develop an understanding of how the library is actually structured.

Once you run it, you can get dates out:

    val timexAnnotations = doc.get(classOf[TimeAnnotations.TimexAnnotations])
    for (timexAnn <- timexAnnotations) {
      val timeExpr = timexAnn.get(classOf[TimeExpression.Annotation])
      val temporal = timeExpr.getTemporal()
      val range = temporal.getRange()
 
      println(temporal)
      println(range)
    }

For the above example, this gives you the following (note alternating “temporal” and “range”). Note the “offset” lines as well – you can set a reference date for these, if you wish, so that

XXXX-SU OFFSET P-1Y
(XXXX-SU OFFSET P-1Y,XXXX-SU OFFSET P-1Y,)
XXXX-WXX-2TAF
null
T13:00
(T13:00:00.000,T13:00:59.999,PT1M)
T15:00
(T15:00:00.000,T15:00:59.999,PT1M)

If you add the following line, these ranges will fix themselves:

doc.set(classOf[CoreAnnotations.DocDateAnnotation], "2013-07-14")

Which gives you:

2012-SU
(2012-06-01,2012-09,P3M)

One thing I haven’t figured out yet is whether you scan specify locale settings for this – presumably in parsing dates, you at least want to know which of month/day are intended to be first, even if you treat the text as English as a whole (that said, this may require first identifying a language and building a different pipeline – e.g. if the library can’t handle French, Spanish, etc, being able to handle their dates is irrelevant).

For more examples, and information on customizing this, see the Stanford NLP documentation.

The following error:

Exception in thread "main" java.lang.RuntimeException: Error parsing file: edu/stanford/nlp/models/sutime/defs.sutime.txt

Is caused by using the Stanford NLP jars, but not the entire project on the classpath. To fix it, you want to download the “full” distribution and add that folder to the classpath.

I’ve written previously about the mechanics of building decision trees: extract data from some system, build a model on it, then save the model in a file for later:

Once you get that far, you’ll likely find that you want to try different models or change the parameters on the ones you’re using.

Ideally, you want to write code like this, which runs several different experiments in sequence, saving the results to a file:

args = {'criterion': 'entropy', 'max_depth': 5, 'min_samples_split': 10}
createModels(treeParams=args, folds = 3)
 
args = {'criterion': 'entropy', 'max_depth': 10, 'min_samples_split': 10}
createModels(treeParams=args, folds = 3)
 
args = {'criterion': 'entropy', 'max_depth': 15, 'min_samples_split': 10}
createModels(treeParams=args, folds = 3)

Once you start running experiments, you’ll get loads of files, so it’s important to name them based on what you’re running. Having saved off the results, you’ll be able to save models in source control and keep a permanent record of what experiments you ran.

Like unit tests, you can write out the results of accuracy tests as well, which lets you see how well you’re doing.

To make the filing system clear, the key is to take a python dictionary and turn it into a file name. With that in hand, we convert the model to JSON, and write it and the test results to a file.

def save(trees, features, args):
  print "Saving..."
  idx = 0
  params = ""
  for k in sorted(args.keys()):
    params = params + k + "-" + str(args[k]) + " "
 
  for t, report in trees:
    f = open('D:\\projects\\tree\\tree ' + params + \
             " fold " + str(idx) + ".json", 'w')
    f.write(report)
    f.write(treeToJson(t, features))
    f.close()
    idx = idx + 1

When we define the createModels function, it forces us to define and extract what this model-building process requires – for instance, what database tables to pull data from, a function to extract the value we want to predict, and how many folds we want to run.

The database operation in particular can be pretty heavy (pulling hundreds of thousands of records into memory), so memoization is key here.

def createModels(treeParams = None, folds = None, _cache = {}):
  print "Creating models..."
 
  def f(a):
    if '>' in a:
      return 1
    else:
      return 0
 
  if len(_cache) == 0:
    _cache['data'], _cache['outputs'] = \
      extract('income_trn', f, 'category')
    _cache['intData'], _cache['features'] = \
      transform(_cache['data'],  _cache['outputs'])
 
  trees = runTests(_cache['intData'], _cache['outputs'], \
                   treeParams, folds)
  save(trees, _cache['features'], treeParams)

In any project where you reshape real data, you typically spend an inordinate amount of time on data transformations, and much less on fun steps like model training or performance tuning. This I’ve found true whether you do machine learning, data warehousing, or data migration projects.

Fortunately most commercial products and libraries that work in those areas provide utilities for common operations, and this is an area where scikit-learn really shines.

For instance, when we run tests we might train the model on 75% of the data, then validate it on 25% of the data. There are different strategies like this, but in this case I’d like to do that four times (each time removing a different 25% of the data). If I had to write the code to do that, it would be a pain – one more source of defects.

Scikit-learn, provide around a half dozen different implementations for splitting data, so if you run into a problem, chances are all you need to do is change which class you instantiate in the cross_validation package:

def runTests(intData, classify, treeParams, folds):
  print "Testing data..."
 
  rs = cross_validation.ShuffleSplit(len(intData), n_iter=folds,
    test_size=.25, random_state=0)
 
  foldNumber = 1
  trees = []
  for train_index, test_index in rs:
    print "Fold %s..." % (foldNumber)
    train_data = [intData[idx] for idx in train_index]
    test_data = [intData[idx] for idx in test_index]
 
    train_v = [classify[idx] for idx in train_index]
    test_v = [classify[idx] for idx in test_index]
 
    clf = tree.DecisionTreeClassifier(**treeParams)
    clf = clf.fit(train_data, train_v)
 
    predictions = [clf.predict(r)[0] for r in test_data]
    report = classification_report(test_v, predictions)
 
    trees.append( (clf, report) )
    foldNumber = foldNumber + 1
 
  return trees

Similarly, one of the painful parts of the tree implementation is figuring out how to use data that has both text and numeric attributes. This is a specific case of the general problem of transforming data, and scikit-learn has dozens of classes to help in this area.

def transform(measurements, classify):
  print "Transforming data..."
 
  vec = DictVectorizer()
  intData = vec.fit_transform(measurements).toarray()
  featureNames = vec.get_feature_names()
 
  return intData, featureNames

As a digression, there is an interesting technical problem that lies hidden under the surface of the API. Trees specifically require that you make all your rows of data arrays of numbers – while this is very frustrating when you come in with strings, this is by design and not by accident and the code below using DictVectorizer will transform the data as you need.

When I first began researching python for data analysis, I was doing a broad search for tools, products, and libraries that might replace parts of the SQL + Relational database ecosystem. This includes tools that fall under the NoSQL umbrella, like Cassandra, Hadoop, and Solr, but also some ETL and data wrangling tools, like R, SAS, Informatica, and python.

If someone specifically wanted to avoid SQL as a language, for instance, there are quite a few options: swap in a different database underneath, use an ORM library to not have to see SQL, or use some sort of in-memory structure.

The python ORM (sqlalchemy) is quite nice for the purposes used in this article, as we can trivially read an entire table into RAM, converting each row into a dictionary:

def extract(tableName, resultXForm, resultColumn):
  print "Loading from database..."
 
  from sqlalchemy import create_engine, MetaData, Table
  from sqlalchemy.sql import select
  engine = create_engine(
                "postgresql+pg8000://postgres:postgres@localhost/pacer",
                isolation_level="READ UNCOMMITTED"
            )
  conn = engine.connect()
  meta = MetaData()
 
  table = Table(tableName, meta, autoload=True, autoload_with=engine)
 
  def toDict(row, columns):
    return {columns[i]: x for i, x in enumerate(row) \
      if columns[i] != resultColumn}
 
  s = select([table])
  result = conn.execute(s)
 
  columns = [c.name for c in table.columns]
  resultIdx = columns.index(resultColumn)
 
  data = [[c for c in row] for row in result]
  split = [toDict(row, columns) for row in data]
  classes = [resultXForm(row[resultIdx]) for row in data]
  return (split, classes)

There’s lots of code out there that looks like this, and it’s kind of kludgy, because eventually you’ll have so much data you wish you could switch algorithms as it grows, while serializing infrequently used structures to disk…which is exactly what relational databases give you.

One of the key value points of the scientific python stack is NumPy, which bridges a part of that gap (if you read “NumPy Internals“, it sounds an awful lot like something out of a database textbook).

This internal storage, then, is the reason for the above mentioned issue with Trees: internally, they use a massive array of floats, using NumPy underneath, so that it can be really fast on large datasets.

And with that, with a little bit of effore, we have a script that is almost exactly two hundred lines of code, allowing us to harness hundreds of thousands of engineering and grad student hours to find patterns out in the world.

If you do the following:

[str(x) for x in data]

You’ll sometimes get this error:

UnicodeEncodeError: 'ascii' codec can't encode character u'\xe1' in position 8: ordinal not in range(128)

This indicates that you have non-ascii characters in the data, and should use a wider type. You can fix it by doing the following (alternately, you can do something like base64 encoding, although I’m not sure why you’d want to do that):

[unicode(x) for x in data]

If you do this:

from sklearn import preprocessing
lb = preprocessing.LabelBinarizer()
lb.fit(["a", 2])

You will get the following error:

ValueError: Mix of label input types (string and number)

When you mix numbers and strings, it’s unclear whether you are mixing different types of classes, or if you’re mixing continuous and non-continuous data. If the latter- you don’t want the LabelBinarizer to run on the continuous data, and you should remove it, then re-add to the data later. If the former, you can convert the integers to strings.

I’m running some tests on sklearn decision trees, and the lessons learned so far may be interesting.

I’ve put my measurement code at the end – I’m tracking % correct, number of tests that are positive, negative, and false positives and negatives.

• When running predictions, if you have a defect where you include the ‘answer’ column in the test columns, the above code gives you a division by zero, which is a good check.
• For my data, when I run with criterion=’entropy’ I get 2% increase in accuracy, but other people I talked to on twitter have had the opposite
• criterion=’entropy’ is noticeably slower than the default (‘gini’)
• The default decision tree settings create trees that are very deep (~20k nodes for ~100k data points)
• For my use case, I found that limiting the depth of trees and forcing each node to have a large number of samples (50-500) made much simpler trees with only a small decrease in accuracy.
• In forcing nodes to have more samples, the accuracy decreased ~0-5%, roughly along the range of how many samples were included at each node (50-500)
• I found that I needed to remove a lot of my database columns to get a meaningful result. For instance originally I had ID columns, which lets sklearn pick up data created in a certain time window (since the IDs are sequential) but I don’t think this is useful for what I want to do.
• You have to turn class based attribute values into integers (it appears to be using a numpy float class internally for performance reasons)
• SKLearn appears to only use range based rules. Combine this with the above and you get a lot of rules like “status > 1.5″
• The tree could conceivably generate equality conditions within the structure, although it’d be hard to tell (e.g. “status > 1.5″, “status < 2.5" would be equivalent to "status = 2" if status is an integer)
• I’m more interesting in discovering useful rules than in future predictions; it helps a lot to generate JSON
• Within the JSON, the “entropy” and “impurity” field shows you how clean the rule is (0 = good). The “value” field shows how many items fit the rule (small numbers are probably not useful, at least for me)

testsRun = 0 testsPassed = 0 testsFalseNegative = 0 testsFalsePositive = 0 testsPositive = 0 testsNegative = 0 for t in test: prediction = clf.predict(t)[0] if prediction == 0: testsNegative = testsNegative + 1 else: testsPositive = testsPositive + 1   if prediction == test_v[testsRun]: testsPassed = testsPassed + 1 else: if prediction == 0: testsFalseNegative = testsFalseNegative + 1 else: testsFalsePositive = testsFalsePositive + 1   testsRun = testsRun + 1   print "Percent Pass: {0}".format(100 * testsPassed / testsRun) print "Percent Positive: {0}".format(100 * testsPositive / testsRun) print "Percent Negative: {0}".format(100 * testsNegative / testsRun) print "Percent False positive: {0}".format(100 * testsFalseNegative / (testsFalsePositive + testsFalseNegative)) print "Percent False negative: {0}".format(100 * testsFalsePositive / (testsFalsePositive + testsFalseNegative))

SKLearn has a function to convert decision trees to “graphviz” (for rendering) but I find JSON more helpful, as you can read it more easily, as well as use it in web apps. The function below will give you JSON.

The reason this is necessary (vs the JSON.dumps) library is that the Decision Tree interfaces don’t support the interfaces the JSON library needs to run. Additionally, even if it did, the JSON library in python dies on very small floating point numbers, which is why it’s not used at all in my version.

 
def treeToJson(decision_tree, feature_names=None):
  from warnings import warn
 
  js = ""
 
  def node_to_str(tree, node_id, criterion):
    if not isinstance(criterion, sklearn.tree.tree.six.string_types):
      criterion = "impurity"
 
    value = tree.value[node_id]
    if tree.n_outputs == 1:
      value = value[0, :]
 
    jsonValue = ', '.join([str(x) for x in value])
 
    if tree.children_left[node_id] == sklearn.tree._tree.TREE_LEAF:
      return '"id": "%s", "criterion": "%s", "impurity": "%s", "samples": "%s", "value": [%s]' \
             % (node_id, 
                criterion,
                tree.impurity[node_id],
                tree.n_node_samples[node_id],
                jsonValue)
    else:
      if feature_names is not None:
        feature = feature_names[tree.feature[node_id]]
      else:
        feature = tree.feature[node_id]
 
      if "=" in feature:
        ruleType = "="
        ruleValue = "false"
      else:
        ruleType = "<="
        ruleValue = "%.4f" % tree.threshold[node_id]
 
      return '"id": "%s", "rule": "%s %s %s", "%s": "%s", "samples": "%s"' \
             % (node_id, 
                feature,
                ruleType,
                ruleValue,
                criterion,
                tree.impurity[node_id],
                tree.n_node_samples[node_id])
 
  def recurse(tree, node_id, criterion, parent=None, depth=0):
    tabs = "  " * depth
    js = ""
 
    left_child = tree.children_left[node_id]
    right_child = tree.children_right[node_id]
 
    js = js + "\n" + \
         tabs + "{\n" + \
         tabs + "  " + node_to_str(tree, node_id, criterion)
 
    if left_child != sklearn.tree._tree.TREE_LEAF:
      js = js + ",\n" + \
           tabs + '  "left": ' + \
           recurse(tree, \
                   left_child, \
                   criterion=criterion, \
                   parent=node_id, \
                   depth=depth + 1) + ",\n" + \
           tabs + '  "right": ' + \
           recurse(tree, \
                   right_child, \
                   criterion=criterion, \
                   parent=node_id,
                   depth=depth + 1)
 
    js = js + tabs + "\n" + \
         tabs + "}"
 
    return js
 
  if isinstance(decision_tree, sklearn.tree.tree.Tree):
    js = js + recurse(decision_tree, 0, criterion="impurity")
  else:
    js = js + recurse(decision_tree.tree_, 0, criterion=decision_tree.criterion)
 
  return js

SQL Alchemy makes it easy to get types out of the database:

from sqlalchemy import *
engine = create_engine(
                "postgresql+pg8000://postgres:postgres@localhost/postgres",
                isolation_level="READ UNCOMMITTED"
            )
c = engine.connect()
 
meta = MetaData()
 
t = Table('table', meta, autoload=True, autoload_with=engine, schema='test')
 
columns = [col for col in t.columns]

And then from there, you can filter the column list down to things you want.

 
import sqlalchemy.sql.sqltypes
 
def useColumn(c):
  if (type(c.type) is TIMESTAMP):
    return False
 
  if (type(c.type) is VARCHAR):
    if (c.type.length == 24):
      return False
 
  if (type(c.type) is DATE):
    return False
 
  if (c.name.startswith("internal_")):
    return False
 
  if (c.name == "dont_use_me"): 
    return False
 
  return True

For certain columns, SQL Alchemy will give you an object that is a database specific type (e.g. there is a Postgres namespace), but you can find the exact class name:

columns[0].type.__class__
 
...sqlalchemy.sql.sqltypes.INTEGER

The scikit-learn documentation has an argument to control how the decision tree algorithm splits nodes:

criterion : string, optional (default=”gini”)
The function to measure the quality of a split. 
Supported criteria are “gini” for the Gini impurity 
and “entropy” for the information gain.

It seems like something that could be important since this determines the formula used to partition your dataset at each point in the dataset.

Unfortunately the documentation tells you nothing about what you should use, other than trying each to see what happens, so here’s what I found (spoiler: it doesn’t appear to matter):

• Gini is intended for continuous attributes, and Entropy for attributes that occur in classes (e.g. colors
• “Gini” will tend to find the largest class, and “entropy” tends to find groups of classes that make up ~50% of the data((http://paginas.fe.up.pt/~ec/files_1011/week%2008%20-%20Decision%20Trees.pdf))
• “Gini” to minimize misclassification
• “Entropy” for exploratory analysis
• Some studies show this doesn’t matter – these differ less than 2% of the time
• Entropy may be a little slower to compute