Remove duplicate rows from table in Oracle

Background

This is classic database question to check candidates knowledge about SQL queries. You have a table where lets say you have duplicate entries (lets also say column1 and column2 can form a candidate key). Now you need to remove duplicates from then table. That is all rows in the table should be distinct. How would you do this?

 Query to remove duplicate rows from table in Oracle

You can execute following query to remove duplicates - 

DELETE FROM your_table
WHERE rowid not in
(SELECT MIN(rowid)
FROM your_table
GROUP BY column1, column2);

column 1 and column2 as I mentioned for candidate keys. You can very well add all columns in it.

Example

Queries :

create table schema8.EMPLOYEE(ID int, name varchar2(255));
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(2,'John');
insert into schema8.EMPLOYEE values(2,'John');
insert into schema8.EMPLOYEE values(3,'Sam');
insert into schema8.EMPLOYEE values(3,'Sam');
insert into schema8.EMPLOYEE values(3,'Sam');

ROWID Pseudocolumn  in Oracle

For each row in the database, the ROWID pseudocolumn returns the address of the row. Oracle Database rowid values contain information necessary to locate a row.

Rowid values have several important uses:

• They are the fastest way to access a single row.
• They can show you how the rows in a table are stored.
• They are unique identifiers for rows in a table.

NOTE : You should not use ROWID as the primary key of a table. If you delete and reinsert a row with the Import and Export utilities, for example, then its rowid may change. If you delete a row, then Oracle may reassign its rowid to a new row inserted later.

NOTE : Although you can use the ROWID pseudocolumn in the SELECT and WHERE clause of a query, these pseudocolumn values are not actually stored in the database. You cannot insert, update, or delete a value of the ROWID pseudocolumn.

Related Links

• Removing duplicate rows from table in Oracle
• ROWID Pseudocolumn  
• Basic PL/SQL syntax and query executions on Oracle 11g R2 database(OSFG)  
• How does database indexing work?(OSFG)
• Select top N records from each category in PL/SQL (OSFG)

ReentrantLock in Java

ReentrantLocks

Lets me first try to explain reentrancy concept in a simplistic and generic way. We will come to Java specific details a bit later. Reentrancy is lay man terms means ability to enter again. In terms of thread it mean thread can acquired same lock again without blocking itself. Refreshing our multi threading concepts here. When you synchronize over an object the thread obtains a lock on it before entering the critical region (inside synchronized block) and till this thread releases this lock no other thread can acquire it and enter the critical region. 

NOTE : We do this to make compound operations atomic so that there is no race condition or invalid state.

But what happens when we call an synchronized instance method from inside another synchronized instance method. Eg - 

public class TestClass {

    public synchronized void method1() {
        // some code
        method2();
    }

    public synchronized void method2() {
        // some other code
    }

}

Here for a thread to enter either of the method has to obtain a lock on the instance (this) before entering the method. Now we are calling method 2 from method1 which is again synchronized with same instance (this). So thread will try to acquire lock again. If locks were not reentrant in nature we would have ended up in deadlock. 

Note : In Java all intrinsic locks are reentrant in nature. 

Note : Synchronization is built around an internal entity known as the intrinsic lock or monitor lock. (The API specification often refers to this entity simply as a "monitor.") Intrinsic locks play a role in both aspects of synchronization: enforcing exclusive access to an object's state and establishing happens-before relationships that are essential to visibility.Every object has an intrinsic lock associated with it. Explicit locks are introduced in Java 1.5 like semaphore, cyclic barrier etc.

Now lets see Reentant lock in Java that was introduced in Java 1.5.

ReentrantLock  in Java

As per Java doc

A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities like -

