Tuesday, June 29, 2010

mysql hack - altering huge tables

You have a huge mysql table - maybe 100 GB. And you need to run alter on it - to either add an index, drop an index, add a column or drop a column. If you run the simple mysql "alter table" command, you will end up spending ages to bring the table back into production.

Here is a simple hack to get the thing done. The benefit of the hack is that the alter runs quite fast. But since this is a hack, you will need to take care of the backups - in case anything goes wrong. I have seen this hack work effectively with both MyISAM and InnoDB tables.

Here i have created a simple table to show this hack process. You can assume that this table has billions of rows and is more than 100GB in size.

CREATE TABLE `testhack` (
`id` int(11) NOT NULL DEFAULT '0',
`unq` varchar(100) DEFAULT NULL,
`keyword` varchar(250) DEFAULT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `unq` (`unq`)
) ENGINE=MyISAM

I need to drop the unique key. So, i create a new table testhack_new with the following schema

CREATE TABLE `testhack_new` (
`id` int(11) NOT NULL DEFAULT '0',
`unq` varchar(100) DEFAULT NULL,
`keyword` varchar(250) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM

Flush both tables with read lock

mysql> Flush tables with read lock;

Open another terminal. And go to the mysql/data/<database> directory. Do the following:

mysql/data/test $ mv testhack.frm testhack_old.frm; mv testhack_new.frm testhack.frm; mv testhack_old.frm testhack_new.frm; mv testhack.MYI testhack_old.MYI; mv testhack_new.MYI testhack.MYI; mv testhack_old.MYI testhack_new.MYI;

So, what is happening here is that the index, table definitions are being switched. After this process, the table definition of testhack will not contain the unique key. Now unlock the tables in the main window. And run repair tables to remove any issues.

mysql> unlock tables;
mysql> repair tables testhack;
+---------------+--------+----------+-------------------------------------------+
| Table         | Op     | Msg_type | Msg_text                                  |
+---------------+--------+----------+-------------------------------------------+
| test.testhack | repair | warning  | Number of rows changed from 0 to 20000000 | 
| test.testhack | repair | status   | OK                                        | 
+---------------+--------+----------+-------------------------------------------+

The repair table rebuilds the indexes. It is faster since it skips the use of key_cache for rebuilding the index (which is used in a normal alter table scenario).

Tuesday, June 22, 2010

How Solar Power Works

What is solar energy ?

Solar energy is radiant energy which is produced by the sun. Each day the sun radiates, or sends out, an immense amount of energy. The sun radiates more energy in a second than people have used since the beginning of time!

The energy of the Sun originates from within the sun itself. Like other stars, the sun is mostly a big ball of gases––mostly hydrogen and helium atoms.

The hydrogen atoms in the sun’s core combine to form helium and generate energy in a process called nuclear fusion.

During nuclear fusion, the sun’s extremely high pressure and temperature cause hydrogen atoms to come apart and their nuclei (the central cores of the atoms) to fuse or combine. Four hydrogen nuclei fuse to become one helium atom. But the helium atom contains less mass compared to four hydrogen atoms that fused. Some matter is lost during nuclear fusion. The lost matter is emitted into space as radiant energy.

It requires many years for the energy in the sun’s core to make its way to the solar surface, after which just a little over eight minutes to travel the 93 million miles to earth. The solar energy travels to the earth at a speed of 186,000 miles per second, the velocity of light.

Simply a small percentage of the power radiated from the sun into space strikes our planet, one part in two billion. Yet this quantity of energy is enormous. Everyday enough energy strikes the usa to provide the nation’s energy needs for one and a half years!

Where does all this energy go?

About 15 percent of the sun’s energy that hits our planet is reflected back to space. Another 30 percent is used to evaporate water, which, lifted into the atmosphere, produces rainfall. Solar energy is also absorbed by plants, the land, and the oceans. The rest could be employed to supply our energy needs.

Who invented solar energy ?

Humans have harnessed solar power for centuries. As early as the 7th century B.C., people used simple magnifying glasses to concentrate the light of the sun into beams so hot they would cause wood to catch fire. More than a century ago in France, a scientist used heat from a solar collector to make steam to drive a steam engine. At first of this century, scientists and engineers began researching ways to use solar power in earnest. One important development was a remarkably efficient solar boiler introduced by Charles Greeley Abbott, a united states astrophysicist, in 1936.

The solar hot water heater gained popularity at this time in Florida, California, and the Southwest. The industry started in the early 1920s and was in full swing just before World War II. This growth lasted prior to the mid-1950s when low-cost propane took over as primary fuel for heating American homes.

The public and world governments remained largely indifferent to the possibilities of solar power before oil shortages of the1970s. Today, people use solar technology to heat buildings and water and also to generate electricity.

How we use solar power today ?

Solar energy can be used in several different ways, of course. There are 2 simple types of solar energy:

* Solar thermal energy collects the sun's warmth through 1 of 2 means: in water or in an anti-freeze (glycol) mixture.
* Solar photovoltaic energy converts the sun's radiation to usable electricity.

Listed below are the five most practical and popular ways that solar power can be used:

1. Small portable solar photovoltaic systems. We see these used everywhere, from calculators to solar garden tools. Portable units can be utilised for everything from RV appliances while single panel systems can be used traffic signs and remote monitoring stations.

2. Solar pool heating. Running water in direct circulation systems via a solar collector is a very practical method to heat water for your pool or hot spa.

3. Thermal glycol energy to heat water. In this method (indirect circulation), glycol is heated by sunshine and the heat is then transferred to water in a warm water tank. This process of collecting the sun's energy is more practical now than ever. In areas as far north as Edmonton, Alberta, solar thermal to heat water is economically sound. It can pay for itself in 3 years or less.

4. Integrating solar photovoltaic energy into your home or business power. In many parts on the planet, solar photovoltaics is an economically feasible approach to supplement the power of your home. In Japan, photovoltaics are competitive with other forms of power. In america alone, new incentive programs make this form of solar power ever more viable in many states. An increasingly popular and practical method of integrating solar energy into the power of your home or business is through the usage of building integrated solar photovoltaics.

5. Large independent photovoltaic systems. When you have enough sun power at your site, you may be able to go off grid. You may also integrate or hybridize your solar power system with wind power or other forms of renewable energy to stay 'off the grid.'

How do Photovoltaic panels work ?

Silicon is mounted beneath non-reflective glass to create photovoltaic panels. These panels collect photons from the sun, converting them into DC electrical energy. The power created then flows into an inverter. The inverter transforms the power into basic voltage and AC electric power.

Pv cells are prepared with particular materials called semiconductors such as silicon, which is presently the most generally used. When light hits the Photovoltaic cell, a specific share of it is absorbed inside the semiconductor material. This means that the energy of the absorbed light is given to the semiconductor.

The energy unfastens the electrons, permitting them to run freely. Solar power cells also have one or more electric fields that act to compel electrons unfastened by light absorption to flow in a specific direction. This flow of electrons is a current, and by introducing metal links on the top and bottom of the -Photovoltaic cell, the current can be drawn to use it externally.

Do you know the pros and cons of solar energy ?

Solar Pro Arguments

- Heating our homes with oil or gas or using electricity from power plants running with coal and oil is a reason for climate change and climate disruption. Solar energy, on the other hand, is clean and environmentally-friendly.

- Solar hot-water heaters require little maintenance, and their initial investment could be recovered within a relatively short time.

- Solar hot-water heaters can work in almost any climate, even just in very cold ones. You just have to choose the right system for your climate: drainback, thermosyphon, batch-ICS, etc.

- Maintenance costs of solar powered systems are minimal and the warranties large.

- Financial incentives (USA, Canada, European states…) can aid in eliminating the price of the initial investment in solar technologies. The U.S. government, for example, offers tax credits for solar systems certified by by the SRCC (Solar Rating and Certification Corporation), which amount to 30 percent of the investment (2009-2016 period).

Solar Cons Arguments

- The initial investment in Solar Water heaters or in Photovoltaic Electric Systems is greater than that required by conventional electric and gas heaters systems.

- The payback period of solar PV-electric systems is high, as well as those of solar space heating or solar cooling (only the solar domestic hot water heating payback is short or relatively short).

- Solar water heating do not support a direct combination with radiators (including baseboard ones).

- Some ac (solar space heating and the solar cooling systems) are expensive, and rather untested technologies: solar air-con isn't, till now, a really economical option.

- The efficiency of solar powered systems is rather influenced by sunlight resources. It's in colder climates, where heating or electricity needs are higher, that the efficiency is smaller.

About the writer - Barbara Young writes on RV solar power kits in her personal hobby web log 12voltsolarpanels.net. Her work is dedicated to helping people save energy using solar energy to reduce CO2 emissions and energy dependency.

Wednesday, June 16, 2010

Writing your first map-reduce program on hadoop

Before we go ahead with the actual program, lets have a look at what map-reduce is and its usage.

Map-Reduce is a programming model or concept which helps in implementing and processing large scale data sets. MapReduce model consists of two functions map() and reduce(). The map() function is applied to all input items in the input data set converting them to a set of key-value pairs. Multiple map jobs can be run in parallel over different processing nodes to process large data sets.

Map (K1, V1) = List (K2, V2).

The list of processed pairs (K2,V2) is collected by the MapReduce framework. All pairs with the same key are grouped together, creating one group for each one of the generated keys. The reduce function is then applied to each group in parallel to produce a collection of "similar" values.

Reduce (K2, List(V2)) = List (V3)

Since both map and reduce jobs can be run in parallel, they could be distributed over a large number of processing nodes to process large data sets.

Lets write a simple program to count the number of characters in each string using the MapReduce concept but without using any framework. Our program here would create some random strings and use MapReduce concept to distribute the task over a number of threads and eventually output the total number of characters.

// MyMapReduce.java
import java.util.*;

public class MyMapReduce
{
  List<List<String>> buckets = new ArrayList<List<String>>();
  List<String> intermediateresults = new ArrayList<String>();
  List<String> values = new ArrayList<String>();

  public void init()
  {
    for(int i = 1; i<=30; i++)
    {
      values.add("zyx" + new Integer(i).toString());
    }
    System.out.println("**Running Conversion into Buckets**\n");
    //convert the input data in smaller chunks. Here dividing 30 strings into chunks of 6 chunks of 5.
    List b = step1ConvertIntoBuckets(values,5);
    System.out.println("*DONE*\n");
    System.out.println("**Running #Map Function# concurrently for all Buckets\n");
    List res = step2RunMapFunctionForAllBuckets(b);
    System.out.println("*MAP Done*\n");
    System.out.println("**Running #Reduce Function# for collating Intermediate Results and Printing Results\n");
    step3RunReduceFunctionForAllBuckets(res);
    System.out.println("*REDUCE Done*\n");
  }
  public List step1ConvertIntoBuckets(List list,int numberofbuckets)
  {
    int n = list.size();
    int m = n / numberofbuckets;
    int rem = n% numberofbuckets;

    int count = 0;
    System.out.println("BUCKETS");
    for(int j =1; j<= numberofbuckets; j++)
    {
      List<String> temp = new ArrayList<String>();
      for(int i=1; i<= m; i++)
      {
        temp.add((String)values.get(count));
        count++;
      }
      buckets.add(temp);
      temp = new ArrayList<String>();
    }
    if(rem != 0)
    {
      List<String> temp = new ArrayList<String>();
      for(int i =1; i<=rem;i++)
      {
        temp.add((String)values.get(count));
        count++;
      }
      buckets.add(temp);
    }
    System.out.println(buckets);
    return buckets;
  }

  public List step2RunMapFunctionForAllBuckets(List list)
  {
    for(int i=0; i< list.size(); i++)
    {
      List<String> elementList = (ArrayList)list.get(i);
      new StartThread(elementList).start();
    }
    try
    {
      Thread.currentThread().sleep(1000);
    }catch(Exception e)
    {    }
    return intermediateresults;
  }

  public void step3RunReduceFunctionForAllBuckets(List list)
  {
    int sum =0;
    for(int i=0; i< list.size(); i++)
    {
      //you can do some processing here, like finding max of all results etc
      int t = Integer.parseInt((String)list.get(i));
      sum += t;
    }
    System.out.println("\nTotal Count is "+ sum+"\n");
  }

  class StartThread extends Thread
  {
    private List<String> tempList = new ArrayList<String>();
    public StartThread(List<String> list)
    {
      tempList = list;
    }
    public void run()
    {
      System.out.println("In Map...");
      for (String str : tempList)
      {
        synchronized(this)
        {
          intermediateresults.add(new Integer(str.length()).toString());
        }
      }
    }
  }
  public static void main(String[] args)
  {
    MyMapReduce my = new MyMapReduce();
    my.init();
  }
}

In this program, you have an arraylist of 30 strings. It is being divided into 5 batches of 6 strings. Each Batch is run in parallel in a thread and the processed information is collected in an intermediate arraylist. The reduce function is then called which loops through the intermediate arraylist and sums up the counts to output the information. Here only the Map function is being distributed over multiple threads. The reduce simply loops through the output of map and sums up the information.

Compile and run the program - output is :

$ java MyMapReduce 
**Running Conversion into Buckets**

BUCKETS
[[zyx1, zyx2, zyx3, zyx4, zyx5, zyx6], [zyx7, zyx8, zyx9, zyx10, zyx11, zyx12], [zyx13, zyx14, zyx15, zyx16, zyx17, zyx18], [zyx19, zyx20, zyx21, zyx22, zyx23, zyx24], [zyx25, zyx26, zyx27, zyx28, zyx29, zyx30]]
*DONE*

**Running #Map Function# concurrently for all Buckets

In Map...
In Map...
In Map...
In Map...
In Map...
*MAP Done*

**Running #Reduce Function# for collating Intermediate Results and Printing Results


Total Count is 141

*REDUCE Done*

A mapreduce framework like hadoop provides the distributed setup to run such mapreduce programs over a large number of processing nodes. It can automatically handle the spawning of processing threads and store the intermediatory information in some temporary file among its nodes.

Pre-requisite : setup hadoop on multiple nodes refer - http://jayant7k.blogspot.com/2008/10/setting-up-hadoop.html

Here is the same code written in the hadoop 0.20.1 map-reduce framework

import java.io.*;
import java.util.*;

import org.apache.hadoop.conf.*;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.*;
import org.apache.hadoop.mapreduce.*;
import org.apache.hadoop.util.*;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class WordCount extends Configured implements Tool {

  public static class MapClass extends Mapper<Object, Text, Text, IntWritable> {

    private final static IntWritable one = new IntWritable(1);
    private Text word = new Text();

    public void map(Object key, Text value, Context context) throws IOException, InterruptedException {
      String line = value.toString();
      StringTokenizer itr = new StringTokenizer(line);
      while (itr.hasMoreTokens()) {
        word.set(itr.nextToken());
        context.write(word, one);
      }
    }
  }

  /**
   * A reducer class that just emits the sum of the input values.
   */
  public static class Reduce extends Reducer<Text, IntWritable, Text, IntWritable> {

    public void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
      int sum = 0;
      for (IntWritable value : values) {
        sum += value.get();
      }
      context.write(key, new IntWritable(sum));
    }
  }

  static int printUsage() {
    System.out.println("wordcount [-r <reduces>] <input> <output>");
    ToolRunner.printGenericCommandUsage(System.out);
    return -1;
  }

  public int run(String[] args) throws Exception {
    Configuration conf = new Configuration();
    Job job = new Job(conf, "WordCount example for hadoop 0.20.1");

    job.setJarByClass(WordCount.class);
    job.setMapperClass(MapClass.class);
    job.setCombinerClass(Reduce.class);
    job.setReducerClass(Reduce.class);

    // the keys are words (strings)
    job.setOutputKeyClass(Text.class);
    // the values are counts (ints)
    job.setOutputValueClass(IntWritable.class);


    List<String> other_args = new ArrayList<String>();
    for(int i=0; i < args.length; ++i) {
      try {
        // The number of map tasks was earlier configurable, 
        // But with hadoop 0.20.1, it is decided by the framework.
        // Since this heavily depends on the input data size and how it is being split.
        if ("-r".equals(args[i])) {
          job.setNumReduceTasks(Integer.parseInt(args[++i]));
        } else {
          other_args.add(args[i]);
        }
      } catch (NumberFormatException except) {
        System.out.println("ERROR: Integer expected instead of " + args[i]);
        return printUsage();
      } catch (ArrayIndexOutOfBoundsException except) {
        System.out.println("ERROR: Required parameter missing from " +
            args[i-1]);
        return printUsage();
      }
    }
    // Make sure there are exactly 2 parameters left.
    if (other_args.size() != 2) {
      System.out.println("ERROR: Wrong number of parameters: " + other_args.size() + " instead of 2.");
      return printUsage();
    }
    FileInputFormat.addInputPath(job, new Path(other_args.get(0)));
    FileOutputFormat.setOutputPath(job, new Path(other_args.get(1)));

    //submit job and wait for completion. Also show output to user.
    job.waitForCompletion(true);
    return 0;
  }
  public static void main(String[] args) throws Exception {
    int res = ToolRunner.run(new Configuration(), new WordCount(), args);
    System.exit(res);
  }
}
Compile, create jar and run the file
$ javac -classpath ../hadoop-0.20.1/hadoop-0.20.1-core.jar -d wordcount_classes/ WordCount.java
$ jar -cvf wordcount.jar -C wordcount_classes/ .
$ cd ../hadoop-0.20.1
$ ./bin/hadoop jar ../progs/wordcount.jar WordCount -r 2 /user/hadoop/input /user/hadoop/output

