Classe ZDBFTABLE – Índice em Memória

Introdução

Nos posts anteriores, começamos a ver a implementação da classe ZDBFTABLE, uma forma de leitura de arquivos no formato DBF, sem o uso de Driver ou RDD, lendo o arquivo direto no disco usando as funções de baixo nível de arquivo do AdvPL. Agora, vamos ver como criar um índice eficiente em memória

Classe ZDBFMEMINDEX

Criar um índice para um arquivo DBF é uma forma não apenas de permitir uma navegação ordenada nos registros, mas também uma forma de realizar uma busca muito rápida pelo índice. Como a ideia original da classe ZDBFTABLE é realizar leitura de dados de um DBF, seria deveras interessante ter uma forma de criar um ou mais índices para a tabela.

Devido a natureza das tabelas DBF, um índice com chave simples ou composta (um ou mais campos) pode usar qualquer expressão ou função do AdvPL, onde o resultado da expressão é gravado em um índice no disco. A implementação da classe de índice em memória implementa esta funcionalidade, mas sem persistir o índice em disco. Ele é criado e mantido na memória por um array ordenado.

CLASS ZDBFMEMINDEX

   DATA oDBF		// Objeto ZDBFTABLE relacionado ao índice 
   DATA cIndexExpr      // Expressão AdvPL original do índice
   DATA bIndexBlock     // CodeBlock para montar uma linha de dados do índice
   DATA aIndexData      // Array com os dados do índice ordenado pela chave 
   DATA aRecnoData      // Array com os dados do índice ordenado pelo RECNO 
   DATA nCurrentRow     // Numero da linha atual do índice 
   DATA lSetResync      // Flag de resincronismo pendente da posição do índice
   DATA lVerbose

   METHOD NEW(oDBF)     // Cria o objeto do índice
   METHOD CREATEINDEX(cIndexExpr) // Cria o índice baseado na chave fornecida 
   METHOD CLOSE()       // Fecha o índice e limpa os dados da memória 

   METHOD GetFirstRec() // Retorna o RECNO do primeiro registro do índice
   METHOD GetPrevRec()  // Retorna o RECNO do Registro anterior do índice
   METHOD GetNextRec()  // Retorna o RECNO do próximo registro do índice
   METHOD GetLastRec()  // Retorna o RECNO do último registro do índice 
   
   METHOD GetIndexExpr()  // Rertorna a expressão de indexação 
   METHOD GetIndexValue() // Retorna o valor da chave de indice do registro atual 
   METHOD GetIndexRecno() // REtorna o numero do RECNO da posição do índice atual 
   METHOD IndexSeek()     // Realiza uma busca ordenada por um valor informado 
   METHOD RecordSeek()    // REaliza uma busca no indice pelo RECNO 
   METHOD UpdateKey()     // Atualiza uma chave de indice ( em implementação ) 
   
   METHOD _BuildIndexBlock(cIndexExpr) // Cria o codeblock da chave de indice 
   METHOD _CheckSync()    // Verifica a necessidade de sincronizar o indice 
   METHOD SetResync()     // Seta flag de resincronismo pendente
   METHOD SetVerbose()    // Seta modo verbose com echo em console ( em implementação 
   
ENDCLASS

Trocando em miúdos

Quando navegamos pela ordem física de registros de uma tabela DBF — ou seja, pelo número do RECNO — basicamente somamos uma unidade no marcador de registro para acessar o próximo, e subtraímos uma unidade para acessar o registro anterior, o primeiro registro da tabela é o número um, e o último registro é o maior registro da tabela (LastRec).

Quando optamos por realizar a navegação por um índice, basicamente criamos uma lista ordenada do tipo chave-valor, onde cada registro gera uma chave baseado na expressão de indexação, e o índice é responsável por guardar a chave e o número do RECNO correspondente desta chave. Uma vez que a lista seja ordenada, cada chave aponta para um registro físico (RECNO).

Logo, ao navegar usando um índice, eu preciso ter um marcador de controle (::nCurrentRow) para informar em qual linha do índice eu estou posicionado, e quando a tabela receber uma instrução de SKIP(), para ir para o próximo registro, se eu estou usando um índice, eu pergunto para o índice qual é o número do próximo registro que eu preciso posicionar.