•  It takes a fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation. Note however, that fairness of locks does not guarantee fairness of thread scheduling. Thus, one of many threads using a fair lock may obtain it multiple times in succession while other active threads are not progressing and not currently holding the lock. Also note that the untimed tryLock method does not honor the fairness setting. It will succeed if the lock is available even if other threads are waiting - ReentrantLock(boolean fair)
• It provides tryLock() method which acquires lock only if it is not held by other threads. We can also use timeout with this method which means thread will time out of waiting if lock is not acquired till the timeout value. This is better than intrinsic locks where you have to wait indefinitely.
• It also provides facility to interrupt thread while waiting using.  ReentrantLock provides a method called lockInterruptibly() [Acquires the lock unless the current thread is interrupted.], which can be used to interrupt thread when it is waiting for lock.
• Lastly it also provides functionality to get list of all threads waiting for the lock - getWaitingThreads(Condition condition)
  (Returns a collection containing those threads that may be waiting on the given condition associated with this lock).

NOTE : This lock supports a maximum of 2147483647 recursive locks by the same thread. Attempts to exceed this limit result in Error throws from locking methods.

Example -

 class Test {
   ReentrantLock reLock = new ReentrantLock();
   // ...

   public void m() {
     reLock.lock();  // block until condition holds
     try {
       // ... method body
     } finally {
       reLock.unlock()
     }
   }
 }

Working

Also, the way reentrancy is achieved is by maintaining a counter for number of locks acquired and owner of the lock. If the count is 0 and no owner is associated to it, means lock is not held by any thread. When a thread acquires the lock, JVM records the owner and sets the counter to 0.If same thread tries to acquire the lock again the counter is incremented, and when the owning thread exist synchronized block counter is decremented. When count reaches 0 again lock is released.

Most generic example are Segments used in ConcurrenHashMap. Each segment is essentially a ReentrantLock that allows only single thread to access that part of the map. You can refer to the link above to see how it works. Adding relevant snippet here -

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    //The number of elements in this segment's region.
    transient volatile int count;
    //The per-segment table. 
    transient volatile HashEntry<K,V>[] table;
}

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        //logic to store data in map
    } finally {
        unlock();
    }
}

NOTE : ReentrantLock was introduced since Java 5.

Related Links

• 'Reentrancy' in java (SO)
• Why use a ReentrantLock if one can use synchronized(this)?(SO)
• ReentrantLock JavaDoc
• How ConcurrentHashMap Works Internally in Java(OSFG) 
• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency(OSFG)

Implementing blocking queue in Java

Blocking Queue

Blocking queue is a queue that has a limit of elements it can hold and once that limit has reached enqueuing thread needs to wait for some thread to dequeue elements and make space. Similarly if queue becomes empty then dequeuing thread  has to wait until some thread enqueues elements in it.

Diagrammatically it is as follows -

Lets see how can we implement it in Java.

Blocking queue implementation in Java

 Code is as follows - 

package com.osfg.models;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @author athakur
 * Model class for blocking queue
 */
public class BlockingQueue<E> {
    
    private Queue<E> bQueue = new LinkedList<E>();
    private int maxQueueSize; 
    
    public BlockingQueue(int maxQueueSize) {
        this.maxQueueSize = maxQueueSize; 
    }
    
    public synchronized void enqueue(E e) throws InterruptedException {
        
        while(bQueue.size() == maxQueueSize) {
            wait();
        }
        bQueue.add(e);
        // notify if any thread is waiting to dequeue as data is now available
        notifyAll();
    }
    
    public synchronized E dequeue() throws InterruptedException{
        
        while(bQueue.size() == 0) {
            wait();
        }
        E e = bQueue.remove();
        notifyAll();
        return e;
        
    }

}

Notice how we are using wait() and notifyAll() calls. Also observer both enqueue and dequeue methods are synchronized. So at a time only one thread can execute them. You can also find this code in my data structure github repository. Also see the Thread Pool implementation in Java which uses the blocking queue internally.


Producer - Consumer design can be built using blocking queue. Producers enqueue jobs in the queue and wait when the queue is full where as consumers dequeue jobs in the queue and wait when the queue is empty. Famous example of producer consumer design in Thread pool implementation where you can enqueue your tasks in the queue and threads from Threadpool will dequeue and process it. As mentioned before you can see the code for blocking queue and thread pool in my github repository (Links in Related Links section below).

Related Links

• Blocking Queue github
• ThreadPool implementation in Java github