10/06/16 17:00:47 WARN mapred.JobClient: Use GenericOptionsParser for parsing the arguments. Applications should implement Tool for the same.
10/06/16 17:00:48 INFO input.FileInputFormat: Total input paths to process : 2
10/06/16 17:00:48 INFO mapred.JobClient: Running job: job_201006141203_0008
10/06/16 17:00:49 INFO mapred.JobClient:  map 0% reduce 0%
10/06/16 17:00:58 INFO mapred.JobClient:  map 100% reduce 0%
10/06/16 17:01:10 INFO mapred.JobClient:  map 100% reduce 100%
10/06/16 17:01:12 INFO mapred.JobClient: Job complete: job_201006141203_0008
10/06/16 17:01:12 INFO mapred.JobClient: Counters: 17
10/06/16 17:01:12 INFO mapred.JobClient:   Job Counters 
10/06/16 17:01:12 INFO mapred.JobClient:     Launched reduce tasks=2
10/06/16 17:01:12 INFO mapred.JobClient:     Launched map tasks=2
10/06/16 17:01:12 INFO mapred.JobClient:     Data-local map tasks=2
10/06/16 17:01:12 INFO mapred.JobClient:   FileSystemCounters
10/06/16 17:01:12 INFO mapred.JobClient:     FILE_BYTES_READ=2009
10/06/16 17:01:12 INFO mapred.JobClient:     HDFS_BYTES_READ=1467
10/06/16 17:01:12 INFO mapred.JobClient:     FILE_BYTES_WRITTEN=4142
10/06/16 17:01:12 INFO mapred.JobClient:     HDFS_BYTES_WRITTEN=1356
10/06/16 17:01:12 INFO mapred.JobClient:   Map-Reduce Framework
10/06/16 17:01:12 INFO mapred.JobClient:     Reduce input groups=0
10/06/16 17:01:12 INFO mapred.JobClient:     Combine output records=142
10/06/16 17:01:12 INFO mapred.JobClient:     Map input records=33
10/06/16 17:01:12 INFO mapred.JobClient:     Reduce shuffle bytes=2021
10/06/16 17:01:12 INFO mapred.JobClient:     Reduce output records=0
10/06/16 17:01:12 INFO mapred.JobClient:     Spilled Records=284
10/06/16 17:01:12 INFO mapred.JobClient:     Map output bytes=2200
10/06/16 17:01:12 INFO mapred.JobClient:     Combine input records=190
10/06/16 17:01:12 INFO mapred.JobClient:     Map output records=190
10/06/16 17:01:12 INFO mapred.JobClient:     Reduce input records=142
Here is an explanation of the program

