func (m *Meta) enQueueDDLJob(key []byte, job *model.Job) error {
	b, err := job.Encode()
	if err != nil {
		return errors.Trace(err)
	}
	return m.txn.RPush(key, b)
}

func (d *ddl) onDropForeignKey(t *meta.Meta, job *model.Job) error {
	schemaID := job.SchemaID
	tblInfo, err := d.getTableInfo(t, job)
	if err != nil {
		return errors.Trace(err)
	}

	var (
		fkName model.CIStr
		found  bool
		fkInfo model.FKInfo
	)
	err = job.DecodeArgs(&fkName)
	if err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	for _, fk := range tblInfo.ForeignKeys {
		if fk.Name.L == fkName.L {
			found = true
			fkInfo = *fk
		}
	}

	if !found {
		return infoschema.ErrForeignKeyNotExists.Gen("foreign key doesn't exist", fkName)
	}

	nfks := tblInfo.ForeignKeys[:0]
	for _, fk := range tblInfo.ForeignKeys {
		if fk.Name.L != fkName.L {
			nfks = append(nfks, fk)
		}
	}
	tblInfo.ForeignKeys = nfks

	_, err = t.GenSchemaVersion()
	if err != nil {
		return errors.Trace(err)
	}

	switch fkInfo.State {
	case model.StatePublic:
		// We just support record the foreign key, so we just make it none.
		// public -> none
		job.SchemaState = model.StateNone
		fkInfo.State = model.StateNone
		err = t.UpdateTable(schemaID, tblInfo)
		if err != nil {
			return errors.Trace(err)
		}
		// finish this job
		job.State = model.JobDone
		return nil
	default:
		return ErrInvalidForeignKeyState.Gen("invalid fk state %v", fkInfo.State)
	}

}

// How to add index in reorganization state?
//  1. Generate a snapshot with special version.
//  2. Traverse the snapshot, get every row in the table.
//  3. For one row, if the row has been already deleted, skip to next row.
//  4. If not deleted, check whether index has existed, if existed, skip to next row.
//  5. If index doesn't exist, create the index and then continue to handle next row.
func (d *ddl) addTableIndex(t table.Table, indexInfo *model.IndexInfo, reorgInfo *reorgInfo, job *model.Job) error {
	seekHandle := reorgInfo.Handle
	version := reorgInfo.SnapshotVer
	count := job.GetRowCount()

	for {
		startTS := time.Now()
		handles, err := d.getSnapshotRows(t, version, seekHandle)
		if err != nil {
			return errors.Trace(err)
		} else if len(handles) == 0 {
			return nil
		}

		count += int64(len(handles))
		seekHandle = handles[len(handles)-1] + 1
		err = d.backfillTableIndex(t, indexInfo, handles, reorgInfo)
		sub := time.Since(startTS).Seconds()
		if err != nil {
			log.Warnf("[ddl] added index for %v rows failed, take time %v", count, sub)
			return errors.Trace(err)
		}

		job.SetRowCount(count)
		batchHandleDataHistogram.WithLabelValues(batchAddIdx).Observe(sub)
		log.Infof("[ddl] added index for %v rows, take time %v", count, sub)

	}
}

// EnQueueDDLJob adds a DDL job to the list.
func (m *Meta) EnQueueDDLJob(job *model.Job) error {
	b, err := job.Encode()
	if err != nil {
		return errors.Trace(err)
	}
	return m.txn.RPush(mDDLJobListKey, b)
}

// AddHistoryDDLJob adds DDL job to history.
func (m *Meta) AddHistoryDDLJob(job *model.Job) error {
	b, err := job.Encode()
	if err != nil {
		return errors.Trace(err)
	}
	return m.txn.HSet(mDDLJobHistoryKey, m.jobIDKey(job.ID), b)
}

func (d *ddl) delReorgTable(t *meta.Meta, job *model.Job) error {
	tblInfo := &model.TableInfo{}
	err := job.DecodeArgs(tblInfo)
	if err != nil {
		// arg error, cancel this job.
		job.State = model.JobCancelled
		return errors.Trace(err)
	}
	tblInfo.State = model.StateDeleteReorganization
	tbl, err := d.getTable(job.SchemaID, tblInfo)
	if err != nil {
		return errors.Trace(err)
	}

	err = d.dropTableData(tbl)
	if err != nil {
		return errors.Trace(err)
	}

	// finish this background job
	job.SchemaState = model.StateNone
	job.State = model.JobDone

	return nil
}