Simple PL/SQL code to throw NO_DATA_FOUND exception

Background

Good database question for beginners.Write a simple PL/SQL code snippet to throw NO_DATA_FOUND exception. You cannot raise this exception. Maybe try to understand how the candidate answers this. Simple code is as follows - 

DECLARE
   nowt VARCHAR(10);
BEGIN
   SELECT * INTO nowt FROM DUAL WHERE 1=0;
END;
/

and it should throw the exception - 

Error starting at line 8 in command:
DECLARE
   nowt VARCHAR(10);
BEGIN
   SELECT * INTO nowt FROM DUAL WHERE 1=0;
END;
Error report:
ORA-01403: no data found
ORA-06512: at line 4
01403. 00000 -  "no data found"
*Cause:    
*Action: 

Related Links

• Database Normalization(OSFG)
• Declare variables in PL/SQL(OSFG)
• Basic PL/SQL syntax and query executions on Oracle 11g R2 database(OSFG)
• Difference between DML and DDL statements in SQL(OSFG)
• Simple PL/SQL code to throw NO_DATA_FOUND exception 

Simple program to create deadlock between two threads and it's fix

Background

This is one of the very basic Java multithreading question - to write a simple java program to demonstrate a deadlock. So in this post I will provide code to demonstrate that - 

Java code to create deadlock between two threads

Code is as follows - 

/**
 * 
 * @author athakur
 * Simple deadlock program
 */
public class Deadlock {
    
    public static void main(String args[]) {
        
        final Object resourceOne = "res1";
        final Object resourceTwo = "res2";
        
        new Thread(new Runnable() {
            
            @Override
            public void run() {
                
                synchronized(resourceOne) {
                    System.out.println(Thread.currentThread().getName() + " accquired resource 1");
                    try {
                        Thread.sleep(2000);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                    synchronized(resourceTwo) {
                        System.out.println(Thread.currentThread().getName() + " accquired resource 2");
                    }
                }
            }
        }).start();
        
        new Thread(new Runnable() {
            
            @Override
            public void run() {
                synchronized(resourceTwo) {
                    try {
                        Thread.sleep(2000);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + " accquired resource 2");
                    synchronized(resourceOne) {
                        System.out.println(Thread.currentThread().getName() + " accquired resource 1");
                    }
                }
            }
        }).start();
        
    }

}

Copy above code in Deadloc.java file, compile and run it. You should see following output in console - 

Thread-0 accquired resource 1
Thread-1 accquired resource 2

And the program should hang.

Explanation

Thread 1 acquires lock over resource 1 and goes to sleep for 2 seconds. After sleep it would try to acquire lock on resource 2. When thread 1 was sleeping, thread 2 acquired lock over resource 2 and went to sleep for 2 seconds. After 2 seconds thread 2 would try to acquired lock on resource 1. Now it does not matter which thread wakes up. It will not be able to get lock on inner resource as other thread has acquired it and waiting for other to release. This will led to deadlock.

How to resolve this deadlock?

You can use Reentrant locks introduced in Java 1.5 to check if lock is available before locking it or you can do a timed lock (If lock is not available in x time move on). 

Another way to resolve this is to always have a fixed order to acquire lock. So both T1 and T2 threads will always lock resource 1 before trying to acquire lock on resource 2. This breaks the cycle that can lead to deadlock.

There is more more stupid way to prevent deadlock. When you are spawning new threads from main thread call join from main thread on all new threads before calling start() on next thread. Stupid? I know. It is same as single threaded application as you are executing threads sequentially. 

Couple of tips that may come handy -

• don't use multiple threads (like Swing does, for example, by mandating that everything is done in the EDT)
• don't hold several locks at once. If you do, always acquire the locks in the same order
• don't execute foreign code while holding a lock
• use interruptible locks

Related Links

• Race Condition, Synchronization, atomic operations and Volatile keyword(OSFG)
• ThreadLocal class in Java(OSFG)
• ReentrantLock in Java(OSFG) 
• How to avoid deadlock in Java Threads (java revisited)
• Tips to prevent deadlocks in java (SO)