Configuration is the configuration which is replicated at all nodes in HDFS. All HDFS nodes run on their own JVM. JobTracker runs on master and accepts jobs from clients. It distributes the job into parts and sends the parts over to all the nodes via TaskTracker. taskTracker communicates with the jobtracker and keeps on asking for more job to run - as and when it finishes its task. Tasktracker can run multiple instances for multiple tasks. You set the mapper class and the reducer class in job.

job.setMapperClass();
job.setReducerClass();

You can also specify the input and output paths in the job

FileInputFormat.addInputPath(job, Path);
FileOutputFormat.setOutputPath(job, Path);

You can also set a number of other options in the Job.

job.setNumReduceTasks(); //set number of reduce tasks
job.setOutputFormat(); //set the output format

Job is submitted by calling either of.

job.submit(); //send the job to the cluster and return - non blocking
job.WaitForCompletion(); // send the job to the cluster and wait for its completion

Job determines the proper division of input into parts and sends job data to master jobtracker server. Tasktracker asks the jobtracker for its inputsplit data and the job to run. It calls mapper for each record received from the inputSplit. Mapper should extend the mapreduce.Mapper class which has code for some of the required functions of mapper. All mappers run separately on each node inside the tasktracker running on separate instances of jvm. There is no sharing of data. If you set a static variable in one mapper, you will not get its value in another mapper on another tasktracker.

Map(Object key, Object value, Context context)

To allow serialization and transfer of all types of data, java defines its own writable class. These box classes like Text (for String), IntWritable (for integers), LongWritable (for long) are instances of base class Writable (for values), and instances of WritableComparable (for Keys). Context is used to collect and write the ouput into intermediate as well as final files.

context.write() takes (Key,Value)

Partitioner is used to get the partition number for a given key. By default HashPartitioner is used which uses key.hashCode() to return the partition number. You can use job to specify custo
m partitioner.

Reducer(Object Key, Iterator Values, Context context)

Keys and values sent to one partition all go to the same reduce task. Reduce calls are sorted by key. Reducer sends the data to the recordwriter which writes the data to a output file.

Hadoop provides lots of flexibility to override the components and customize the input and output data.

HadoopStreaming can be used to interface the hadoop map-reduce framework with arbitary program code. It uses stdin and stdout for data flow. You can define a separate program for each of map
per and reducer in any language of your choice.