func (m *Meta) updateDDLJob(index int64, job *model.Job, key []byte) error {
	// TODO: use timestamp allocated by TSO
	job.LastUpdateTS = time.Now().UnixNano()
	b, err := job.Encode()
	if err != nil {
		return errors.Trace(err)
	}
	return m.txn.LSet(key, index, b)
}

// runDDLJob runs a DDL job.
func (d *ddl) runDDLJob(t *meta.Meta, job *model.Job) {
	log.Infof("[ddl] run DDL job %s", job)
	if job.IsFinished() {
		return
	}

	if job.State != model.JobRollback {
		job.State = model.JobRunning
	}

	var err error
	switch job.Type {
	case model.ActionCreateSchema:
		err = d.onCreateSchema(t, job)
	case model.ActionDropSchema:
		err = d.onDropSchema(t, job)
	case model.ActionCreateTable:
		err = d.onCreateTable(t, job)
	case model.ActionDropTable:
		err = d.onDropTable(t, job)
	case model.ActionAddColumn:
		err = d.onAddColumn(t, job)
	case model.ActionDropColumn:
		err = d.onDropColumn(t, job)
	case model.ActionModifyColumn:
		err = d.onModifyColumn(t, job)
	case model.ActionAddIndex:
		err = d.onCreateIndex(t, job)
	case model.ActionDropIndex:
		err = d.onDropIndex(t, job)
	case model.ActionAddForeignKey:
		err = d.onCreateForeignKey(t, job)
	case model.ActionDropForeignKey:
		err = d.onDropForeignKey(t, job)
	case model.ActionTruncateTable:
		err = d.onTruncateTable(t, job)
	default:
		// Invalid job, cancel it.
		job.State = model.JobCancelled
		err = errInvalidDDLJob.Gen("invalid ddl job %v", job)
	}

	// Save errors in job, so that others can know errors happened.
	if err != nil {
		// If job is not cancelled, we should log this error.
		if job.State != model.JobCancelled {
			log.Errorf("[ddl] run ddl job err %v", errors.ErrorStack(err))
		} else {
			log.Infof("[ddl] the job is normal to cancel because %v", errors.ErrorStack(err))
		}

		job.Error = toTError(err)
		job.ErrorCount++
	}
}

func (d *ddl) convert2RollbackJob(t *meta.Meta, job *model.Job, tblInfo *model.TableInfo, indexInfo *model.IndexInfo) error {
	job.State = model.JobRollback
	job.Args = []interface{}{indexInfo.Name}
	// If add index job rollbacks in write reorganization state, its need to delete all keys which has been added.
	// Its work is the same as drop index job do.
	// The write reorganization state in add index job that likes write only state in drop index job.
	// So the next state is delete only state.
	indexInfo.State = model.StateDeleteOnly
	job.SchemaState = model.StateDeleteOnly
	err := t.UpdateTable(job.SchemaID, tblInfo)
	if err != nil {
		return errors.Trace(err)
	}
	err = kv.ErrKeyExists.Gen("Duplicate for key %s", indexInfo.Name.O)
	return errors.Trace(err)
}

func (d *ddl) getReorgInfo(t *meta.Meta, job *model.Job) (*reorgInfo, error) {
	var err error

	info := &reorgInfo{
		Job:   job,
		d:     d,
		first: job.SnapshotVer == 0,
	}

	if info.first {
		// get the current version for reorganization if we don't have
		var ver kv.Version
		ver, err = d.store.CurrentVersion()
		if err != nil {
			return nil, errors.Trace(err)
		} else if ver.Ver <= 0 {
			return nil, errors.Errorf("invalid storage current version %d", ver.Ver)
		}

		job.SnapshotVer = ver.Ver
	} else {
		info.Handle, err = t.GetDDLReorgHandle(job)
		if err != nil {
			return nil, errors.Trace(err)
		}
	}

	if info.Handle > 0 {
		// we have already handled this handle, so use next
		info.Handle++
	}

	return info, errors.Trace(err)
}

// addTableHistoryInfo adds schema version and table information that are used for binlog.
// tblInfo is added except for the following operations: create database, drop database.
func addTableHistoryInfo(job *model.Job, ver int64, tblInfo *model.TableInfo) {
	// TODO: Remove it.
	// This is for compatibility with previous version.
	job.Args = []interface{}{ver, tblInfo}
	if job.BinlogInfo != nil {
		job.BinlogInfo.AddTableInfo(ver, tblInfo)
	}
}