Método CreateIndex()

METHOD CREATEINDEX( cIndexExpr ) CLASS ZDBFMEMINDEX

// Guarda a expressão original do indice
::cIndexExpr := cIndexExpr

// Monta o CodeBlock para a montagem da linha de dados
// com a chave de indice
::_BuildIndexBlock( cIndexExpr )

// Agora varre a tabela montando o o set de dados para criar o índice
::aIndexData := {}
::aRecnoData := {}

// Coloca a tabela em ordem de regisrtros para a criação do indice
::oDBF:DbSetORder(0)
::oDBF:DBClearFilter()
::oDBF:DbGoTop()

While !::oDBF:Eof()
	// Array de dados 
	// [1] Chave do indice
	// [2] RECNO
	// [3] Numero do elemento do array aIndexData que contém este RECNO
	aadd( ::aIndexData , { Eval( ::bIndexBlock , ::oDBF ) , ::oDBF:Recno() , NIL } )
	::oDBF:DbSkip()
Enddo

// Sorteia pela chave de indice, usando o RECNO como criterio de desempate
// Duas chaves iguais, prevalesce a ordem fisica ( o menor recno vem primeiro )
aSort( ::aIndexData ,,, { |x,y| ( x[1] < y[1] ) .OR. ( x[1] == y[1] .AND. x[2] < y[2] ) } )

// Guardando a posicao do array ordenado pelos dados na terceira coluna do array 
aEval( ::aIndexData , {| x,y| x[3] := y })

// Agora, eu preciso tambem de um indice ordenado por RECNO 
// Porem fazendo referencia a todos os elementos do array, mudandi apenas a ordenação 

// Para fazer esta magica, cria um novo array, referenciando 
// todos os elementos do array principal , então ordena
// este array pelo RECNO
::aRecnoData := Array(len(::aIndexData))
aEval(::aIndexData , {|x,y| ::aRecnoData[y] := x })

// Ordena o array aRecnoData em ordem crescente de RECNO
aSort( ::aRecnoData ,,, { |x,y| x[2] < y[2] } )

Return .T.

Aqui é que a mágica acontece. Neste fonte eu uso e abuso de Arrays, aEval e ASort. Primeiro, eu preciso criar um array que tenha pelo menos o valor da expressão de ordenação de cada registro, e o número do registro correspondente. Estes dados serão armazenados no array ::aIndexData. Por razões que eu vou explicar mais abaixo, este array possui uma coluna adicional, que contém qual é o número deste elemento no próprio array — parece não fazer sentido, mas vai fazer.

Primeiro, a expressão AdvPL recebida para criar o índice pode retornar uma String, um número ou uma data. Podemos criar uma chave composta usando dois campos por exemplo, mas como a expressão final do valor chave a ser ordenado é única, a expressão de índice normalmente concatena estes campos — sendo eles do tipo  “C” Caractere, por exemplo. Se existem campos de tipos diferentes a serem usados para gerar um índice, normalmente convertemos tudo para string: Campos numéricos são convertidos para Caractere usando a função STR(), passando como parâmetro o valor do campo, o tamanho do campo e a quantidade de decimais. Para campos data, convertemos para string usando DTOS() — que converte a data no formado AAAAMMDD (ou YYYYMMDD), própria para ordenação em string.

::_BuildIndexBlock( cIndexExpr )

Uma vez montado o CodeBlock para gerar um valor de chave de ordenação por registro, usamos o objeto  oDBF para limpar qualquer filtro da tabela, usar a ordem física dos registros, posicionar no primeiro, e criar o array por enquanto apenas com o valor de cada chave, e o RECNO correspondente — primeira e segunda colunas do Array — varrendo a tabela do primeiro ao último registro.

While !::oDBF:Eof()
	// Array de dados 
	// [1] Chave do indice
	// [2] RECNO
	// [3] Numero do elemento do array aIndexData que contém este RECNO
	aadd( ::aIndexData , { Eval( ::bIndexBlock , ::oDBF ) , ::oDBF:Recno() , NIL } )
	::oDBF:DbSkip()
