Short Answer:
The cx_Oracle library you are using is for Windows. Aws Lambda environment is Amazon Linux, *.pyd are Python libraries for Windows.
Long Answer:
You have to deploy the linux version
The first thing you are getting wrong is the python library you are providing along your code to AWS Lambda. I guess you are developing locally in a Windows machine so when you do:
pip install cx_Oracle -t ./
you get a python precompiled library for Windows which is the cx_Oracle.cp36-win_amd64.pyd file.
AWS Lambdas run in Linux containers. You can find some info about the environment here.
The precompiled library for Linux is cx_Oracle.cpython-36m-x86_64-linux-gnu.so. You can download it manually from the Pypi repository.
So when you execute a python script in a Linux environment it will try to find the linux precompiled version of the library in the current path, the cx_Oracle.cpython-36m-x86_64-linux-gnu.so file. That is why you are getting the error message:
Unable to import module 'lambda_handler': No module named 'cx_Oracle'
The second thing important here is that the cx_Oracle python library calls the Oracle Instant Client which is a native library. If you have a working example on your windows machine you must have this installed. For windows this library is in the form of .dll files. For linux this native library is in the form of .so files.
You will need to provide the Oracle client for Linux along with your code in your deployment package because the are not already available in the Amazon Linux environment.
And the last thing is to tell Python how to find this dynamic library. In Linux systems shared libraries are looked for in the directories present in this environment variable LD_LIBRARY_PATH. In Amazon Linux this variable contains:
LD_LIBRARY_PATH:/var/lang/lib:/lib64:/usr/lib64:/var/runtime:/var/runtime/lib:/var/task:/var/task/lib:/opt/lib
The /var/task directory is whre your deployment resides. So if you add the Oracle instant client for Linux under /var/task/lib which is ./lib in your development directory you are done.
Your deployment package should be similar to this:
├── lib
│ ├── libclntsh.so <-- Oracle instant client linux files
│ .
│ .
│ .
├── python_handler.py <-- Lambda function code
└── cx_Oracle.cpython-36m-x86_64-linux-gnu.so <-- cx_Oracle library