func (d *ddl) runDDLJob(t *meta.Meta, job *model.Job) {
	if job.IsFinished() {
		return
	}

	job.State = model.JobRunning

	var err error
	switch job.Type {
	case model.ActionCreateSchema:
		err = d.onCreateSchema(t, job)
	case model.ActionDropSchema:
		err = d.onDropSchema(t, job)
	case model.ActionCreateTable:
		err = d.onCreateTable(t, job)
	case model.ActionDropTable:
		err = d.onDropTable(t, job)
	case model.ActionAddColumn:
		err = d.onAddColumn(t, job)
	case model.ActionDropColumn:
		err = d.onDropColumn(t, job)
	case model.ActionAddIndex:
		err = d.onCreateIndex(t, job)
	case model.ActionDropIndex:
		err = d.onDropIndex(t, job)
	case model.ActionAddForeignKey:
		err = d.onCreateForeignKey(t, job)
	case model.ActionDropForeignKey:
		err = d.onDropForeignKey(t, job)
	default:
		// invalid job, cancel it.
		job.State = model.JobCancelled
		err = errInvalidDDLJob.Gen("invalid ddl job %v", job)
	}

	// saves error in job, so that others can know error happens.
	if err != nil {
		// if job is not cancelled, we should log this error.
		if job.State != model.JobCancelled {
			log.Errorf("run ddl job err %v", errors.ErrorStack(err))
		}

		job.Error = err.Error()
		job.ErrorCount++
	}
}

func (d *ddl) onModifyColumn(t *meta.Meta, job *model.Job) error {
	tblInfo, err := d.getTableInfo(t, job)
	if err != nil {
		return errors.Trace(err)
	}
	newCol := &model.ColumnInfo{}
	oldColName := &model.CIStr{}
	err = job.DecodeArgs(newCol, oldColName)
	if err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	oldCol := findCol(tblInfo.Columns, oldColName.L)
	if oldCol == nil || oldCol.State != model.StatePublic {
		job.State = model.JobCancelled
		return infoschema.ErrColumnNotExists.GenByArgs(newCol.Name, tblInfo.Name)
	}
	*oldCol = *newCol
	err = t.UpdateTable(job.SchemaID, tblInfo)
	if err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	ver, err := updateSchemaVersion(t, job)
	if err != nil {
		return errors.Trace(err)
	}
	job.SchemaState = model.StatePublic
	job.State = model.JobDone
	addTableHistoryInfo(job, ver, tblInfo)
	return nil
}

func (d *ddl) delReorgTable(t *meta.Meta, job *model.Job) error {
	var startKey kv.Key
	if err := job.DecodeArgs(&startKey); err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	limit := reorgTableDeleteLimit
	delCount, err := d.dropTableData(startKey, job, limit)
	if err != nil {
		return errors.Trace(err)
	}
	// Finish this background job.
	if delCount < limit {
		job.SchemaState = model.StateNone
		job.State = model.JobDone
	}
	return nil
}

func (d *ddl) getTableInfo(t *meta.Meta, job *model.Job) (*model.TableInfo, error) {
	schemaID := job.SchemaID
	tableID := job.TableID
	tblInfo, err := t.GetTable(schemaID, tableID)
	if terror.ErrorEqual(err, meta.ErrDBNotExists) {
		job.State = model.JobCancelled
		return nil, errors.Trace(infoschema.ErrDatabaseNotExists)
	} else if err != nil {
		return nil, errors.Trace(err)
	} else if tblInfo == nil {
		job.State = model.JobCancelled
		return nil, errors.Trace(infoschema.ErrTableNotExists)
	}

	if tblInfo.State != model.StatePublic {
		job.State = model.JobCancelled
		return nil, ErrInvalidTableState.Gen("table %s is not in public, but %s", tblInfo.Name.L, tblInfo.State)
	}

	return tblInfo, nil
}