Monday, June 07, 2010

Innodb now supports native AIO on Linux

With the exception of Windows InnoDB has used ’simulated AIO’ on all other platforms to perform certain IO operations. The IO requests that have been performed in a ’simulated AIO’ way are the write requests and the readahead requests for the datafile pages. Let us first look at what does ’simulated AIO’ mean in this context.

We call it ’simulated AIO’ because it appears asynchronous from the context of a query thread but from the OS perspective the IO calls are still synchronous. The query thread simply queues the request in an array and then returns to the normal working. One of the IO helper thread, which is a background thread, then takes the request from the queue and issues a synchronous IO call (pread/pwrite) meaning it blocks on the IO call. Once it returns from the pread/pwrite call, this helper thread then calls the IO completion routine on the block in question which includes doing a merge of buffered operations, if any, in case of a read. In case of a write, the block is marked as ‘clean’ and is removed from the flush_list. Some other book keeping stuff also happens in IO completion routine.

What we have changed in the InnoDB Plugin 1.1 is to use the native AIO interface on Linux. Note that this feature requires that your system has libaio installed on it. libaio is a thin wrapper around the kernelized AIO on Linux. It is different from Posix AIO which requires user level threads to service AIO requests. There is a new boolean switch, innodb_use_native_aio, to choose between simulated or native AIO, the default being to use native AIO.

How does this change the design of the InnoDB IO subsystem? Now the query thread instead of enqueueing the IO request actually dispatches the request to the kernel and returns to the normal working. The IO helper thread, instead of picking up enqueued requests, waits on the IO wait events for any completed IO requests. As soon as it is notified by the kernel that a certain request has been completed it calls the IO completion routine on that request and then returns back to wait on the IO wait events. In this new design the IO requesting thread becomes kind of a dispatcher while the background IO thread takes on the role of a collector.

What will this buy us? The answer is simple – scalability. For example, consider a system which is heavily IO bound. In InnoDB one IO helper thread works on a maximum of 256 IO requests at one time. Assume that the heavy workload results in the queue being filled up. In simulated AIO the IO helper thread will go through these requests one by one making a synchronous call for each request. This means serialisation forcing the request that is serviced last to wait for the other 255 requests before it gets a chance. What this implies is that with simulated AIO there can be at most ‘n’ IO requests in parallel inside the kernel where ‘n’ is the total number of IO helper threads (this is not entirely true because query threads are also allowed to issue synchronous requests as well, but I’ll gloss over that detail for now). In case of native AIO all 256 requests are dispatched to the kernel and if the underlying OS can service more requests in parallel then we’ll take advantage of that.

The idea of coalescing contiguous requests is now off loaded to the kernel/IO scheduler. What this means is that which IO scheduler you are using or the properties of your RAID/disk controller may now have more affect on the overall IO performance. This is also true because now many more IO requests will be inside the kernel than before. Though we have not run tests to specifically certify any particular IO scheduler the conventional wisdom has been that for database engine workloads perhaps no-op or deadline scheduler would give optimal performance. I have heard that lately a lots of improvements have gone in cfq as well. It is for you to try and as always YMMV. And we look forward to hear your story.

NOTE:InnoDB h as always used native AIO on Windows and it continues to do so in Plugin 1.1. innodb_use_native_aio will have no affect on Windows.

Friday, June 04, 2010

Postgresql tuning - quick tips

The configuration file for postgresql is located in <postgresql_install_dir>/data/postgresql.conf

You can alter the following settings in the config for better performance of postgresql.

# listen to all ip addresses
listen_addresses = '*'

# should not exceed 1000. Req 400 bytes per connection
max_connections = 500

# used for managing connection, active operations
# should be 1/4 of the available memory

shared_buffers = 1024MB

# dedicated memory for each operation. Used basically for sorting
# should be available_memory/max_connections for normal operations. Max available_memory/(2*max_connections)
# another way of getting this number is using the EXPLAIN ANALYZE query. If the plan shows "sort method: external merge disk: 7532kb", then work_mem of 8Mb can do wonders.

work_mem = 1MB

# same as work_mem but for vaccum, alter, other ddl qry.
# should be around 256MB

maintenance_work_mem = 256MB

# size of write ahead log files
# default 8 KB. 1 MB is enough for large systems.
# SMP machines are better with 8 MB

wal_buffers = 1MB

# After every transaction, pgsql forces a commit to disk out its write-ahead log.
# defaults to fsync.
# generally switched to open_sync, but it is buggy on many platforms.
# Should be benchmarked with very heavy query, before switching.

wal_sync_method = fsync

# estimate of how much memory is available for disk caching by the OS and within the DB itself
# recomended to 1/2 of available memory. On unix can be set to free+cached from "free".

effective_cache_size = 512MB

# by default 3*16MB per segment = 48 MB. Can be resource intensive on modern systems.
# setting it to 32 - checkpoint every 512 MB can be effective in reducing disk io

checkpoint_segments = 32

# checkpoint occurs every 5 minutes. can be increased
checkpoint_timeout = 5min

# should be increased if you want to collect a lot of information for helping pgsql to create query plans
default_statistics_target=100

# Synchronous commit introduced in pgsql 8.3 allows a small amount of data loss (in case of failure) for large boost in number of updates on the database per second.
synchronous_commit=on

# If after tweaking every variable, your query execution plan still is not acceptable,
# you can bring down the random page cost to 3.0 or 2.0.
# setting this variable lower will encourage the query optimizer to use random access index scans.

random_page_cost=4.0

Friday, May 28, 2010

Quick sort algorithm

Quicksort follows the simple strategy of dividing the data into parts and sorting it.

Simple steps for the algorithm are:
  • Pick an element, called a pivot, from the list.
  • Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  • Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

Time complexity of the quick sort algorithm is O(n log n). And the worst case time complexity is O(n^2). Quicksort has a space complexity of O(log n).

Lets see a java program to do quick sort

public class QuickSort {

    public int[] data;
    public QuickSort(int[] data)
    {
        this.data = data;
    }

    public void sortMe()
    {
        this.sortMe(data, 0, data.length-1);
    }

    public void sortMe(int[] array, int start, int end)
    {
        int i=start;
        int k=end;

        if((end - start) < 1) //return if there is < 1 element
            return;

        int pivot = array[start]; //take an integer as pivot
        while(k > i) //while the left and right indices have not met
        {
            //from left to right find first element greater than pivot
            while(array[i] <= pivot && i <= end && k > i) 
                i++;
            //from right to left find first element smaller than pivot
            while(array[k] > pivot && k >= start && k >= i)
                k--;
            //if left index is still smaller than right, swap the elements
            if(k > i)
                swap(array, i, k);
        }
        //swap the last element in the left partition with the pivot.
        swap(array, start, k);

        //quicksort left partition
        sortMe(array, start, k-1);
        //quicksort right partition
        sortMe(array, k+1, end);
    }

    public void swap(int[] array, int idx1, int idx2)
    {
        int temp=array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }

    public void printMe(int[] data)
    {
        for(int x=0; x<data.length; x++)
        {
            System.out.print(data[x]+", ");
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] data = {9,2,6,4,11,88,66,44,55,32,23,5,32,10};
        QuickSort qs = new QuickSort(data);
        System.out.print("Before Sorting : ");
        qs.printMe(data);
        qs.sortMe();        
        System.out.print("After Sorting : ");
        qs.printMe(qs.data);
    }

}

Wednesday, May 19, 2010

Setting up replication on postgresql9.0 beta

Eventually postgresql comes out with its inbuilt replication solution in 9.0 beta. Setting up of replication is quite simple. We will look at setting up a simple master-slave replication between two servers of postgresql.