Enddo

Feito isso, a ordenação deste array deve levar em conta que, caso hajam expressões de índice de mesmo valor, o campo RECNO passa a ser um fator de ordenação. Chaves repetidas do índice são ordenadas pelo valor do RECNO, no menor para o maior.

// Sorteia pela chave de indice, usando o RECNO como criterio de desempate
// Duas chaves iguais, prevalesce a ordem fisica ( o menor recno vem primeiro )
aSort( ::aIndexData ,,, { |x,y| ( x[1] < y[1] ) .OR. ( x[1] == y[1] .AND. x[2] < y[2] ) } )

Agora que o array ::aIndexData está ordenado, vamos preencher a terceira coluna com a posição de cada elemento no array ordenado. Para isso,  preenchemos a terceira coluna deste Array usando:

// Guardando a posicao do array ordenado pelos dados na terceira coluna do array 
aEval( ::aIndexData , {| x,y| x[3] := y })

A função AEVAL() passa dois parâmetros para o Codeblock, o primeiro é o elemento do Array em processamento, e o segundo parâmetro é o número da posição deste elemento no Array. Deste modo, eu uso esta AEval() para atribuir o número da própria posição neste array.

O pulo do gato vêm agora. Embora eu possa estar usando um índice para navegar na tabela,  uma vez que faça um “Goto” em um determinado registro, eu preciso posicionar nele. E ao fazer isso, eu preciso pesquisar no array de índice qual é a posição atual do índice para o registro que eu posicionei. Afinal, uma vez posicionado em um registro pelo seu número, ao perguntar qual é o próximo registro desta ordem para o índice, como ele vai saber onde ele está ?!

::aRecnoData := Array(len(::aIndexData))
aEval( ::aIndexData , {|x,y| ::aRecnoData[y] := x })
aSort( ::aRecnoData ,,, { |x,y| x[2] < y[2] } )

Para isso, o array chamado de ::aRecnoData, foi criado. Ele serve para referenciar todos os elementos do primeiro array, porém ordenando os elementos pelo RECNO. Deste modo eu não duplico os dados na memória, apenas faço referência aos elementos do primeiro array, em outra ordenação.

Assim, quando eu faço um posicionamento direto na tabela usando Goto() — sem usar o índice — eu ligo um flag de re-sincronismo pendente, e quando eu voltar a navegar pelo índice, caso exista um re-sincronismo pendente, eu uso o array ordenado pelo RECNO para realizar uma busca binária, para localizar qual é a linha do array ordenado pela chave de índice (::aIndexData) que corresponde ao RECNO atualmente posicionado na tabela — e justamente esta informação está na terceira coluna dos elementos de ambos os arrays.  Ao recuperar a posição do índice atual, eu consigo ir para o anterior ou próximo elementos na ordem do índice.

Método interno _BuildIndexBlock

De modo similar — praticamente uma cópia — ao método de filtro de tabela, o método que cria o Codeblock para a geração do valor chave de ordenação a partir da expressão AdvPL informada, espera que qualquer campo da tabela referenciado no índice esteja em letras maiúsculas. Desse modo ele cria um Codeblock de ordenação que recebe o objeto da tabela em si, e retorna o valor da chave de ordenação baseado na expressão informada usando o conteúdo dos campos do registro atualmente posicionado.

METHOD _BuildIndexBlock(cIndexExpr) CLASS ZDBFMEMINDEX
Local aCampos := {}
Local cTemp
Local nI, nPos

// Cria lista de campos
aEval( ::oDBF:aStruct , {|x| aadd(aCampos , x[1]) } )

// Ordena pelos maiores campos primeiro
aSort( aCampos ,,, {|x,y| alltrim(len(x)) > alltrim(len(y)) } )

// Copia a expressao de índice
cTemp := cIndexExpr

// Troca os campos por o:Fieldget(nCpo)
// Exemplo : CAMPO1 + CAMPO2 será trocado para o:FieldGet(1) + o:FieldGet(2)