func (d *ddl) delReorgSchema(t *meta.Meta, job *model.Job) error {
	dbInfo := &model.DBInfo{}
	if err := job.DecodeArgs(dbInfo); err != nil {
		// arg error, cancel this job.
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	tables, err := t.ListTables(dbInfo.ID)
	if terror.ErrorEqual(meta.ErrDBNotExists, err) {
		job.State = model.JobDone
		return nil
	}
	if err != nil {
		return errors.Trace(err)
	}

	if err = d.dropSchemaData(dbInfo, tables); err != nil {
		return errors.Trace(err)
	}

	// finish this background job
	job.SchemaState = model.StateNone
	job.State = model.JobDone

	return nil
}

// runBgJob runs a background job.
func (d *ddl) runBgJob(t *meta.Meta, job *model.Job) {
	job.State = model.JobRunning

	var err error
	switch job.Type {
	case model.ActionDropSchema:
		err = d.delReorgSchema(t, job)
	case model.ActionDropTable, model.ActionTruncateTable:
		err = d.delReorgTable(t, job)
	default:
		job.State = model.JobCancelled
		err = errInvalidBgJob
	}

	if err != nil {
		if job.State != model.JobCancelled {
			log.Errorf("[ddl] run background job err %v", errors.ErrorStack(err))
		}
		job.Error = toTError(err)
		job.ErrorCount++
	}
}

func (d *ddl) delReorgSchema(t *meta.Meta, job *model.Job) error {
	var startKey kv.Key
	var tableIDs []int64
	if err := job.DecodeArgs(&tableIDs, &startKey); err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	isFinished, err := d.dropSchemaData(tableIDs, startKey, job, t)
	if err != nil {
		return errors.Trace(err)
	}
	if !isFinished {
		return nil
	}

	// finish this background job
	job.SchemaState = model.StateNone
	job.State = model.JobDone

	return nil
}

func (d *ddl) onCreateForeignKey(t *meta.Meta, job *model.Job) error {
	schemaID := job.SchemaID
	tblInfo, err := d.getTableInfo(t, job)
	if err != nil {
		return errors.Trace(err)
	}

	var fkInfo model.FKInfo
	err = job.DecodeArgs(&fkInfo)
	if err != nil {
		job.State = model.JobCancelled
		return errors.Trace(err)
	}
	fkInfo.ID = allocateIndexID(tblInfo)
	tblInfo.ForeignKeys = append(tblInfo.ForeignKeys, &fkInfo)
	ver, err := updateSchemaVersion(t, job)
	if err != nil {
		return errors.Trace(err)
	}

	switch fkInfo.State {
	case model.StateNone:
		// We just support record the foreign key, so we just make it public.
		// none -> public
		job.SchemaState = model.StatePublic
		fkInfo.State = model.StatePublic
		err = t.UpdateTable(schemaID, tblInfo)
		if err != nil {
			return errors.Trace(err)
		}
		// Finish this job.
		job.State = model.JobDone
		addTableHistoryInfo(job, ver, tblInfo)
		return nil
	default:
		return ErrInvalidForeignKeyState.Gen("invalid fk state %v", fkInfo.State)
	}
}

func (d *ddl) onCreateTable(t *meta.Meta, job *model.Job) error {
	schemaID := job.SchemaID
	tbInfo := &model.TableInfo{}
	if err := job.DecodeArgs(tbInfo); err != nil {
		// arg error, cancel this job.
		job.State = model.JobCancelled
		return errors.Trace(err)
	}

	tbInfo.State = model.StateNone

	tables, err := t.ListTables(schemaID)
	if terror.ErrorEqual(err, meta.ErrDBNotExists) {
		job.State = model.JobCancelled
		return errors.Trace(infoschema.ErrDatabaseNotExists)
	} else if err != nil {
		return errors.Trace(err)
	}

	for _, tbl := range tables {
		if tbl.Name.L == tbInfo.Name.L {
			if tbl.ID != tbInfo.ID {
				// table exists, can't create, we should cancel this job now.
				job.State = model.JobCancelled
				return errors.Trace(infoschema.ErrTableExists)
			}

			tbInfo = tbl
		}
	}

	ver, err := updateSchemaVersion(t, job)
	if err != nil {
		return errors.Trace(err)
	}

	switch tbInfo.State {
	case model.StateNone:
		// none -> public
		job.SchemaState = model.StatePublic
		tbInfo.State = model.StatePublic
		err = t.CreateTable(schemaID, tbInfo)
		if err != nil {
			return errors.Trace(err)
		}
		// finish this job
		job.State = model.JobDone
		addTableHistoryInfo(job, ver, tbInfo)
		return nil
	default:
		return ErrInvalidTableState.Gen("invalid table state %v", tbInfo.State)
	}
}