The way replication works in postgres is that the master keeps on writing "write ahead log" files (also known as wal files). The slave can be configured to run either in recovery mode or hot standby. The difference being that in recovery mode the wal files require to be shipped using something like a cron. And the slave applies the wal files to its database. The problem here is that it is not smooth and the delay between master and slave can be big. The logic of hot standby is that the slave connects to the master and fetches the log files from master. And it applies those log files on its database. Here the lag between master and slave is not huge since the slave tries to keep up with the master. This is also known as streaming replication because the wal files are continuously shipped to the slave and applied there. There could be multiple slaves fetching wal files from master and applying to their own database. As opposed to mysql the slave here is readonly - it cannot be modified. It can be used only as read-only slave for select queries.

Lets look at deploying master-slave replication between two servers

Master server : 172.16.3.173
Slave server : 172.16.3.211

Step 1:
Install postgresql 9.0 on both servers. Simple steps for installation are
$ ./configure
$ make
$ make install
$ adduser postgres

Step 2:
Initialize the data directory on master. No need to initialize it on slave - since we will be copying the master directory to slave for starting replication.
$ mkdir /usr/local/pgsql/data
$ chown -R postgres.postgres /usr/local/pgsql/data
$ su - postgres
$ /usr/local/pgsql/bin/initdb -D /usr/local/pgsql/data

In case you are trying to create a slave of existing postgres database, you can simply skip these steps and install postgres on a slave machine - and not initialize the data directory on the slave machine.

Step 3:
Change config on master so that any slave is authorized connect to the master. Add the following line to pg_hba.conf of master.
$ vim data/pg_hba.conf
host    replication     postgres        172.16.3.211/22         trust
This says that 172.16.3.211 (the slave) is allowed to connect to master for replication without any password. Configure this for all slaves (if you plan to have multiple slaves).

Step 4:
Change parameters on the master postgresql for streaming replication.
$ vim data/postgresql.conf
# allow all ip addresses to connect to the master.
listen_addresses = '*'

# set wal_level for hot standby replication.
wal_level = hot_standby

# enable archiving to an archive directory accessible from the standby. Not required for streaming replication. But set it for "just in case" scenarios 
archive_mode = on
archive_command = 'cp "%p" /path/to/archive_directory/"%f"'

# set the number of concurrent slave connections
max_wal_senders = 5

# set the minimum no of WAL segments to be retained in the pg_xlog directory from where the slave can pick up the WAL segments.
# This prevents removal of WAL segments before they are shipped the slave.
wal_keep_segments = 32

Step 5:
Start postgres on primary/master server.

Step 6:
Create a backup of master and ship it to the slave server.
$ ./bin/psql -c "SELECT pg_start_backup('postgres',true)"
$ rsync -a /usr/local/pgsql/data postgres@172.16.3.211:/usr/local/pgsql/data
$ ./bin/psql -c "SELECT pg_stop_backup()"

Step 7:
Clean the data directory in slave and set replication parameters.
$ rm /usr/local/pgsql/data/postmaster.pid
Here the postgresql.conf is same as master, so just set the parameters required by slave.
$ vim /usr/local/pgsql/data/postgresql.conf
# disable archiving
archive_mode = off
# enable read-only queries on slave - during replication/recovery
hot_standby = on


Step 8:
Setup the parameters in recovery.conf required for streaming replication
$ vim recovery.conf
# shell command for copying log files back from the archive. Should not be required.
restore_command = 'cp -i /home/postgres/archive/%f "%p" </dev/null'
# enable standby
standby_mode = 'on'
# connection information for connecting to master
primary_conninfo = 'host=172.16.3.173 port=5432 user=postgres'
# stop streaming and enable the server to work in read/write mode, if this file is found.
# server keeps on polling for the trigger file and stops replication once this file is found. The server can then be used in read/write mode.
trigger_file = '/usr/local/pgsql9.0/data/stop.replication'



Step 9:
Start postgres on slave. It will start streaming replication between master and slave.
To check replication see if sender process is active on master
$ ps -ef | grep sender
postgres 12332 12158  0 10:13 ?        00:00:00 postgres: wal sender process postgres 172.16.3.211(41497) streaming 0/90149F0
postgres 16233  9474  0 11:36 pts/2    00:00:00 grep sender
On slave check if receiver process is working
$ ps -ef | grep receiver
postgres 27952 27945  0 10:12 ?        00:00:00 postgres: wal receiver process   streaming 0/9014974        
postgres 30354 23492  0 11:36 pts/0    00:00:00 grep receiver

That is it. Run a few DML/DDL queries on master and check if they are being replicated on slave. The lag between master and slave is not noticable.

Friday, April 09, 2010

An intro to Thrift

What is thrift - a software framework for scalable cross language service development. It combines software stack with a code generation engine to build services that work efficiently and seamlessly between C++, Java, Python, Ruby, Erlang, Perl, Smalltalk etc.

Thrift allows you to define data types and service interfaces in a simple definition file. Taking the definition file as input the thrift compiler generates code that can be used to easily build RPC clients and servers that communicate seamlessly across programming languages.

You can find all this stuff at http://incubator.apache.org/thrift/.

My intention here is to provide a step by step guide to installing and building simple services in java/php using thrift. Since till date there is no proper tutorial, this should be helpful.

To download thrift, you can either get it from http://incubator.apache.org/thrift/download/ or do

$ svn co http://svn.apache.org/repos/asf/incubator/thrift/trunk thrift
$ cd thrift

Installation steps

$ ./bootstrap.sh
$ ./configure
$ make
$ make install


thrift depends on c++ boost libraries. To install boost libraries on ubuntu do

$ sudo apt-get install libboost-dev libboost-doc libboost-thread-dev libboost-python-dev

or

$ sudo apt-get install libboost-*

One problem i ran into while doing "sudo make install" was

Error: JAVA_HOME is not defined correctly.
We cannot execute java

The solution to this is

$ su
$ <enter password>
$ export JAVA_HOME=/path/to/jdk
$ export ANT_HOME=/path/to/ant
$ export PATH=$JAVA_HOME/bin:$ANT_HOME/bin:$PATH
$ make install


It would install the required libraries for all supported languages.

Now lets try writing a very simple service using thrift and use php/java clients to communicate with the service.

First we need to create a thrift definition file.

$ mkdir test # create a separate working directory
$ cd test
$ vim time.thrift # paste the following code in time.thrift

namespace java tserver.gen  // define namespace for java code
namespace php tserver  // define namespace for php code

typedef i64 Timestamp

service TimeServer {  // define the service you want to implement
  Timestamp time(),   // define the funcionalities the service would provide.
            string date(),
            i64 multiply(1:i32 num1, 2:i32 num2),
}
Namespaces are the places where code would be generated - what we call package in java.

Create a separate directory to store source files

$ mkdir src
$ cd src
$ vim TimeServerImpl.java

Create a java source file for implementing the functions that we had defined in the time.thrift file. The name of the file is the Service name (as defined in the thrift file) followed by "Impl". Provide the body of the functions in this file.

package server;

import java.util.*;
import org.apache.thrift.*;
import tserver.gen.*;

class TimeServerImpl implements TimeServer.Iface
{
  public long time() throws TException
  {
    long time = System.currentTimeMillis();
    System.out.println("Current time : "+time);
    return time;
  }