For nI := 1 to len(aCampos)
	cCampo := alltrim(aCampos[nI])
	nPos   := ::oDBF:Fieldpos(cCampo)
	cTemp  := StrTran( cTemp , cCampo,"o:FieldGet(" +cValToChar(nPos)+ ")")
Next

// Monta a string com o codeblock para indice
cTemp := "{|o| "+cTemp+"}"

// Monta efetivamente o codeblock de indice
::bIndexBlock := &(cTemp)

Return

Busca Binária – Métodos RecordSeek() e IndexSeek()

Uma busca binária somente pode ser realizada em cima de um array ordenado. A ideia e a implementação são simples: Você define um limite superior e inferior de busca, começando no primeiro e terminando no último elemento da lista, tira a média deste valor — calcula o “meio” entre estes dois pontos — e verifica se o valor procurado é igual, menor ou maior.

Se for igual, achou. Se for menor, redefine que o limite inferior para a busca é a posição do meio menos um , recalcula o meio novamente considerando os novos valores de topo e fim, e repete a busca. Caso o valor buscador for maior que o valor do meio da lista, redefine que o limite superior é o valor atual de meio mais um, recalcula o meio novamente considerando os novos valores de topo e fim, e repete a busca.

O desempenho desse tupo de busca é espantoso, pois a cada operação de comparação, metade da lista é desconsiderada. Deste modo, num pior cenário, em uma lista com 4 bilhões de registros, foram necessárias — no máximo — 32 comparações para encontrar um valor ou saber que ele não está lá. Vamos ver por exemplo o método para a busca no array ordenado pelo RECNO:

METHOD RecordSeek(nRecno) CLASS ZDBFMEMINDEX
Local lFound := .F. 
Local nTop := 1 
Local nBottom := Len(::aRecnoData)
Local nMiddle 

If nBottom > 0

	If nRecno < ::aRecnoData[nTop][2]
		// Chave de busca é menor que a primeira chave do indice
		Return 0
	Endif

	If nRecno > ::aRecnoData[nBottom][2]
		// Chave de busca é maior que a última chave
		Return 0
	Endif

	While nBottom >= nTop

		// Procura o meio dos dados ordenados
		nMiddle := Int( ( nTop + nBottom ) / 2 )

		If ::aIndexData[nMiddle][2] == nRecno
			// Achou 
			lFound := .T. 
			EXIT
		ElseIf nRecno < ::aRecnoData[nMiddle][2]
			// RECNO menor, desconsidera daqui pra baixo 
			nBottom := nMiddle-1
		ElseIf nRecno > ::aRecnoData[nMiddle][2]
			// RECNO maior, desconsidera daqui pra cima
			nTop := nMiddle+1
		Endif
	
	Enddo

	If lFound
		// Retorna a posição do array de dados 
		// ordenados (aIndexData) que contem este RECNO 
		Return ::aRecnoData[nMiddle][3]
	Endif
	
Endif

Return 0

O método IndexSeek() também usa o mesmo princípio, porém é feito em cima do array ordenado pela chave de índice (::aIndexData, coluna 1). Normalmente as buscas demoram menos de dois milésimos de segundo, em testes realizados com uma lista de 109 mil elementos. Também pudera, no máximo em 16 comparações este algoritmo localiza a informação. Se a informação procurada estiver fora do range de dados, em apenas uma ou duas comparações o algoritmo já determina que a informação com aquela chave não existe e retorna .F. para a operação de busca.

Observações

A classe de índice em memória não é usada diretamente, na verdade ela é usada internamente pelos métodos de criação de índice, ordenação e busca ordenada publicados na classe ZDBFTABLE. Através dela criamos, usamos e fechamos um ou mais índices.

Conclusão

Era uma prova de conceito de leitura, está virando quase um Driver completo. Já estou trabalhando na criação de tabelas e inclusão/alteração de dados, mas isso exige outros truques com os índices já criados, para permitir manutenção dos índices nestas operações. Assim que tiver mais novidades, sai mais um post.

Novamente agradeço a todos pela audiência, e lhes desejo TERABYTES de SUCESSO 😀

 

 

 

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s