  public String date() throws TException
  {
    Calendar now = Calendar.getInstance();
    String dt = now.get(Calendar.YEAR)+"-"+(now.get(Calendar.MONTH)+1)+"-"+now.get(Calendar.DAY_OF_MONTH)+" "+now.get(Calendar.HOUR_OF_DAY)+":"+now.get(Calendar.MINUTE)+":"+now.get(Calendar.SECOND);
    System.out.println(" date : "+dt);
    return dt;
  }

  public long multiply(int num1, int num2) throws TException
  {
    System.out.println("Got : "+num1+", "+num2);
    return num1*num2;
  }
}

$ vim Server.java

Create a file for providing the service. This program simply has a main function which binds the service to a particular port and makes the server ready to accept connections and provide response. This code will generally remain constant unless you want to provide additional functionality at server level.

package server;

import java.io.*;
import org.apache.thrift.protocol.*;
import org.apache.thrift.protocol.TBinaryProtocol.*;
import org.apache.thrift.server.*;
import org.apache.thrift.transport.*;
import tserver.gen.*;

public class Server
{
  private void start()
  {
    try
    {
      TServerSocket serverTransport = new TServerSocket(7911);
      TimeServer.Processor processor = new TimeServer.Processor(new TimeServerImpl());
      Factory protFactory = new TBinaryProtocol.Factory(true, true);
      TServer server = new TThreadPoolServer(processor, serverTransport, protFactory);
      System.out.println("Starting server on port 7911 ...");
      server.serve();
    }catch(TTransportException e)
    {
      e.printStackTrace();
    }
  }

  public static void main(String[] args)
  {
    Server srv = new Server();
    srv.start();
  }
}

$ vim TimeClient.java

And create a client which will connect to the server on the specified port and call the provided functions.
package client;

import java.net.*;
import org.apache.thrift.*;
import org.apache.thrift.protocol.*;
import org.apache.thrift.transport.*;

import tserver.gen.TimeServer.Client;

public class TimeClient {
  private void start(){
    TTransport transport;
    try {
      transport = new TSocket("localhost", 7911);
      TProtocol protocol = new TBinaryProtocol(transport);
      // this client depends on the client class in the gen-java/tserver/gen/TimeServer.java file
      // public static class Client implements TServiceClient, Iface
      Client client = new Client(protocol); 
      transport.open();
      long time = client.time();
      System.out.println("Time from server:" + time);
      String dt = client.date();
      System.out.println("Got date from server: "+dt);
      long res = client.multiply(30,100);
      System.out.println("Multiply from server: "+res);
      transport.close();
    } catch (TTransportException e) {
      e.printStackTrace();
    } catch (TException e) {
      e.printStackTrace();
    }
  }

  public static void main(String[] args) {
    TimeClient c = new TimeClient();
    c.start();
  }
}
Now lets move ahead and generate the thrift code. And compile everything.

$ thrift --gen java time.thrift
$ vim build.xml


Write a simple build.xml to build these files
<project name="tserver" default="tserver" basedir=".">
<description>Time Server Tutorial</description>

<property name="src" location="src" />
<property name="gen" location="gen-java" />
<property name="build" location="build" />
<property name="cpath" location="/usr/local/lib/libthrift.jar:/usr/local/lib/slf4j-api-1.5.11.jar" />

<target name="init">
<tstamp />
<mkdir dir="${build}"/>
</target>

<target name="compile" depends="init">
<javac srcdir="${gen}" destdir="${build}" classpath="${cpath}" >  
<compilerarg value="-Xlint:deprecation"/> 
</javac>
<javac srcdir="${src}" destdir="${build}" classpath="${cpath}:${gen}" >   
<compilerarg value="-Xlint:deprecation"/> 
</javac>
</target>

<target name="tserver" depends="compile">
<jar jarfile="tserver.jar" basedir="${build}"/>
</target>

<target name="clean">
<delete dir="${build}" />
<delete file="tserver.jar" />
</target>

</project>
If you will check out the build file, you will see that the classpath contains slf4j-api-x.y.z.jar file. Download these files from http://www.slf4j.org/download.html and put two files (slf4j-api-x.y.z.jar and slf4j-simple-x.y.z.jar) from the archive in the /usr/local/lib directory to satisfy the required dependencies.

To complile the file run ant and create two files runClient and runServer to run the server and clients.

$ ant
$ cat runClient
java -cp tserver.jar:/usr/local/lib/libthrift.jar:/usr/local/lib/slf4j-api-1.5.11.jar:/usr/local/lib/slf4j-simple-1.5.11.jar client.TimeClient
$ cat runServer
java -cp tserver.jar:/usr/local/lib/libthrift.jar:/usr/local/lib/slf4j-api-1.5.11.jar:/usr/local/lib/slf4j-simple-1.5.11.jar server.Server


On compiling you will get the tserver.jar file created.

Now run the server and the client

$ ./runServer
Starting server on port 7911 ...

$ ./runClient
Time from server:1270726146716
Got date from server: 2010-4-8 16:59:6
Multiply from server: 3000


Now lets try building a client in php. First we will generate the thrift-code for php and then write the client to interact with the java server.

$ thrift --gen php time.thrift
$ mkdir php # create a directory to store your php client source code.
$ cd php
$ vim PhpClient.php

<?php

//location of thrift php libraries
$GLOBALS['THRIFT_ROOT'] = './lib';

require_once $GLOBALS['THRIFT_ROOT'].'/Thrift.php';
require_once $GLOBALS['THRIFT_ROOT'].'/protocol/TBinaryProtocol.php';
require_once $GLOBALS['THRIFT_ROOT'].'/transport/TSocket.php';
require_once $GLOBALS['THRIFT_ROOT'].'/transport/THttpClient.php';
require_once $GLOBALS['THRIFT_ROOT'].'/transport/TBufferedTransport.php';

error_reporting(E_ALL);
$GEN_DIR = '../gen-php';
require_once $GEN_DIR.'/time/TimeServer.php';
require_once $GEN_DIR.'/time/time_types.php';
error_reporting(E_ALL);

try {
  $socket = new TSocket('localhost', 7911);
  $transport = new TBufferedTransport($socket, 1024, 1024);
  $protocol = new TBinaryProtocol($transport);
  // this client depends on the client class in the gen-php/time/TimeServer.php file
  // class TimeServerClient implements TimeServerIf
  $client = new TimeServerClient($protocol);

  $transport->open();

  $time = $client->time();
  print "time frm server = $time\n";
  $res = $client->multiply(100,5000);
  print "multiply frm server = $res\n";
  $transport->close();

} catch (TException $tx) {
  print 'TException: '.$tx->getMessage()."\n";
}
?>
As you can see, in the code, the thrift library for php is included in the lib directory inside the php directory.
Create the lib directory and copy the required library files from thrift installation directory to the lib directory.

$ mkdir lib
$ cp -r /path/to/thrift/lib/php/src/* lib/


Now try running your php client. Remember to fire up your java server.

$ php -q PhpClient.php

You may get tons of errors "failed opening './lib/packages/time/time_types.php' for inclusion". For this you will need to edit the generated php files. The time_types.php file is in the generated directory "gen-php".

$ vim ../gen-php/time/TimeServer.php

Add the following lines

include_once '../gen-php/time/time_types.php';
//include_once $GLOBALS['THRIFT_ROOT'].'/packages/time/time_types.php';

now "php -q PhpClient.php" works...

Monday, March 22, 2010

Design patterns : Decorator pattern

A decorator is a class which wraps the original class. This allows the user to extend the functionality of certain objects at runtime. The pattern is designed in a way that multiple decorators can be stacked on top of each other. Decorators are used to avoid the rigidity that subclassing provides.

php example
<?php                                                                                                                                                                   
/**                                                                                                                                                                     
 * The smallest cohesive interface we can think of for this type        
 * of Decorator. This is the Component interface.
*/                                                                                                                                                                     
interface HtmlElement                                                   
{ /**                                                                                                * @return string    html code
*/                                                                                                                                                                   
  public function __toString();                                         

  /**
   * @return string    the name of the POST request key for this element,
   *                   aka the "name" attribute.                         
   */                                                                    
  public function getName();                                             
}                                                                        

/**
 * Represents a <input type="text" /> html element.
 * It can be created programmatically and then printed.  
 * This is the only ConcreteComponent.                   
 */                                                      
class InputText implements HtmlElement                   
{                                                        
  protected $_name;                                      

  public function __construct($name)
  {                                 
    $this->_name = $name;           
  }                                 

  public function getName()
  {                        
    return $this->_name;   
  }                        

  public function __toString()
  {                           
    return "<input type=\"text\" id=\"{$this->_name}\" name=\"{$this->_name}\" />\n";
  }                                                                                        
}                                                                                          

/**
 * Very simple base class to share the wrapping code between Decorators.
 * This is the Decorator participant.                                   
 */                                                                     
abstract class HtmlDecorator implements HtmlElement                     
{                                                                       
  protected $_element;                                                  

  public function __construct(HtmlElement $input)
  {                                              
    $this->_element = $input;                    
  }                                              

  /**
   * All operations are delegated by default, not changing anything
   * of the original behavior.                                     
   * ConcreteDecorators will override the methods they are interested in.
   */                                                                    
  public function getName()                                              
  {                                                                      
    return $this->_element->getName();                                   
  }                                                                      

  public function __toString()
  {                           
    return $this->_element->__toString();
  }                                      
}                                        

/**
 * Adds a custom <label> element alongside the <input> one.
 * Example of ConcreteDecorator.                           
 */                                                        
class LabelDecorator extends HtmlDecorator                 
{
  protected $_label;                                       

  public function setLabel($label)
  {                               
    $this->_label = $label;       
  }                               

  public function __toString()
  {                           
    $name = $this->getName(); 
    return "<label for=\"{$name}\">{$this->_label}</label>\n"
      . $this->_element->__toString();                                      
  }                                                                         
}                                                                           

/**
 * Adds a <span> containing an error message after the <input> element.
 * Example of ConcreteDecorator.                                       
 */                                                                    
class ErrorDecorator extends HtmlDecorator                             
{                                                                      
  protected $_error;                                                   

  public function setError($message)
  {                                 
    $this->_error = $message;       
  }                                 

  public function __toString()
  {                           
    return $this->_element->__toString()
      . "<span>{$this->_error}</span>\n";
  }                                                     
}                                                       

$input = new InputText('nickname');
$labelled = new LabelDecorator($input);
$labelled->setLabel('Nick:');          
echo "Using labelDecorator => \n",$labelled, "\n";

$input = new InputText('nickname');
$error = new ErrorDecorator($input);
$error->setError('You must enter a unique nickname');
echo "Using errorDecorator => \n",$error, "\n";   

// how can we obtain a LabelledErrorInputText, which has both the <label>
// and <span> elements?                                                  
$input = new InputText('nickname');                                      
$labelled = new LabelDecorator($input);                                  
$labelled->setLabel('Nick:');                                            
$error = new ErrorDecorator($labelled); // a Decorator wrapping another one
$error->setError('You must enter a unique nickname');                      
echo "Using both labelDecorator & errorDecorator => \n".$error;         
?>                                                                         

Output : 

Using labelDecorator =>
<label for="nickname">Nick:</label>
<input type="text" id="nickname" name="nickname" />

Using errorDecorator =>
<input type="text" id="nickname" name="nickname" />
<span>You must enter a unique nickname</span>

Using both labelDecorator & errorDecorator =>
<label for="nickname">Nick:</label> 
<input type="text" id="nickname" name="nickname" />
<span<You must enter a unique nickname>/span>


Some code in java

interface iComponent                                             
{                                                                
  public void doStuff();                                         
}                                                                

class component implements iComponent
{                                    
  public void doStuff()              
  {                                  
    System.out.println("component does stuff");
  }                                            
}                                              

interface decorator extends iComponent
{                                     
  public void addedBehaviour();       
}                                     

class concreteDecorator implements decorator
{                                           
  iComponent comp;                          
  public concreteDecorator(iComponent comp) 
  {                                         
    super();                                
    this.comp = comp;                       
  }                                         

  public void addedBehaviour()
  {                           
    System.out.println("Added behaviour in decorator");
  }                                                    

  public void doStuff()
  {                    
    comp.doStuff();    
    addedBehaviour();  
  }                    
}                      

class concreteDeco2 implements decorator
{                                       
  iComponent comp;                      
  public concreteDeco2(iComponent comp) 
  {                                     
    super();                            
    this.comp = comp;                   
  }                                     

  public void addedBehaviour()
  {
    System.out.println("Added behaviour in deco no 2");
  }

  public void doStuff()
  {
    comp.doStuff();
    addedBehaviour();
  }

}

public class decoClient
{
  public static void main(String[] args)
  {
    iComponent comp = new component();
    decorator deco = new concreteDecorator(comp);
    deco.doStuff();
    decorator deco2 = new concreteDeco2(comp);
    deco2.doStuff();
  }
}

Output :

component does stuff
Added behaviour in decorator
component does stuff
Added behaviour in deco no 2

Friday, March 05, 2010

Storing trees in databases

A tree is a graph which is connected, uni-directed and acyclic. Lets look at different options of storing such trees in databases.

Parent - Child Model

The most common model for storing hierarchical information is storing the reference of the parent node along with the child node.

so for a tree

EmployeeBosssalary
ANULL1000
BA900
CA950
DC800
EC700
FC600

For this model, the table to be created would be:

create table employee_tree(employee varchar(10) not null primary key, boss varchar(10), salary decimal(10,2) not null);

Some sample operations :
  • Finding the root node : select * from employee_tree where boss is NULL
  • Finding all leaf nodes : select e1.* from employee_tree as e1 left join employee_tree as e2 on e1.employee=e2.boss where e2.employee is null
  • Retrieving a single path : select e1.employee as lev1, e2.employee as lev2, e3.employee as lev3 from employee_tree as e1 left join employee_tree as e2 on e2.boss = e1.employee left join employee_tree as e3 on e3.boss = e2.employee where e1.employee = 'A' and e3.employee='F';

Some problems with this model:
  • Update : if you run "update employee_tree set employee = 'C1' where employee='C'", then all nodes below "C" are left with boss who does notexist. To handle this, you should run a transaction with two queries, one being the above query and another being the query "update employee_tree set boss = 'C1' where employee = 'C'"
  • Insert : if you run a query "Insert into employee_tree (employee, boss) values ('G','H'),('H','G')" you get two employees 'G' & 'H' who are both employees and bosses of each other.
  • Insert : Another problem with insert is "Insert into employee_tree (employee, boss) values ('M','M')". Now 'M' is the boss of 'M'.
  • Delete : Run "Delete from employee_tree where emp = 'C'". Again we create a situation where 'D','E','F' are left with a boss who does not exist. So in effect, deletion would require the tree to be traversed.
  • Descendants : It is difficult to get the number of descendents for a given node in a single query. You will have to write some script and un some recursive function to get that number

Fixing this model: Following checks should be in place to fix this model.
  • An employee cannot be his own boss : Check if ( boss != employee ) or (boss = 0 and employee = 0)
  • On deletion use cascade to remove the employees to that boss
  • To prevent cyclic relations : add unique key (employee, boss)
  • Check for validity of tree (edges = nodes - 1) : count(*) from employee_tree - 1 = count(boss) from employee_tree where boss is not null
  • Check for only single root : select count(*) from employee_tree where boss_id is null = 1

Path Enumeration model

create table employee(emp_id char(1) not null primary key, emp_name varchar(10), emp_path varchar(255) not null);
emp_idemp_nameemp_path
AA NameA
BB NameAB
CC NameAC
DD NameACD
EE NameACE
FF NameACF
The sample operations are easy here
  • Finding root node : select * from employee where length(emp_path)=1;
  • Finding all leaf nodes : This is going to be difficult, You will have to write a script to extract this info
  • Prevent cyclic relations : check whether after removing the node from the path string, the path is reduced by only 1 node. Query : CHECK(NOT EXISTS(select * from employee as e1, employee as e2 where length(replace(e1.emp_path,e2.emp_id,'')) < (length(e1.emp_path)-length(e2.emp_id)) ));
  • No path can be longer than the total no of nodes in the tree : CHECK( (select max(length(e1.emp_path)) from employee as e1) <= (select coun t(e2.emp_id) * length(e2.emp_id) from employee as e2) )
  • Depth of the tree is the path divided by the length of emp_id string : CHAR_LENGTH(emp_path) / CHAR_LENGTH(emp_id); If emp_ids are not fixed length then the depth is : CHAR_LENGTH(emp_path) - CHAR_LENGTH(REPLACE(emp_path,'/','')) + 1 [here / is the separator that is path is written as 'A/B/C'. If you use any other separator, you need to change it in the function as well]
  • To find all subtrees for a parent : the immediate solution is "Select * from employee where emp_path like concat('%',<Parent_emp_id>,'%')". But this query does not use indexes. Another way of doing this is "select * from employee where emp_path like concat((select emp_path from employee where emp_id='<Parent_emp_id>'),'%');"
  • To find the immediate subchildren of a parent : "select * from employee where emp_path like concat((select emp_path from employee where emp_id='<Parent_emp_id>'),'_');"
  • To search for superiors : "create table sequence(seq int not null); insert into sequence values (1),(2),(3),(4),(5); select substring(e1.emp_path from (seq * char_length(e1.emp_id)) for char_length(e1.emp_id)) as emp_id from employee e1, sequence s1 where e1.emp_id = '<emp_id_to_search_for>' and s1.seq <= char_length(e1.emp_path)/char_length(e1.emp_id);"
  • To find the relationships among superiors : "select e2.* from employee e1, employee e2 where e1.emp_id = '<emp_id_to_search_for>' and POSITION(e2.emp_path in e1.emp_path) = 1;"
  • To delete a subtree : "DELETE from employee where emp_path like concat(select emp_path from employee where emp_id='<Dead_node_emp_id>','%')" We may need to write the two queries separately;
  • To delete a node : "Delete from employee where emp_id='<emp_id_of_dead_node>'" And "Update employee set emp_path = replace(emp_path,'<emp_id_of_dead_node>','')" Both queries should be in a single transaction.
  • Inserting a node : "select emp_path from employee where emp_id = '<emp_id_of_boss>'; insert into employee values ('<new_emp_id>','<new_emp_name>',concat('<selected_emp_boss_path>','<new_emp_id>'))"

A derivative of the path enumeration model is the edge enumeration model. In Edge enumeration model the path consists of a set of integers that make the path from the root to the node - from left to right.

For example :
Employee nameEdge path
A1.
B1.1.
C1.2.
D1.2.1
E1.2.2
F1.2.3
The benefit of the edge enumeration model over the path enumeration model is that you do not have to worry about long strings. The numbers give an implied ordering to siblings that have meaning.

Nested set model


Here each node is assigned a beginning and an ending node hierarchy number based on the total amount of data in the hierarchical tree.

An example table could be :

create table emp(emp_id int not null auto_increment primary key, emp_name varchar(10), lft int not null, rgt int not null);
Emp idEmp NameLftRgt
1A112
2B23
3C411
4D56
5E78
6F910
Operations in this model:
  • Finding the root node : "select * from emp where lft = 1"
  • Finding leaf nodes : "select * from emp where lft = rgt - 1"
  • Finding subtree : select node.* from emp as node, emp as parent where node.lft > parent.lft and node.lft < parent.rgt and parent.emp_id='&l t;parent_employee_id>';"
  • Retrieving a single path : "select parent.* from emp as node, emp as parent where node.lft > parent.lft and node.lft < parent.rgt and node. emp_id='<leaf_node_id>' order by parent.lft;"
  • Finding depth of nodes : "select node.emp_name, (COUNT(parent.emp_name)-1) as depth from emp as node, emp as parent where node.lft BETWEEN parent.lft and parent.rgt group by node.emp_name order by node.lft;"
  • Add a single node as child of node with no existing children : If you want to insert a node 'G' below 'B', then the new node 'G' would have left and right values '3' and '4' and all nodes after it (in sequence) would have to increase their left and right values by 2. The procedure
    for it would be
    lock table emp write;
    select @myleft := lft from emp where emp_name='<add_below_this_node>';
    update emp set rgt = rgt+2 where rgt > @myleft;
    update emp set lft = lft+2 where lft > @myleft;
    insert into emp values ('','G',&myleft+1,@myleft+2);
    unlock tables;
    
  • As a single node after a node(not as a new child) : modify the earlier procedure a little.
    lock table emp write;
    select @myright := rgt from emp where emp_name='<add_after_this_node>';
    update emp set rgt = rgt+2 where rgt > @myright;
    update emp set lft = lft+2 where lft > @myright;
    insert into emp values ('','G',&myright+1,@myright+2);
    unlock tables;
    
  • Delete a node and its children : Deletion is just opposite to a adding. After deletion, its width has to be deleted from all nodes to the right.
    lock table emp write;
    select @myleft := lft, @myright := rgt, @mywidth := rgt - lft + 1 from emp where emp_name='<node_to_be_deleted>';
    delete from emp where lft between @myleft and @myright;
    update emp set rgt = rgt - @mywidth where rgt > @myright;
    update emp set lft = lft - @mywidth where lft > @myright;
    unlock tables;
    
  • Delete only the parent node: In this case the child nodes will have to be moved up to the level of the parent.
    lock table emp write;
    select @myleft := lft, @myright := rgt, @mywidth := rgt - lft + 1 from emp where emp_name='<parent_to_be_deleted>';
    delete from emp where lft = @myleft;
    update emp set rgt = rgt - 1, lft = lft - 1 where lft between @myleft and @myright;
    update emp set rgt = rgt - 2 where rgt > @myright;
    update emp set lft = lft - 2 where lft > @myleft;
    unlock tables;
    
Hybrid model

A parent child with nested set model would server the purpose much better. (node, parent, left, right). But with hybrid models, inserts would be more expensive as compared to selects. So it is important to evaluate the pros and cons and figure out what would be best for the purpose tha t your application serves.

Nested intervals model.

This model is similar to the nested set model with the use of rational numbers (a/b) instead of numbers. So in our above tree the left and right values would change.
Emp idEmp NameLftRgt
1A0/1111/11
2B1/112/11
3C3/1110/11
4D4/115/11
5E6/117/11
6F8/119/11

This is a bit complex to implement, but plays well with all the queries.

Proprietary solutions

Oracle, DB2 and Microsoft SQL Server support heirarchial data. In opensource Postgresql 8.4 supports the addition and querying of heirarchial data basically by using a "CONNECT BY" clause. It would be better if their official documentation is referred to for info regarding the syntax for implementing heirarchial data in relational databases.